§1線性規劃的對偶問題的提出

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

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

0.max3￡=XbAXt.sCXz實際問題提出：某廠生產甲、乙兩種產品，產量、利潤、設備臺時如下模型所示第二章線性規劃的對偶理論

從另一個角度討論這個問題：另一方面，工廠決定設備轉讓、收取租金，確定租價。設y1，y2，y3分別為設備A、B、C每臺時的租價，同意租讓的原則：產品甲租讓的租費不低于原利潤32元，其余產品類似。工廠將所有設備臺時都出租，其收入和約束為：矩陣形式

為什么目標取最小？租金定的越高就不會有人來租，問題就沒有實際意義，工廠和接受者都愿意的條件為上述規劃問題的解。其中Y=（y1，y2，y3）§２線性規劃的對偶理論原問題與對偶問題的數學模型原問題：對偶問題：

標準對偶問題化成對偶問題的標準形

1.若原問題的約束條件全部是等式約束

總結：原問題與對偶問題的對應關系

2.其它形式，按線性規劃化標準形的方法進行進一步有原問題（或對偶問題）對偶問題（或原問題）

目標函數maxz目標函數minw

約束條件:m個對偶變量數:m個變量

第i個約束條件類型約束為≤對偶變量:yi

≥0

第i個約束條件類型約束為≥對偶變量:yi

≤0

第i個約束條件類型約束為=對偶變量:yi是自由變量

決策變量總數:n個約束條件總數為n個

決策變量xi≥0第j個約束條件類型為≥

決策變量xi≤0第j個約束條件類型為≤

決策變量xi是自由變量第j個約束條件類型為=

原問題中的價值向量與對偶問題中的資源向量對換,“上下對換”.

原問題:X在C和A的右邊;對偶問題:Y在b和A的左邊,“左右對換”

對偶問題的基本性質和基本定理1.對稱性定理：對偶問題的對偶是原問題證明：2.弱對偶性定理

若X（0）和Y（0）分別是原問題和對偶問題的可行解，則有CX（0）≤Y（0）b3.若原問題（對偶問題）可行，但目標函數無界，則其對偶問題（原問題）無可行解。4.最優性定理

若X（0）和Y（0）分別是原問題和對偶問題的可行解，且有CX（0）=Y（0）b,則X（0）和Y（0）分別是原問題和對偶問題的最優解。

5.對偶定理

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

綜上，一對對偶問題的解必然為下列情況之一：1、原問題和對偶問題都有解，且目標函數值相等2、一個問題具有無界解，另一個問題無可行解3、原問題和對偶問題都無可行解6.互補松弛定理

若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(對偶問題是緊的)。例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

由第一約束條件可知對偶問題無可行解，因而無最優解。由此原問題也無最優解。例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。試用對偶理論找出原問題的最優解.解:

先寫出它的對偶問題

maxz=4y1+3y2y1+2y2≤2y1-y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3y1,y2≥0將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最優值為ω*=5§３對偶問題的經濟解釋（影子價格）由對偶定理知，當達到最優解時有：

z=CX（0）=Y（0）b=y1（0）b1+y2（0）b2+…+ym（0）bm在最優解處，常數項bi

的微小改變對目標函數值的影響（在不改變最優基情況下）有這說明若原問題的bi增加一個單位，則由此引起的最優目標函數值增加量，就等于該約束條件相對應的對偶變量yi的最優值。因此，最優對偶變量yi的值，就相當于對單位變化的第i種資源在實現最大利潤時的一種價格估計，這種估計被稱之為影子價格。原問題：可以理解為資源的合理利用使總利潤最大對偶問題：估計資源的價值問題（但并不是第ｉ種資源的實際成本，而是根據企業制造產品的收益估計資源的單位價值，既資源在最優產品組合時具有的潛在價值）影子價格：不同于市場價格，是企業內部估計或核算價格例：某廠生產Ⅰ、Ⅱ種產品要消耗鋼、煤、機械加工時間，現有資源數和利潤表如下，試制定一個最優生產計劃。單位消耗Ⅰ

Ⅱ現有資源數鋼煤機時１２２２１６１００１８０２４０利潤１３解得：對偶問題:由互補松弛條件：解得：所以：鋼增加一噸，收入增加3/4萬煤增加一噸，收入增加0

機時增加一個，收入增加1/4萬

煤本身沒有用完，再增加量，收入也不會增加，而另兩種資源已經用完，再增加資源才會增加收益影子價格在經濟管理中的作用:指示企業內部挖潛的方向：yi高,對目標增益貢獻大,應重視此資源的組織、采購；(2)指導企業的購銷決策：yi*是新增資源的價值，在最優產品不變的情況下，購入資源價格大于yi*時，企業虧損，若企業有市價高于影子價格的資源，應設法將其轉讓；(3)用影子價格分析工藝改變后對資源節約的收益:(4)指導企業間的分工協作:

企業接受外協加工時，制定收費標準可依據影子價格，以使雙方都有利潤，可以促進協作；當外協單位支付的報酬不低于影子價格時，企業可以接受，合作可以促進產品更新換代，以發揮各自優勢。例：A、B、C三廠生產車床、刨床，若只生產一種產品，每天效率表如右圖。三個廠車、刨床需求比例為1：2，試制定最優分工協作計劃，使總的套數最多。解：A、B、C三廠編號為1，2，3

車、刨床的編號為1，2效率車床刨床ABC4223為第i廠生產第j種產品的時間比例則：三廠生產車床總數：三廠生產刨床總數：展開得：總套數為E，則解得：生產車床：3/4×5=15/4（臺）生產刨床：4×1+1/4×2+3×1=15/2（臺）A廠只生產刨床，B廠3/4生產車床，1/4生產刨床C廠只生產刨床此計劃能否執行看較單獨生產獲利增加情況A廠單獨生產：解得A廠生產能力：2/3×1=2/3臺車床

1/3×4=4/3臺刨床（每天生產一臺車床或4臺刨床而需求比例為1:2）（用2/3的能力生產車床，1/3的能力生產刨床）B廠單獨生產：B廠生產能力：1/6×5=5/6臺車床

5/6×2=5/3臺刨床解得：C廠單獨生產：解得：C廠生產能力：3/7×2=6/7臺車床

4/7×3=12/7臺刨床