§3線性規劃的對偶問題的提出每個線性規劃都有另一個線性規劃(對偶問題)與它密切相關，對偶理論揭示了原問題與對偶問題的內在聯系。

0,0768940453643.3032max212121212133???íì￡+￡+￡++=xxxxxxxxtsxxz矩陣形式

0.max3￡=XbAXt.sCXz

實際問題提出：某廠生產甲、乙兩種產品，產量、利潤、設備臺時如下模型所示1可編輯ppt從另一個角度討論這個問題：工廠決定轉讓設備收取租金，如何確定租價？設y1，y2，y3分別為出租單位設備臺時的租價和出讓單位原材料Ａ、Ｂ的附加額。2可編輯ppt

為什么目標取最小？租金定的越高就不會有人來租，問題就沒有實際意義，工廠和接受者都愿意的條件為上述規劃問題的解。其中Y=（y1，y2，y3）3可編輯ppt?íì3=+?íì3￡==0,.0.maxmaxXbIXAXtsXbAXtsCXZCXZs理論上4可編輯ppt因為Y的上界為無限大,所以Ｙ只能有最小值。5可編輯ppt§4線性規劃的對偶理論原問題與對偶問題的數學模型原問題標準形式：對偶問題標準形式：

標準對偶問題6可編輯ppt標準形式下原問題與對偶問題的對應關系7可編輯ppt根據下表寫出原問題與對偶問題的表達式xjyjx1x2by1y2y314020481612c238可編輯ppt

如果原問題約束條件是等式約束9可編輯ppt原問題中的價值向量與對偶問題中的資源向量對換（上下對換）

原問題:X在C和A的右邊;對偶問題:Y在b和A的左邊（左右對換）10可編輯ppt對偶問題的基本性質和基本定理1.對稱性定理：對偶問題的對偶是原問題證明：11可編輯ppt2.弱對偶性定理

若X（0）和Y（0）分別是原問題和對偶問題的可行解，則有CX（0）≤Y（0）b3.若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。由弱對偶定理可證得證明:因為X（0）是原問題的可行解，故有AX（0）≤b。又因為Y(0)是對偶問題的可行解，則有Y（0）AX（0）≤Y（0）b,及Y（0）A≥C故CX（0）≤Y（0）AX（0）≤Y（0）b亦即CX（0）≤Y（0）b

證畢12可編輯ppt4.最優性定理

若X（0）和Y（0）分別是原問題和對偶問題的可行解，且有

CX（0）=Y（0）b

,則X（0）和Y（0）分別是原問題和對偶問題的最優解。

證明：設X是原問題任一可行解，Y（0）是對偶問題的可行解，根據弱對偶性定理，有CX≤Y（0）b

因為CX（0）=Y（0）b，故CX≤CX（0），即X（0）是原問題的最優解。設Y為對偶問題的任一可行解，同理有Yb≥Y（0）b

即Y（0）是對偶問題的最優解。13可編輯ppt5.對偶定理

有一對對偶的線性規劃問題，若其中有一個有最優解，則另一個也有最優解，且相應的目標函數值相等。

證明：設X（0）是原問題的最優解，對應的基矩陣為B,非基變量的檢驗數為CN-CBB-1N≤0全體檢驗數C-CBB-1A≤0，即C≤CBB-1A令Y（0）=CBB-1，則有Y（0）A≥C

即Y（0）是對偶問題的可行解。

由于z=CX（0）=CBXB（0）=CBB-1b=Y（0）b（目標值相等）

由最優性定理可知Y（0）為對偶問題的最優解。14可編輯ppt綜上，一對對偶問題的解必然下列情況之一：1、原問題和對偶問題都有解，且目標函數值相等2、一個問題具有無界解，另一個問題無可行解3、一個問題無可行解,另一個問題或具有無界解或無可行解15可編輯ppt6.互補松弛定理

若X（0）和Y（0）分別是原問題和對偶問題的可行解，則X（0）和Y（0）都是最優解的充要條件是Y（0）Xs=0和YsX（0）=0。

其中Xs=(xs1,xs2,…,xsm)T，xs1,xs2,…,xsm是原問題的松弛變量.

Ys=(ys1,ys2,…,ysn)T，ys1,ys2,…,ysn是對偶問題的剩余變量。

松弛的含義是如果有某個原始最優解X(0)，使得對某個下標j，滿足X(0)j>0(原問題是松的)，那么與之對應的對偶約束在最優的情況下為等式，即ysj=0(對偶問題是緊的)；如果原始約束在最優情況下對某個下標i滿足x(0)si>0(原問題是松的)，那么，對偶最優解中與之對應的y(0)i=0(對偶問題是緊的)。16可編輯ppt證明:原問題對偶問題

maxz=CXminω=Yb

AX+Xs=bYA-Ys=C

X,Xs≥0Y,Ys≥0

z=(YA-Ys)X=YAX-YsX

ω=Y(AX+Xs)=YAX+YXs

若Y(0)Xs=0和YsX(0)=0,則Y(0)b=Y(0)AX(0)=CX(0)，根據性質4可知

X(0),Y(0)為最優解。

