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

tuyến tính là hữu hạn. 2  Bài toán quy hoạch tuyến tính Xét bài toán quy hoạch tuyến tính f = 4x1 + x2 + x3  min x1 +2x2  x3 = 5 x1  x2 + 2x3 = 5 xj  0, j=1,2,3 VD5: Trong một phương án cực biên, số thành phần dương không vượt quá m. Nếu số thành phần này bằng m ta có phương án cực biên không suy biến, ngược lại ta có phương án cực biên không suy biến. Trong các vectơ sau.vectơ nào là phương án, vectơ nào là phương án cực biên không suy biến?      0 1 20,5,5 , 5,0,0 , 1,4,4x x x   3  Bài toán quy hoạch tuyến tính 1 2 3 1 2 1 5 , , , 1 1 2 5 A A A b                          Giải: Ta có các vectơ cột liên kết với các biến là: 0 0 0 1 1 2 2 3 3 1 2 1 5 0. 5. 5. 1 1 2 5 x A x A x A b                             1 1 1 1 1 2 2 3 3 1 2 1 5 5. 0. 0. 1 1 2 5 x A x A x A b                             nên x0 là phương án, ngoài ra hệ vectơ liên kết với các biến dương là A2, A3 độc lập tuyến tính nên x0 là phương án cực biên, số thành phần dương của bằng 2 nên x0 là phương án cực biên không suy biến. Tương tự, ta có x1 là phương án cực biên suy biến. 4  Bài toán quy hoạch tuyến tính 2 2 2 1 1 2 2 3 3 1 2 1 5 1. 4. 4. 1 1 2 5 x A x A x A b                             x2 cũng là phương án nhưng không phải là phương án cực biên vì hệ vectơ liên kết với các biến dương là A1, A2, A3 phụ thuộc tuyến tính. Xét bài toán quy hoạch tuyến tính f = x1 + 2 x2  x3  min x1 + x2 + x3 = 4 x1  x2 = 0 xj  0, j=1,2,3 VD6: Trong các vectơ sau.vectơ nào là phương án, vectơ nào là phương án cực biên không suy biến?      0 1 22,2,0 , 0,0,4 , 1,1,2x x x   5  Bài toán quy hoạch tuyến tính VD7: Tìm tất cả các phương án cực biên của bài toán f = 2x1 + x3 + 5x4  min x1 + x3 + x4 = 5 x2  x3 + 2x4 = 1 xj  0, j=1,2,3,4 1 2 3 4 1 0 1 1 5 , , , , 0 1 1 2 1 A A A A b                                Giải: Ta có các vectơ cột liên kết với các biến là: Từ đây ta có 6 hệ vectơ độc lập tuyến tính là {A1, A2}, {A1, A3}, {A1, A4}, {A2, A3}, {A2, A4}, {A3, A4} Xét hệ {A1, A2}, ta biểu diễn b qua A1, A2 nghĩa là tìm x1, x2 sao cho b = x1A1 + x2A2, giải hệ này ta có b = 5A1 + A2. Vectơ x0 = (5, 1, 0, 0) là phương án cực biên. 6  Bài toán quy hoạch tuyến tính Với hệ {A1, A3}, ta có b = 6A1  A3. Vectơ (6, 0, 1, 0) không phải là phương án. Với hệ {A1, A4}, ta có b = 9/2A1 + 1/2A4. Vectơ x1 = (9/2, 0, 0,1/2) là phương án cực biên. Với hệ {A2, A3}, ta có b = 6A2 + 5A3. Vectơ x2 = (0, 6, 5, 0) là phương án cực biên. Với hệ {A2, A4}, ta có b = 9A2 + 5A4. Vectơ (0, 9, 0, 5) không phải là phương án. Với hệ {A3, A4}, ta có b = 3A3 + 2A4. Vectơ x3 = (0, 0, 3, 2) là phương án cực biên. 7  Bài toán quy hoạch tuyến tính 1.3.2 Tìm phương án cực biên Do số thành phần dương của một phương án cực biên không suy biến là bằng m nên suy ra số thành phần bằng 0 sẽ là n – m. Từ đó muốn tìm phương án cực biên ta có thể cho n – m thành phần bằng 0 rồi tính giá trị của m thành phần còn lại. VD8: Tìm tất cả các phương án cực biên của bài toán f = 2x1  x3 + 2x4  min x1 + x2 + x3 + x4 = 10 2x2 + x3  x4 = 6 xj  0, j=1,2,3,4 8  Bài toán quy hoạch tuyến tính VD9: Tìm tất cả các phương án cực biên của bài toán f = 2x1 + x3 + 5x4  min x1 + x3 + x4 = 5 x2  x3 + 2x4 = 1 xj  0, j=1,2,3,4 Giải: Cho x1 = 0, x2 = 0 ta có hệ x3 + x4 = 5 suy ra x3 = 3  x3 + 2x4 = 1 x4 = 2 Vectơ x0 = (0, 0, 3, 2) là phương án cực biên. Cho x1 = 0, x3 = 0 ta có hệ x4 = 5 suy ra x2 = 9 x2 + 2x4 = 1 x4 = 5 Vectơ (0, 9, 0, 5) không phải là phương án. 9  Bài toán quy hoạch tuyến tính Cho x1 = 0, x4 = 0 ta có hệ x3 = 5 suy ra x2 = 6 x2  x3 = 1 x3 = 5 Vectơ x1 = (0, 6, 5, 0) là phương án cực biên. Cho x2 = 0, x3 = 0 ta có hệ x1 + x4 = 5 suy ra x1 = 9/2 2x4 = 1 x4 = 1/2 Vectơ x2 = (9/2, 0, 0, 1/2) là phương án cực biên. Cho x2 = 0, x4 = 0 ta có hệ x1 + x3 = 5 suy ra x1 = 6  x3 = 1 x3 = 1 Vectơ (6, 0, 1, 0) không phải là phương án. 10  Bài toán quy hoạch tuyến tính Ta gọi vectơ Cho x3 = 0, x4 = 0 ta có hệ x1 = 5 x2 = 1 Vectơ x3 = (5, 1, 0, 0) là phương án cực biên. VD10: Tìm tất cả các phương án cực biên của bài toán f = 2x1  x3 + 2x4  min x1 + x2 + x3 + x4 = 10 2x2 + x3  x4 = 6 xj  0, j=1,2,3,4 11  Bài toán quy hoạch tuyến tính 1.4 Các tính chất chung của bài toán quy hoạch tuyến tính Ta gọi vectơ  Tập các phương án của bài toán quy hoạch tuyến tính là tập lồi nghĩa là nếu x, y là hai phương án bất kỳ của bài toán thì mọi tổ hợp x + (1 )y,  R: 0    1 cũng là một phương án của bài toán.  Tập các phương án tối ưu của bài toán quy hoạch tuyến tính cũng là một tập lồi.  Nếu bài toán quy hoạch tuyến tính dạng chính tắc có tập phương án khác rỗng thì nó có ít nhất một phương án cực biên. 12  Bài toán quy hoạch tuyến tính Ta gọi vectơ  Điều kiện cần và đủ để bài toán quy hoạch tuyến tính dạng chính tắc có phương án tối ưu là nó có tập phương án khác rỗng và hàm mục tiêu bị chặn.  Nếu bài toán quy hoạch tuyến tính dạng chính tắc có phương án tối ưu thì nó có ít nhất một phương án cực biên là phương án tối ưu. VD11: Giải bài toán quy hoạch tuyến tính f = 2x3  x4  min x1 + 2x3 + x4 = 6 x2 + x3  2x4 = 2 xj  0, j=1,2,3,4 13  Bài toán quy hoạch tuyến tính Giải: Cho x1 = 0, x2 = 0 ta có hệ 2x3 + x4 = 6 suy ra x3 = 14/5 x3  2x4 = 2 x4 = 2/5 Vectơ x0 = (0, 0, 14/5, 2/5) là phương án cực biên. Cho x1 = 0, x3 = 0 ta có hệ x4 = 6 suy ra x2 = 14 x2  2x4 = 2 x4 = 6 Vectơ x1 = (0, 14, 0, 6) là phương án cực biên. Cho x1 = 0, x4 = 0 ta có hệ 2x3 = 6 suy ra x2 = 1 x2 + x3 = 2 x3 = 3 Vectơ (0, 1, 3, 0) không phải là phương án. 14  Bài toán quy hoạch tuyến tính Cho x2 = 0, x3 = 0 ta có hệ x1 + x4 = 6 suy ra x1 = 7 2x4 = 2 x4 = 1 Vectơ (7, 0, 0, 1) không phải là phương án. Cho x2 = 0, x4 = 0 ta có hệ x1 = 2 x3 = 2 Vectơ x2 = (2, 0, 2, 0) là phương án cực biên. Cho x3 = 0, x4 = 0 ta có hệ x1 = 6 x2 = 2 Vectơ x3 = (6, 2, 0, 0) là phương án cực biên. 15  Bài toán quy hoạch tuyến tính Ta gọi vectơ Ta có x0 = (0, 0, 14/5, 2/5)  f(x0) = 2.14/5  2/5 = 26/5 x1 = (0, 14, 0, 6)  f(x1) = 2.0  6 = 6 x2 = (2, 0, 2, 0)  f(x2) = 2.2  0 = 4 x3 = (6, 2, 0, 0)  f(x3) = 2.0  0 = 0 Suy ra phương án tối ưu của bài toán là x1 = (0, 14, 0, 6) và giá trị tối ưu fmin = f(x1) = 6. VD12: Giải bài toán quy hoạch tuyến tính f = x1 +6x3  5x4  min x1 + 2x3 + 3x4 = 5 3x2  x3 + 2x4 = 8 xj  0, j=1,2,3,4 16  Bài toán quy hoạch tuyến tính 1.5 Giải bài toán quy hoạch tuyến tính hai biến bằng phương pháp hình học Ta gọi vectơ Giải: Biểu diễn lên mặt phẳng toạ độ Oxy các đường thẳng: x + y = 6, 2x + 3y = 6, x  y = 2, x = 0 và y = 0. Xác định miền ràng buộc D là giao của các miền thoả mãn các điều kiện ràng buộc. VD13: Giải bài toán quy hoạch tuyến tính f = 4x +3y  min x + y  6 2x + 3y  6 x  y  2 x  0, y  0 17  Bài toán quy hoạch tuyến tính Ta gọi vectơ Người ta chứng minh được rằng f đạt giá trị nhỏ nhất tại một trong các đỉnh của nó. Tại E: f = 6 Tại O: f = 18 Tại P: f = 10 Tại Q: f = 8.4 Từ đó ta có fmin = 10 khi x = 4, y = 2. Dịch chuyển các đường mức 4x + 3y = f bằng cách tịnh tiến song song theo vectơ pháp tuyến (4, 3) theo mức f của đường thẳng 4x + 3y = 0. 18  Bài toán quy hoạch tuyến tính Ta gọi vectơ VD14: Giải bài toán quy hoạch tuyến tính f = 6x + 10y  min x + y  20 x + 2y  30 x  0, y  0