Bài giảng Tối ưu hóa - Chương 1 bài toán quy hoạch tuyến tính

TỐI ƯU HÓA CHƯƠNG 1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH I. CÁC VÍ DỤ I. CÁC VÍ DỤ VÍ DỤ 2 (Tổng quát) VÍ DỤ 3 Một công ty trang trại dự định trồng 2 loại cây là tiêu và cà phê trên 3 khu đất A, B, C có diện tích lần lượt là 120, 100, 150 (ha). Do đặc điểm các khu đất khác nhau nên chi phí sản xuất (triệu đồng/ha), năng suất (tạ/ha) khác nhau và cho ở bảng sau : • KHU ĐẤT TIÊU CÀ PHÊ A 4 7 3 10 B 5 8 5 12 C 6 10 4 11 VÍ DỤ 3 ►Yêu cầu • Sản lượng tiêu tối thiểu là 1 tấn • Sản lượng cà phê tối thiểu là 2 tấn • Hãy lập mô hình bài toán tìm phương án phân phối đất trồng sao cho thỏa mãn yêu cầu về sản lượng với chi phí thấp nhất. VÍ DỤ 4 • Để nuôi một loại gia súc trong 1 ngày cần có tối thiểu các chất prôtit, gluxit, chất khoáng tương ứng là 80, 120, 10 (g). Tỷ lệ % theo khối lượng các chất trên có trong các loại thức ăn A, B, C như sau : THỨC ĂN Prôtit Gluxit Chất khoáng A 30 20 1 B 40 15 2 C 25 30 4 VÍ DỤ 4 • Giá 1kg thức ăn A, B, C tương ứng là 3000đ, 4000đ, 5000đ. • Hãy lập mô hình bài toán tìm lượng thức ăn cần mua trong ngày để nuôi loại gia súc đó. II CÁC DẠNG BÀI TOÁN Dạng tổng quát • Tìm sao cho • 1 2( , ,..., ) n nx x x R 1 1 2 2 1 1 2 2 1 1 1 2 2 2 1 1 2 2 ( ) c + c + . . . + c min (max) a + a + . . . + a b i I a + a + . . . + a b i I a + a + . . . + a = b i n n i i in n i i i in n i i i in n i f X x x x x x x x x x x x x       3 1 2 3 I 0 j J 0 j J R j J j j j x x x               1 2 1 2... = {1 , 2 ,..., m } ; ... = {1 , 2 ,..., n}n nI I I J J J    DẠNG CHÍNH TẮC 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 ( ) c + c + . . . + c min (max) a + a + . . . + a = b a + a + . . . + a = b . . . a + a + . . . + a = b n n n n n n m m mn n m f X x x x x x x x x x x x x   0 j = 1, jx n         