Giáo trình tối ưu hóa - Chương 3

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 1.1. 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...
Nội dung trích xuất từ tài liệu:
Giáo trình tối ưu hóa - Chương 3 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 1.1. 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 a11x1 + a12x2 + ... + a1nxn ≤ b1 a21x1 + a22x2 + ... + a2nxn ≤ b2 ... am1x1 + 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 + .... + bmym 44 với các điều kiện ràng buộc: a11y1 + a21y2 + ... + am1ym ≥ c1 a12y1 + a22y2 + ... + am2ym ≥ c2 ... a1ny1 + a2ny2 + ... + amnym ≥ cn y1, y2, ..., ym ≥ 0. Các biến y1, 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. 1.2. Ý 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 x2 + 2x3 ≤ 40 2x1 + x1 + 3x2 + 2x3 ≤ 80 x1, 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 và 80 (đơn vị). Hãy xác định phương án sản xuất đạt lợi nhuận lớn nhất, biết lợi nhuận / đơn vị sản phẩm bán ra là 2, 4 và 3 (đơn vị tiền tệ) cho các sản phẩm loại I, II và III. Giả sử có một khách hàng muốn mua lại các đơn vị nguyên liệu loại A, B và C. Bài toán đặt ra là cần định giá các đơn vị nguyên liệu. Rõ ràng rằng giá các nguyên liệu được quy định bởi giá trị của sản phẩm mà chúng tạo nên. Nếu các sản phẩm này mang lại lợi nhuận lớn trên thị trường thì giá ước định của các nguyên liệu này phải cao, còn nếu trái lại thì giá ước định của chúng là thấp. Mặt khác, lợi nhuận của các sản phẩm thu được trên thị trường lại phụ thuộc vào nhiều yếu tố như: giá cả các sản phẩm được bán trên thị trường (đã được thị trường chấp nhận), lượng dự trữ nguyên liệu hiện có, hệ số chi phí sản xuất … Như vậy, giá ước định của các nguyên liệu A, B và C phụ thuộc vào: – Hệ số hàm mục tiêu của bài toán gốc: c1 = 8, c2 = 4 và c3 = 63. – Ma trận ràng buộc các hệ số chi phí sản xuất: 45 ⎡3 4 2 ⎤ A = ⎢2 1 2 ⎥ . ⎢ ⎥ ⎢1 3 2⎥ ⎣ ⎦ – Hệ số dự trữ các loại nguyên liệu: ⎡60 ⎤ b = ⎢40 ⎥ . ⎢⎥ ⎢80 ⎥ ⎣⎦ Tuy nhiên, mối phụ thuộc đó không dễ dàng xác định được. Để giải quyết vấn đề này hoàn toàn có thể dựa vào việc phân tích bài toán đối ngẫu. Gọi y1 là giá ước định một đơn vị nguyên liệu loại A, y2 là giá ước định một đơn vị nguyên liệu loại B, còn y3 là giá ước định một đơn vị nguyên liệu loại C (y1, y2, y3 ≥ 0). Chúng ta hãy đi xét bài toán đối ngẫu: Min u = 60y1 + 40y2 + 80y3 với các điều kiện ràng buộc 3y1 + 2y2 + y3 ≥ 2 4y1 + y2 + 3y3 ≥ 4 2y1 + 2y2 + 2y3 ≥ 3 y1, y2, y3 ≥ 0. Thật vậy, u = 60y1 + 40y2 + 80y3 chính là tổng chi phí phải bỏ ra nếu người khách hàng muốn mua 60 đơn vị nguyên liệu loại A, 40 đơn vị nguyên liệu loại B và 80 đơn vị nguyên liệu loại C. Tất nhiên người khách hàng muốn tổng chi phí u càng bé càng tốt. Xét ràng buộc thứ nhất. Vế trái là 3y1 + 2y2 + y3 chính là số tiền khách hàng phải bỏ ra để mua 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. Đây ...