對偶規劃

對偶規劃最初是由馮·諾伊曼（vonNeu-mann，J.）於1947年提出來的，以後庫恩（Kuhn，H.W.）和塔克爾(Tucker，A.W.）證明了對偶定理。哥德曼（Goldman，A.J.）和塔克爾於1956年比較系統地敍述了對偶規劃的理論。

對偶線性規劃的經濟背景是：若原問題是利用有限資源安排最優生產方案，以獲得最大總產值的線性規劃問題，則它的對偶問題就是在相同資源的條件下，正確估計資源的使用價值，以達到支付最少費用的線性規劃問題。簡言之，若原問題為求解資源的最優配置問題，則對偶問題就是求解估價資源的使用價值問題。 ^[2] 

假定原問題是最大化問題，即線性規劃問題（LP），它的標準形式：

其對偶問題（DLP）如下式所示： ^[3] 

用矩陣形式表示，對稱形式的線性規劃問題的原問題為：

其對偶問題為：

或寫作

上述都是一對對稱形式的對偶線性規劃，在原線性規劃問題與對偶線性規劃問題之間有着整齊的對稱性，其特徵是：

1.一個問題求極大max，對應另一個問題求極小min。

2.求極大問題中的約束條件為“≤”，求極小問題中的約束條件為“≥”。

3.原問題中有個變量，對偶問題中就有個約束條件。原問題中有m個約束條件，對偶問題中就有m個變量（稱為對偶變量）。

4.原問題的目標函數中變量的係數就是對偶問題約束條件的常數項。原問題中約束條件的常數項就是對偶問題目標函數中變量的係數。

5.兩個互為對偶問題的約束條件的係數矩陣互為轉置矩陣。

6.原問題與對偶問題中的變量均有非負約束。 ^[4] 

因為並非所有線性規劃問題具有對稱形式，故對下面討論更加一般形式下線性規劃問題如何寫出其對偶問題。無論是堆成或非堆成的線性規劃問題在寫出其對偶問題時，對於A、B、C和目標函數的對應關係都適用，區別的只是約束條件的形式與其對應變量的取值。下面將對稱或不對稱線性規劃原問題同對偶問題的轉換時的對應關係，統一歸納為下表所示形式。

對稱定理：對偶問題的對偶問題是原問題。

弱對偶性定理：X_o、Y_o若分別是標準形式的原問題及對偶問題的可行解，則有CX_o≤Y_ob。

如果X_o是原問題的可行解，Y_o是對偶問題的可行解，並且CX_o=Y_ob，那麼X_o和Y_o分別為原問題和對偶問題的最優解。

對偶定理（強對偶性）：若原問題及其對偶問題均具有可行解，則兩者均具有最優解，且它們最優解的目標函數值相等。

設X_o，Y_o分別是原問題和對偶問題的可行解，U_o為原問題的鬆弛變量的值、V_o為對偶問題剩餘變量的值。X_o, Y_o分別是原問題和對偶問題最優解的充分必要條件是 Y_oU_o = 0，V_oX_o= 0。 ^[5]