Bài toán đối ngẫu

Trong quy hoạch tuyến tính, bài toán gốc và bài toán đối ngẫu bổ sung cho nhau. Đáp số của bài này đồng thời là đáp số của bài kia.

Cơ bản

Các bài toán quy hoạch tuyến tính là những bài toán tối ưu hóa trong đó hàm mục tiêu và các điều kiện chế ước đều là tuyến tính.

Kiểu bài toán trong trường hợp tuyến tính

Trong bài toán gốc, hàm mục tiêu là một kết hợp tuyến tính của n biến số. Có m điều kiện chế ước, mỗi điều kiện đặt ra một mức giới hạn trên cho kết hợp tuyến tính của n biến số. Mục tiêu là tối đa hóa giá trị của hàm mục tiêu với những điều kiện chế ước đặt ra. Một đáp số là một vector (một danh sách) của n giá trị cho phép đạt giá trị tối đa của hàm mục tiêu.

Trong bài toán đối ngẫu, hàm mục tiêu là một kết hợp tuyến tính của m giá trị vốn là m điều kiện chế ước trong bài toán gốc. Có n điều kiện chế ước đối ngẫu, mỗi cái đặt ra một giới hạn dưới cho một kết hợp tuyến tính của m biến số đối ngẫu.

Nguyên lý đối ngẫu

Trong lý thuyết tối ưu hóa, nguyên lý đối ngẫu phát biểu rằng các bài toán tối ưu có thể xem từ cả hai phía, phía bài toán gốc và phía bài toán đối ngẫu.

Định lý đối ngẫu

Định lý đối ngẫu phát biểu rằng trong trường hợp tuyến tính sẽ có một đồng trị tính toán trực tiếp giữa đáp số của bài toán gốc và đáp số của bài toán đối ngẫu.

Ví dụ về đồng trị này và cách tính được giới thiệu tại [1] Lưu trữ 2007-03-18 tại Wayback Machine.

Trường hợp phi tuyến

Trong trường hợp quy hoạch phi tuyến tính, các điều kiện chế ước không nhất thiết phải tuyến tính. Tuy nhiên, nhiều nguyên lý chung vẫn được áp dụng.

Để đảm bảo rằng một bài toán phi tuyến tính có một giá trị cực đại toàn cục duy nhất, thông thường người ta sắp xếp theo một tiêu chí đơn giản hóa chẳng hạn như độ lồi. Nếu độ cong của các điều kiện chế ước và của hàm mục tiêu được xem như miền thực hiện (feasible region) luôn lồi, thì sẽ có giá trị tối ưu toàn cục duy nhất.

Đây chính là ý nghĩa của điều kiện Karush-Kuhn-Tucker. Họ cho trước những điều kiện đủ dựa trên độ lồi để xác định bài toán quy hoạch phi tuyến tính có giá trị tối ưu toàn cục duy nhất. Có các điều kiện cần để cho có thể xác định hướng cho đáp án tối ưu. Một đáp án tối ưu có thể là một giá trị tối ưu cục bộ, chứ không nhất thiết phải là một giá trị tối ưu toàn cục.

Tham khảo

• Dantzig, G.B., 1963. Linear Programming and Extensions, Princeton University Press, Princeton, NJ.
• Gass, Saul I., IFORS' Operational Research Hall of Fame: Albert William Tucker, International Transactions in Operational Research, Volume 11 Issue 2, Page 239 - tháng 3 năm 2004, doi:10.1111/j.1475-3995.2004.00455.x. [2]
• Gass, Saul I., IFORS' Operational Research Hall of Fame: George B. Dantzig, International Transactions in Operational Research, Volume 10 Issue 2 Page 191 - tháng 3 năm 2003, doi:10.1111/1475-3995.00403. [3]
• Nering, E.D and Tucker, A.W., 1993, Linear Programming and Related Problems, Academic Press, Boston, MA.