Lý thuyết Bài toán quy hoạch tuyến tính đối ngẫu - Chương 2: Lý thuyết đối ngẫu

Nội dung text: Lý thuyết Bài toán quy hoạch tuyến tính đối ngẫu - Chương 2: Lý thuyết đối ngẫu

1. Bài toán gốc Chỉ số Bài toán đối ngẫu f( x ) c , x min g( y )  b , y  max n aij x j b i yi 0 j 1 iI 1 n aij x j b i y 0 j 1 iI 2 i n aij x j b i y j 1 iI 3 i m a y c x 0 jJ 1  ij i j j i 1 m jJ a y c x j 0 2  ij i j i 1 m a y c x j jJ 3  ij i j i 1
2. Ví dụ 1: Viết bài toán đối ngẫu của bài toán sau đây: f( x ) 4 x1 3 x 2 7 x 3  min 12x1 5 x 2 3 x 3 5 (1) xx13 2 (2) 2x1 x 2 x 3 1 (3) x1; x 2 ; x 3 0 (4) Để dễ thấy ta sẽ viết rõ các ma trận
3. 2. Mối quan hệ giữa bài toán gốc và bài toán đối ngẫu: Trong phần này ta chỉ xét bài toán gốc dạng min.
4. 2.5. Định lý 3: ( Định lý độ lệch bù ) Các phương án xy , của bài toán gốc và đối ngẫu đều là phương án tối ưu điều kiện cần và đủ là b Ax, y c yA , x 0 n bi  a ij x j y i 0 i 1, m j 1 hay m c a y x 0 j 1, n . j ij i j i 1
5. Cơ sở Hệ số P/án 1 -2 2 0 x1 x2 x3 x4 A1 1 6 1 1 0  A3 2 8 0 2 1 5 f(x0 ) = 22 0 7 0 14 A4 0 3/2 1/4 1/4 0 1 A3 2 1/2 -5/4 3/4 1 0 f(x1 ) = 1 -7/2 7/2 0 0
6. Bài toán đối ngẫu (Q) là : g y 6 y12 8 y  max y1 1 yy12 22 y2 2 4yy12 5 0 yy12, Phương án tối ưu của bài toán (Q) được tìm từ hệ phương trình
7. 6 (x x 4 x ) y 0 1 2 4 1 6 (2 4 4.0) y1 0 8 (2.4 0 5.0)y 0 8 (2x2 x 3 5 x 4 ) y 2 0 2 1 (y 0. y ) x 0 1 (yy12 0. 2 0 1 2 1 2 (yy 2 4 0 2 (y1 2 y 2 ) x 2 0 12 2 (0.yy 0 0 2 (0.y1 y 2 ) x 3 0 12 0 (4y 5 y ) x 0 0 (4yy12 5 0 0 1 2 4 Hệ phương trình tương đương 1 yy 0. 0 y1 1 12 3 2 yy 2 0 y2 12 2
8. Vậy phương án tối ưu của bài toán đối 3 ngẫu là: y y 12 , y 1, và giá trị tối ưu là: 2 3 g g( y ) 6 y 8 y 6 1 8 6 max 1 2 2
9. Ta thấy bài toán (Q) giải dễ hơn bài toán (P) vì (P) là bài toán có biến giả (bài toán M), do đó ta giải bài toán (Q). g y 3 y1 2 y 2 7 y 3 0 y 4 0 y 5  max 3y1 y 2 3 y 3 y 4 15 y1 y 2 4 y 3 y 5 19 yjj 0, 1,5
10. Cơ sở Hệ số P/án 3 2 7 0 0 y1 y2 y3 y4 y5 A1 3 1/3 1 1/9 0 4/9 -1/3 A3 7 14/3 0 2/9 1 -1/9 1/3 f(x2 ) = 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 f(x3 ) = 34 1 0 0 1 1
11. Các ẩn y 1 ,,,, y 2 y 3 x 1 x 2 thỏa hệ phương trình: 15 3y y 3 y x 0 (1) 1 2 3 1 19 y y 4 y x 0 (2) 1 2 3 2 3 3x1 x 2 . y 1 0 (3) 2 x1 x 2 . y 2 0 (4) 7 3x1 4 x 2 . y 3 0 (5)
12. Bây giờ ta giải bài toán gốc và sử dụng định lý độ lệch bù để tìm lại phương án tối ưu của bài toán đối ngẫu. Thêm vào ba ẩn phụ và ba ẩn giả, sau đó sắp xếp các phần tử lên bảng đơn hình và tính toán ta được.
13. Cơ Hệ P/ 15 19 0 0 0 M M M Sở Số án x1 x2 x3 x4 x5 x6 x7 x8 A6 M 3  1 -1 0 0 1 0 0 A7 M 2 1 1 0 -1 0 0 1 0 A8 M 7 3 4 0 0 -1 0 0 1 f(x0) = 12M 9 6 -1 -1 -1 0 0 0 -15 -19 0 0 0 0 0 0 A1 15 1 1 1/3 -1/3 0 0 1/3 0 0 A7 M 1 0 2/3 1/3 -1 0 -1/3 1 0 A8 M 4 0 3 1 0 -1 -1 0 1 11/3 f(x1) = 5M+15 0 4/3 -1 -1 -7/3 0 0 0 -14 -5 0 0 5 0 0
14. Cơ Hệ P/ 15 19 0 0 0 M M M Sở Số án x1 x2 x3 x4 x5 x6 x7 x8 A1 15 1 1 0 0 -4 1 0 4 -1 A3 0 1 0 0 1 -9 2 -1 9 -2 A2 19 1 0 1 0 3 -1 0 -3 1 f(x4) = 34 0 0 0 0 0 -1 -1 -1 0 0 0 -3 -4 0 3 4 Bài toán tối ưu, với phương án tối ưu là x4 = (1, 1, 1, 0, 0, 0, 0, 0) và giá trị tối ưu fmin = f(x4) = 34.
15. 3y1 y 2 3 y 3 15 y1 0 y1 y 2 4 y 3 19 y 2 3 y 0 y 4 1 3 gmax g y 3 y 1 2 y 2 7 y 3 34
16. Ví dụ 1: Xét lại bài toán QHTT f( x ) x1 2 x 2 2 x 3 0 x 4  min x1 x 2 46 x 4 ()P 2x2 x 3 5 x 4 8 xjj 0, 1,4 Bài toán (P) có p/án tối ưu x (2,4,0,0) Cơ sở liên kết là {A1,A2}. Vậy p/án tối ưu của bài toán đối ngẫu là : 1 1 1 1 1 0.5 3 y cB 1, 2 1, 2 1, 0 2 0 0.5 2
17. 20 25 30 0 0 0 Co So CJ Ph.An y1 y2 y3 y4 y5 y6 A4 0 1 6 1 3 1 0 0 A5 0 1 2 7 1 0 1 0 A6 0 1 1 3 8 0 0 1 -20 -25 -30 0 0 0 A4 0 5/8 45/8 -1/8 0 1 0 -3/8 A5 0 7/8 15/8 53/8 0 0 1 -1/8 A3 30 1/8 1/8 3/8 1 0 0 1/8 -65/4 -55/4 0 0 0 15/4 A1 20 1/9 1 -1/45 0 8/45 0 -1/15 A5 0 2/3 0 20/3 0 -1/3 1 0 A3 30 1/9 0 17/45 1 -1/45 0 2/15 0 -127/9 0 26/9 0 8/3 A1 20 17/150 1 0 0 53/300 1/300 -1/15 A2 25 1/10 0 1 0 -1/20 3/20 0 A3 30 11/150 0 0 1 -1/300 -17/300 2/15 0 0 0 131/60 127/60 8/3
18. 2.7 Mệnh đề: Giả sử AAA jj12 , , , jm là cơ sở đơn vị liên kết của phương án cực biên xất phát của bài toán gốc dạng chính tắc. Khi đó phương án tối ưu của bài toán đối ngẫu có thể tính theo công thức: y c, c , , c j1 j 1 j 2 j 2 jmm j , , , Trong đó j 12 j j m là các ước lượng ứng với các cột AAA jj12 , , , jm xuất hiện ở bảng c, c , , c đơn hình cuối cùng và j12 j jm là các hệ x, x , , x số của j12 j j m .
19. 1 -2 2 0 Co So CJ Ph.An x1 x2 x3 x4 A1 1 6 1 1 0 4 A3 2 8 0 2 1 5 0 7 0 14 A4 0 3/2 1/4 1/4 0 1 A3 2 1/2 -5/4 3/4 1 0 -7/2 7/2 0 0 A4 0 4/3 2/3 0 -1/3 1 A2 -2 2/3 -5/3 1 4/3 0 7/3 0 -14/3 0 A1 1 2 1 0 -1/2 3/2 A2 -2 4 0 1 1/2 5/2 0 0 -7/2 -7/2
20. Ví dụ: Ta xét bài tập 11 ở bài 4 chương 1 f x1 x 2 x 3 min 6x1 2 x 2 x 3 20 x1 7 x 2 3 x 3 25 3x1 x 2 8 x 3 30 xjj 0, 1,2,3. Đối ngẫu của bài toán này là bài toán g( y ) 20 y1 25 y 2 30 y 3 max 6y1 y 2 3 y 3 1 2y1 7 y 2 y 3 1 y1 3 y 2 8 y 3 1 yii 0, 1,3
21. Phương án tối ưu là y = ( 17/150, 1/10, 11/150, 0, 0, 0,) Giá trị tối ưu g = 209/30. từ đây ta suy ra ph. Án tối ưu của bài toán gốc như sau x c, c , , c j1 j 1 j 2 j 2 jmm j Ta có cơ sở liên kết của phương án cực biên xuất phát trong bảng đơn hình đầu là AAA4,, 5 6
22. x 131/60, 127/60, 8/3 Tóm lại, giữa bài toán gốc và đối ngẫu ta có các kết qủa sau: i) Nếu bài toán gốc (đối ngẫu) có phương án tối ưu thì bài toán đối ngẫu (gốc) cũng có phương án tối ưu. Phương án tối ưu có thể tìm bằng ba phương pháp. Giá trị tối ưu của hai bài toán là bằng nhau
23. Nếu bài toán gốc (hoặc đối ngẫu) có tập phương án bằng rỗng thì bài toán đối ngẫu (hoặc gốc) có tập phương án bằng rỗng, hoặc có hàm mục tiêu không bị chặn. Bài tập 1: Chứng minh bài toán sau không có phương án tối ưu. f( x ) x1 7 x 2 2 x 3 6 x 4 max x1 3 x 2 x 3 x 4 10 2x1 5 x 2 x 3 4 x 4 15 xjj 0, 1,4 .
24. Bài tập 2: Cho bài toán (P) f( x ) 4 x1 6 x 2 5 x 3 3 x 4 min x1 3 x 2 3 x 3 2 x 4 9 x1 4 x 2 2 x 3 x 4 7 xjj 0; 1,4. a)Phát biểu bài toán đối ngẫu (Q) của bài toán (P). b) Giải bài toán Q và suy ra phương án tối ưu của bài toán (P) bằng ba cách.
25. 9 7 0 0 0 0 Co So CJ Ph.An A1 A2 A3 A4 A5 A6 A3 0 4 1 1 1 0 0 0 A4 0 6 3 4 0 1 0 0 A5 0 5 3 2 0 0 1 0 A6 0 3 2 1 0 0 0 1 - 9 - 7 0 0 0 0 A3 0 5/2 0 1/2 1 0 0 -1/2 A4 0 3/2 0 5/2 0 1 0 -3/2 A5 0 1/2 0 1/2 0 0 1 -3/2 A1 9 3/2 1 1/2 0 0 0 1/2 0 -5/2 0 0 0 9/2 A3 0 11/5 0 0 1 -1/5 0 -1/5 A2 7 3/5 0 1 0 2/5 0 -3/5 A5 0 1/5 0 0 0 -1/5 1 -6/5 A1 9 6/5 1 0 0 -1/5 0 4/5 0 0 0 1 0 3