Giáo trình Quy hoạch tuyến tính - Chương 4: Bài toán đối ngẫu

1 1 2 2 m 1j 1 2j 2 1 1j 1 2j 2 2 1j 1 2j 2 3 1 2 3 .. max(min) .. ; (4') .. ; (5') .. ; (6')( ) 0; (1') 0; (2') ; (3') m mj m j mj m j mj m j i i i g b y b y b y a y a y a y c j J a y a y a y c j J a y a y a y c j JQ y i I y i I y R i I                           Bài toán sau đây được gọi là bài toán đối ngẫu của bài toán (P), ta gọi là bài toán (Q) Trong đó các cặp ràng buộc (1) – (1), (2) – (2), .., (6) – (6) được gọi là các ràng buộc đối ngẫu với nhau. 3  Bài toán quy hoạch tuyến tính VD21: Viết bài toán đối ngẫu (Q) biết 1 2 3 4 5 1 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 4 1 3 5 2 4 2 3 2 min 2 12 2 3 2 5 3 2 6 ( ) 3 2 3 , 0 0 , f x x x x x x x x x x x x x x x x x x P x x x x x x x x x                             4  Bài toán quy hoạch tuyến tính Giải: Bài toán đối ngẫu của bài toán (P) là bài toán sau: 1 2 3 4 1 2 3 4 1 3 4 1 2 4 1 2 3 4 1 2 3 1 2 4 3 12 5 6 3 max 2 3 2 3 2 1 2 3( ) 3 2 1 2 2 0 , , 0 , . g y y y y y y y y y y y y y yQ y y y y y y y y y y y R                            5  Bài toán đối ngẫu 2.1.2 Cách thành lập bài toán đối ngẫu Ta gọi vectơ Bài toán gốc Bài toán đối ngẫu f = cjxj  min g = biyi  max aijxj  bi yi  0  bi  0 = bi  R xj  0 ajiyi  cj  0  cj  R = cj 6  Bài toán quy hoạch tuyến tính VD22: Viết bài toán đối ngẫu (Q) biết 1 2 4 5 1 3 4 5 1 3 4 5 1 2 3 4 5 1 2 3 4 5 2 5 3 4 1 3 min 2 2 4 3 2 7 ( ) 2 3 3 6 2 4 3 , 0 , , 0 , . f x x x x x x x x x x x x P x x x x x x x x x x x x x x x R                           7  Bài toán quy hoạch tuyến tính Giải: Bài toán đối ngẫu của bài toán (P) là bài toán sau: 1 2 3 4 1 2 3 4 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 3 2 4 4 7 6 3 max 2 1 3 2 1 2 3 4 0( ) 2 1 2 3 3 , , 0, 0 f y y y y y y y y y y y y y yQ y y y y y y y y y y R y y                            Lưu ý: Ta có đối ngẫu của bài toán đối ngẫu chính là bài toán gốc ban đầu. 8  Bài toán đối ngẫu 2.2 Mối liên hệ giữa bài toán gốc và bài toán đối ngẫu 2.2.1 Định lý 1 (Đối ngẫu yếu) Ta gọi vectơ Ta xét bài toán quy hoạch tuyến tính gốc dạng tìm min. Cho x, y theo thứ tự là phương án của bài toán gốc và đối ngẫu ta có f(x)  g(y). Lưu ý: Từ định lý nếu ta có phương án của bài toán gốc và đối ngẫu theo thứ tự là x, y mà f(x) = g(y) thì x, y lần lượt là phương án tối ưu của bài toán gốc và bài toán đối ngẫu. 2.2.2 Định lý 2 (Đối ngẫu mạnh) Nếu một trong hai bài toán có phương án tối ưu thì bài toán đối ngẫu của nó cũng có phương án tối ưu và giá trị tối ưu của các hàm mục tiêu của chúng là bằng nhau. 9  Bài toán đối ngẫu Ta gọi vectơ 2.2.3 Định lý 3 (Định lý tồn tại) Một cặp bài toán và bài toán đối ngẫu của nó chỉ có thể xảy ra một trong 3 khả năng loại trừ sau:  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 cùng có phương án tối ưu và giá trị tối ưu của hai hàm mục tiêu là bằng nhau.  Một bài toán có phương án còn 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 không bị chặn trong miền ràng buộc. 10  Bài toán đối ngẫu Ta gọi vectơ 2.2.4 Định lý 4 (Độ lệch bù) Một cặp phương án x, y của bài toán gốc và đối ngẫu là phương án tối ưu khi và chỉ khi chúng nghiệm đúng hệ thức sau 1 1 0 1, 0 1, n i ij j i j m j ji i j i b a x y i m c a y x j n                 Lưu ý: bi – aijxj là độ lệch ở ràng buộc thứ i ở bài toán gốc và cj – ajiyi là độ lệch ở ràng buộc thứ j ở bài toán đối ngẫu của nó. 11  Bài toán đối ngẫu 2.3 Giải bài toán đối ngẫu 2.3.1 Áp dụng định lý độ lệch bù Ta gọi vectơ VD23: Cho bài toán gốc có phương án tối ưu là x* = (2, 4, 0, 0) và giá trị tối ưu là fmin = 6. Tìm phương án tối ưu của bài toán đối ngẫu. f = x1  2x2 + 2x3  min x1 + x2 + 4x4 = 6 2x2 + x3 + 5x4 = 8 xj  0, j=1,2,3,4 12  Bài toán đối ngẫu Ta gọi vectơ Giải: Ta có bài toán đối ngẫu của bài toán đã cho: g = 6y1 + 8y2  max y1  1 y1 + 2y2  2 y2  2 4y1 + 5y2  0 y1, y2  R Do x* = (2, 4, 0, 0) nên áp dụng định lý độ lệch bù ta có: 1 y1 = 0 hay y1 = 1 2  (y1 + 2y2) = 0 y2 = 3/2 Suy ra phương án tối ưu của bài toán đối ngẫu là y* = (1, 3/2) và gmax = 6.1 + 8.(3/2) = 6 = fmin 13  Bài toán đối ngẫu Ta gọi vectơ VD24: Cho bài toán gốc có phương án tối ưu là x* = (0, 1, 0, 2, 3) và giá trị tối ưu là fmin = 6. Tìm phương án tối ưu của bài toán đối ngẫu. f = x1 + x2 + x3 + x4 + x5  min 3x1 + x2 + x3 = 1 5x1 + x2 + x3 + x4 = 3 2x1 + 5x2 + x3 + x5 = 8 xj  0, j=1,2,3,4,5 Giải: Ta có bài toán đối ngẫu của bài toán đã cho: 14  Bài toán đối ngẫu Ta gọi vectơ Do x* = (0, 1, 0, 2, 3) nên áp dụng định lý độ lệch bù ta có: 1 (y1 + y2 + 5y3 ) = 0 hay y1 = 5 1  y2 = 0 y2 = 1 1  y3 = 0 y3 = 1 Suy ra phương án tối ưu của bài toán đối ngẫu là y* = (5, 1, 1) và gmax = 5 + 3 + 8 = 6 = fmin g = y1 + 3y2 + 8y3  max 3y1 + 5y2 + 2y3  1 y1 + y2 + 5y3  1 y1 + y2 + y3  1 y2  1 y3  1 yi  R,, i=1,2,3 15  Bài toán đối ngẫu 2.3.2 Dùng bảng đơn hình của bài toán gốc Ta gọi vectơ VD25: Giải bài toán gốc Suy ra phương án tối ưu của bài toán đối ngẫu. f = x1  2x2 + 2x3  min x1 + x2 + 4x4 = 6 2x2 + x3 + 5x4 = 8 xj  0, j=1,2,3,4 Giải: Phương án cực biên ban đầu x0 = (6, 0, 8, 0) Lập bảng đơn hình 16  Bài toán đối ngẫu Biến cơ sở Hệ số Phương án x1 x2 x3 x4  1 -2 2 0 x1 1 6 1 1 0 (4) [3/2] x3 2 8 0 2 1 5 8/5 Bảng 1 22 0 7 0 [14] x4 0 3/2 1/4 1/4 0 1 6 x3 2 1/2 -5/4 3/4 1 0 [2/3] Bảng 2 1 -7/2 [7/2] 0 0 17  Bài toán đối ngẫu x4 0 4/3 (2/3) 0 -1/3 1 [2] x2 -2 2/3 -5/3 1 4/3 0 Bảng 3 -4/3 [7/3] 0 -14/3 0 x1 1 2 1 0 -1/2 3/2 x2 -2 4 0 1 1/2 5/2 Bảng 4 -6 0 0 -7/2 -7/2 Phương án tối ưu x* = (2, 4, 0, 0), fmin = 6. Biến cơ sở ở bước lặp đầu tiên là x1 và x3 suy ra phương án tối ưu của bài toán đối ngẫu cho bởi: y1 = 1 + c1 = 0 + 1 = 1 y2 = 3 + c3 = 7/2 + 2 = 3/2 18  Bài toán đối ngẫu Ta gọi vectơ VD26: Giải bài toán gốc Suy ra phương án tối ưu của bài toán đối ngẫu. f = x1 + x2 + x3 + x4 + x5  min 3x1 + x2 + x3 = 1 5x1 + x2 + x4 = 3 2x1 + 5x2 + x5 = 8 xj  0, j=1,2,3,4,5 19  Bài toán đối ngẫu Ta gọi vectơ Biến cơ sở Hệ số Phương án x1 x2 x3 x4 x5  1 1 1 1 1 x3 1 1 (3) 1 1 0 0 [1/3] x4 1 3 5 1 0 1 0 3/5 x5 1 8 2 5 0 0 1 4 Bảng 1 12 [9] 6 0 0 0 Giải: Phương án cực biên ban đầu x0 = (0, 0, 1, 3, 8) Lập bảng đơn hình 20  Bài toán đối ngẫu Ta gọi vectơ x1 1 1/3 1 (1/3) 1/3 0 0 [1] x4 1 4/3 0 -2/3 -5/3 1 0 x5 1 22/3 0 13/3 -2/3 0 1 22/13 Bảng 2 9 0 [3] -3 0 0 x2 1 1 3 1 1 0 0 x4 1 2 2 0 -1 1 0 x5 1 3 -13 0 -5 0 1 Bảng 3 6 -9 0 -6 0 0 21  Bài toán đối ngẫu Ta gọi vectơ Phương án tối ưu x* = (0, 1, 0, 2, 3), fmin = 6. Biến cơ sở ở bước lặp đầu tiên là x3, x4và x5 suy ra phương án tối ưu của bài toán đối ngẫu cho bởi: y1 = 3 + c3 = 6 + 1 = 5 y2 = 4 + c4 = 0+ 1 = 1 y3 = 5 + c5 = 0+ 1 = 1 *Quy tắc: Nếu cơ sở ban đầu là ma trận đơn vị thì để 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ác ước lượng k của các biến cơ sở xk ở bảng đơn hình đầu tiên rồi cộng thêm hệ số ck tương ứng. 22  Bài toán đối ngẫu 2.4 Phương pháp đơn hình đối ngẫu Ta gọi vectơ Phương pháp đơn hình đối ngẫu thường áp dụng cho các bài toán có sẵn ma trận đơn vị nhưng có hệ số bi < 0. Xuất phát từ một “giả phương án” nghĩa là vectơ thoả mãn các điều kiện nhưng không thoả mãn ràng buộc về dấu.  Tìm một “giả phương án”  Lập bảng đơn hình đối ngẫu. Nếu các phần tử trong cột giả phương án đều không âm thì ta có phương án tối ưu.  Dòng quay r là dòng có chứa phần tử âm nhỏ nhất trong cột giả phương án.  Cột quay là cột s tương ứng với tỷ số nhỏ nhất trong các tỷ số k/zrk với zrk < 0. Tiếp tục biến đổi bảng đơn hình bình thường 23  Bài toán đối ngẫu Ta gọi vectơ VD27: Dùng phương pháp đơn hình đối ngẫu, giải bài toán f = x1 + 2x2 + 3x3 + 4x4  min x1 + x2 + x3 + 4x4  6 4x1 + x2 + x3 + x4  9 xj  0, j=1,2,3,4 Giải: Ta đưa bài toán về dạng chính tắc: f = x1 + 2x2 + 3x3 + 4x4  min  x1  x2  x3  4x4 + x5 =  6  4x1  x2  x3  x4 + x6 =  9 xj  0, j=1,2,3,4,5,6 24  Bài toán đối ngẫu Giả phương án (0, 0, 0, 0, 6, 9) Lập bảng đơn hình đối ngẫu: Biến cơ sở Hệ số Giả phương án x1 x2 x3 x4 x5 x6 1 2 3 4 0 0 x5 0 -6 -1 -1 -1 -4 1 0 x6 0 [-9] (-4) -1 -1 -1 0 1 Bảng 1 0 -1 -2 -3 -4 0 0 25  Bài toán đối ngẫu x5 0 [-15/4] 0 -3/4 -3/4 (-15/4) 1 -1/4 x1 1 9/4 1 1/4 1/4 1/4 0 -1/4 Bảng 2 9/4 0 -7/4 -11/4 -15/4 0 -1/4 x4 4 1 0 1/5 1/5 1 -4/15 1/15 x1 1 2 1 1/5 1/5 0 1/15 -4/15 Bảng 3 6 0 -1 -2 0 -1 0 Phương án tối ưu x* = (2, 0, 0, 1, 0, 0) Giá trị tối ưu fmin = f(x*) = 6 26  Bài toán đối ngẫu Ta gọi vectơ VD28: Dùng phương pháp đơn hình đối ngẫu, giải bài toán f = 15x1 + 12x2 + 10x3  min 3x1 + 4x2 + 2x3  160 x1 + 2x2 + 3x3  140 xj  0, j=1,2,3 Giải: Ta đưa bài toán về dạng chính tắc: f = 15x1 + 12x2 + 10x3  min  3x1  4x2  2x3  x4 =  160  x1  2x2  3x3  x5 =  140 xj  0, j=1,2,3,4,5 27  Bài toán đối ngẫu Giả phương án (0, 0, 0, 160, 140) Lập bảng đơn hình đối ngẫu: Biến cơ sở Hệ số Giả phương án x1 x2 x3 x4 x5 15 12 10 0 0 x4 0 [-160] -3 (-4) -2 1 0 x5 0 -140 -1 -2 -3 0 1 Bảng 1 0 -15 [-12] -10 0 0 28  Bài toán đối ngẫu x2 12 40 3/4 1 1/2 -1/4 0 x5 0 [-60] 1/2 0 (-2) -1/2 1 Bảng 2 480 -6 0 -4 -3 0 x2 12 25 7/8 1 0 -3/8 ¼ x3 10 30 -1/4 0 1 1/4 -1/2 Bảng 3 600 -7 0 0 -2 -2 Phương án tối ưu x* = (0, 25, 30, 0, 0, 0) Giá trị tối ưu fmin = f(x*) = 600