Định lýĐã chứng minh

Định lý đối ngẫu mạnh trong quy hoạch tuyến tính

Phát biểu

Xét quy hoạch tuyến tính gốc $\min\ c^\top x$ với ràng buộc $Ax \ge b,\ x \ge 0$ , và bài toán đối ngẫu $\max\ b^\top y$ với ràng buộc $A^\top y \le c,\ y \ge 0$ . Nếu một trong hai bài toán có nghiệm tối ưu thì bài toán kia cũng có, và giá trị tối ưu của chúng bằng nhau: $c^\top x^* = b^\top y^*$ .

Vì sao đúng?

Đối ngẫu yếu luôn đúng: mọi giá trị khả thi của bài toán đối ngẫu là chặn dưới của mọi giá trị khả thi bài toán gốc, giống như giá người mua đề nghị không bao giờ vượt quá giá trị thật của tài nguyên. Đối ngẫu mạnh khẳng định khoảng cách này triệt tiêu đúng tại điểm tối ưu — các biến đối ngẫu đóng vai trò 'giá bóng' công bằng cho từng ràng buộc tài nguyên, sao cho định giá mọi tài nguyên theo giá bóng cho đúng chi phí tối ưu của bài toán gốc, không còn dư thừa.

Phác thảo chứng minh

Chứng minh chuẩn dùng bổ đề Farkas: giả sử bài toán gốc có giá trị tối ưu $z^*$ nhưng miền khả thi của đối ngẫu không đạt tới giá trị đó; khi đó hệ 'khả thi đối ngẫu và $b^\top y > z^*$ ' vô nghiệm, nên theo bổ đề Farkas tồn tại một chứng cứ cho thấy điều này buộc phải có một điểm khả thi gốc với giá trị mục tiêu nhỏ hơn $z^*$ , mâu thuẫn. Tương đương, ta tách tập trên đồ thị của hàm giá trị bài toán gốc khỏi gốc tọa độ bằng một siêu phẳng, vector pháp tuyến của nó chính là nghiệm đối ngẫu tối ưu $y^*$ .

Người phát biểu

nêu năm 1947John von Neumann

Chủ đề chứa định lý này

Quy hoạch tuyến tính Tối ưu lồi

Định lý liên quan

Điều kiện Karush–Kuhn–Tucker Cực tiểu địa phương của hàm lồi là cực tiểu toàn cục

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

George B. Dantzig (1963). Linear Programming and Extensions
John von Neumann, Oskar Morgenstern (1944). Theory of Games and Economic Behavior