反之,X(0),Y(0)為最優解,則CX(0)=Y(0)AX(0)=Y(0)b

可知必有Y(0)Xs=0和YsX(0)=0。證畢

17可編輯ppt7.原問題的檢驗數對應對偶問題的一個基本解設B是原問題的一個可行基,有A=(B,N)maxz=CBXB+CNXNminω=YbBXB+NXN+XS=bYB-Ys1=CBXB,XN，Xs≥0

YN-Ys2=CNY,Ys1，Ys2≥0YS=（YS1，YS2）證明:原問題對偶問題

maxz=CXminω=Yb

AX+Xs=bYA-Ys=C

X,Xs≥0Y,Ys≥018可編輯ppt當原問題有解XB=B-1b，XN=0時,檢驗數為：CN-CBB-1N，-CBB-1

令Y=CBB-1，代入對偶問題的約束條件得：Ys1=0，-Ys2=CN-CBB-1N則（Y，Ys1，Ys2）為對偶問題的基本解證畢19可編輯ppt檢驗數性質：原問題檢驗數行對應其對偶問題的一個基解,關系如下:

XBXNXs0CN-CBB-1N-CBB-1

Ys1-Ys2-Y20可編輯ppt例4已知線性規劃問題

maxz=x1+x2

-x1+x2+x3

≤2

-2x1+x2-x3

≤1

x1,x2,x3≥0

試用對偶理論證明上述線性規劃問題無最優解。

證:首先看到該問題存在可行解，例如X=(0,0,0)

而上述問題的對偶問題為

minω=2y1+y2

-y1-2y2≥1

y1+y2≥1

y1-y2≥0

y1,y2≥0

由第一約束條件可知對偶問題無可行解，因而無最優解。由此原問題也無最優解。21可編輯ppt例5已知線性規劃問題minω=2x1+3x2+5x3+2x4+3x5

x1+x2+2x3+x4+3x5

≥42x1-x2+3x3+x4+x5

≥3xj≥0,j=1,2,3,4,5

已知其對偶問題的最優解為y1*=4/5,y2*=3/5；z=5。試用對偶理論找出原問題的最優解.22可編輯ppt解:先寫出它的對偶問題

maxz=4y1+3y22y1+y2≤2y1-y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3y1,y2≥023可編輯ppt將y1*,y2*的值代入上述約束條件，得(2),(3),(4)為嚴格不等式；由互補松弛性得x2*=x3*=x4*=0因y1,y2

0，原問題的兩個約束條件應取等式，故有x1*+3x5*=42x1*+x5*=3求解后得x1*=1，x5*=1故原問題的最優解為X*=(1,0,0,0,1)T最優值為ω*=524可編輯ppt§5對偶問題的經濟解釋（影子價格）由對偶定理知，當達到最優解時有：z=CX（0）=Y（0）b=y1（0）b1+y2（0）b2+…+ym（0）bm在最優解處，常數項bi的微小改變對目標函數值的影響（在不改變最優基情況下）有這說明若原問題的bi增加一個單位，則由此引起的最優目標函數值增加量等于該約束條件對應的對偶變量yi的最優值。因此，最優對偶變量yi的值，就相當于對單位變化的第i種資源在實現最大利潤時的一種價格估計，這種估計被稱之為影子價格。25可編輯ppt原問題：可以理解為資源的合理利用使總利潤最大對偶問題：估計資源的價值問題（但并不是第ｉ種資源的實際成本，而是根據企業制造產品的收益估計資源的單位價值，既資源在最優產品組合時具有的潛在價值）影子價格：不同于市場價格，是企業內部估計或核算價格例：某廠生產Ⅰ、Ⅱ種產品要消耗鋼、煤、機械加工時間，現有資源數和利潤表如下，試制定一個最優生產計劃。單位消耗ⅠⅡ現有資源數鋼煤機時１２２２１６１００１８０２４０利潤１３26可編輯ppt解得：對偶問題:由互補松弛條件：解得：27可編輯ppt所以：鋼增加一噸，收入增加3/4萬煤增加一噸，收入增加0機時增加一個，收入增加1/4萬煤本身沒有用完，再增加量，收入也不會增加，而另兩種資源已經用完，再增加資源才會增加收益。28可編輯ppt影子價格在經濟管理中的作用:指示企業內部挖潛的方向：

yi高,對目標增益貢獻大,應重視此資源的組織、采購；

(2)指導企業的購銷決策：yi*是新增資源的價值，在最優產品不變的情況下，購入資源價格大于yi*時，企業虧損，若企業有市價高于影子價格的資源，應設法將其轉讓；(3)用影子價格分析工藝改變后對資源節約的收益:(4)指導企業間的分工協作:29可編輯ppt企業接受外協加工時，制定收費標準可依據影子價格，以使雙方都有利潤，可以促進協作；當外協單位支付的報酬不低于影子價格時，企業可以接受，合作可以促進產品更新換代，以發揮各自優勢。例：A、B、C三廠生產車床、刨床，若只生產一種產品，效率表如右圖。車、刨床需求比例為1：2，試制定最優分工協作計劃，使總的套數最多。解：A、B、C三廠編號為1，2，3車、刨床的編號為1，2效率車床