Các định lý cơ bản về cặp bài toán đối ngẫu

§2 Các định lý cơ bản về cặp bài toán đối ngẫu 1. Mối quan hệ giữa cặp bài toán đối ngẫu 2. Ứng dụng của bài toán đối ngẫu: 2. 1. Tìm PATƯ của bài toán đối ngẫu 2. 2. Chứng tỏ tính tối ưu của một phương án 2. 3. Giải bài toán có dạng đặc biệt. Mối quan hệ giữa cặp bài toán đối ngẫu Bài toán đối ngẫu: Mối quan hệ giữa cặp bài toán đối ngẫu Mối quan hệ giữa hai bài toán được thể hiện trong các định lý sau: Định lý 1: Đối với cặp bài toán đối ngẫu bao giờ cũng chỉ xẩy ra một trong 3 trường hợp 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, lúc đó cả hai bài toán đều có PATƯ và giá trị hàm mục tiêu của chúng bằng nhau - Một trong 2 bài toán không có phương án, bài toán kia có phương án, khi ấy bài toán có phương án sẽ không có PATƯ. Mối quan hệ giữa cặp bài toán đối ngẫu Hệ quả 1: Nếu một trong 2 bài toán đối ngẫu có PATƯ thì bài toán kia cũng có PATƯ Mối quan hệ giữa cặp bài toán đối ngẫu Hệ quả 2: x0, y0 là hai phương án của bài toán (I), (I’), khi đó x0, y0 là PATƯ khi và chỉ khi f(x0) = g(y0) Chứng minh: Điều kiện cần: Được suy từ định lý trên Điều kiện đủ: Gọi x’ là phương án bất kì của bài toán (I), khi đó ta có: Mối quan hệ giữa cặp bài toán đối ngẫu Hay x0 là PATƯ. Mặt khác do f(x0) = g(y0) nên theo định lý trên y0 cũng là PATƯ. Định lý 2: (Tiêu chuẩn tối ưu) Hai phương án của cặp bài toán đối ngẫu là PATƯ khi và chỉ khi với mỗi cặp ràng buộc đối ngẫu nếu một ràng buộc thõa mãn với dấu bất đẳng thức thực sự thì ràng buộc kia thõa mãn với dấu bằng. Chứng minh: Mối quan hệ giữa cặp bài toán đối ngẫu x0 = (x01, x02 , ... , x0n) và y0 = (y01, y02, ... , y0m) lần lượt là PATƯ cua bài toán (I) và (I’) Xét đẳng thức: Mối quan hệ giữa cặp bài toán đối ngẫu Do x0, y0 là PATƯ khi và chỉ khi: Điều kiện cần: x0, y0 là PATƯ nên: Mặt khác ta có: Vì vậy: - Nếu x0j > 0 thì: - Nếu thì x0j = 0 Mối quan hệ giữa cặp bài toán đối ngẫu Điều kiện đủ: Hiển nhiên được suy ra từ bất đẳng thức trên Định lý 3: (Tiêu chuẩn tối ưu phát biểu cho cặp bài toán đối ngẫu tổng quát) Điều kiện cần và đủ để 2 phương án x0, y0 của cặp bài toán đối ngẫu tối ưu là trong mỗi cặp ràng buộc đối ngẫu nếu ràng buộc này thõa mãn với dấu bất đẳng thức thực sự thì ràng buộc kia thõa mãn với dấu bằng. Ứng dụng của bài toán đối ngẫu 2.1 Tìm PATƯ của bài toán đối ngẫu PP 1: Nhờ tiêu chuẩn tối ưu nên khi ta biết được PATƯ của một trong cặp bài toán đối ngẫu thì ta dễ dàng tìm được PATƯ của bài toán còn lại. Ví dụ 1: Cho bài toán QHTT sau: Cho biết bài toán trên có PATƯ là x0 = (7, 0, -9). Hãy lập và giải bài toán đối ngẫu của bài toán trên. Tìm PATƯ của bài toán đối ngẫu Giải: Bài toán đối ngẫu là: f(x) = 15y1 + 8y2 + 10y3  Max Các ràng buộc: -3y1 + 2y2 + 4y3  3 2y1 - y2 + 2y3  4 -4y1 - 5y2 + 2y3  1 Trong đó: y1  0, y2  0, y3  0 Do bài toán đối ngẫu có phương án tối ưu là x0 = (7, 0, -9) nên theo định lí độ lệch bù yếu ta có: -3y1 + 2y2 + 4y3 = 3 (1) -4y1 -5y2 + 2y3 = 1 (2) Tìm PATƯ của bài toán đối ngẫu Mặt khác khi thay phương án x0 vào các ràng buộc của bài toán gốc ta thấy ràng buộc thứ ba thõa mãn không chặt nên: y2 = 0 (3) Từ hệ phương trình (1), (2), (3) ta dễ dàng suy ra nghiệm là y0 = (1/5, 0, 9/10) ta thấy nghiệm này thõa mãn hai ràng buộc còn lại của bài toán đối ngẫu nên nó là PATƯ của bài toán đối ngẫu. Vậy bài toán đối ngẫu có phương án tối ưu là: y0 = (1/5, 0, 9/10) và g(y0) = 12. Tìm PATƯ của bài toán đối ngẫu Phương pháp 2: (Sử dụng bảng đơn hình) Để vận dụng PP này ta dùng thuật toán đơn hình để giải (I), khi đó PATƯ của bài toán (I’) sẽ là: yi = cj + j i = 1, 2, …. , m cj, j là hệ số tương ứng với ẩn cơ sở xj của phương trình thứ i trong bảng đơn hình đầu tiên. j là hệ số trong bảng đơn hình cuối cùng ứng với PATƯ. Lưu ý: Trong bảng đơn hình đối với bài toán (I) cần phải đưa vào cột đơn hình ứng với ẩn giả Tìm PATƯ của bài toán đối ngẫu Ví dụ: Cho bài toán QHTT : f(x) = x1 + 2x2 + 3x3 + 3x4  Max Các ràng buộc: 2x1 + x2 + x3 + 2x4  20 x1 + 2x2 + 3x3 + 4x4 = 18 2x1 + x2 + 2x3 + x4  16 Trong đó: x1  0, x2  0, x3  0, x4  0 a. Hãy giải bài toán. b. Hãy viết bài toán đối ngẫu và chỉ ra PATƯ của bài toán đối ngẫu. Tìm PATƯ của bài toán đối ngẫu Bài toán ở dạng chuẩn: f(x) = x1 + 2x2 + 3x3 + 3x4 – Mx7 – Mx8  Max Các ràng buộc: 2x1 + x2 + x3 + 2x4 + x5 = 20 x1 + 2x2 + 3x3 + 4x4 + x7 = 18 2x1 + x2 + 2x3 + x4 - x6 + x8 = 16 Trong đó: x5, x6 là biến phụ; x7, x8 là biến giả x1  0, x2  0, x3  0, x4  0, x5  0, x6  0; x7  0; x8  0 Tìm PATƯ của bài toán đối ngẫu Tìm PATƯ của bài toán đối ngẫu Tìm PATƯ của bài toán đối ngẫu PATƯ của bài toán mở rộng là : (3,0,5,0,9,0,0,0) Giá trị hàm mục tiêu đạt được là : f(x) = 18 PATƯ của bài toán xuất phát: (3,0,5,0) fmax = 18 Chứng tỏ tính tối ưu của một phương án Vấn đề: Không giải bài toán QHTT xem xét phương án x0 có là PATƯ hay không? Phương pháp: Lập bài toán đối ngẫu, giả sử x0 là PATƯ sau đó dùng tiêu chuẩn tối ưu để tìm phương án tương ứng với x0, nếu tồn tại phương án tương ứng thì x0 là PATƯ còn không tồn tại phương án chứng tỏ x0 không là PATƯ. Chứng tỏ tính tối ưu của một phương án Ví dụ: Cho bài toán QHTT f(x) = - 8x1 + 6x2 + 4x3 + 5x4  min Ràng buộc: x1 – 2x3 + x4  7 -2x1 + x2 – x3 + 3x4 = -4 3x1 – x2 + 2x3 – 6x4  5 x1  0; x2  0; x4  0 a. Viết bài toán đối ngẫu của bài toán trên b. Chứng tỏ x* = (3, 0, -2, 0) là phương án. x* có là PATƯ hay không? Tìm tập PATƯ của bài toán đối ngẫu? c. Tìm tập PATƯ của bài toán xuất phát? Giải bài toán có dạng đặc biệt Ví dụ: Giải bài toán QHTT f(x) = 12x1 + 27x2 + 6x3  min Ràng buộc: 2x1 + 3x2 + 2x3  12 x1 + 3x2 + x3  6 6x1 + 9x2 + 2x3  24 x1 0; x2  0; x3  0; Giải bài toán có dạng đặc biệt Giải: Bài toán đối ngẫu f(y) = 12y1 + 6y2 + 24y3  MAX Các ràng buộc: 2y1 + y2 + 6y3  12 3y1 + 3y2 + 9y3  27 2y1 + y2 + 2y3  6 Trong đó: y1  0, y2  0, y3  0 Giải bài toán có dạng đặc biệt Giải bài toán có dạng đặc biệt Giải bài toán có dạng đặc biệt PATƯ của bài toán đối ngẫu là: (3/2, 0, 3/2) Giá trị hàm mục tiêu đạt được là: gmax = 54 Bài tập về bài toán đối ngẫu Bài 1: Cho bài toán QHTT: f(x) = 2x1 – x2 + x3 - 5x4 + 3x5  min 2x1 + 3x2 – x4 + 2x5  -12 -x1 – 3x3 + x4 – x5 = 1 4x1 + 2x2 + x3 + 3x5  20 x2  0; x3  0; x4  0 Chứng tỏ rằng vectơ x0 = (4, 2, 0, 5, 0) không phải là một PATƯ của bài toán. Bài tập về bài toán đối ngẫu Bài 2: Cho bài toán QHTT: f(x) = -5x1 + 2x2 + 2x3 - 4x4  min x1 + 2x3+ x4 = 14 4x2 – 14x3 + x4  36 2x2 - 3x3+ x4  12 3x2 - 5x3+ 2x4  23 x1  0; x2  0; x3  0; x4  0 Chứng tỏ rằng x0 = (9, 7/2, 0, 5) là một PATƯ. Tìm tập tất cả các PATƯ? Bài tập về bài toán đối ngẫu Bài 3: Cho bài toán QHTT: f(x) = x1 + mx2 + 3x3  min 2x1 + x2 – x3 = 4 (m – 2)x1 + 2x2 + x3  5 2x1 - x2 + 3x3 = 8 x1  0; x2  0; x3  0 a. Hãy giải bài toán khi m = 1 b. Tìm các giá trị của m để x0 = (5/2, 0, 1) là PATƯ của bài toán đó. Bài tập về bài toán đối ngẫu Bài toán ở dạng chuẩn: f(x) = x1 + x2 + 3x3 + Mx5 + Mx6  min Các ràng buộc: 2x1 + x2 - x3 + x5= 4 - x1 + 2x2 + x3 + x4 = 5 2x1 - x2 + 3x3 + x6 = 8 Trong đó: x4 là biến phụ x5, x6 là biến giả xj  0, j = 1,2, 3, 4, 5, 6 Bài tập về bài toán đối ngẫu Bài tập về bài toán đối ngẫu Bài tập về bài toán đối ngẫu Bài tập về bài toán đối ngẫu Bài 4: Cho bài toán QHTT: f(x) = -2x1 + ax2 + x3 - 3x4 + bx5  min x1 - 2x2 + 2x3 – 6x4 - x5 = -1 x2 – x3 + 3x4 – x5 = 1 -x1 - x2 + 2x3 - 5x4 + 2x5 = -2 xj  0 j= 1, 2, 3, 4, 5 a. Chứng tỏ vectơ x0 = (1, 0, 2, 1, 0) là một phương án cơ bản không suy biến của bài toán b. Hãy xác định a, b để x0 là PATƯ của bài toán