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

ThS. Phạm Trí Cao * Chương 2 03/01/2014 1 1 CHƯƠNG 2: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU 2  I) CÁCH THÀNH LẬP BÀI TOÁN QHTT ĐỐI NGẪU Để lập bài toán QHTT đối ngẫu được đơn 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. 3 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 <= 2520  x1 + 2x2 + 2x3 + 3x4 = 2800  x1 >=0 , x2 >=0 , x3 <=0 , x4 tùy ý 4 ThS. Phạm Trí Cao * Chương 2 03/01/2014 2 5 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 6 7  Quy tắc lập bài toán đối ngẫu:  Qua 2 ví dụ trên ta có quy tắc lập bt đối ngẫu như sau:  Hàm mục tiêu của bài toán gốc min (max)  hàm mục tiêu của bài toán đối ngẫu max (min).  Véc tơ hệ số hàm mục tiêu của bài toán gốc trở thành véc tơ hệ số vế phải ràng buộc chung của bài toán đối ngẫu.  Véc tơ hệ số vế phải ràng buộc chung của bài toán gốc trở thành véc tơ hệ số hàm mục tiêu của bài toán đối ngẫ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. 8  Dấu một ràng buộc chung của bài toán gốc quy định dấu một ràng buộc biến tương ứng của bài toán đối ngẫu. Dấu một ràng buộc biến của bài toán gốc quy định dấu một ràng buộc chung tương ứng của bài toán đối ngẫu.  Cách nhớ: bạn đọc nên thuộc lòng 2 câu “thần chú”:  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.  Bài toán gốc max: ràng buộc chung trái dấu, ràng buộc biến cùng dấu. ThS. Phạm Trí Cao * Chương 2 03/01/2014 3 9 Quy tắc về dấu được cho trong bảng sau: GỐC min ĐỐI NGẪU max Ràng buộc chung >= <= = >=0 <=0 tùy ý Ràng buộc biến Ràng buộc biến >=0 <=0 tùy ý <= >= = Ràng buộc chung ĐỐI NGẪU min GỐC Max 10  II) CÁC ĐỊNH LÝ ĐỐ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 (P*) là bài toán QHTT. Ta có thể kẻ 2 bảng đơn hình để giải 2 bài toán này riêng lẻ. Tuy nhiên, việc này sẽ phức tạp nếu bài toán có nhiều biến và nhiều ràng buộc. Vậy có cách nào giúp ta chỉ phải kẻ 1 bảng đơn hình cho 1 bài toán mà có kết quả cho cả 2 bài toán không?  Bài toán gốc (P) ta có 3 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 bài toán đối ngẫu (P*) trực tiếp bằng phương pháp đơn hình. Từ patư y* của (P*) ta suy ra patư x* của bài toán gốc (P). 11 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*), theo cách 2. 12 ThS. Phạm Trí Cao * Chương 2 03/01/2014 4 13 Các định lý đối ngẫu: Xét cặp bài toán đối ngẫu:  (P) (P*) f(x) =  min f*(y) =  max xX yY X là miền ràng buộc (tập pa) của bài toán (P). Y là miền ràng buộc của bài toán (P*).  Chi tiết xem trong sách. 14 Từ các định lý trên ta có kết quả sau: * Cả hai bài toán cùng có pa thì cả 2 bài toán cùng có patư, và giá trị tối ưu của 2 hàm mục tiêu luôn bằng nhau. * 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 bị chặn dưới, hoặc (P*) có pa thì f*(y) không bị chặn trên). * Cả 2 bài toán cùng không có pa thì hiển nhiên chúng cùng không có patư. 15 Câu hỏi: Qua các kết quả này ta có cách để kiểm tra bài toán có patư hay không, trước khi kẻ bảng đơn hình giải nó. Họ thực hiện điều đó như thế nào !? Lời giải đáp xem trong sách. 16  Nhắc lại:  Ràng buộc chặt là ràng buộc xảy ra dấu =  Ràng buộc lỏng là ràng buộc xảy ra dấu bất đẳng thức thực sự ()  Các khái niệm này xét cho cả ràng buộc chung và ràng buộc biến ĐL3 (độ lệch bù yếu):  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. ThS. Phạm Trí Cao * Chương 2 03/01/2014 5 17 Cách tìm patư của bài toán đối ngẫu dựa vào định lý đối ngẫu:  Từ các định lý đối ngẫu trên ta có cách làm như sau:  Từ patư x* của (P) và các cặp ràng buộc đối ngẫu, ta sẽ được hệ phương trình tuyến tính theo y (có các ẩn là y1, y2, ). Giải hệ pttt này ta được nghiệm y*. Kiểm tra: Nếu y* là pa của (P*) thì y* sẽ là patư của (P*), và hai giá trị tối ưu sẽ bằng nhau (f*max = fmin). 18 Ví dụ 2.5: Bài toán gốc (P) f(x) = (6, 2, 5).(x1, x2, x3)  max                                      19 8 10 3 2 1 . 521 201 132 x x x xj >=0, j= 1,3 1) Giải (P) bằng phương pháp đơn hình? 2) Viết bài toán đối ngẫu (P*), tìm patư của (P*)? Giải: 1) Ta có patư của (P) là x*= (4, 0, 2) , fmax = 34 19 Bài toán đối ngẫu (P*) f*(y) = (10, 8, 9).(y1, y2, y3)  min                                      5 2 6 3 2 1 . 521 203 112 y y y yi >=0, i= 1,3 20 Các cặp ràng buộc đối ngẫu: 2x1 + 3x2 + x3 =0  x1 + 2x3 =0  x1 + 2x2 + 5x3 =0 x1 >=0  2y1 + y2 + y3 >= 6 x2 >=0  3y1 + 2y3 >= 2 x3 >=0  y1 + 2y2 + 5y3 >= 5 ThS. Phạm Trí Cao * Chương 2 03/01/2014 6 21 Ta có: 2(4) + 3(0) + 2 = 10 (c)  4 + 2(2) = 8 (c)  x2= 0 (c)  4 + 2(0) + 5(2) = 14 < 19 (l)  y3 = 0 x1 = 4 >0 (l)  2y1 + y2 + y3 = 6 x3 = 2 >0 (l)  y1 + 2y2 + 5y3 = 5 Giải hệ pttt trên ta được: y*= (7/3, 4/3, 0). Kiểm tra y* là pa của (P*): ta thấy y* thỏa tất cả các ràng buộc của bài toán (P*) nên là pa của (P*). Vậy y* là patư duy nhất của (P*) , f*min = fmax = 34 22 Ví dụ 2.7: Bài toán gốc (P): f(x)= (17, 10, 4).(x1,x2,x3)  max                                        40 0 20 3 2 1 . 134 151 713 x x x x1 =0 1) Dùng phương pháp đơn hình giải bài toán (P)? 2) Viết bài toán đối ngẫu (P*), giải (P*)? Giải: 1) Ta có patư của (P) là x*= (0, 13, 1) và fmax= 134 23 Bài toán đối ngẫu (P*): f*(y)= (20, 0, 40).(y1,y2,y3)  min                                        4 10 17 3 2 1 . 117 351 413 y y y y1 >=0, y2 <=0, y3 tùy ý Các cặp ràng buộc đối ngẫu: 3x1 + x2 + 7x3 =0 x1 + 5x2 + x3 >= 0  y2 <=0 x1 <=0  3y1 + y2 + 4y3 <= 17 x3 >=0  7y1 + y2 + y3 >= 4 24 Ta có: 0 + 5(13) + 1 = 66 >0  y2 = 0 x3= 1 >0  7y1 + y2 + y3 = 4 Ta thấy đây là hệ pttt có 2 pt, 3 ẩn. Giải hệ ta được nghiệm y* (có 1 ẩn tự do). Muốn y* là pa của (P*) thì y* phải thỏa các ràng buộc còn lại của (P*) là: 3y1 + y2 + 4y3 =0 (b) ; y1 + 5y2 + 3y3 = 10 ThS. Phạm Trí Cao * Chương 2 03/01/2014 7 25 Vậy để tìm y* thì ta giải hệ sau:  7y1 + y2 + y3 = 4  y1 + 5y2 + 3y3 = 10  y2 = 0 Giải hệ trên ta được: y*= (1/10, 0, 33/10). Ta thấy y* thỏa 2 ràng buộc (a), (b) còn lại nên y* là pa của (P*). Vậy y* là patư duy nhất của (P*) và f*min = fmax = 134. 26 Ví dụ 2.9: Bài toán gốc (P) f = 6x1 + 8x2 + 9x3 + 9x4  max                                          16 16 12 4 3 2 1 . 2212 2231 1322 x x x x xj >= 0, j= 1,4 Giải bt đối ngẫu (P*) bằng cách dùng định lý đối ngẫu? Giải: Dùng pp ĐH giải (P) ta được x*= (0, 0, 2, 6) , fmax = 72 27 Bt đối ngẫu (P*) f* = 12y1 + 16y2 + 16y3  min                                          9 9 8 6 3 2 1 . 221 223 132 212 y y y * Các cặp ràng buộc đối ngẫu: x1 >=0  2y1 + y2 + 2y3 >= 6 x2 >=0  2y1 + 3y2 + y3 >= 8 x3 >=0  3y1 + 2y2 + 2y3 >= 9 x4 >=0  y1 + 2y2 + 2y3 >=9 28  x3 = 2>0  3y1 + 2y2 + 2y3 = 9  x4 = 6>0  y1 + 2y2 + 2y3 = 9 Giải hệ ta được: y*= (0, y3+9/2, y3) , với y3IR Muốn y* là pa của (P*) thì y* phải thỏa 2 ràng buộc còn lại:  2(0) + (-y3+9/2) + 2y3 >= 6  2(0) + 3(-y3+9/2) + y3 >= 8  ta được: 3/2 <= y3 <= 11/4 Vậy y*= (0, -y3+9/2, y3) , với y3[3/2, 11/4] là pa của (P*) nên là patư của (P*). Vậy y* là patư tổng quát của (P*) , f*min = 72  Bài toán (P*) có vô số patư. ThS. Phạm Trí Cao * Chương 2 03/01/2014 8 29 Ta thấy, từ patư của (P) ta suy ra patư của (P*) bằng cách giải hệ pttt. Vấn đề đặt ra là: Nếu (P) có vô số patư thì mỗi patư của (P) có cho ra 1 patư tương ứng của (P*) hay không? Hay mọi patư của (P) chỉ cho ra cùng 1 patư của (P*)? Ví dụ 2.10: Bài giải chi tiết xem trong sách. 30 Ví dụ 2.10: Bài toán (P) f(x)= (2, 3, 2, 5, 6).(x1, x2, x3, x4, x5)  min                                                 8 14 20 5 4 3 2 1 . 23120 10111 21013 x x x x x xj >=0, j= 1,5 31 Bài toán (P*) f*(y)= (20, 14, 8).(y1, y2, y3)  max                                                        6 5 2 3 2 3 2 1 . 212 301 110 211 013 y y y y2 =0 32 Các cặp ràng buộc đối ngẫu: x1 + x2 + x3  x5 <= 14 y2 <=0   2x2 + x3 3x4 + 2x5 >= 8  y3 >=0 x1 >=0 3y1  y2 <= 2 x2 >=0 y1 + y2 2y3 <= 3 x3 >=0 y2 + y3 <= 2 x4 >=0  y1  3y3 <= 5 x5 >=0 2y1  y2 + 2y3 <= 6 ThS. Phạm Trí Cao * Chương 2 03/01/2014 9 33 Ví dụ 2.11: Với (P) và (P*) của VD 2.10  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)? HD:  Ta dùng kết quả sau:  x là pa của (P).  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) 34 1) Với x= (0, 6, 6, 0, 7) Thay vào các cặp ràng buộc đối ngẫu: 0 + 6 + 6  7 = 5 < 14  y2 = 0 x2= 6>0  y1 + y2  2y3 = 3 x3= 6>0  y2 + y3 = 2 x5= 7>0  2y1  y2 + 2y3 = 6 Giải hệ ta có y*= (1, 0, 2). Ta thấy y* là pa của (P*) nên y* là patư của (P*). Do đó x là patư của (P). 35 2) Với x= (0, 2, 3, 0, 9) Thay vào các cặp ràng buộc đối ngẫu: 0 + 2 + 3  9 = 4 < 14  y2 = 0 2(2) + 3  3(0) + 2(9) = 17 > 8  y3 = 0 x2= 2>0  y1 + y2  2y3 = 3 x3= 3>0  y2 + y3 = 2 x5= 9>0  2y1  y2 + 2y3 = 6 Giải hệ, ta có hệ vô nghiệm. Vậy x không là patư của (P). 36  VD 2.12:  Bài toán (P)  f(x) = 3x1 + x2 + 2x3 + 3x4 + 2x5 + 4x6 min  2x1 + x3 + x4 + 2x6 = 5  3x1 + x2 + 2x4 + x6 = 11  x1 + 2x4 + x5 + x6 = 5  xj >=0 , j= 1,6  x = (5/2, 7/2, 0,0, 5/2, 0) có là patư của bài toán (P) không?  Bài giải chi tiết xem trong sách. ThS. Phạm Trí Cao * Chương 2 03/01/2014 10 37 Ví dụ 2.13: Bài toán (P) f= 8x1 + 6x2 + 9x3  min                                          16 18 15 12 3 2 1 . 312 314 211 123 x x x 1) Chứng tỏ rằng: kẻ bảng đơn hình giải trực tiếp (P) sẽ có 14 biến? 2) Giải (P) bằng cách giải bài toán đối ngẫu của nó? 38 Bài toán đối ngẫu (P*) f* = 12y1 + 15y2 + 18y3 + 16y4  max                                          9 6 8 4 3 2 1 . 3321 1112 2413 y y y y yi >=0, i= 1,4 Giải bài toán (P*) bằng pp đơn hình sẽ có 7 biến. Ta có patư của bt (P*) là y*= (11/10, 7/2, 3/10, 0) , f*max = 711/10 39  Các cặp ràng buộc đối ngẫu:  3x1 + 2x2 + x3 >=12  y1 >=0  x1 + x2 + 2x3 >=15  y2 >=0  4x1 + x2 + 3x3 >=18  y3 >=0  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) Vậy x* là patư duy nhất của (P), fmin = 711/10 Mời ghé thăm trang web: 40  https://sites.google.com/a/ueh.edu.vn/phamtricao/  https://sites.google.com/site/phamtricao/