Bài toán đối ngẫu và một số ứng dụng 1. Phát biểu bài toán đối ngẫu . Phát biểu bài toán Tương ứng với mỗi BTQHTT (còn gọi là bài toán gốc) có một bài toán đối ngẫu. Bài toán đối ngẫu của BTQHTT cũng là một BTQHTT. Như vậy, bài toán gốc và bài toán đối ngẫu của nó lập thành một cặp BTQHTT, tính chất của bài toán này có thể được khảo sát thông qua bài toán kia. Nhiều quy trình tính toán hay phân tích được hoàn thiện khi xem xét cặp bài toán trên trong mối. | Chương III Bài toán đôi ngẫu và một sô ứng dụng 1. Phát biểu bài toán đôi ngẫu . Phát biểu bài toán Tương ứng với mỗi BTQHTT còn gọi là bài toán gốc có một bài toán đối ngẫu. Bài toán đối ngẫu của BTQHTT cũng là một BTQHTT. Như vậy bài toán gốc và bài toán đối ngẫu của nó lập thành một cặp BTQHTT tính chất của bài toán này có thể được khảo sát thông qua bài toán kia. Nhiều quy trình tính toán hay phân tích được hoàn thiện khi xem xét cặp bài toán trên trong mối liên quan chặt chẽ của chúng mang lại lợi ích trong việc giải quyết các vấn đề phát sinh từ thực tế. Với mục đích tìm hiểu bước đầu chúng ta xét bài toán gốc là bài toán quy hoạch tuyến tính BTQHTT dạng Max với các ràng buộc chỉ có dấu và các biến đều thoả mãn điều kiện không âm. Bài toán gốc Max z c1x1 c2x2 . cnxn với các điều kiện ràng buộc f cijjXj al x2 . Cíjnxn a2X1 a x . a2nXn bi b2 amiXi am2X2 . amnXn bm x1 x2 . xn 0. Lúc đó BTQHTT sau đây được gọi là bài toán đối ngẫu của BTQHTT trên. Bài toán đối ngẫu Min u b1y1 b2y2 . b ym 44 với các điều kiện ràng buộc aiiyi a2jy 2 . am ym C1 ai2yi a22y2 . am2ym C2 aìnyì a2ny2 . amnym cn yi y2 . ym 0. Các biến yb y2 . ym được gọi là các biến đối ngẫu. Trong trường hợp này do bài toán gốc có m ràng buộc nên bài toán đối ngẫu có m biến đối ngẫu. Biến đối ngẫu yi tương ứng với ràng buộc thứ i của bài toán gốc. . Ý nghĩa của bài toán đối ngẫu Ví dụ 1. Xét bài toán gốc Max z 2x1 4x2 3x3 với các ràng buộc 3x1 4x2 2x3 60 2x1 x2 2x3 40 x1 3x2 2x3 80 xb x2 x3 0. Cần tìm các giá trị của các biến quyết định x1 x2 x3 để các ràng buộc được thoả mãn và hàm mục tiêu đạt giá trị lớn nhất. Bài toán này có ý nghĩa kinh tế như sau Giả sử một xí nghiệp sản xuất ba loại sản phẩm I II và III. Để sản xuất ra một đơn vị sản phẩm I cần có 3 đơn vị nguyên liệu loại A 2 đơn vị nguyên liệu loại B và 1 đơn vị nguyên liệu loại C. Các chỉ tiêu đó cho một đơn vị sản phẩm loại II là 4 1 và 3. Còn cho đơn vị sản phẩm loại III là 2 2 và 2. Lượng nguyên liệu dự trữ loại A và B hiện có là 60 40
