強對偶性

巳知原線性規劃

及其對偶線性規劃

，下面給出

之間關係的強對偶性定理，總假設

的標準型分別為

^[2]  。

若

有最優解

，則

亦有最優解

，而且

的最優解對應的目標函數值相等，即

證明： 把

分別用矩陣表示。

設

是用單純形法求出的

的最優解，它對應的基為

，而且必有全體檢驗數

。

下面把(1)化為標準形，並求全體檢驗數的表示式。

其中

為鬆弛變量構成的向量，不失一般性設

，相應地

，從而

由此可見

中各變量的檢驗數均為0，

中各變量的檢驗數均由

表示；

中各變量的檢驗數均由

表示，對應於最優基B，全體檢驗數均小於等於0，所以有

設

，由(6)知必有

，因為

所以

由(5)知

把

代入得

從而有

由此可見

是

的可行解，又因為

即

所以

是

的最優解，而且

的最優目標函數值

等於

的最優目標函數值

。證畢 ^[2]  。

本定理的逆命題也成立，證法類同。

線性規劃的對偶理論指研究線性規劃問題和它對應的對偶問題之間存在的變量、係數及數學符號的嚴格對應關係的理論。線性規劃的對偶理論，不僅存在於原始問題與對偶問題的數學模型中，而且存在於整個求解過程中。線性規劃的對偶理論主要有：

(1)對稱性。即對偶問題的對偶是原始問題。

(2)弱對偶性。若

是原始問題的可行解，

是對偶問題的可行解，則有

。 ^[3] 

(3)最優性。若

是原始問題的一個可行解，

是對偶問題的一個可行解，且

，那麼

是原始問題的一個最優解。

(4)無界性。若原始問題(對偶問題)的解無界，那麼對偶問題(原始問題)無可行解。

(5)強對偶性。若原始問題(對偶問題)有一個確定的最優解，那麼對偶問題(原始問題)也有一個確定的最優解，而且這兩個最優解所對應的目標函數值相等，即

。

(6)原始問題(對偶問題)的檢驗數對應於對偶問題(原始問題)的一個解。線性規劃問題的對偶理論，不僅為建立對偶問題的數學模型提供了依據，而且為進一步擴大單純形法求解線性規劃問題的範圍，形成對偶單純形法和進行靈敏度分析奠定了理論基礎 ^[1]  。

互為對偶的兩個線性規劃，它們的解之間的關係如表1所示 ^[2]  。