Bài giảng môn Quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính

Nội dung text: Bài giảng môn Quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính

1. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Bài toán lập kế hoạch sản xuất Một công ty sản xuất n loại sản phẩm Sj (j=1,2, ,n) sử dụng m loại nguyên liệu Ni (i = 1,2, ,m). Biết: + Lượng nguyên liệu Ni cần thiết dùng để sản xuất MỘT SỐ BÀI TOÁN MỞ ĐẦU một đơn vị sản phẩm Sj là: aij + Trữ lượng nguyên liệu loại Ni là: bi + Tiền lãi một đơn vị sản phẩm Sj là: cj Hãy xây dựng kế hoạch sản xuất cho công ty để có lợi nhuận nhiều nhất. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Minh hoạ dữ liệu bài toán: Giải: Sản phẩm Số nguyên Gọi xj là lượng Sj (j=1,2, ,n) cần sản xuất. xj ≥ 0. S S S Nguyên liệu 1 2 n liệu tối đa Lượng nguyên liệu N1 dùng cho sản xuất: a11x1 + a12x2 + + a1nxn ≤ b1 N1 a11 a12 a1n b1 Lượng nguyên liệu N2 dùng cho sản xuất: N2 a21 a22 a2n b2 a21x1 + a22x2 + + a2nxn ≤ b2 Lượng nguyên liệu Nm dùng cho sản xuất: Nm am1 am2 amn bm am1x1 + am2x2 + + amnxn ≤ bm Tiền lãi/đơn vị Số tiền lãi mà công ty thu được là: c1 c2 cn sản phẩm f = f(x1, x2, , xn) = c1x1 + c2x2 + + cnxn Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Mô hình toán học của bài toán Bài toán vốn đầu tư Tìm x = (x1, x2, , xn) sao cho Một xí nghiệp xử lý giấy có n phân xưởng Sj f(x) = c1x1 + c2x2 + + cnxn ⟶ max (j=1,2, ,n) xử lý m loại giấy Ni (i=1,2, ,m). với các ràng buộc Biết: a11x1 + a12x2 + + a1nxn ≤ b1 . + Lượng giấy loại Ni mà cuối năm phân xưởng Sj có a21x1 + a22x2 + + a2nxn ≤ b2 thể xử lý (nếu cùng đầu tư một đơn vị vốn vào các phân xưởng) là: aij am1x1 + am2x2 + + amnxn ≤ bm + Lượng giấy Ni tối thiểu cần phải xử lý theo hợp x1, x2, , xn ≥ 0 . đồng lao động là: bi Đây là một bài toán quy hoạch tuyến tính. Lập kế hoạch đầu tư để xí nghiệp hoàn thành hợp đồng lao động với tổng vốn đầu tư là nhỏ nhất. Chuongnn-hui.blogspot.com 1
2. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Minh hoạ dữ liệu bài toán: Giải: Phân xưởng Lượng rác xử Gọi xj là lượng vốn đầu tư cho Sj (j=1,2, ,n). xj ≥ 0. S S S Loại rác thải 1 2 n lý tối thiểu Lượng giấy N1 xử lý được: a11x1 + a12x2 + + a1nxn ≥ b1 N1 a11 a12 a1n b1 Lượng giấy N2 xử lý được: N2 a21 a22 a2n b2 a21x1 + a22x2 + + a2nxn ≥ b2 Lượng giấy Nm xử lý được: Nm am1 am2 amn bm am1x1 + am2x2 + + amnxn ≥ bm Số vốn mà xí nghiệp cần đầu tư là: f = f(x1, x2, , xn) = x1 + x2 + + xn Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Mô hình toán học của bài toán Bài toán vận tải Tìm x = (x1, x2, , xn) sao cho Xí nghiệp cần vận chuyển hàng hoá từ m điểm phát f(x) = x1 + x2 + + xn ⟶ min Pi (i=1,2, ,m) đến n điểm thu Tj (j=1,2, ,n). Biết với các ràng buộc + Lượng hàng có ở điểm phát Pi là: ai a11x1 + a12x2 + + a1nxn ≥ b1 . + Lượng hàng cần ở mỗi điểm thu Tj là: bj a21x1 + a22x2 + + a2nxn ≥ b2 . + Phí chuyển một đơn vị hàng từ Pi đến Tj là: cij Giả sử tổng lượng hàng có ở các điểm phát bằng am1x1 + am2x2 + + amnxn ≥ bm tổng lượng hàng cần ở các điểm thu. x1, x2, , xn ≥ 0 . Hãy lập kế hoạch vận chuyển hàng hoá với tổng chi Đây là một bài toán quy hoạch tuyến tính. phí là nhỏ nhất và đảm bảo yêu cầu thu phát. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Minh hoạ dữ liệu bài toán: Giải: Điểm thu Gọi xij là lượng hàng cần chuyển từ Pi (i=1,2, ,m) T1:b1 T2:b2 Tn:bn Điểm phát đến Tj (i=1,2, ,m). xij ≥ 0. Lượng hàng chuyển đi từ P là: c c c i P :a 11 12 1n x + x + + x = a 1 1 i1 i2 in i c21 c22 c2n P :a Lượng hàng chuyển đến Tj là: 2 2 x1j + x2j + + xmj = bj cm1 cm2 cmn Tổng chi phí vận chuyển là: Pm:am f = f(x11, x12, , xmn) = c11x11 + c12x12 + + cmnxmn Chuongnn-hui.blogspot.com 2
3. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Mô hình toán học của bài toán Bài tập: Tìm x = (x11, x12, , xmn) sao cho Lập mô hình toán học của các bài toán sau: f(x) = c11x11 + c12x12 + + cmnxmn ⟶ min 1. Một xí nghiệp sản xuất ba loại sản phẩm A, B và với các ràng buộc C chế tạo từ ba loại nguyên liệu I, II và III . Lượng nguyên liệu I, II và III mà xí nghiệp có lần lượt là x11 + x12 + + x1n = a1 20, 40, 30. Lượng nguyên liệu I, II, III cần cho một . x + x + + x = a đơn vị sản phẩm loại A lần lượt là 3, 3, 2, loại B lần m1 m2 mn m lượt là 3, 2, 1, loại C lần lượt là 2, 1, 1 đơn vị. x + x + + x = b 11 21 m1 1 Hãy lập kế hoạch sản xuất để xí nghiệp thu tiền lãi . nhiều nhất, biết tiền lãi một đơn vị sản phẩm loại A x1n + x2n + + xmn = bn lãi 2 triệu đồng, loại B lãi 4 triệu đồng và loại C lãi x11, x12, , xmn ≥ 0 . 3 triệu đồng. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 2. Một Xí nghiệp chăn nuôi cần mua thức ăn tổng 3. Một Xí nghiệp xử lý giấy có ba phân xưởng I, II, hợp T1, T2, T3 cho gia súc với tỷ lệ chất dinh III cùng xử lý ba loại giấy A, B, C. Nếu đầu tư 10 dưỡng là: 1 kg T1 chứa 3 đơn vị D1, 3 đơn vị D2 và triệu đồng vào mỗi phân xưởng thì cuối năm phân 2 đơn vị D3; 1 kg T2 chứa 3 đơn vị D1, 2 đơn vị D2 xưởng I xử lý được 3 tạ giấy A, 3 tạ giấy B, 2 tạ giấy và 1 đơn vị D3; 1 kg T3 chứa 2 đơn vị D1, 1 đơn vị C, phân xưởng II xử lý được 3 tạ giấy A, 2 tạ giấy B, D2 và 1 đơn vị D3. Mỗi bữa ăn, gia súc cần tối thiểu 1 tạ giấy C, phân xưởng III xử lý được 2 tạ giấy A, 1 20 đơn vị D1, 40 đơn vị D2 và 30 đơn vị D3. Biết tạ giấy B, 1 tạ giấy C. rằng 1 kg T1 có giá là 2 ngàn đồng, 1 kg T2 có giá là Theo yêu cầu Xí nghiệp phải xử lý ít nhất 2 tấn giấy 4 ngàn đồng, 1 kg T3 có giá là 3 ngàn đồng. loại A, 4 tấn giấy loại B, 3 tấn giấy loại C. Hỏi cần Hỏi Xí nghiệp phải mua bao nhiêu kg T1, T2, T3 đầu tư vào mỗi phân xưởng bao nhiêu tiền để xí cho một bữa ăn để bảo đảm tốt về chất dinh dưỡng nghiệp hoàn thành công việc với giá tiền đầu tư là và tổng số tiền mua là nhỏ nhất? nhỏ nhất. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 4. Một xí nghiệp chế biến đồ gỗ dùng 3000 đơn vị 5. Một xí nghiệp có thể sử dụng tối đa 510 giờ máy gỗ nguyên liệu nhóm I, 5000 đơn vị gỗ nguyên liệu cán, 360 giờ máy tiện và 150 giờ máy mài để chế nhóm II và 2000 đơn vị gỗ nguyên liệu nhóm III để tạo 3 sản phẩm A, B và C. Để chế tạo một sản phẩm sản xuất tủ trang trí, bàn ghế và giường cao cấp. A cần 9 giờ máy cán, 5 giờ máy tiện và 3 giờ máy Một bộ tủ trang trí bán giá 500000đ dùng 30 đơn vị nhóm I, 10 đơn vị nhóm II và 10 đơn vị nhóm III. mài; một sản phẩm B cần 3 giờ máy cán, 4 giờ máy Một bộ bàn ghế bán giá 800000đ dùng 40 đơn vị tiện; một sản phẩm C cần 5 giờ máy cán, 3 giờ máy nhóm I, 20 đơn vị nhóm II và 50 đơn vị nhóm III. tiện và 2 giờ máy mài. Mỗi sản phẩm A trị giá 48 Một bộ giường bán giá 400000đ dùng 10 đơn vị ngàn đồng, mỗi sản phẩm B trị giá 16 ngàn đồng và nhóm I, 50 đơn vị nhóm II và 80 đơn vị nhóm III. mỗi sản phẩm C trị giá 27 ngàn đồng. Hãy cho biết Hãy xác định số lượng các sản phẩm cần sản xuất xí nghiệp cần chế tạo mỗi loại bao nhiêu sản phẩm sao cho xí nghiệp đạt lợi nhuận nhiều nhất? để có tổng giá trị sản phẩm lớn nhất. Chuongnn-hui.blogspot.com 3
4. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 6. Một người nông dân muốn sản xuất lúa gạo và 7. Một xưởng làm cửa sắt có những thanh thép dài lúa mì trên 50 ha đất của ông ta với nguồn nước 12 m, cần cắt thành 8 đoạn dài 4m, 5 đoạn dài 5m dự trữ là 90 ngàn m3 nước và nguồn nhân lực gổm và 3 đoạn dài 7m. Có 5 mẫu cắt sau. Mẫu 1: 3 đoạn 250 công. Biết rằng để sản xuất 1 tấn lúa gạo cần dài 4m, không thừa. Mẫu 2: 1 đoạn 4m, 1 đoạn 5m, sử dụng 3 ha đất, 5 ngàn m3 nước và 15 công với thừa 3m. Mẫu 3: 1 đoạn 4m, 1 đoạn 7m, thừa 1m. lợi nhuận là 18 USD, để sản xuất một tấn lúa mì Mẫu 4: 2 đoạn 5m, thừa 2m. Mẫu 5: 1 đoạn 5m, 1 cần sử dụng 3 ha đất, 4 ngàn m3 nước và 12 công đoạn 7m, không thừa. với lợi nhuận là 21 USD. Hỏi cần dùng những mẫu cắt nào để tiết kiệm nhất. Hỏi người nông dân phải sản xuất bao nhiêu tấn lúa mỗi loại để đạt lợi nhuận cao nhất. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 8. Một xưởng sản xuất dự định mua hai loại máy để in hình vẽ trên vải. Máy A có thể in 100m/phút và chiếm 50 mét vuông diện tích sàn, còn máy B có thể in 200m/phút và chiếm 140 mét vuông diện tích sàn. Xưởng cần in ít nhất 600m/phút và có diện tích sàn để đặt máy in tối đa là 350 mét BÀI TOÁN QUY HOẠCH TUYẾN TÍNH vuông. Mỗi máy A có giá là 22 triệu đồng và mỗi máy B có giá 42 là triệu đồng. Hỏi cần mua bao nhiêu máy in mỗi loại sao cho tốn ít chi phí nhất. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Bài toán quy hoạch tuyến tính tổng quát Ví dụ: Tìm x = (x1, x2, , xn) sao cho + f(x) = x1 – 2x3 – x4 – 2x6 ⟶ max f(x) = c1x1 + c2x2 + + cnxn ⟶ max(min) (1) x1 + 2x2 – x4 + x5 ≤ 8 với các ràng buộc x1 – 3x3 – x4 + 3x6 ≥ 2 2x + x + x – x = 5 ai1x1 + ai2x2 + + ainxn ≤ bi, i ∊ I1 (2) 1 2 3 4 – x + x + 2x – 3x ≥ 6 ai1x1 + ai2x2 + + ainxn ≥ bi, i ∊ I2 (3) 1 3 4 5 2x2 – 2x3 – x4 – 2x6 ≤ 11 ai1x1 + ai2x2 + + ainxn = bi, i ∊ I3 (4) x1, x4 ≥ 0 xj ≥ 0, j ∊ J1 (5) Với I 1 ∪ I 2 ∪ I 3 ={1,2, ,m}, . x2, x3, x6 ≤ 0 xj ≤ 0, j ∊ J2 (6) I 1 ∩ I 2 ∩ I 3 = ∅ . x ∊ ℝ và J ∪J ∪J ={1,2, ,n}, 5 xj ∊ ℝ, j ∊ J3 (7) 1 2 3 . J1∩J2∩J3=∅ Chuongnn-hui.blogspot.com 4
5. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Một số khái niệm Dạng chính tắc của bài toán quy hoạch tuyến tính Hàm mục tiêu: hàm f(x) = c1x1 + c2x2 + + cnxn Tìm x = (x1, x2, , xn) sao cho f(x) = c x + c x + + c x ⟶ max(min) Phương án: vectơ x = (x1, x2, , xn) thoả mãn các 1 1 2 2 n n điều kiện ràng buộc từ (2) đến (7). ai1x1 + ai2x2 + + ainxn = bi, i = 1, 2, , m Phương án tối ưu: phương án làm cho hàm mục xj ≥ 0, j = 1, 2, , n . tiêu đạt max hay min nghĩa là thoả mãn (1). hay Tập phương án tối ưu: tập hợp tất cả các phương f(x) = ∑cjxj ⟶ max(min) án của bài toán. ∑aijxj = bi, i = 1, 2, , m Giải bài toán quy hoạch tuyến tính: là tìm phương xj ≥ 0, j = 1, 2, , n . Lưu ý: Mọi bài toán quy hoạch tuyến tính đều có án tối ưu cho bài toán. thể biến đổi đưa về dạng chính tắc. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Để biến đổi bài toán về dạng chính tắc tìm min ta Ví dụ: Biến đổi về dạng chính tắc thực hiện như sau: + f(x) = x1 – 3x2 + 2x3 – x4 ⟶ max + Biến hàm mục tiêu f ⟶ max thành g ⟶ min, với 2x1 + x2 + x3 – x4 ≤ 8 g = f. x1 – x3 + x4 = 5 x – 2x – x + 3x ≥ 7 + Biến ràng buộc ∑aijxj ≤ bi thành ∑aijxj + xn+i = bi 1 2 3 4 x , x ≥ 0 bằng cách bổ sung thêm biến xn+i ≥ 0. 1 3 x ≤ 0 + Biến ràng buộc ∑aijxj ≥ bi thành ∑aijxj – xn+i = bi 2 g(x) = – x1 – 2x3 – 3x7 + x8 – x9 ⟶ min x ∊ ℝ bằng cách bổ sung thêm xn+i ≥ 0. 4 2x1 + x3 + x5 – x7 – x8 + x9 = 8 + Đổi biến xj ≤ 0 thành biến x′j ≥ 0 với x′j = xj x1 – x3 + x8 – x9 = 5 + Đổi biến xj ℝ thành hiệu x′j x″j với x′j , x″j ≥ 0 x1 – x3– x6 + 2x7 + 3x8 – 3x9= 7 và x′j x″j = xj xj ≥ 0, j=1,2, ,9 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH + f(x) = 2x1 – x2 + x3 – 3x4 ⟶ min Phương án cực biên x1 + 2x2 + 2x3 – x4 ≥ 6 Xét bài toán 2x1 – x2 – 2x3 + x4 = 9 f(x) = ∑cjxj ⟶ min 3x1 –x2 + x3 + 2x4 ≤ 12 ∑aijxj = bi, i = 1, 2, , m x2, x4 ≥ 0 x ≥ 0, j = 1, 2, , n . f(x) = – x – 3x – 2x + x – x ⟶ min j x1 ≤ 0 2 4 7 8 9 Vectơ liên kết với biến x là vectơ cột A = [a ] 2x – x – x – x + 2x – 2x = 6 j j ij m 1 x3 ∊ ℝ 2 4 5 7 8 9 có các thành phần là hệ số tương ứng của biến x . – x + x – 2x – 2x + 2x = 9 j 2 4 7 8 9 Phương án cực biên: phương án mà hệ vectơ liên –x + 2x + x – 3x + x – x = 12 2 4 6 7 8 9 kết với các biến x > 0 tạo thành một hệ vectơ độc x ≥ 0, j=1,2, ,9 j j lập tuyến tính. Lưu ý: Từ đây ta chỉ xét các bài toán dạng chính tắc tìm min. Chuongnn-hui.blogspot.com 5
6. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Biến cơ sở là biến xj > 0, vectơ Aj tương ứng với Ví dụ: biến cơ sở gọi là vectơ cơ sở, biến phi cơ sở là biến + Xét bài toán xj = 0. f(x) = 4x1 + x2 + x3 ⟶ min Phương án cực biên không suy biến là phương án x1 +2x2 x3 = 5 có đúng m biến cơ sở, nếu số biến cơ sở bé hơn m x1 x2 + 2x3 = 5 ta có phương án cực biên suy biến. xj ≥ 0, j=1,2,3 Số các phương án cực biên của một bài toán quy Vectơ nào sau là phương án cực biên không suy hoạch tuyến tính là hữu hạn. biến: x0 = (1, 4, 4), x1 = (5, 0, 0), x2 = (0, 5, 5)? ĐS: x2 = (0, 5, 5) Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH + Xét bài toán Lưu ý: Cách thành lập một phương án cực biên của f(x) = x1 + 2x2 x3 ⟶ min bài toán quy hoạch tuyến tính dạng chính tắc: x1 + x2 + x3 = 4 + Xác định hệ vectơ liên kết với n biến. x1 x2 = 0 + Tìm các hệ con {Ai}, i = 1, 2, ,m gồm m véctơ xj ≥ 0, j=1,2,3 độc lập tuyến tính của hệ vectơ Số hệ con này hữu Vectơ nào sau là phương án cực biên không suy hạn. 0 1 2 biến: x = (1, 1, 2), x = (2, 2, 0), x = (0, 0, 4)? + Biểu diễn vectơ b theo hệ con {Ai} ở trên, ta ĐS: x1 = (2, 2, 0) được các hệ số biểu diễn. Thành lập vectơ x có các thành phần là hệ số biểu diễn. + Loại đi những vectơ x có thành phần âm, các véctơ còn lại là các phương án cực biên. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Ví dụ: Tìm các phương án cực biên của bài toán Lưu ý: + f(x) = 2x1 + x3 + 5x4 ⟶ min Do số thành phần dương của một phương án cực biên không suy biến là bằng m nên suy ra số thành x1 + x3 + x4 = 5 9 1 ĐS: (5, 1, 0, 0), ( , 0, 0, ), phần bằng 0 sẽ là n – m. x2 x3 + 2x4 = 1 2 2 x ≥ 0, j=1,2,3,4 (0, 6, 5, 0), (0, 0, 3, 2) Từ đó suy ra muốn tìm phương án cực biên ta có j thể cho n – m thành phần bằng 0 rồi tính giá trị của + f(x) = 2x1 x3 + 2x4 ⟶ min m thành phần còn lại bằng cách giải hệ m phương x1 + x2 + x3 + x4 = 10 trình m ẩn. 16 14 2x2 + x3 x4 = 6 ĐS: (0, 0, 8, 2), (0, , 0, ), 3 3 xj ≥ 0, j=1,2,3,4 (4, 0, 6, 0), (7, 3, 0, 0) Chuongnn-hui.blogspot.com 6
7. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Ví dụ: Tìm các phương án cực biên của bài toán Các tính chất chung của bài toán quy hoạch + f(x) = x1 + 6x3 5x4 ⟶ min tuyến tính x + 2x + 3x = 5 8 7 5 + Tập các phương án của bài toán quy hoạch tuyến 1 3 4 ĐS: (5, , 0, 0), (0, , , 0), 3x x + 2x = 8 3 2 2 tính là một tập lồi nghĩa là nếu x, y là hai phương 2 3 4 14 5 (0, , 0, ) án bất kỳ của bài toán thì mọi tổ hợp x + (1 )y, xj ≥ 0, j=1,2,3,4 9 3  ∊ ℝ: 0 ≤ ≤ 1 cũng là một phương án của bài + f(x) = x1 6x3 + x4 x5 ⟶ max toán. x1 + 2x4 + x5 = 8 + Tập các phương án tối ưu của bài toán quy x2 + x4 x5 = 4 ĐS: (8,4,6,0,0), (2,10,0,0,6), hoạch tuyến tính cũng là một tập lồi. x3 + x4 + x5 = 6 (0,0,2,4,0), (0,6,0,2,4) + Nếu bài toán quy hoạch tuyến tính dạng chính x ≥ 0, j=1,2, ,5 tắc có tập phương án khác rỗng thì nó có ít nhất j một phương án cực biên. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH + Điều kiện cần và đủ để bài toán quy hoạch tuyến Ví dụ: Giải các bài toán quy hoạch tuyến tính tính dạng chính tắc có phương án tối ưu là nó có + f(x) = x1 + 6x3 5x4 ⟶ min tập phương án khác rỗng và hàm mục tiêu bị chặn. x + 2x + 3x = 5 14 5 1 3 4 ĐS: x* = (0, , 0, ), + Nếu bài toán quy hoạch tuyến tính dạng chính 3x x + 2x = 8 9 3 tắc có phương án tối ưu thì nó có ít nhất một 2 3 4 25 x ≥ 0, j=1,2,3,4 fmin = phương án cực biên là phương án tối ưu. j 3 + f(x) = x 6x + x x ⟶ max Lưu ý: Từ đây, ta có thể giải bài toán quy hoạch 1 3 4 5 tuyến tính dạng chính tắc nếu biết nó có phương x1 + 2x4 + x5 = 8 án tối ưu bằng cách tìm tất cả các phương án cực x2 + x4 x5 = 4 ĐS: x* = (0,6,0,2,4), biên của bài toán, phương án tối ưu là phương án x3 + x4 + x5 = 6 fmax = 2 mà giá trị hàm mục tiêu lớn nhất (hay nhỏ nhất). xj ≥ 0, j=1,2, ,5 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Giải bài toán quy hoạch tuyến tính hai + f(x) = x + 3y ⟶ max biến bằng phương pháp hình học x + 2y ≤ 6 Ví dụ: 2x + y ≤ 10 + f(x) = 2x +3y ⟶ min ‒x + y ≤ 4 3x + y ≥ 3 x ≥ 0, y ≥ 0 x 4y ≤ 6 ĐS: fmax = 9 tại A (0;3) x + 2y ≤ 6 x ≥ 0, y ≥ 0 ĐS: fmin = 2 tại C(1; 0) Chuongnn-hui.blogspot.com 7
8. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Cơ sở của phương pháp đơn hình Dựa vào phương án hiện có, ta tìm cách đánh giá phương án đó có là phương án tối ưu hay chưa, nếu phương án đang xét đã là phương án tối ưu thì PHƯƠNG PHÁP ĐƠN HÌNH mục đích của ta đã đạt, được nếu chưa là phương án tối ưu thì ta thay thế bởi nó một phương án mới GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH tốt hơn. Xét bài toán dạng chính tắc (P) f(x) = ∑cjxj ⟶ min ∑aijxj = bi, i = 1, 2, , m xj ≥ 0, j = 1, 2, , n Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 0 0 0 0 Giả sử ta có phương án x = x1 , x2, , xm, 0, , 0 Định lý: ( Dấu hiệu tối ưu) với các biến cơ sở tương ứng x , x , , x và hệ 0 0 0 1 2 m Nếu x = x1 , x2, , xm, 0, , 0 là một phương án vectơ cơ sở liên kết là {A }, i = 1,2, ,m. i cực biên của (P) sao cho ∆j ≤ 0 với mọi j = 1,2, ,n 0 0 0 0 Giá trị mục tiêu f x = c1x1 + c2x2 + ⋯ + cmxm. thì x là phương án tối ưu. Đặt ∆j= c1x1j + c2x2j + ⋯ + cmxmj − cj Định lý: ( Dấu hiệu không có phương án tối ưu) j với x = (x1j, x2j, , xmj) là toạ độ của các vectơ Aj Nếu ngoài cơ sở liên kết của phương án cực biên j đối với hệ cơ sở {Ai}, gọi là ước lượng của biến xj. tồn tại j sao cho ∆j > 0 và x ≤ 0 nghĩa là xij≤ 0 với mọi i = 1,2, ,m thì (P) không có phương án tối ưu. Lưu ý: Nếu ma trận cột tạo bởi hệ vectơ cơ sở {Ai} là ma trận đơn vị thì xij = aij. Rõ hơn là hàm mục tiêu không bị chặn dưới trên tập phương án. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Ví dụ: + Xét bài toán + Xét bài toán f(x) = 7x1 ‒ 26x2 + 9x3 ⟶ min f(x) = x1 + 6x2 + 9x3 ⟶ min x1 ‒ 2x2 = 5 x1 + 2x3 = 6 ‒x2 + x3 = 7 x2 + x3 = 8 xj ≥ 0, j = 1, 2, 3. xj ≥ 0, j = 1, 2, 3. Vectơ x = (5, 0, 7) có phải là phương án tối ưu hay Vectơ x = (6, 8, 0) có phải là phương án tối ưu hay không? không? ĐS: x không phải là phương án tối ưu. ĐS: x là phương án tối ưu. fmin = 54. Chuongnn-hui.blogspot.com 8
9. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Định lý: Thuật toán đơn hình Nếu ngoài cơ sở liên kết của phương án cực biên Xét bài toán tồn tại j sao cho ∆j > 0 và có ít nhất một xij > 0 với i f(x) = ∑cjxj ⟶ min nào đó thì ta luôn có thể tìm được một phương án ∑aijxj = bi, i = 1, 2, , m cực biên mới tốt hơn x, nghĩa là phương án này x ≥ 0, j = 1, 2, , n làm cho hàm mục tiêu nhỏ hơn phương án x. j bi ≥ 0, i=1,2, ,m và có sẵn ma trận đơn vị. + Tìm phương án cực biên ban đầu: Giả sử ma trận đơn vị tạo bởi các vectơ cột Ai, i = 1,2, ,m thì ta có phương án cực biên ban đầu 0 0 0 0 x = x1 , x2, , xm, 0, , 0 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH + Đánh giá phương án hiện có: lập bảng đơn hình + Xây dựng phương án mới – Phương pháp phần như hình bên dưới và căn cứ vào đó để đánh giá tử trục quay: Biến Hệ Phương x x x Xác định cột quay s là cột mà s > 0 lớn nhất, biến 1 2 n  cơ sở tương ứng xs là biến cơ sở đưa vào. cơ sở số án c1 c2 cn 0 0 xr x1 c1 x1 x11 x12 x1n Dòng quay r là dòng mà  nhỏ nhất với θ = , r r x 0 ks x2 c2 x2 x21 x22 x2n biến cơ sở tương ứng xr là biến cơ sở đưa ra. Phần tử quay xrs là phần tử giao giữa dòng quay r 0 xm cm xm xm1 xm2 xmn và cột quay s. 0 f(x ) 1 2 n Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Xác định các thành phần phương án x1 mới: Ví dụ: Giải các bài toán 0 + f(x) = x ‒ x ‒ 2x + 2x ‒ 3x ⟶ min xr PA s ↓ 1 2 4 5 6 nếu i = r i 1 xrs 0 x1 + x4 + x5 ‒ x6 = 2 x = x xis i x0x − x0x i i rs r is r x + x + x = 12 nếu i ≠ r 0 2 4 6 xrs xr xrs x3 + 2x4 + 4x5 + 3x6 = 9 Xác định các hệ số biểu diễn x ij mới xj ≥ 0, j = 1, 2, ,6. ĐS: Phương án tối ưu x* = (0, 8, 0, 3, 0, 1). Giá trị xrj j ↓ s ↓ nếu i = r i tối ưu f = ‒17. ′ xrs x x min xij = xijxrs−xrjxis ij is nếu i ≠ r r x rs xrj xrs Chuongnn-hui.blogspot.com 9
10. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH + f(x) = ‒2x1 ‒ 4x2 + x3 ‒ x4 ⟶ min Lưu ý: + Nếu bài toán có b ≥ 0, i=1,2, ,m và chưa có sẵn x1 + 3x2 + x5 = 4 i ma trận đơn vị ta có thể thực hiện biến đổi ma trận 2x1 + x2 ‒ x3 + x6 = 3 hệ số mở rộng của hệ điều kiện ràng buộc để có ma x2 + 4x3 + x4 = 3 trận đơn vị. xj ≥ 0, j = 1, 2, ,6. Ví dụ: Giải bài toán ĐS: Phương án tối ưu x* = (1, 1, 0, 2, 0, 0). Giá trị + f(x) = ‒ 3x1 + x2 + 3x3 ‒ x4 ⟶ min tối ưu fmin = ‒8. x1 + 2x2 ‒ x3 + x4 = 2 2x1‒ 6x2 + 3x3 + 3x4 = 9 x1 ‒ x2 + x3 ‒ x4 = 6 xj ≥ 0, j = 1,2,3,4. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐS: Bài toán trở thành + f(x) = 3x1 ‒ 4x2 ‒ 5x3 + 6x4 ⟶ min f(x) = ‒ 3x1 + x2 + 3x3 ‒ x4 ⟶ min x1 + x2 + x3 + 13x4 = 14 6 x + x = 3 2x1+ x2 + 14x4 = 11 1 5 4 12 3x2 + x3 + 14x4 = 16 x2 ‒ x4 = 2 5 xj ≥ 0, j = 1,2,3,4. 23 x ‒ x = 5 3 5 4 xj ≥ 0, j = 1, 2, 3, 4. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐS: Bài toán trở thành Thuật toán đơn hình mở rộng Xét bài toán f(x) = 3x1 ‒ 4x2 ‒ 5x3 + 6x4 ⟶ min 27 f(x) = ∑c x ⟶ min x + x = 4 j j 1 5 4 ∑aijxj = bi, i = 1, 2, , m 16 x + x = 3 xj ≥ 0, j = 1, 2, , n 2 5 4 22 với bi ≥ 0, i=1,2, ,m và chưa có sẵn ma trận đơn vị x + x = 7 3 5 4 (giả sử bài toán còn thiếu m vectơ đơn vị). xj ≥ 0, j = 1, 2, 3, 4. Ta bổ sung thêm m biến xn+i, i=1,2, ,m để có được ma trận đơn vị và đưa về xét hàm mục tiêu g = ∑cjxj + Mxn+1 + Mxn+2 + + Mxn+m với M là một số rất lớn, lớn hơn bất cứ số nào khác. Chuongnn-hui.blogspot.com 10
11. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Bài toán trở thành bài toán M sau đây Ta dùng thuật toán đơn hình để giải bài toán M với g(x) = ∑cjxj + Mxn+1 + Mxn+2 + + Mxn+m ⟶ min một vài lưu ý: ∑aijxj + xn+i = bi, i = 1, 2, , m + Nếu đã có k vectơ đơn vị thì ta bổ sung vào m – k xj ≥ 0, j = 1, 2, , n+m biến để có ma trận đơn vị cấp m. Lưu ý: + Hàm mục tiêu g, ước lượng của các biến x có Nếu bài toán M có phương án tối ưu (x, t) với t > 0 j j thể viết dưới dạng g = AM + B, j = jM+ j. t = (xn+1, , xn+m) thì bài toán chính không có phương án. Nếu bài toán M có phương án tối ưu + Để so sánh các ước lượng ta có (x, 0) thì x là phương án tối ưu của bài toán chính αj > 0 αj > αk ∆j ≥ 0 ⇔ , ∆j ≥ ∆k⇔ và nếu bài toán M không có phương án tối ưu thì αj = 0,βj ≥ 0 αj = αk,βj ≥ βk bài toán chính cũng không có phương án tối ưu. và các hệ số A, B, ,  được trình bày trên 2 dòng. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Ví dụ: Giải bài toán + f(x) = 3x1 ‒ 4x2 ‒ 5x3 + 6x4 ⟶ min + f(x) = ‒ 3x1 + x2 + 3x3 ‒ x4 ⟶ min x1 + x2 + x3 + 13x4 = 14 x1 + 2x2 ‒ x3 + x4 = 2 2x1+ x2 + 14x4 = 11 2x1‒ 6x2 + 3x3 + 3x4 = 9 3x2 + x3 + 14x4 = 16 x1 ‒ x2 + x3 ‒ x4 = 6 xj ≥ 0, j = 1,2,3,4. xj ≥ 0, j = 1,2,3,4. ĐS: Phương án tối ưu x* = (4, 3, 7, 0). Giá trị tối ĐS: Phương án tối ưu x* = (3, 2, 5, 0). Giá trị tối ưu fmin = ‒35. ưu fmin = 8. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Lưu ý: Với bài toán dạng chính tắc tìm max ta thực 2 17 39 ĐS: Phương án tối ưu x* = ( , , , 0, 0). Giá trị hiện tương tự, chỉ khác là nếu ∆ ≥ 0, ∀j = 1,2, ,n 3 6 2 j 88 thì phương án đang xét là tối ưu, nếu có ∆j < 0 mà tối ưu fmax = . xj ≤ 0 thì bài toán không có lời giải, cột quay s là 3 + f(x) = 3x1 ‒ x2 ‒ 2x3 ⟶ max cột tương ứng với ∆s < 0 nhỏ nhất. Ví dụ: Giải bài toán ‒x1 + 3x2 + x3 + x4 = 7 + f(x) = 2x1 + 3x2 + x3 ⟶ max 3x1‒ 4x2 + 8x3 + x5 = 10 x1 ‒ 5x2 + x3 = 6 4x1‒ 2x2 + x6 = 12 2x1+ 2x2 + x4 = 7 xj ≥ 0, j = 1,2, ,6. ‒x1 + 2x2 + x5 = 5 ĐS: Phương án tối ưu x* = (5, 4, 0, 0, 11, 0). Giá trị xj ≥ 0, j = 1,2,3,4,5. tối ưu fmax = 11. Chuongnn-hui.blogspot.com 11
12. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Giải bài toán quy hoạch tuyến tính với EXCEL trong đó ở dòng phương án, ta gán các giá trị ban Cài thêm công cụ Add-ins Solver đầu là 1 (hay 0) cho các biến xj ≥ 0. + Options ⟶ Add-Ins ⟶ Excel Add-Ins. + Trong hộp thoại Add-Ins ta click chọn Solver Add-In. Tổ chức dữ liệu trên bảng tính Tiến hành nhập liệu trên bảng tính Excel như sau Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Tiến hành giải bài toán + Data ⟶ Solver + Trong hộp thoại Solver Parameters: Set Objective: click chọn ô chứa giá trị mục tiêu B8. Max/Min/Equal To: chọn loại bài toán để giải. By Changing Cells: click chọn địa chỉ tuyệt đối của các ô ghi các giá trị ban đầu của biến. Subject to the Constraints: nhập các ràng buộc. Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Ta có thể sửa đổi, thêm bớt các ràng buộc. Muốn thêm vào ràng buộc ta click chọn nút Add. trong hộp thoại Add Constraint: Cell Reference: click chọn địa chỉ chứa công thức. Ô dấu: lựa chọn dấu của các ràng buộc tương ứng. Constraint: Ô chứa giá trị vế phải của các ràng buộc tương ứng (ta cũng có thể nhập trực tiếp giá trị vế phải của ràng buộc tương ứng). Chuongnn-hui.blogspot.com 12
13. QUY HOẠCH TUYẾN TÍNH 02/09/2012 Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Select a solving method: click chọn phương pháp Hãy lập kế hoạch sản xuất sao cho lãi thu được giải, ở đây là Simplex LP phương pháp đơn hình. nhiều nhất? Trong hộp thoại Solver Result: Minh hoạ dữ liệu bài toán: Keep Solver Solution: Lấy kết quả, in ra bảng tính. Sản phẩm Số nguyên A B Restore Original Values: Huỷ kết quả vừa tìm được Nguyên liệu liệu tối đa và trả các biến về tình trạng ban đầu. I 2 1 8 Save Scenario: Lưu kết quả vừa tìm được thành II 0 6 24 một tình huống để có thể xem lại sau này. III 4 0 12 Lưu ý: Có 3 loại báo cáo là Answer, Sensitivity và Tiền lãi/đơn vị Limits. 3 5 sản phẩm Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Mô hình toán học của bài toán Tương tự hãy lập mô hình toán học cho bài toán: Tìm x = (x , x ) sao cho Một công ty sản xuất 2 loại sơn nội thất và sơn 1 2 ngoài trời, sử dụng 2 loại nguyên liệu A, B với trữ f(x) = 3x1 + 5x2 ⟶ max lượng là 6 tấn và 8 tấn. Một tấn sơn nội thất cần 2 với các ràng buộc tấn nguyên liệu A và 1 tấn nguyên liệu B, một tấn 2x + x ≤ 8 sơn ngoài trời cần 1 tấn nguyên liệu A và 2 tấn 1 2 nguyên liệu B. Lượng sơn nội thất không hơn sơn 6x2 ≤ 24 ngoài trời quá 1 tấn, lượng sơn nội thất tối đa là 2 4x1 ≤ 12 tấn. Giá bán một tấn sơn nội thất là 2000USD, giá bán một tấn sơn ngoài trời là 3000USD. x1, x2 ≥ 0 Hỏi cần sản xuất mỗi loại sơn bao nhiêu tấn để có doanh thu lớn nhất ? Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Bài toán tổng quát: Một công ty sản xuất n loại sản phẩm Sj (j=1,2, ,n) sử dụng m loại nguyên liệu Ni (i = 1,2, ,m). Biết: + Lượng nguyên liệu Ni cần thiết dùng để sản xuất một đơn vị sản phẩm Sj là: aij + Trữ lượng nguyên liệu Ni là: bi + Tiền lãi một đơn vị sản phẩm Sj là: cj Hãy xây dựng kế hoạch sản xuất cho công ty để có lợi nhuận nhiều nhất. Chuongnn-hui.blogspot.com 13