Quy hoạch tuyến tính

2.1 Định nghĩa bài toán đối ngẫu2.1.1 Định nghĩaXét bài toán quy hoạch tuyến tính gốc (P Bài toán quy hoạch tuyến tínhBà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)
Nội dung trích xuất từ tài liệu:
Quy hoạch tuyến tínhTa gọi vectơ  Bài toán đối ngẫu 2.1 Định nghĩa bài toán đối ngẫu 2.1.1 Định nghĩa Xét bài toán quy hoạch tuyến tính gốc (P) f  c1 x1  c2 x2  ..  cn xn  min(max) ai1 x1  ai2 x2  ..  ain xn  bi ; i  I1 (1) ai1 x1  ai2 x2  ..  ain xn  bi ; i  I 2 (2) ai1 x1  ai2 x2  ..  ain xn  bi ; i  I 3 (3) ( P)  x  0; j  J (4) 1  x  0; j  J (5) j j 2  x j  R; j  J 3 (6) 1  Bài toán quy hoạch tuyến tínhBà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) g  b1 y1  b2 y2  ..  bm ym  max(min) a1j y1  a2j y2  ..  amj ym  c j ; j  J1 (4) a1j y1  a2j y2  ..  amj ym  c j ; j  J 2 (5) a y  a y  ..  a y  c ; j  J (6)(Q)  1j 1 2j 2 3 mj m j yi  0; i  I1 (1)   yi  0; i  I 2 (2)  yi  R; i  I 3 (3)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. 2  Bài toán quy hoạch tuyến tínhVD21: Viết bài toán đối ngẫu (Q) biết f  2 x1  x2  3x3  x4  2 x5  min  x1  x2  2 x3  x4  x5  12  x3  3x4  2 x5  5 2 x1  x1  3x2  2 x4  x5  6  ( P) 3x1  2 x2  x3  x4  3  x1 , x3  0  x5  0  x2 , x4    3  Bài toán quy hoạch tuyến tínhGiải: Bài toán đối ngẫu của bài toán (P) là bài toán sau: g  12 y1  5 y2  6 y3  3 y4  max  y1  2 y2  y3  3 y4  2  y1  3 y3  2 y4  1 2 y1  y2  y4  3 (Q )   y1  3 y2  2 y3  y4  1  y  2 y  y  2  y1  0 , 2y , y3  0 , y  R. 1 2 4 3 4Ta gọi vectơ  Bài toán đối ngẫu 2.1.2 Cách thành lập bài toán đối ngẫu Bài toán gốc Bài toán đối ngẫu f = cjxj  min g = biyi  max  bi 0 aijxj  bi 0 yi R = bi 0  cj ajiyi 0  cj xj R = cj 5  Bài toán quy hoạch tuyến tínhVD22: Viết bài toán đối ngẫu (Q) biết f  x1  x2  x4  3x5  min  x1  2 x3  2 x4  x5  4  x1  3x3  x4  2 x5  7  ( P) 2 x1  3x2  x3  x4  3x5  6  x1  2 x2  4 x3  x4  x5  3  x2 , x5  0 , x3 , x4  0 , x1  R.  6  Bài toán quy hoạch tuyến tínhGiải: Bài toán đối ngẫu của bài toán (P) là bài toán sau: f  4 y1  7 y2  6 y3  3 y4  max  y1  y2  2 y3  y4  1 3 y3  2 y4  1 2 y1  3 y2  y3  4 y4  0 (Q)  2 y1  y2  y3  y4  1  y  2 y  3 y  y  3  y1, y 2R, y 3 0, y  0 4 2 1 3 4Lưu ý: Ta có đối ngẫu của bài toán đối ngẫu chính là bàitoán gốc ban đầu. 7Ta gọi vectơ  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 Ta xét bài toán quy hoạch tuyến tính gốc dạng tìm min. 2.2.1 Định lý 1 (Đối ngẫu yếu) 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. 8Ta gọi vectơ  Bài toán đối ngẫu 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 ...