Chương 1: Bài toán quy hoạch tuyến tính

Tài liệu tham khảo về Bài toán quy hoạch tuyến tính...
Nội dung trích xuất từ tài liệu:
Chương 1: 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 BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ BÀI 2. CÁC KHÁI NIỆM CƠ BẢN BÀI 3. CÁC DẠNG ĐẶC BIỆT CỦA BTQHTT BÀI 4. GIẢI BTQHTT BẰNG PP HÌNH HỌC BÀI 5. GIẢI BTQHTT BẰNG PP ĐƠN HÌNH 1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 1. Bài toán cái túi n f ( x )   ci xi  max i 1 n  ai xi  b  i 1  x  0 (i  1, n), nguyen  i 2 1 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 1. Bài toán cái túi Vd: Một cái giỏ trái cây chứa tối đa 15 kg. Loại Khối lượng (g) Giá bán (100đ/quả) Dưa hấu 1200 55 Bưởi 450 80 Đu đủ 650 120 f ( x)  55x1  80x2  120x3  max (min) 1,2x1  0,45x2  0,65x3  15  x1 , x2 , x3  0, nguyen 3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 2. Bài toán lập kế hoạch sản xuất tối ưu  Mô hình toán như sau: 4 2 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 2. Bài toán lập kế hoạch sản xuất tối ưu n R  c i 1 i x i  max  n   a ij x i  b j ( j  1, m )  i 1  x  0 ( i  1, n )  i 5 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 2. Bài toán lập kế hoạch sản xuất tối ưu Vd: Lập mô hình tối ưu xác định số lượng từng loại SP mà DN X cần sx để doanh số lớn nhất (giả sử cầu> cung) NVL Trữ lượng SP A1 SP A2 SP A3 SP A4 SP A5 Vải M1 15400 m 2,2 2,5 3,2 2,2 2,8 Vải M2 4800 m 1,5 1,2 1,5 1,8 2,4 Cúc M3 87500 cái 15 14 18 12 24 Dây M4 26800 sợi 3 4 8 2 12 Giá bán (triệu đồng/cái) 1,2 1,5 2,8 1,4 3,4 Gọi x1, x2, x3, x4, x5 lần lượt là số SP A1, A2, A3, A4 & A5 mà doanh nghiệp sẽ sản xuất. 6 3 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 2. Bài toán lập kế hoạch sản xuất tối ưu Mô hình bài toán:f ( x)  1,2x11 1,5x22  2,8x33 1,4x44  3,4x55  max2,2x11  2,5x22  3,2x33  2,2x44  2,8x55  154001,5x11 1,2x22 1,5x33 1,8x44  2,4x55  480015x11 14x22 18x33 12x44  24x55  875003x  4x  8x  2x 12x  26800 11 22 33 44 55   x11, x22, x33, x44, x55  0, nguyen xii  0, nguyen i  1,5 7 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 3. BT xác định khẩu phần thức ăn tối ưu  Mô hình toán như sau: 8 4 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 3. BT xác định khẩu phần thức ăn tối ưu m C  cx i 1 i i  min  m  aij xi b j ( j  1, n)  i 1  x  0 (i  1, m)  i 9 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 3. BT xác định khẩu phần thức ăn tối ưuVí dụ: Để nuôi 1 loại gia súc, người ta có thể sử dụng4 loại thức ăn F1, F2, F3 & F4 với hàm lượng (%) cácchất dinh dưỡng N1, N2 & N3 trong từng loại như sau: Loại thức ăn Nhu cầu (g) Chất dinh dưỡng F1 F2 F3 F4 Min Max N1 20 24 30 20 800 N2 15 18 18 450 1200 N3 25 20 26 950 Giá mua (1000đ/kg) 32 26 28 37 10 5 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ 3. BT xác định khẩu phần thức ăn tối ưu f ( x)  32 x1  26 x2  28 x3  37 x4  min0,20 x1  0,24 x2  0,30 x3  0,20 x4  0,800,15 x1  0,18 x2  0,18 x4  1,200,15 x1  0,18 x2  0,18 x4  0,450,25 x  0,20 x  0,26 x  0,95 1 3 4  xi  0 i  1,4  11 CHƯƠNG I- BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BÀI 1. MỘT SỐ BÀI TOÁN THỰC TẾ4. Bài toán vận tải đóng n m  m f (x)  cij xij  min   x ij  a i i 1 j 1  j 1  n   x ij  b j  ...