強對偶性

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

基本介紹

• 中文名：強對偶性
• 外文名：strong duality property
• 所屬學科：數學
• 所屬問題：運籌學(線性規劃的對偶理論)
• 相關概念：線性規劃，最優解，目標函式等

強對偶性定理

巳知原線性規劃 及其對偶線性規劃 ，下面給出 之間關係的強對偶性定理，總假設 的標準型分別為 。

若有最優解，則亦有最優解，而且的最優解對應的目標函式值相等，即

定理證明

證明： 把 分別用矩陣表示。

設是用單純形法求出的的最優解，它對應的基為，而且必有全體檢驗數。

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

其中為鬆弛變數構成的向量，不失一般性設，相應地，從而

由此可見

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

中各變數的檢驗數均由表示；

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

設，由(6)知必有，因為

所以

由(5)知

把代入得

從而有

由此可見是的可行解，又因為

即

所以是的最優解，而且的最優目標函式值等於的最優目標函式值。證畢。

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

線性規劃的對偶理論

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

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

(2)弱對偶性。若是原始問題的可行解，是對偶問題的可行解，則有。

(3)最優性。若是原始問題的一個可行解，是對偶問題的一個可行解，且，那么是原始問題的一個最優解。

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

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

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

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

原始問題	對偶問題
有最優解	有最優解
有可行解，無有界最優解	無可行解
無可行解	有可行解，無有界最優解
無可行解	無可行解