Bài giảng Tối ưu hóa - Chương 2: Bài toán quy hoạch tuyến tính đối ngẫu

Nội dung text: Bài giảng Tối ưu hóa - Chương 2: Bài toán quy hoạch tuyến tính đối ngẫu

1. ThS. Phạm Trí Cao * Chương 2 03/01/2014  I)CÁCHTHÀNHLẬPBÀITOÁN CHƯƠNG 2: QHTT ĐỐI NGẪU BÀI TOÁN QUY HOẠCH  Để lập bài toán QHTT đối ngẫu được đơn TUYẾN TÍNH ĐỐI NGẪU giản ta nên chuyển bài toán về dạng ma trận, bằng cách tách các giá trị số và biến riêng ra. 1 2  Ví dụ 2.1:  Bài toán gốc (P):  f(x) = x1 +2x2 +0x3 4x4 min  4x1 +6x2 +x3 +x4 >= 1680  x1 +x2 5x3 +2x4 =0 , x2 >=0 , x3 <=0 , x4 tùy ý 3 4 1
2. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Nhận xét:  Bài toán đối ngẫu cũng là bài toán QHTT.  Bài toán gốc (P) có patư là x*= (212, 0, 92, 924) và fmin= -3484, bài toán đối ngẫu (P*) có patư là y*= (47/70, -27/70, -91/70) và fmax= -3484.  Các cặp ràng buộc đối ngẫu: là các cặp ràng buộc có dạng bất đẳng thức.  Viết các cặp ràng buộc đối ngẫu cho VD2.1?  VD2.2 5 6  Quy tắc lập bài toán đối ngẫu: Dấu một ràng buộc chung của bài toán gốc quy  Qua 2 ví dụ trên ta có quy tắc lập bt đối ngẫu như sau: định dấu một ràng buộc biến tương ứng của bài Hàm mục tiêu của bài toán gốc min (max) toán đối ngẫu. hàm mục tiêu của bài toán đối ngẫu max (min).  Dấu một ràng buộc biến của bài toán gốc quy định Véc tơ hệ số hàm mục tiêu của bài toán gốc trở thành dấu một ràng buộc chung tương ứng của bài toán véc tơ hệ số vế phải ràng buộc chung của bài toán đối đối ngẫu. ngẫu.  Cách nhớ: bạn đọc nên thuộc lòng 2 câu “thần  Véc tơ hệ số vế phải ràng buộc chung của bài toán gốc chú”: trở thành véc tơ hệ số hàm mục tiêu của bài toán đối  ngẫu. Bài toán gốc min: ràng buộc chung cùng dấu, ràng buộc biến trái dấu. Ma trận hệ số của bài toán gốc lấy chuyển vị trở thành ma trận hệ số của bài toán đối ngẫu.  Bài toán gốc max: ràng buộc chung trái dấu, ràng 7 8 buộc biến cùng dấu. 2
3. ThS. Phạm Trí Cao * Chương 2 03/01/2014 Quy tắc về dấu được cho trong bảng sau:  II) CÁC ĐỊNH LÝ ĐỐI NGẪU GỐC ĐỐI NGẪU  Ta nhận xét thấy: bài toán gốc (P) và bài toán đối ngẫu min max (P*) là bài toán QHTT. Ta có thể kẻ 2 bảng đơn hình để >= >=0 giải 2 bài toán này riêng lẻ. Tuy nhiên, việc này sẽ phức Ràng buộc chung =0 = Ràng buộc chung  Cách 1: Dùng phương pháp đơn hình để giải trực tiếp (P). tùy ý =  Cách 2: Giải bài toán đối ngẫu (P*) trực tiếp bằng ĐỐI NGẪU GỐC phương pháp đơn hình. Từ patư y* của (P*)tasuyra min Max patư x* của bài toán gốc (P). 9 10  Vấn đề đặt ra là: từ patư tối ưu y* của (P*) ta làm thế nào suy ra được patư x* của (P), theo cách 2.  Bài toán đối ngẫu (P*) có 2 cách giải:  Cách 1: Dùng phương pháp đơn hình để giải trực tiếp (P*).  Cách 2: Giải (P*) thông qua (P), nghĩa là từ patư x* của (P) ta suy ra patư y* của (P*).  Vấn đề đặt ra là: từ patư x* của (P) ta làm thế nào suy ra được patư tối ưu y* của (P*), 11 theo cách 2. 12 3
4. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Các định lý đối ngẫu:  Từ các định lý trên ta có kết quả sau:  Xét cặp bài toán đối ngẫu:  *Cảhaibàitoáncùngcópathìcả2bài  (P) (P*) toán cùng có patư, và giá trị tối ưu của 2 f(x) = min f*(y) = max hàm mục tiêu luôn bằng nhau. x Xy Y  * Chỉ 1 bài toán có pa thì cả 2 bài toán cùng không có patư (giả sử (P) có pa thì f(x) không  X là miền ràng buộc (tập pa) của bài toán (P). bị chặn dưới, hoặc (P*) có pa thì f*(y) không  Y là miền ràng buộc của bài toán (P*). bị chặn trên).  * Cả 2 bài toán cùng không có pa thì hiển  Chi tiết xem trong sách. nhiên chúng cùng không có patư. 13 14 Câu hỏi:  Nhắc lại: Qua các kết quả này ta có cách để kiểm  Ràng buộc chặt là ràng buộc xảy ra dấu = tra bài toán có patư hay không, trước khi  Ràng buộc lỏng là ràng buộc xảy ra dấu bất đẳng kẻ bảng đơn hình giải nó. Họ thực hiện thức thực sự ( )  Các khái niệm này xét cho cả ràng buộc chung và điều đó như thế nào !? ràng buộc biến  ĐL3 (độ lệch bù yếu): Lời giải đáp xem trong sách.  x*, y* là patư của (P), (P*) x*, y* là pa của (P), (P*) và thỏa điều kiện: Trong các cặp ràng buộc đối ngẫu, nếu ràng buộc này là lỏng thì ràng buộc kia là chặt. 15 16 4
5. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Cách tìm patư của bài toán đối ngẫu dựa vào Ví dụ 2.5: định lý đối ngẫu: Bài toán gốc (P)  Từ các định lý đối ngẫu trên ta có cách làm như f(x) = (6, 2, 5).(x1, x2, x3) max sau: 2 3 1 x 10 1  Từ patư x* của (P) và các cặp ràng buộc đối ngẫu, 1 0 2 . x 8 2 ta sẽ được hệ phương trình tuyến tính theo y (có 1 2 5 x 19 các ẩn là y1,y2, ). Giải hệ pttt này ta được 3 nghiệm y*. xj >=0, j= 1,3  Kiểm tra: 1) Giải (P) bằng phương pháp đơn hình? Nếu y* là pa của (P*) thì y* sẽ là patư của (P*), 2) Viết bài toán đối ngẫu (P*), tìm patư của (P*)? và hai giá trị tối ưu sẽ bằng nhau (f*max =fmin). Giải: 17 1)18 Ta có patư của (P) là x*= (4, 0, 2) , fmax = 34 Bài toán đối ngẫu (P*)  Các cặp ràng buộc đối ngẫu:  2x1 +3x2 +x3 =0 f*(y) = (10, 8, 9).(y1, y2, y3) min  x1 +2x3 =0 2 1 1 y 6  x +2x +5x =0 1 1 2 3 3  x >=0  2y +y +y>= 6 3 0 2 . y 2 1 1 2 3  x >=0  3y +2y >= 2 2 2 1 3 1 2 5 y 5  x3 >=0  y1 +2y2 +5y3 >= 5 3 yi >=0, i= 1,3 19 20 5
6. ThS. Phạm Trí Cao * Chương 2 03/01/2014 Ta có: Ví dụ 2.7: Bài toán gốc (P): 2(4) + 3(0) + 2 = 10 (c)  f(x)= (17, 10, 4).(x1,x2,x3) max 4 + 2(2) = 8 (c)  3 1 7 x 20 1 x2= 0 (c)  1 5 1 . x 0 2 4 + 2(0) + 5(2) = 14 0 (l) 2y1 + y2 + y3 = 6 x =0 x3 = 2 >0 (l) y1 + 2y2 + 5y3 = 5 1 2 3 Giải hệ pttt trên ta được: y*= (7/3, 4/3, 0). 1) Dùng phương pháp đơn hình giải bài toán (P)? Kiểm tra y* là pa của (P*): ta thấy y* thỏa tất cả các 2) Viết bài toán đối ngẫu (P*), giải (P*)? ràng buộc của bài toán (P*) nên là pa của (P*). Giải: 21 22 Vậy y* là patư duy nhất của (P*) , f*min = fmax = 34 1) Ta có patư của (P) là x*= (0, 13, 1) và fmax= 134 Bài toán đối ngẫu (P*): Ta có: f*(y)= (20, 0, 40).(y1,y2,y3) min 3 1 4 y 17 0 + 5(13) + 1 = 66 >0 y2 = 0 1 1 5 3 . y 10 x3= 1 >0 7y1 + y2 + y3 = 4 2 7 1 1 y 4 3 Ta thấy đây là hệ pttt có 2 pt, 3 ẩn. Giải hệ ta được y1 >=0, y2 =0 Muốn y* là pa của (P*) thì y* phải thỏa các ràng buộc x1 + 5x2 + x3 >= 0  y2 =0 (b) ; y + 5y + 3y = 10 23 x3 >=0  7y1 + y2 + y3 >= 4 24 1 2 3 1 1 2 3 6
7. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Vậy để tìm y* thì ta giải hệ sau: Ví dụ 2.9: Bài toán gốc (P)  7y1 +y2 +y3 =4 f = 6x1 + 8x2 + 9x3 + 9x4 max  y +5y +3y =10 1 2 3 x 1  y =0 2 2 3 1 12 2 x 2 1 3 2 2 . 16  Giải hệ trên ta được: y*= (1/10, 0, 33/10). Ta x 3 thấy y* thỏa 2 ràng buộc (a), (b) còn lại nên 2 1 2 2 16 x y* là pa của (P*). 4 xj >= 0, j= 1,4  Vậy y* là patư duy nhất của (P*) và f*min = Giải bt đối ngẫu (P*) bằng cách dùng định lý đối ngẫu? fmax = 134. Giải: 25 26Dùng pp ĐH giải (P) ta được x*= (0, 0, 2, 6) , fmax = 72 Bt đối ngẫu (P*)  x3 =2>0 3y1 +2y2 +2y3 =9 f* = 12y1 + 16y2 + 16y3 min  x4 =6>0 y1 +2y2 +2y3 =9 2 1 2 6  Giải hệ ta được: y*= (0, y3+9/2, y3) , với y3 IR y  Muốn y* là pa của (P*) thì y* phải thỏa 2 ràng 2 3 1 1 8 . y buộc còn lại: 3 2 2 2 9  2(0) + (-y3+9/2) + 2y3 >= 6 y 3 1 2 2 9  2(0) + 3(-y3+9/2) + y3 >= 8 * Các cặp ràng buộc đối ngẫu:  ta được: 3/2 =0  2y1 + y2 + 2y3 >= 6  Vậy y*= (0, -y3+9/2, y3),vớiy3 [3/2, 11/4] là pa của (P*) nên là patư của (P*). x2 >=0  2y1 + 3y2 + y3 >= 8  Vậy y* là patư tổng quát của (P*) , f* =72 x3 >=0  3y1 + 2y2 + 2y3 >= 9 min  Bài toán (P*) có vô số patư. x27 4 >=0  y1 + 2y2 + 2y3 >=9 28 7
8. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Ta thấy, từ patư của (P) ta suy ra patư của Ví dụ 2.10: (P*) bằng cách giải hệ pttt. Bài toán (P) f(x)= (2, 3, 2, 5, 6).(x1, x2, x3, x4, x5) min  Vấn đề đặt ra là: Nếu (P) có vô số patư thì x 1 mỗi patư của (P) có cho ra 1 patư tương ứng 3 1 0 1 2 x 20 của (P*) hay không? Hay mọi patư của (P) 2 1 1 1 0 1 . x 14 chỉ cho ra cùng 1 patư của (P*)? 3 0 2 1 3 2 x 8 4  Ví dụ 2.10: x 5  Bài giải chi tiết xem trong sách. 29 30 xj >=0, j= 1,5 Bài toán (P*)  Các cặp ràng buộc đối ngẫu:  x1 +x2 +x3 x5 = 8  y >=0 3 1 0 2 2 3 4 5 3  x >=0  3y y =0  y1 +y2 2y3 =0  y2 +y3 =0  y 3y =0  2y1 y2 +2y3 =0 32 8
9. ThS. Phạm Trí Cao * Chương 2 03/01/2014  Ví dụ 2.11: 1) Với x= (0, 6, 6, 0, 7)  Với (P) và (P*) của VD 2.10 Thay vào các cặp ràng buộc đối ngẫu:  1) Xét xem x= (0, 6, 6, 0, 7) có là patư của (P)?  2) Xét xem x= (0, 2, 3, 0, 9) có là patư của (P)? 0 + 6 + 6 7 = 5 0 y1 + y2 2y3 = 3  HD: x3= 6>0 y2 + y3 = 2  Ta dùng kết quả sau: x5= 7>0 2y1 y2 + 2y3 = 6  x là pa của (P). Giải hệ ta có y*= (1, 0, 2).  x là patư của (P) tồn tại y là pa của (P*)  (Với y tìm được từ x và các cặp rb buộc đối ngẫu) Ta thấy y* là pa của (P*) nên y* là patư của (P*). 33 Do34 đó x là patư của (P). 2) Với x= (0, 2, 3, 0, 9)  VD 2.12:  Bài toán (P) Thay vào các cặp ràng buộc đối ngẫu:  f(x) = 3x1 +x2 +2x3 +3x4 +2x5 +4x6 min 0 + 2 + 3 9 = 4 8 y3 = 0  x1 +2x4 +x5 +x6 =5 x2= 2>0 y1 + y2 2y3 = 3  xj >=0 , j= 1,6 x3= 3>0 y2 + y3 = 2 x = 9>0 2y y + 2y = 6  x=(5/2,7/2,0,0,5/2,0)cólàpatưcủabàitoán(P) 5 1 2 3 không? Giải hệ, ta có hệ vô nghiệm.  Bài giải chi tiết xem trong sách. Vậy35 x không là patư của (P). 36 9
10. ThS. Phạm Trí Cao * Chương 2 03/01/2014 Ví dụ 2.13: Bài toán đối ngẫu (P*) Bài toán (P) f* = 12y1 + 15y2 + 18y3 + 16y4 max y f= 8x1 + 6x2 + 9x3 min 1 3 1 4 2 8 3 2 1 12 y x 2 2 1 1 1 . 6 1 1 1 2 15 y 3 . x 1 2 3 3 9 2 4 1 3 18 y 4 x 3 2 1 3 16 yi >=0, i= 1,4 1) Chứng tỏ rằng: kẻ bảng đơn hình giải trực tiếp (P) sẽ Giải bài toán (P*) bằng pp đơn hình sẽ có 7 biến. có 14 biến? Ta có patư của bt (P*) là y*= (11/10, 7/2, 3/10, 0) , f*max 372) Giải (P) bằng cách giải bài toán đối ngẫu của nó? 38= 711/10  Các cặp ràng buộc đối ngẫu: Mời ghé thăm trang web:  3x1 +2x2 +x3 >=12  y1 >=0 40  x +x+2x >=15  y >=0 1 2 3 2   4x +x+3x >=18  y >=0 1 2 3 3   2x1 +x2 +3x3 >=16  y4 >=0  Ta có:  y1 = 11/10 >0 3x1 +2x2 +x3 =12  y2 =7/2>0 x1 +x2 +2x3 =15  y3 =3/10>0 4x1 +x2 +3x3 =18  Giải hệ ta có: x*= (-9/10, 9/2, 57/10) 39 Vậy x* là patư duy nhất của (P), fmin = 711/10 10