Bài toán đối ngẫu và ứng dụng

BÀI 3 1. Cách thiết lập bài toán đối ngẫu: * Nguyên tắc thiết lập bài toán đối ngẫu: 1) Nếu f(x) min (max) thì max (min) 2) Số ràng buộc chính trong bài toán này bằng số biến số trong bài toán kia 3) Hệ số trong hàm mục tiêu của bài toán này là hệ số tự do của hệ ràng buộc trong bài toán kia. 4) Ma trận điều kiện của hai bài toán là chuyển vị của nhau. 5) Ràng buộc về biến của bài toán này tương ứng với ràng buộc về dấu của bài toán kia. 6) Biến không có ràng buộc về dấu trong bài toán này thì ràng buộc tương ứng trong bài toán kia có dấu “=” 7) Ràng buộc bất đẳng thức trong hệ ràng buộc chính của bài toán min cùng chiều với ràng buộc dấu trong bài toán max 8) Ràng buộc bất đẳng thức trong hệ ràng buộc chính của bài toán max ngược chiều với ràng buộc dấu trong bài toán min. Ví dụ 1: viết bài toán đối ngẫu của bài toán QHTT sau: 2) Cặp ràng buộc đối ngẫu: Cặp ràng buộc đối ngẫu là cặp ràng buộc bất đẳng thức (kể cả ràng buộc dấu) trong hai bài toán cùng tương ứng với một cặp chỉ số. Ví dụ: trong ví dụ 1 ta có cặp ràng buộc đối ngẫu là : (1), (9); (2), (10); (3), (6); (4), (7); (5), (8) Ví dụ 2: viết bài toán đỗi ngẫu và tìm các cặp ràng buộc đối ngẫu của bài toán sau: Ý nghĩa kinh tế của bài toán đối ngẫu: Xét bài toán lập kế hoạch sản xuất: Ta giả thiết tình huống có người muốn mua toàn bộ số lượng các yếu tố sản xuất của xí nghiệp. Khi đó giá bán nên đặt ra là bao nhiêu? Gọi yi (i = 1,2,3) là giá bán một đơn vị yếu tố sản xuất loại i. (yi 0) Ta có số tiền thu được khi bán các yếu tố sản xuất dùng để sản xuất ra một đơn vị sản phẩm Loại 1: Loại 2: Đối với người bán: Đối với người mua: Mô hình: 3) Các định lý đối ngẫu: Định lý 1: Cho hai bài toán đối ngẫu (P) và . Khi đó xảy ra ba trường hợp: Cả hai đều không có PA. Cả hai đều có PA. Khi đó cả hai đều giải được. Cặp x* và y* là tối ưu  f(x*) = g(y*) Một bài toán có PA, bài toán còn lại không có PA. Khi đó hàm mục tiêu của bài toán có PA không bị chặn trên tập các PA, do đó bài toán này không có PATƯ. * Hệ quả : Nếu một trong hai bài toán có PATƯ thì bài toán kia cũng có PATƯ. 3) Các định lý đối ngẫu: Định lý 2 : (độ lệch bù yếu) Cho x và y là hai phương án của hai bài toán. Khi đó x và y là hai phương án tối ưu của hai bài toán  nếu trong cặp ràng buộc đối ngẫu ràng buộc của bài toán này là lỏng thì ràng buộc đối ngẫu của nó là chặt. Hệ quả: Nếu một cặp ràng buộc là lỏng đối với PATƯ của bài toán này thì ràng buộc đối ngẫu của nó phải là chặt với PATƯ của bài toán kia. 4) Ứng dụng của bài toán đối ngẫu: Ví dụ 3: Cho bài toán QHTT: a) Hãy giải bài toán bằng phương pháp đơn hình b) Viết bài toán đối ngẫu c) Tìm phương án tối ưu của bài toán đối ngẫu a) Đáp số: x* = (32,0,30,0,0) f(x*) = 184 b) c) x* = (32,0,30,0,0) x1 = 32 0: y1 = 2 x3 = 30 0: y2 = 4 Ta có ràng buộc (*) và (**) là cặp ràng buộc đối ngẫu mà x* thỏa lỏng ở ràng buộc (*) => y* thỏa chặt ở ràng buộc (**) => y3 = 0 Vậy y* = (2,4,0) Ví dụ 4: a) Giải bài toán ở ví dụ 2 bằng phương pháp đơn hình b) Viết bài toán đối ngẫu và các cặp ràng buộc đối ngẫu. c) Tìm PATƯ của bài toán đối ngẫu. Giải: a) Đáp số: x* = (0,4,0,8) fmax = f(x*) = 128 b) Các cặp ràng buộc đối ngẫu: (1),(11); (2),(12); (3),(7); (4),(8); (5),(9); (6),(10) c) Vậy: 5) Một số dạng bài toán cơ bản: Bài toán 1: Nếu x* là PATƯ của bài toán (P). Tìm toàn bộ PATƯ của bài toán . Phương pháp giải: Sử dụng định lý độ lệch bù yếu. Bài toán 2: Tìm PATƯ của bài toán (P). Phương pháp giải: Giải bài toán đối ngẫu sau đó sử dụng định lý độ lệch bù yếu tìm PATƯ của bài toán (P). Ví dụ: Giải bài toán QHTT sau: Giải: Chuyển sang giải bài toán đối ngẫu: Ta có: Bài toán 3: Cho bất kỳ x*. Hỏi x* có phải là PATƯ. Phương pháp giải: Từ x* sử dụng định lý độ lệch bù yếu ta giải tìm y* Nếu có nghiệm y* và f(x*) = thì x* là PATƯ Nếu không có nghiệm y* thì x* không là PATƯ. Giải bài toán QHTT sau đây bằng cách giải bài toán đối ngẫu và dùng định lý độ lệch bù yếu: Đáp số: Giải bài toán QHTT sau đây bằng phương pháp đơn hình. Viết bài toán đối ngẫu và tìm PATƯ của bài toán đối ngẫu bằng cách sử dụng định lý độ lệch bù yếu. Đs: