設原問題是（記為LP）：

對偶問題是（記為DP）：這里A是m×n矩陣X是n×1列向量，Y是1×m行向量。假設Xs與Ys分別是（LP）與（DP）的松馳變量?！拘再|1】

對稱性對偶問題的對偶是原問題。

【證】設原問題是2.1.3對偶定理它與下列線性規(guī)劃問題是等價的：再寫出它的對偶問題。它與下列線性規(guī)劃問題是等價的即是原問題。

由表2－1知，它的對偶問題是【性質2】

弱對偶性

設X°、Y°分別為（LP）與（DP）的可行解，則

【證】因為X°、Y°是可行解，故有AX°≤b,X°≥0及Y°A≥C，Y°≥0,將不等式AX°≤b

兩邊左乘Y°得Y°AX°≤Y°b再將不等式Y°A≥C

兩邊右乘X°，故

CX°≤Y°AX≤Y°b這一性質說明了兩個線性規(guī)劃互為對偶時，求最大值的線性規(guī)劃的任意目標值都不會大于求最小值的線性規(guī)劃的任一目標值，不能理解為原問題的目標值不超過對偶問題的目標值。得CX°≤Y°AX°由這個性質可得到下面幾個結論：

（1）（LP）的任一可行解的目標值是（DP）的最優(yōu)值下界；（DP）的任一可行解的目標是（LP）的最優(yōu)值的上界；（2）在互為對偶的兩個問題中，若一個問題可行且具有無界解，則另一個問題無可行解；(3）若原問題可行且另一個問題不可行，則原問題具有無界解。

注意上述結論（2）及（3）的條件不能少。一個問題有可行解時，另一個問題可能有可行解（此時具有無界解）也可能無可行解。例如：無可行解，而對偶問題有可行解，由結論（3）知必有無界解?！拘再|3】最優(yōu)準則定理設X°與Y°分別是（LP）與（DP）的可行解，則當X°、Y°是（LP）與（DP）的最優(yōu)解當且僅當CX°=Y°b.【證】若X°、Y°為最優(yōu)解，B為（LP）的最優(yōu)基，則有Y°=CBB－1，并且當CX°=Y°b時，由性質1，對任意可行解有即Y°b是（DP）中任一可行解的目標值的下界，CX°是（LP）中任一可行解的目標值的上界，從而X°、Y°是最優(yōu)解。【性質4】

還可推出另一結論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。【證】設（LP）有最優(yōu)解X°，那么對于最優(yōu)基B必有C－

CBB-1A≤0與－CBB-1≤0，即有Y°A≥C與Y°≥0，這里Y°=CBB-1

，從而Y°是可行解，對目標函數有由性質3知Y°是最優(yōu)解。由性質4還可推出另一結論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。證明：由兩者均有可行解，則根據弱對偶定理可知兩者均有界，因此均有最優(yōu)解。以下對于標準型的線性規(guī)劃問題及其對偶問題證明在最優(yōu)解時，原問題與對偶問題相等。的最優(yōu)值相等。定理5(主對偶定理)

若(LP)和(DP)均可行，那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。設B是其最優(yōu)基，是與之對應的最優(yōu)的基本可行解。令，則對應于基B的檢驗數滿足：

因此成為對偶問題的一個可行解，且此時對應的目標函數值為：

注意到原問題的最優(yōu)目標值為：恰好與對偶問題的目標函數值相等。【性質6】

（LP）的檢驗數的相反數對應于（DP）的一組基本解.

其中第j個決策變量xj的檢驗數的相反數對應于（DP）中第j個松弛變量的解，第i個松弛變量的檢驗數的相反數對應于第i個對偶變量yi的解。反之，（DP）的檢驗數（注意：不乘負號）對應于（LP）的一組基本解。證明略。【例2.1】線性規(guī)劃（1）用單純形法求最優(yōu)解；（2）寫出每步迭代對應對偶問題的基本解；（3）從最優(yōu)表中寫出對偶問題的最優(yōu)解；（4）用公式Y=CBB-1求對偶問題的最優(yōu)解。【解】（1）加入松弛變量x4、x5后，單純形迭代如表2－2所示。表2－2XBx1x2x3x4x5b(1)x4x52*1-102410012→4λj6↑-2100

(2)x1x510-1/21/2*131/2-1/20113→λj01↑-5-30

(3)x1x21001460-11246λj00-11-2-2

最優(yōu)解X=（4，6，0），最優(yōu)值Z=6×4－2×6=12；

（2）設對偶變量為y1、y2,松弛變量為y3、y4、y5,Y=（y1、y2、y3、y4、y5），由性質6得到對偶問題的基本解（y1、y2、y3、y4、y5）

=（－λ4，－λ5，－λ1，－λ2，－λ3），即

表2－2（1）中λ=（6，－2，1，0，0），

則Y（1）=（0，0，-6，2，－1）表2－2（2）中λ=（0，1，－5，－3，0），

則Y（2）=（3，0，0，－1，5）表2－2（3）中λ=（0，0，－11，－2，－2），

則Y（3）=（2，2，0，0，11）（1）因為表2－2（3）為最優(yōu)解，故

Y（3）=（2，2，0，0，11）為對偶問題最優(yōu)解；（1）表2－2（3）中的最優(yōu)基

B-1為表2－2（3）中x4，x5兩列的系數，即CB=（6，－2），因而本節(jié)您學了六個對偶性質；這些性質是研究原問題與對偶問題解的對應關系；表2－3也許對您了解這些性質有幫助。表2－3一個問題max另一個問題min有最優(yōu)解有最優(yōu)解性質4無最優(yōu)解無最優(yōu)解無最優(yōu)解性質4無界解（有可行解）無可行解性質2無可行解無界解（有可行解）應用已知最優(yōu)解通過解方程求最優(yōu)解性質5已知檢驗數檢驗數乘以－1求得基本解性質6影子價格

——

是一個向量，它的分量表示最優(yōu)目標值隨相應資源數量變化的變化率。

若x*,y*

分別為（LP）和（DP）的最優(yōu)解，

那么，cT

x*=bT

y*

。

根據f=bTy*=b1y1*+b2y2*+

+bmym*

可知

f/

bi

=

yi*

yi*

表示

bi

變化1個單位對目標f

產生的影響，稱yi*

為bi的影子價格。

注意：若B

是最優(yōu)基，

y*=(BT)-1

cB

為影子價格向量。2.1.4影子價格

影子價格的經濟含義

(1)影子價格是對現有資源實現最大效益時的一種估價企業(yè)可以根據現有資源的影子價格，對資源的使用有兩種考慮：第一，是否將設備用于外加工或出租，若租費高于某設備的影子價格，可考慮出租該設備，否則不宜出租。第二，是否將投資用于購買設備，以擴大生產能力，若市價低于某設備的影子價格，可考慮買進該設備，否則不宜買進。

（2）影子價格表明資源增加對總效益產生的影響。根據推論“設x0和y0分別為原規(guī)劃（P）和對偶規(guī)劃（D）的可行解，當cx0=bTy0時，x0、y0分別是兩個問題的最優(yōu)解”可知，在最優(yōu)解的情況下，有關系

因此，可以將z*看作是bi,i=1,2，…,m的函數，對bi求偏導數可得到

這說明，如果右端常數增加一個單位，則目標函數值的增量將是

影子價格反映了不同的局部或個體的增量可以獲得不同的整體經濟效益。如果為了擴大生產能力，考慮增加設備，就應該從影子價格高的設備入手。這樣可以用較少的局部努力，獲得較大的整體效益。

需要指出，影子價格不是固定不變的，當約束條件、產品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格的經濟含義（2），是指資源在一定范圍內增加時的情況，當某種資源的增加超過了這個“一定的范圍”時，總利潤的增加量則不是按照影子價格給出的數值線性地增