Đối ngẫu của bài toán quy hoạch tuyến tính

(Đố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.