NHỮNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

Tại sân bay Tân Sơn Nhất có nhu cầu vận chuyển 1200 hành khách và 120 tấn hàng bằng máy bay. Giả sử có 2 loại máy bay có thể sử dụng với khả năng vận chuyển của mỗi loại như sau: Máy bay loại A: 01 máy bay có thể chở 150 hành khách và 20 tấn hàng với chi phí tương ứng 240 triệu đồng.
Nội dung trích xuất từ tài liệu:
NHỮNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH CHƯƠNG I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.1/ MỘT SỐ VÍ DỤ DẪN ĐẾN BÀI TOÁN QUY HOẠCH TUYẾN TÍNH: 1.1.1. Bài toán vận chuyển: Tại sân bay Tân Sơn Nhất có nhu cầu vận chuyển 1200 hành khách và 120 t ấn hàng bằng máy bay. Giả sử có 2 loại máy bay có thể sử dụng với khả năng vận chuyển của mỗi loại như sau: Máy bay loại A: 01 máy bay có thể chở 150 hành khách và 20 tấn hàng với chi phí tương ứng 240 triệu đồng. Máy bay loại B: 01 máy bay chở có thể chở 180 hành khách và 16 tấn hàng với chi phí tương ứng là 220 triệu đồng. Hãy lập mô hình tìm phương án sử dụng số máy bay mỗi loại sao cho phải thỏa mãn yêu cầu vận chuyển với tổng chi phí ít nhất. Lập mô hình: Gọi x1 là số lượng máy bay loại A Gọi x2 là số lượng máy bay loại B Tổng chi phí (triệu đồng): Z = 240 x1 + 220x2 Đảm bảo về hành khách: 150 x1 + 180x2 = 1200 Đảm bảo về hàng hóa: 20 x1 + 16 x2 = 120 Đảm bảo thực tế: x1,x2 ≥ 0 Giải bài toán: Z = 240 x1 + 220x2 → min (*) 150 x1 + 180 x2 = 1200   20 x1 + 16 x2 = 120  x ≥ 0; j = 1, 2 () j Giải hệ phương trình trên  x1 = 2, x2 = 5 thay x1 và x2 vào (* ) → Z = 1580 1.1.2/ Bài toán khẩu phần thức ăn : Để nuôi một loại gia súc người ta sử dụng 3 loại thức ăn A, B, C. Tỷ l ệ % theo khối lượng các chất dinh dưỡng P1, P2 có trong các loại thức ăn như sau : Thức ăn Chất dinh dưỡng P1 P2 A 20 10 B 10 10 C 10 20 Yêu cầu trong khẩu phần thức ăn của loại gia súc này: - Chất dinh dưỡng P1 phải có ít nhất là 70g và nhiều nhất là 80g - Chất dinh dưỡng P2 có ít nhất là 90g - Giá 1kg thức ăn A,B,C tương ứng là 2.000đ, 1.000đ, 2.000đ Yêu cầu : Hãy lập mô hình bài toán xác định khố i lượng thức ăn cần mua sao cho tổng chi phí ít nhất. Lập mô hình bài toán : Gọi x1, x2, x3 tương ứng là số g thức ăn A, B, C cần mua - Tổng chi phí Z = 2x1 + x2 + 2x3 - Hàm lượng các chất dinh dưỡng P1: 0,2x1 + 0,1x2 + 0,1x3 thuộc [ 70,80] (g) P2: 0,1 x1 + 0,1x2 + 0,2 x3 ≥ 90 (g) x j ≥ 0 ( j = 1, 2,3) Bài toán: Tìm xj (j= 1,2,3) sao cho Z = 2x1+ x2 + 2x3 → min 2 x1 + x 2 + 2 x3 ≥ 700 2 x + x + x ≤ 800 1 2 3  x1 + x 2 2 x3 ≥ 900 x1 , x 2 , x3 ≥ 0  1.1.3/ Bài toán thời gian thi công ngắn nhất: Để đảm bảo hoàn thành kế hoạch, đơn vị sửa chữa và bảo dưỡng đường nhựa A cần gấp rút hoàn thành 50km sơn vạch mặt đường, trong đó số km đường được sơn kẻ vạch của đường cấp I không nhỏ hơn 20% tổng chiều dài được sơn kẻ vạch của đường cấp II và cấp III. Đơn vị A chỉ có 1 dây chuyền ( người, máy) để làm việc này. Trong khi đ ể thời gian hoàn thành 1km đường cấp I, II, III tương ứng là 12 ngày, 8 ngày và 6 ngày. Định mức tiền sơn cho 1km đường cấp I, II, III tương ứng là 30, 20 và 15 triệu đồng, trong khi kinh phí dành cho công việc này trong thời gian tới chỉ còn 120 (triệu đồng). Hãy lập mô hình xác định chiều dài sơn kẻ vạch cho mỗi cấp đường sao cho tổng thời gian thực hiện là ngắn nhất, đồng thời đảm bảo về kinh phí mua sơn. Lập mô hình: Gọi x1, x2, x3 là chiều dài (km) dự định thực hiện trong tương ứng cấp đường loại I, II, III khi đó. Mục tiêu thời gian: Z = Yêu cầu khối lượng: Yêu cầu chủng loại: Yêu cầu kinh phí Điều kiện tất yếu: x1, x2, x3 ≥ 0 Bài toán: 1.2/ ĐỊNH NGHĨA VÀ CÁC DẠNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.2.1/ Định nghĩa: Bài toán quy hoạch tuyến tính dạng tổng quát: tìm (x1, x2, …, xn) sao cho n ∑c x j → min (max) (1) f (x) = c1x1+ c2x2 + cnxn = j j =1 Với điều kiện n ≤   ∑   aij x j  bi (i = 2,.., m)(2) = 1, j =1  ≥    ≥  0    0  j =(1, 2,..., n)(3) ≤ x j   Tùyý    + Các bi gọi là các hệ số tự do + Các cj gọi là hệ số hàm mục tiêu ( hệ số) + aij gọi là hệ số các ràng buộc chung + f(x) gọi là hàm mục tiêu + Hệ (*) gọi là hệ ràng buộc (2) gọi là ràng buộc chung (c ...