Tiểu luận Quy hoạch tuyến tính

thuộc tuyến tính vào M nên các ước lượng của các biến cũng phụ thuộc tuyến tính vào M : Quy tắc xét dấu và ước lượng như sau : > 0 nếu () hoặc , nếu () hoặc , Trong bảng đơn hình: Tách dòng mục tiêu ( dòng cuối ) thành hai dòng riêng: dòng đầu ghi các hệ số , dòng sau ghi các hệ số (k = 0, 1, 2, …, n+m) Ví dụ 2 : Dùng phương pháp đơn hình giải bài toán QHTT sau : Điều kiện : Đưa vào 1 ẩn phụ x4 và 2 ẩn giả x5, x6 ta có bài toán (M) : Với điều kiện : Lập bảng đơn hình cho bài toán : Cơ sở Hệ số cj Phương án A1 A2 A3 A4 – 2 – 2 – 3 0 A4 0 10 1 2 1 1 10 A5 M 15 1 2 3 0 5 A6 M 20 2 1 [5] 0 4444 Bảng 1 2 2 3 0 3 3 8 0 A4 0 6 3/5 9/5 0 1 10/3 A5 M 3 – 1/5 [7/5] 0 0 15/7 A3 –3 4 2/5 1/5 1 0 20 Bảng 2 4/5 7/5 0 0 – 1/5 7/5 0 0 A4 0 15/7 [6/7] 0 0 1 15/6 A2 – 2 15/7 – 1/7 1 0 0 _ A3 – 3 25/7 3/7 0 1 0 25/3 Bảng 3 1 0 0 0 A1 – 2 5/2 1 0 0 7/6 A2 – 2 5/2 0 1 0 1/6 A3 – 3 5/2 0 0 1 – 1/2 Bảng 4 – 35/2 0 0 0 – 7/6 Vậy phương án tối ưu xÚ = ( 5/2, 5/2, 5/2 ) cơ sở { A1, A2, A3} fmin = – 35/2 Ghi chú : Trường hợp bài toán có dạng với Ta có thể chuyển sang bài toán với Kiểm tra tối ưu : Nếu thì x0 là phương án tối ưu Kiểm tra trường hợp không có phương án tối ưu : Nếu và thì bài toán không có phương án tối ưu. Xây dựng phương án cực biên mới đến thì lập phương án cực biên mới Chọn vectơ đưa vào cơ sở, chọn s thỏa mãn Xác định vectơ loại khỏi cơ sở như trường hợp cực tiểu Các tính toán còn lại như bài toán min Ví dụ 3: Dùng phương pháp đơn hình giải bài toán QHTT sau : Điều kiện : Cách 1: Giải trực tiếp bài toán max Đưa vào phương trình hàm mục tiêu 2 ẩn giả x6, x7 ta có bài toán (M) Điều kiện : Lập bảng đơn hình cho bài toán : Cơ sở Hệ số cj Phương án A1 A2 A3 A4 A5 –1 1 2 0 0 A4 0 6 –2 –1 4 1 0 _ A6 –M 6 2 1 1 0 –1 3 A7 –M 4 [2] 2 –1 0 0 2 Bảng 1 1 –1 –2 0 0 – 4 –3 0 0 1 A4 0 10 0 1 3 1 0 10/3 A6 –M 2 0 –1 [2] 0 –1 1 A1 –1 2 1 1 –1/2 0 0 _ Bảng 2 0 –2 –3/2 0 0 0 1 –2 0 1 A4 0 7 0 [5/2] 0 1 3/2 14/5 A3 2 1 0 –1/2 1 0 –1/2 _ A1 –1 5/2 1 3/4 0 0 –1/4 10/3 Bảng 3 0 –11/4 0 0 –3/4 A2 1 14/5 0 1 0 2/5 3/5 A3 2 12/5 0 0 1 1/5 –1/5 A1 –1 2/5 1 0 0 –3/10 –7/10 Bảng 4 36/5 0 0 0 11/10 9/10 Vậy phương án tối ưu : xÚ= ( 2/5, 14/5, 12/5 ) fmax = 36/5 Cách 2 : Chuyển dạng bài toán từ thành Ta giải bài toán với các điều kiện tương tự cách 1 với hàm mục tiêu  Lập bảng đơn hình cho bài toán Cơ sở Hệ số cj Phương án A1 A2 A3 A4 A5 –1 – 2 0 0 A4 0 6 –2 –1 4 1 0 _ A6 M 6 2 1 1 0 –1 3 A7 M 4 [2] 2 –1 0 0 2 Bảng 1 –1 1 2 0 0 4 3 0 0 –1 A4 0 10 0 1 3 1 0 10/3 A6 M 2 0 –1 [2] 0 –1 1 A1 1 2 1 1 –1/2 0 0 _ Bảng 2 0 2 3/2 0 0 0 –1 2 0 –1 A4 0 7 0 [5/2] 0 1 3/2 14/5 A3 2 1 0 –1/2 1 0 –1/2 _ A1 –1 5/2 1 3/4 0 0 –1/4 10/3 Bảng 3 0 11/4 0 0 3/4 A2 1 14/5 0 1 0 2/5 3/5 A3 2 12/5 0 0 1 1/5 –1/5 A1 –1 2/5 1 0 0 –3/10 –7/10 Bảng 4 –36/5 0 0 0 –11/10 –9/10 Vậy phương án tối ưu : xÚ= ( 2/5, 14/5, 12/5 ) – fmin = –36/5 è fmax = 36/5 BÀI TẬP Dùng phương pháp đơn hình giải bài toán sau: f = -50 x1 – 60x2  min  Giải Thêm 3 ẩn phụ x3,4,5  , ta có: Ta có phương án cực biên ban đầu x0 = (0, 0, 8, 5, 36) với cơ sở tương ứng là ( A3, A4, A5) Lập bảng đơn hình cho bài toán Cơ sở Hệ số Phương án A1 A2 A3 A4 A5 θ -50 -60 0 0 0 A3 0 8 1 [2] 1 0 0 4 A4 0 5 1 1 0 1 0 5 A5 0 36 9 4 0 0 1 9 Bảng 1 50 60 0 0 0 A2 -60 4 1/2 1 ½ 0 0 8 A4 0 1 [1/2] 0 -1/2 1 0 2 A5 0 20 7 0 2 0 1 20/7 Bảng 2 20 0 -30 0 0 A2 -60 3 0 1 1 -1 0 A1 -50 2 1 0 -1 2 0 A5 0 6 0 0 5 14 1 Bảng 3 -280 0 0 -10 -40 0 Vậy phương án cực biên tối ưu mới x = (2,3,0,0,5) fmin = -280 f = 2x1 + 5x2 + 4x3 + x4 - 5x5 à min x1 + 2 x2 + 4x3 -3x5 = 152 4 x2 + 2x3 + x4 + 3x5 = 60 3x2 + x5 ≤ 36 xj ≥ 0 ( j = 1,2,3,4,5) Giải Thêm 1 ẩn phụ x6 ≥ 0, ta có: x1 + x2 + 4 x3 -3x5 = 152 4x2 + 2x3 + x4 + 3x5 = 60 3x2 + x5 + x6 = 36 Xj ≥ 0 (j = 1, 2, 3, 4, 5, 6) Ta có phương án cực biên ban đầu x0 = (152, 0, 0, 60, 0, 36) với cơ sở tương ứng là ( A1, A4, A6 ) Lập bảng đơn hình: Cơ sở Hệ số Phương án A1 A2 A3 A4 A5 A6 θ 2 5 4 1 -5 0 A1 2 152 1 2 4 0 -3 0 38 A4 1 60 0 4 [2] 1 3 0 30 A6 0 36 0 3 0 0 5 1 - Bảng 1 0 1 6 0 2 0 A1 2 32 1 -6 0 -2 -9 0 A3 4 30 0 2 1 ½ 3/2 0 A6 0 36 0 3 0 0 5 1 Bảng 2 184 0 -9 0 -3 -7 0 Vậy phương án cực biên mới tối ưu là x = (32, 0, 30, 0, 0) fmin = 184 f = 6x1 + x2 + x3 + 3x4 + x5 - 7x6 + 6x7 à min -x1 + x2 – x4 + x6 + x7 = 15 2x1 –x3 + 2x6 + x7 = -9 4x1 + 2x4 + x5 – 3x6 = 2 xj ≥ 0 (j = 1,…,7) Giải Điều kiện bài toán được viết lại: -x1 + x2 – x4 + x6 + x7 = 15 -2x1 + x3 – 2x6 – x7 = 9 4x1 + 2x4 + x5 – 3x6 = 2 xj ≥ 0 (j = 1,…,7) Ta có phương án cực biên ban đầu x0 = (0, 15, 9, 0, 2, 0, 0) Với cơ sở ban đầu (A2; A3; A5) Cơ sở Hệ số phương án A1 A2 A3 A4 A5 A6 A7 θ 6 1 1 3 1 -7 6 A2 1 15 -1 1 0 -1 0 [1] 1 15 A3 1 9 -2 0 1 0 0 -2 -1 - A5 1 2 4 0 0 2 1 -3 0 - Bảng 1 -5 0 0 -2 0 3 -6 A6 -7 15 -1 1 0 -1 0 1 1 - A3 1 39 -4 2 1 -2 0 0 1 - A5 1 47 1 3 0 -1 1 0 3 - Bảng 2 -2 -3 0 1 0 0 -9 Bài toán không có phương án tối ưu. -x1 + x2 ≤ 1 3x1 + 2x2 ≤ 6 3x1 + x2 ≤ 9 xj ≥ 0 ( j = 1; 2) f = x1 – x2 à min x1 -x2 ≥ -1 ó 3x1 + 2x2 ≤ 6 -3x1 –x2 ≥ -9 x1 ≥ 0; x2 ≥ 0 Giải Thêm ẩn phụ x3,4,5 ≥ 0 vào, ta có f = x1 – x2 à min -x1 + x2 + x3 = 1 3x1 + 2x2 + x4 = 6 3x1+ 2x2 + x5 = 9 xj ≥ 0 ( j = 1, 2,…, 5) Ta có phương án cực biên ban đầu x0 = (0, 0, 1, 6, 9) Lập bảng đơn hình: Cơ sở Hệ số Phương án A1 A2 A3 A4 A5 θ 1 -1 0 0 0 A3 0 1 -1 [1] 1 0 0 1 A4 0 6 3 2 0 1 0 3 A5 0 9 3 2 0 0 1 9 Bảng 1 -1 1 0 0 0 A2 -1 1 -1 1 1 0 0 A4 0 4 5 0 -2 1 0 A5 0 8 4 0 -1 0 1 Bảng 2 -1 0 0 -1 0 0 Ở bảng đơn hình cuối ta có A1 không phải là cơ sở nhưng ∆1 = 0 Bài toán có vô số phương án tối ưu và fmin = -1 Dùng phương pháp phạt giải các bài toán sau: f = - x1 - 2x2 - 3x3 + x4 à min Điều kiện: x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + x3 + x4 = 10 xj ≥ 0 (j = 1, 2, 3, 4) Giải Thêm 2 ẩn giả x5,6 ≥ 0, ta có bài toán mới: F = -x1 - 2x2 - 3x3 + x4 + Mx5 + Mx6 à min Với các điều kiện ràng buộc mới: x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + x3 + x4 = 10 xj ≥ 0 (j = 1, 2 ,3, 4, 5, 6) Ta có phương án cực biên ban đầu x0 = ( 0; 0; 0; 10; 15; 20) Cơ sở ban đầu : {A5, A6, A4} Lập bảng đơn hình: Cơ sở Hệ số Phương án A1 A2 A3 A4 θ -1 -2 -3 1 A5 M 15 1 2 3 0 5 A6 M 20 2 1 [5] 0 4 A4 1 10 1 2 1 1 10 Bảng 1 2 4 4 0 3 3 8 0 A5 M 3 -1/5 [7/5] 0 0 15/7 A3 -3 4 2/5 1/5 1 0 20 A4 1 6 3/5 9/5 0 1 10/3 Bảng 2 2/5 16/5 0 0 -1/5 7/5 A2 -2 15/7 -1/7 1 0 0 - A3 -3 25/7 3/7 0 1 0 25/3 A4 1 15/7 [6/7] 0 0 1 5/2 Bảng 3 6/7 0 0 0 A2 -2 5/2 0 1 0 1/6 A3 -3 5/2 0 0 1 -1/2 A1 -1 5/2 1 0 0 7/6 Bảng 4 -15 0 0 0 -1 Vậy phương án cực biên tối ưu x0 = ( 5/2, 5/2, 5/2, 0) fmin = 15 f = x1 + 2x2 – x3 à max -x1 +4x2 -2x3 ≤ 6 x1 + x2 +2x3 ≥ 6 2x1 –x2 + 2x3 = 4 x1,2,3 ≥ 0 Giải Ta chuyển bài toán max sang bài toán dạng min. Giải g àmin g = -f = - x1 -2x2 + x3 à min Thêm 2 ẩn phụ x4,5 ≥ 0 và 2 ẩn giả x6,7 ≥ 0 đưa về bài toán (M) G = - x1 -2x2 + x3 + Mx6 + Mx7 à min -x1 + 4x2 - 2x3 + x4 = 6 x1 + x2 + 2x3 – x5 + x6 = 6 2x1 – x2 + 2x3 + x7 = 4 xj ≥ 0 ( j = 1, 2, 3, 4, 5, 6, 7) Ta có phương án cực biên ban đầu x0 = ( 0, 0, 0, 6, 0, 6, 4) với cơ sở tương ứng {A4, A6, A7} Lập bảng đơn hình: Cơ sở Hệ số Phương án A1 A2 A3 A4 A5 θ -1 -2 1 0 0 A4 0 6 -1 4 -2 1 0 - A6 M 6 1 1 2 0 -1 3 A7 M 4 2 -1 [2] 0 0 2 Bảng 1 1 2 -1 0 3 0 4 0 -1 A4 0 10 1 3 0 1 0 10/3 A6 M 2 -1 [2] 0 0 -1 1 A3 1 2 1 -1/2 1 0 0 - Bảng 2 1 3/2 0 0 0 0 2 0 0 -1 A4 0 7 [5/2] 0 0 1 3/2 14/5 A2 -2 1 -1/2 1 0 0 -1/2 -2 A3 1 5/2 ¾ 0 1 0 -1/4 10/3 Bảng 3 11/4 0 0 0 ¾ A1 -1 14/5 1 0 0 2/5 3/5 A2 -2 12/5 0 1 0 1/5 -1/5 A3 1 2/5 0 0 1 -3/10 -7/10 Bảng 4 -36/5 0 0 0 -11/10 -9/10 Vậy phương án cực biên tối ưu của bài toán là x = (14/5, 12/5, 2/5) Và gmin = -36/5 => fmax = 36/5 f = -x1 –x2 +1 -> max g = -f = x1 +x2 -1 -> min -x1 + x2 ≤ 1 3x1 + 2x2 ≥ 6 3x1 +x2 ≤ 9 Giải Thêm 3 ẩn phụ x3,4,6 ≥ 0 và 1 ẩn giả x5≥ 0, ta có G = x1 +x2 +Mx5 - 1 àmin -x1 + x2 +x3 = 1 3x1 + 2x2 –x4 +x5 = 6 3x1 +x2 +x6 = 9 Lập bảng đơn hình Cơ sở hệ số Phương án A1 A2 A3 A4 A6 θ 1 1 0 0 0 A3 0 1 -1 1 1 0 0 - A5 M 6 [3] 2 0 -1 0 2 A6 0 9 3 1 0 0 1 3 Bảng 1 -1 -1 0 0 0 3 2 0 -1 A3 0 3 0 5/3 1 -1/3 0 A1 1 2 1 2/3 0 -1/3 0 A6 0 3 0 -1 0 1 1 Bảng 2 2 0 -1/3 0 0 0 Vậy phương án cực biên mới tối ưu là x = ( 2, 0) gmin = 1 => fmax = -1 Chứng minh x = (2, 4, 0, 0) là phương án cực biên tối ưu của bài toán f(x) = x1 - 2x2 + 2x3 àmin Với điều kiện : x1 + x2 + 4x4 = 6 2x2 + x3 + 5x4 = 8 xj ≥ 0; j = 1, 2, 3, 4 Giải Ta có x = ( 2, 4, 0, 0) thỏa mãn các điều kiện ràng buộc => x là phương án Ngoài ra, ta có cơ sở {A1;A2} là độc lập tuyến tính X là phương án cực biên Ta lập bảng đơn hình của x với cơ sở tương ứng {A1;A2} Cơ sở Hệ số Phương án A1 A2 A3 A4 θ 1 -2 2 0 A1 1 2 1 0 α1 α2 A2 -2 4 0 1 β1 β2 Ta có: A3 = α1. A1 + β1 . A2 ó (0,1) = α1 (1,0) + β1. (1,2) ó 0 = α + β 1 = 2β ó α1 = -1/2 β1 = 1/2 Tương tự ta có A4 = α2. A1 + β2. A2 α2 = -3/2 β2 = 5/2 Đưa vào bảng đơn hình trên, tính ∆ Cơ sở Hệ số Phương án A1 A2 A3 A4 θ 1 -2 2 0 A1 1 2 1 0 -1/2 -3/2 A2 -2 4 0 1 1/2 5/2 0 0 -7/2 -13/2 Ta có ∆i ≤ 0 => x là phương án cực biên tối ưu. CHƯƠNG 3: QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU LÝ THUYẾT Đối ngẫu là một phương pháp mà ứng dụng với mỗi bài toán QHTT đã cho (gọi là bài toán gốc), ta có thể thiết lập một bài toán QHTT khác (gọi là bài toán đối ngẫu) sao cho từ lời giải của bài toán này ta có thể thu được thông tin về lời giải của bài toán kia. Khi phân tích đồng thời cả hai bài toán gốc và dối ngẫu ta có thể rút ra các kết luận sâu sắc cả về mặt toán học lẫn về ý nghĩa thực tiễn. 1. CÁCH LẬP BÀI TOÁN ĐỐI NGẪU 1.1. Xét quy hoạch tuyến tính dạng chuẩn tắc: f(x) = c1x1 + c2x2 + … + cnxn min (P) [Bài toán gốc] Trong đó aij, bi, cj là các hệ số cho trước; x= (x1, x2, … ,xn) Î Rn l vecto biến cần tìm Ta gọi đối ngẫu của (P) là QHTT, ký hiệu (Q), có dạng: g(y) = b1y1+b2y2+ … + bmym max (Q) [Bài toán đối ngẫu] Ở đây y = (y1, y2, … ,ym)Î Rm là vectơ biến cần tìm. Nhận xét: Các ràng buộc chính của (P) « các biến của (Q). Các biến của (P) « các ràng buộc chính của (Q). Các hệ số vế phải ràng buộc chính của (P) trở thành các hệ số mục tiêu của (Q), còn các hệ số mục tiêu của (P) lại trở thành các hệ số vế phải ràng buộc chính của (Q). Bài toán gốc tìm min thì bài toán đối ngẫu tìm max (và ngược lại). Cả hai bài toán (P) và(Q) đều có dạng chuẩn. Ví dụ: tìm bài toán đối ngẫu của bài toán QHTT dạng chuẩn. f(x) = 20x1 + 15x2 ® min Bài toán đối ngẫu là: g(y) = 60y1 + 40y2 + 60y3 ® max Dùng ký hiệu vectơ và ma trận, ta có thể viết: Bài toán gốc: Bài toán đối ngẫu: AT là ma trận chuyển vị của A, là tích vô hướng của hai vectơ a và b. 1.2. Định nghĩa đối ngẫu của bài toán qui hoạch tuyến tính dạng chính tắc: Là bài toán: Dưới dạng vectơ – ma trận, ta có thể viết: Bài toán gốc: Bài toán đối ngẫu: Tổng quát, xét bài toán QHTT có dạng Trong đó I1ÈI2ÈI3 = {1,…,m}, IiÇIk = Æ, i, k = 1, 2, 3 (i¹k); J1ÈJ2ÈJ3 = {1,…,n}, JiÇJk = Æ, j, k = 1, 2, 3(j¹k). Ta gọi đối ngẫu của bài toán trên là bài toán: SƠ ĐỒ ĐỐI NGẪU TỔNG QUÁT Bài toán gốc Bài toán đối ngẫu Các biến gốc: x1, x2,…, xn Các biến đối ngẫu: y1, y2,…,ym Hàm mục tiêu f(x) = c1x1 + c2x2 +…+ cnxn ® min g(y) = b1y1+ b2y2 +…+ bmym ® max Các ràng buộc ai1x1+ai2x2+…+ainxn yi xj a1jy1+a2jy2+…+amjym Nhận xét: Nếu lấy đối ngẫu của bài toán đối ngẫu thì ta sẽ nhận được bài toán gốc. Ví dụ: tìm bài toán đối ngẫu của bài toán sau Bài toán đối ngẫu là: 2. CÁC ĐỊNH LÝ ĐỐI NGẪU. 2.1. Cặp bài toán đối ngẫu dạng chuẩn: (P) (Q) Để tiện nghiên cứu lý thuyế đối ngẫu, ta xét cặp bài toán đối ngẫu (P) và (Q) cho ở dạng chuẩn. Tuy nhiên các kết quả nhận được cũng đúng cho một cặp bài toán đối ngẫu bất kỳ. Định lý 1: (Đối ngẫu yếu). Nếu x là 1 phương án bất kỳ của bài toán gốc (P) và y là 1 phương án bất kỳ của bài toán đối ngẫu (Q) thì: f(x) = c1x1 + c2x2 +…+ cnxn ³ g(y) = b1y1 + b2y2 +…+ bmym Hệ quả: Giá trị mục tiêu của 1 phương án đối ngẫu bất kỳ là 1 cận dưới cho giá trị mục tiêu đối với mọi phương án của bài toán gốc. Nếu hàm mục tiêu của bài toán gốc không bị chặn dưới trong miền ràng buộc của nó thì bài toán đối ngẫu không có bất kỳ mộ phương án nào. Nếu hàm mục tiêu của bài toán đối ngẫu không bị chặn trên trong miền ràng buộc của nó thì bài toán gốc không có bất kỳ một phương án nào. Nếu x* là 1 phương án của bài toán gốc, y* là 1 phương án của bài toán đối ngẫu và f(x*) = g(y*) thì x* là phương án tối ưu của bài toán gốc và y* là phương án tối ưu của bài toán đối ngẫu. Định lý 2: (Đối ngẫu mạnh). Nếu một quy hoạch có phương án tối ưu thì quy hoạch đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của chúng là bằng nhau. Định lý 3: (Định lý tồn tại). Đối với mỗi cặp quy hoạch đối ngẫu nhau thì có thể xảy ra một trong ba khả năng loại trừ nhau sau đây. Cả hai bài toán đều không có phương án. Cả hai bài toán đều có phương án. Khi đó, cả hai bài toán đều có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu là bằng nhau. Một bài toán có phương án và bài toán kia không có phương án. Khi đó, bài toán có phương án sẽ không có phương án tối ưu và hàm mục tiêu của nó không giới nội trong miền ràng buộc. Định lý 4: (Định lý về độ lệch bù). Một cặp phương án x, y của hai bài toán (P), (Q) là những phương án tối ưu khi và chỉ khi chúng nghiệm đúng các hệ thức: (2) Nhận xét: : độ lệch ở ràng buộc I của (P). : độ lệch ở ràng buộc j của(Q). Ghi chú: Các hệ thức (1), (2) nói rằng: với mỗi ràng buộc gốc hay đối ngẫu thì tích của độ lệch ở ràng buộc này và biến đối ngẫu (hay biến gốc) tương ứng với ràng buộc đó phải bằng không. Nói cách khác, nếu một ràng buộc có độ lệch dương thì biến (gốc hay đối ngẫu) tương ứng với ràng buộc đó phải bằng không; ngược lại, nếu một biến gốc hay đối ngẫu có giá trị dương thì phương án của bài toán thỏa mãn ràng buộc tương ứng với dấu bằng. Như vậy, hệ thức (1) có nghĩa là: >bi yi = 0 Và yi > 0 =bi Hệ thức (2) cũng có nghĩa tương tự: < cj xj = 0 Và xj > 0 = cj Định lý 5 (Định lý mạnh về độ lệch bù). Nếu cặp bài toán đối ngẫu (P) và (Q) có phương án thì tồn tại một cặp phương án tối ưu x*, y* nghiệm đúng y* + (Ax* - b) > 0 Và x* + ( c – ATy*) >0 2.2. Tìm phương án tối ưu của bài toán đối ngẫu Nếu biết phương án tối ưu của bài toán gốc, vận dụng lý thuyết đối ngẫu ta có thể suy ra phương án tối ưu của bài tối đối ngẫu tương ứng mà không cần giải nó, Ví dụ: Bài toán qui hoạch tuyến tính Có phương án tối ưu x* = (0, 1, 0, 2, 3) với fmin = 6. Hãy tìm phương án tối ưu của bài toán đối ngẫu tương ứng. Giải Bài toán đối ngẫu của bài toán gốc là: Gọi y* là phương án tối ưu của bài toán đối ngẫu Do x*2, x*3, x*5 >0, nên theo định lý độ lệch bù, y* là nghiệm đúng hệ phương trình: Giải hệ phương trình ta có: Vậy y* (-5, 1, 1) là phương án tối ưu của g(y) với gmax = -5 +(3*1) + (8*1) = 6 = fmin Ví dụ: dùng phương pháp đơn hình giải quy hoạch gốc (P) sau đây, từ đó suy ra lời giải của bài toán đối ngẫu tương ứng với nó. Xuất phát từ phương án cực biên ban đầu x0=(2, 12, 9, 0, 0, 0), cơ sở tương ứng {A1, A2, A3). Quá trình giải được ghi lại trong bảng đơn hình dưới đây. Cơ Sở Hệ số cj Phương án A1 A2 A3 A4 A5 A6 q 1 -1 0 -2 2 -3 A1 1 2 1 0 0 [1] 1 -1 2 A2 -1 12 0 1 0 1 0 1 12 A3 0 9 0 0 1 2 4 3 4,5 Bảng 1 -10 0 0 0 2 -1 1 A4 -2 2 1 0 0 1 1 -1 A2 -1 10 -1 1 0 0 -1 2 5 A3 0 5 -2 0 1 0 2 [5] 1 Bảng 2 -14 -2 0 0 0 -3 3 A4 -2 3 3/5 0 1/5 1 7/5 0 A2 -1 8 -1/5 1 -2/5 0 -9/5 0 A6 -3 1 -2/5 0 1/5 0 2/5 1 Bảng 3 -17 -4/5 0 -3/5 0 -21/5 0 Để tìm lời giải (phương án tối ưu) của bài toán đối ngẫu ta áp dụng qui tắc sau: Qui tắc Nếu cơ sở ban đầu của (P) là cơ sở chính tắc (các vecto đơn vị), giả sử là {Aj, jÎJ}. Để tìm lời giải của bài toán đối ngẫu, ta chọn ra từ bảng đơn hình cuối cùng của (P) các Dj (jÎJ) rồi cộng với hệ số cj tương ứng. Vì thế, lời giải của bài toán đối ngẫu y* = (y*1, y*2, y*3) được xác định như sau: Vậy y* =(, -1, ) và gmax = -17 = fmin BÀI TẬP Viết bài toán đối ngẫu của các qui hoạch tuyến tính sau: f = 2x1 + 3x2 - 4x3 + 5x4+® min Điều kiện Giải Bài toán đối ngẫu của bài toán gốc : g = 10y1 + 8y2 + 9y3 ® max Điều kiện f = x1 - 4x2 - 3x3 - 2x4 ® min Điều kiện Giải Bài toán đối ngẫu của bài toán gốc: g = -y1 + 8y2 - 4y3 ® max Điều kiện Xét qui hoạch tuyến tính: Chứng tỏ rằng bài toán này trùng với bài toán đối ngẫu của nó (bài toán tự đối ngẫu). Giải Giả sử bài toán g’(y) sau đây trùng với bài toán gốc: Bài toán đối ngẫu của bài toán gốc f(x) là: Đưa bài toán đối ngẫu về dạng min ta có bài toán tương đương: Bài toán tương đương của bài toán đối ngẫu trùng với bài toán gốc. Þ bài toán tự đối ngẫu. Þ điều phải chứng minh. Cho bài toán qui hoạch tuyến tính: Có phương án tối ưu x* = (2, 4, 0, 0) và giá trị tối ưu là -6. Hãy tìm phương án tối ưu và giá trị tối ưu của bài toán đối ngẫu. Giải Bài toán đối ngẫu của bài toán gốc: Gọi y* = (y1, y2) là phương án tối ưu của bài toán đối ngẫu. Do x1*, x2* > 0 nên theo định lí về độ lệch bù, y* là nghiệm đúng hệ phương trình Giải hệ phương trình, ta được y* = (1, -). Với gmax = 6.1 + 8.(- ) = -6 = fmin Xét qui hoạch tuyến tính: Phát biểu bài toán đối ngẫu của bài toán trên. Hãy giải một trong hai bài rồi suy ra phương án tối ưu của bài toán còn lại. Giải Bài toán đối ngẫu của bài toán gốc: Ta giải bài toán đối ngẫu: Thêm vào hai ẩn phụ vào ràng buộc thứ nhất và thứ hai. Lập bảng đơn hình, ta có: Cơ sở Hệ số Phương án A1 A2 A3 A4 A5 q 3 2 7 0 0 A4 0 15 3 1 3 1 0 5 A5 0 19 1 1 [4] 0 1 19/4 Bảng 1 0 -3 -2 -7 0 0 A4 0 3/4 [9/4] 1/4 0 1 -3/4 1/3 A3 7 19/4 1/4 1/4 1 0 1/4 19 Bảng 2 133/4 -5/4 -1/4 0 0 7/4 A1 3 1/3 1 [1/9] 0 4/9 -1/3 3 A3 7 14/3 0 2/9 1 -1/9 1/3 21 Bảng 3 101/3 0 -1/9 0 5/9 4/3 A2 2 3 9 1 0 4 -3 A3 7 4 -2 0 1 -1 1 Bảng 4 34 1 0 0 1 1 Þ Phương án tối ưu của bài toán đối ngẫu: y* = (0, 3, 4) Gọi x* = (x1, x2) là phương án tối ưu của bài toán gốc. Do y2*, y3* >0, nên theo định lí về độ lệch bù, x*là nghiệm đúng hệ phương trình: Giải hệ phương trình, ta được: x* = (1, 1) Với fmin = gmax = 34 Xét bài toán quy hoạch tuyến tính: f(x) = 4x1 –x2 -3x3 ® min (*) Viết bài toán đối ngẫu. Chứng tỏ x0 = (-1, 1, 1) là phương án tối ưu. Xác định một phương án tối ưu của bài toán đối ngẫu. Giải Bài toán đối ngẫu của bài toán gốc: g(y) = -2y1 + 4y2 - 3y3 - 6y4 + 3y5 ® max Thay x0 = (-1, 1, 1) vào hệ ràng buộc (*), ta có: x0 = (-1, 1, 1) thỏa (*) Þ x0 là phương án của bài toán gốc. Gọi y0 = (y1, y2, y3, y4, y5) là phương án của bài toán đối ngẫu. Do độ lệch ràng buộc 2, 4 của bài toán gốc khác 0 nên theo định lí về độ lệch bù, y0 là nghiệm đúng hệ phương trình: Giải hệ phương trình, ta được y0 = (1, 0, 1, 0, -1). Với: f(x) = g(x) = -8. Þ x0 = (-1, 1, 1) là phương án tối ưu của bài toán gốc. Þ y0 = (1, 0, 1, 0, -1) là phương án tối ưu của bài toán đối ngẫu. Xét qui hoạch tuyến tính: (*) Kiểm tra tính tối ưu của phương án x0 = (5, -6, 1, -4, 0). Phát biểu bài toán đối ngẫu của bài toán trên. Chứng tỏ bài toán đã cho không có phưong án tối ưu. Giải Thế x0 = (5, -6, 1, -4, 0) vào hệ ràng buộc (*), ta có Do độ lệch ràng buộc 2 khác 0 và x10, x20, x30, x40 khác 0 nên theo định lí về độ lệch bù vectơ x0 = (5, -6, 1, -4, 0) là phương án tối ưu của bài toán gốc khi tồn tại vectơ y0 = (y1, y2, y3) Î R3 sao cho: Hệ này vô nghiệm Þ không tồn tại y0 Î R3 thoả hệ trên. Þ phương án x0 = (5, -6, 1, -4, 0) không phải là phương án tối ưu của bài toán gốc. Bài toán đối ngẫu của bài toán gốc: Ta giải hệ ràng buộc của bài toán đối ngẫu: Hệ này vô nghiệm Þ bài toán đối ngẫu có tập phương án rỗng Mà bài toán gốc có tập phương án khác rỗng (vì x0 là 1 phương án) Þ bài toán gốc không có phương án tối ưu (theo định lí tồn tại). Xét qui hoạch tuyến tính: (*) Kiểm tra tính tối ưu của phương án x0 = (2, 0, 1, -2, 3). Phát biểu bài toán đối ngẫu của bài toán trên. Tìm phương án tối ưu của bài toán đối ngẫu. Giải Thế x0 = (2, 0, 1, -2, 3) vào hệ ràng buộc (*), ta có: Do độ lệch ràng buộc 1 của bài toán gốc khác 0 và x10, x30, x40, x50 khác không nên theo định lí về độ lệch bù vectơ x0 = (2, 0, 1, -2, 3) là phương án tối ưu của bài toán gốc khi tồn tại vectơ y0 = (y1, y2, y3) Î R3 sao cho: Giải hệ phương trình, ta được y0 = (0, 4, 0). Þ tồn tại y0 Î R3 thỏa hệ trên. Þ phương án x0 = ( 2, 0, 1, -2, 3) là phương án tối ưu của bài toán gốc. Bài toán đối ngẫu của bài toán gốc: Vì đã biết x0 = (2, 0, 1, -2, 3) là phương án tối ưu của bài toán gốc nên phương án tối ưu y0 của bài toán đối ngẫu có thể tìm từ định lí độ lệch bù: Thay các giá trị đã biết vào hệ, ta được: Vậy phương án tối ưu của bài toán đối ngẫu là y0 = (0, 4, 0). Với gmax = fmin = -36. Xét qui hoạch tuyến tính: Phát biểu bài toán đối ngẫu của bài toán trên. Hãy giải một trong hai bài toán rồi suy ra phương án tối ưu của bài toán còn lại. Giải Bài toán đối ngẫu của bài toán gốc: Ta giải bài toán gốc Thêm vào hai ẩn phụ x5 ³ 0, x6 ³ 0 vào ràng buộc thứ hai và thứ ba. Lập bảng đơn hình, ta có: Cơ sở Hệ số Phương án A1 A2 A3 A4 A5 A6 q 2 1 1 3 0 0 A1 2 16 1 -2 1 0 0 0 A5 0 8 0 [1] 4 1 1 0 8 A6 0 20 0 1 -2 3 0 1 20 Bảng 1 32 0 -5 1 -3 0 0 A1 2 32 1 0 9 2 2 0 A2 1 8 0 1 4 1 1 0 A6 0 12 0 0 -6 2 -1 1 Bảng 2 72 0 0 21 2 5 0 Þ Phương án tối ưu của bài toán gốc là x0 = (32, 8, 0, 0). Gọi y0 = (y1, y2, y3) là phương án tối ưu của bài toán đối ngẫu. Dựa vào bảng đơn hình, ta có: Vậy phương án tối ưu của bài toán đối ngẫu là y0 = (2, 5, 0). Với gmin = fmax = 72. CHƯƠNG 4: BÀI TOÁN VẬN TẢI LÝ THUYẾT 1. NỘI DUNG BÀI TOÁN VẬN TẢI 1.1. Nội dung bài toán: Giả sử cần vận chuyển một loạt hàng thuần nhất (vật tư, lương thực, …) từ m địa điểm cung cấp (điểm phát) A1, A2,… , Am đến n địa điểm tiêu thụ (điểm thu) B1, B2 …, Bn. Biết rằng: Số lượng hàng có ở Ai là ai (i= 1,…, m) Số lượng hàng cần ở Bj là bj (j = 1,…, n) Chi phí vận chuyển một đơn vị hàng từ Ai đến Bj là cij (i=1,…, m; j = 1,…, n) Vấn đề đặt ra: Lập kế hoạch vận chuyển hàng từ các điểm thu đến tổng chi phí vận chuyển bé nhất và thỏa mãn yêu cầu về thu phát. Đây là một trong những bài toán điển hình và có nhiều ứng dụng nhất của quy hoạch tuyến tính. Bài toán này không có gì phức tạp nếu mạng lưới giao thông tương đối đơn giản và số địa điểm cung cấp, tiêu thụ không nhiều lắm. Tuy nhiên với những mạng lưới đường giao thông phức tạp thì bằng kinh nghiệm và trực giác khó có thể tìm ra được phương án tối ưu. Khi đó, cần sử dụng các phương pháp, dựa vào tính chất đặc thù của bài toán để tìm phương án tối ưu. Mô hình toán học của bài toán: Gọi xij là số lượng hàng cần vận chuyển từ Ai đến Bj. Ta có: : Tổng chi phí vận chuyển : số lượng hàng chở đi từ Ai : số lượng hàng chở tới Bj Mô hình toán học của bài toán là: f(x) = (cực tiểu tổng chi phí vận chuyển) (1) với điều kiện: Điều kiện cần và đủ để bài toán (1) – (4) giải được là phải có điều kiện cân bằng thu phát, nghĩa là tổng cung bằng tổng cầu: Bài toán vận tải (1) – (4) là một dạng đặc biệt của qui hoạch tuyến tính, do đó có thể sử dụng phương pháp đơn hình để giải. Tuy nhiên do bài toán có cấu trúc đặc biệt nên người ta đã ra nhiều phương pháp giải có hiệu quả, trong chương trình này ta sẽ trình bày phương pháp thế vị để giải bài toán vận tải. 1.2. Các tính chất của bài toán vận tải Với điều kiện (5), bài toán vận tải (1) – (4) có các tính chất sau đây: Bài toán luôn có phương