Quy hoạch tuyến tính

Hàm mục tiêu là tuyến tính nên các tập mức của nó là các siêu phẳng song song; khi trượt một siêu phẳng như vậy qua một khối đa diện lồi, điểm cuối cùng nó chạm vào trước khi rời khỏi miền luôn là một đỉnh, không bao giờ là một điểm trong phần trong của một mặt, vì các điểm trong luôn có thể được đẩy xa hơn theo hướng cải thiện hàm mục tiêu.

Vì $P$ là một khối đa diện bị chặn được xác định bởi hữu hạn bất đẳng thức tuyến tính, nó có hữu hạn đỉnh $v_1,\ldots,v_k$, và một sự kiện cổ điển về khối đa diện (định lý Minkowski) khẳng định rằng mọi điểm của $P$ đều là tổ hợp lồi của các đỉnh này: $x=\sum_{i=1}^{k}\lambda_i v_i$, trong đó $\lambda_i\ge 0$ và $\sum_i \lambda_i=1$.

Vì hàm mục tiêu $c^{\mathsf{T}}x$ tuyến tính, tính giá trị của nó trên một tổ hợp lồi như vậy cho $c^{\mathsf{T}}x=\sum_i \lambda_i\left(c^{\mathsf{T}}v_i\right)\le \left(\max_i c^{\mathsf{T}}v_i\right)\sum_i\lambda_i=\max_i c^{\mathsf{T}}v_i$, vì mỗi $\lambda_i\ge 0$ và chúng có tổng bằng $1$.

Điều này cho thấy mọi $x$ khả thi đều có giá trị mục tiêu không vượt quá giá trị đỉnh tốt nhất $\max_i c^{\mathsf{T}}v_i$. Nhưng đỉnh tốt nhất đó, gọi là $v_{i^*}$, tự nó là một điểm khả thi của $P$, nên nó thực sự đạt được cận trên này: $c^{\mathsf{T}}v_{i^*}=\max_{x\in P} c^{\mathsf{T}}x$. Do đó giá trị tối ưu của bài toán quy hoạch tuyến tính đạt được tại đỉnh $v_{i^*}$, chứng minh khẳng định.

Đối ngẫu nói rằng bài toán gốc tối đa hóa và bài toán đối ngẫu tối thiểu hóa là hai cách nhìn về cùng một con số: các biến đối ngẫu $y$ đóng vai trò như giá của các nguồn lực, và đối ngẫu yếu nói rằng không phương án sản xuất khả thi nào có thể kiếm được nhiều hơn giá trị của các nguồn lực nó dùng theo bất kỳ cách định giá hợp lệ nào, còn đối ngẫu mạnh nói rằng tại điểm tối ưu, phương án sản xuất tốt nhất và cách định giá hợp lệ rẻ nhất trùng khớp chính xác với nhau.

(Đối ngẫu yếu.) Cho $x$ là điểm khả thi bất kỳ của bài toán gốc ($Ax\le b$, $x\ge 0$) và $y$ là điểm khả thi bất kỳ của bài toán đối ngẫu ($A^{\mathsf{T}}y\ge c$, $y\ge 0$). Vì $x\ge 0$ và $A^{\mathsf{T}}y\ge c$, nhân bất đẳng thức với vectơ không âm $x$ vẫn giữ nguyên chiều: $c^{\mathsf{T}}x\le \left(A^{\mathsf{T}}y\right)^{\mathsf{T}}x=y^{\mathsf{T}}Ax$. Vì $y\ge 0$ và $Ax\le b$, lập luận tương tự cho $y^{\mathsf{T}}Ax\le y^{\mathsf{T}}b=b^{\mathsf{T}}y$. Kết hợp hai bất đẳng thức, $c^{\mathsf{T}}x\le b^{\mathsf{T}}y$ đúng với mọi cặp khả thi, đó chính là đối ngẫu yếu.

(Đối ngẫu mạnh.) Chạy phương pháp đơn hình trên bài toán gốc cho tới khi nó dừng tại một nghiệm cơ sở khả thi tối ưu $x^{*}$ với ma trận cơ sở tối ưu $B$, sao cho $x^{*}_B=B^{-1}b$ và chi phí rút gọn của mọi biến phi cơ sở đều không âm — điều kiện dừng này tương đương với việc định nghĩa $y^{*\mathsf{T}}=c_B^{\mathsf{T}}B^{-1}$, và có thể kiểm tra rằng nó thỏa $A^{\mathsf{T}}y^{*}\ge c$ và $y^{*}\ge 0$, tức $y^{*}$ khả thi cho bài toán đối ngẫu.

Thay vào, giá trị tối ưu của bài toán gốc là $c^{\mathsf{T}}x^{*}=c_B^{\mathsf{T}}x^{*}_B=c_B^{\mathsf{T}}B^{-1}b=y^{*\mathsf{T}}b=b^{\mathsf{T}}y^{*}$. Kết hợp với đối ngẫu yếu (luôn có $c^{\mathsf{T}}x^{*}\le b^{\mathsf{T}}y^{*}$), đẳng thức ở đây buộc $y^{*}$ cũng phải là nghiệm tối ưu của bài toán đối ngẫu, do đó $c^{\mathsf{T}}x^{*}=b^{\mathsf{T}}y^{*}$, chứng minh đối ngẫu mạnh.