1Lecture4

DualProblem&

SensitivityAnalysis湖南大學(xué)工商管理學(xué)院Dr.E-mail:

2LectureOutlineOriginoftheDualProblemMatrixrepresentation

ofSimplexCharacteristicsofDualProblemSensitivityAnalysisofLP例1(生產(chǎn)計劃問題)：某工廠在計劃期內(nèi)要安排A、B兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品的利潤與所需的勞力、設(shè)備臺時及原材料消耗，如下：產(chǎn)品A產(chǎn)品B資源限額勞動力設(shè)備原材料9434510360工時200臺時300公斤單位產(chǎn)品利潤70120問：如何安排生產(chǎn)使該廠獲利最大？1.What’sdualproblem？3maxz=70x1+120x2s.t.9x1＋4x2

3604x1+5x2

2003x1+10x2

300 x1,x2

04OriginoftheDualProblem

考慮上一講的生產(chǎn)計劃問題，若設(shè)備和原料都用于對外加工，工廠收取加工費，或是將所有資源外售。試問：該廠設(shè)備工時、勞動力和原料該如何定價？OEM(originalequipmentmanufacturer)5

工廠給這些生產(chǎn)要素定價需要考慮:(1)保證自己的利益——價格越高越好(2)使自己的價格具有競爭力——價格越低越好P需求供給Q均衡點圖1供給-需求函數(shù)6設(shè)y1,y2,y3分別表示出租單位勞動力、單位設(shè)備臺時、出讓單位原材料的收益(收益=出售價格-成本)。一個合理的定價是：代工收益不能低于自己生產(chǎn)所得收益，在此前提下使總代工消耗盡量小。即：minw=360y1+200y2+300y39y1+4y2+3y3

70s.t.4y1+5y2+10y3

120y1,y2,y3

0產(chǎn)品A產(chǎn)品B該線性規(guī)劃問題與原問題互為對偶問題maxz=70x1+120x29x1＋4x2

3604x1+5x2

2003x1+10x2

300 x1,x2

0s.t.7DefinitionofDualProblem(LP)maxz=CX

(DP)minw=YbAX

bYA

CX

0Y

0PrimalProblemDualProblems.t.s.t.8PrimalProblemDualProblemxjyiPrimalRelationshipminwDualRelationshipmaxz=minwmax

z

DefinitionofDualProblem9PrimalProblemDualProblemRotates900DefinitionofDualProblem10maxZ=CXs.t.

AX≤b

X≥0bAC≤maxnmminW=bTYTs.t. ATYT≥CT

YT

≥0≥minCTATbTnm原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=約束條件右端項目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項Primal-dualRelationship12建立對偶問題的規(guī)則約束條件變量右端項價值系數(shù)對于上表，特別把握以下要點：maxmin求max的對偶問題時，變量反號求min的對偶問題時，約束反號＝無限制例1：寫出下列規(guī)劃問題的對偶問題maxz=2x1+2x2-4x3

x1+3x2+3x3≤30s.t.4x1+2x2+4x3≤80x1,x2,x3≥0解：minw=30y1+80y2

y1+4y2≥23y1+2y2≥23y1+4y2≥-4y1,y2≥013s.t.

y1

y2例2：寫出下列規(guī)劃問題的對偶問題minz=2x1+8x2-4x3

x1+3x2-3x3≥30-x1+5x2+4x3=804x1+2x2-4x3≤50x1≤0,x2≥0,x3無限制解：maxw=30y1+80y2＋50y3

y1-y2+4y3≥23y1+5y2+2y3≤8-3y1+4y2－4y3＝-4y1≥0,y2無限制,y3≤0

y1

y2

y3s.t.s.t.152.Matrixrepresentation

ofSimplex設(shè)有線性規(guī)劃問題maxz=CXAX≤bX≥0加上松弛變量XS=(xn+1,xn+2,…,xn+m),化為標(biāo)準型maxz=CX＋0XsAX+IXS=bX≥0,XS≥0s.t.s.t.162.Matrixrepresentation

ofSimplex設(shè)A中存在一可行基B，相應(yīng)的變量可分為基變量XB和非基變量XN，價值系數(shù)也分為CB,CN，即A=(B,N)X=(XB,XN)TC=(CB,CN)maxz=CX＋0XsAX+IXS=bX≥0,XS≥0s.t.因而于是maxz=CX＋0XsAX+IXS=bX≥0,XS≥0代入XB,目標(biāo)值檢驗數(shù)令XN=0,XS=0,得基可行解目標(biāo)值s.t.18Matrixrepresentation

of

Simplextableau0σjIb0Cj193.CharacteristicsofDualProblem定理0(對稱性)對偶問題(D)的對偶就是原問題(P).(LP)maxz=CX(DP)minw=YbAX

bYA

CX

0Y

0s.t.s.t.

minz’=-CXmaxw’=-Yb-AX-b-YA

≤-CX

0Y

0s.t.s.t.對偶定義對偶定義203.CharacteristicsofDualProblem若X(0),Y(0)

分別為（LP）和（DP）的可行解，那么CX(0)≤Y(0)b。(證明)該定理說明：如果原問題是最大化問題，則它的任意可行解對應(yīng)的目標(biāo)函數(shù)值都會小于等于其對偶問題(極小化)的任一可行解對應(yīng)的目標(biāo)函數(shù)值定理1（弱對偶性）證明：由X(0),Y(0)

分別為原問題和對偶問題的可行解則,AX(0)≤b,X(0)≥0Y(0)A≥C,Y(0)≥0因此，Y(0)AX(0)≤Y(0)b于是，CX(0)≤Y(0)b21CX(0)≤Y(0)AX(0)CX(0)≤Y(0)AX(0)≤Y(0)b原問題目標(biāo)函數(shù)值有上界，對偶問題則有下界maxz=2x1+2x2-4x3

s.t.X1+3x2+3x3≤304x1+2x2+4x3≤80x1,x2,x3≥0minw=30y1+80y2

s.t.y1+4y2≥23y1+2y2≥23y1+4y2≥-4y1,y2≥0例如任意取一些可行解試試看？X(0)=(1,1,1)TY(0)=(1,1)TCX(0)=0CY(0)=110≤22下界上界LP對偶問題之間解的關(guān)系。23定理2（無界性）一對對偶問題，若其中一個有無界解，則另一個無可行解。若P無界，則D無可行解若D無界，則P無可行解可行域例如24maxz=x1+x2

s.t.-2x1+x2≤40x1-x2≤20x1,x2≥0minw=40y1+20y2s.t.-2y1+y2≥1y1-y2≥1y1,y2≥0對偶問題顯然無可行解！25定理3（最優(yōu)性）若X(0),Y(0)

分別為（LP）和（DP）的可行解，且CX(0)=Y(0)b，那么X(0),Y(0)分別為（LP）和（DP）的最優(yōu)解.證明設(shè)X*是LP問題的任一可行解，由弱對偶定理CX*≤Y(0)b=CX(0)從而X(0)是最優(yōu)解同理Y(0)是最優(yōu)解26定理4（對偶性）若其中一個問題有最優(yōu)解，則另一個問題也有最優(yōu)解，且兩者最優(yōu)值相等.證明證明：設(shè)X*是LP問題的最優(yōu)解，相應(yīng)的最優(yōu)基為B，則檢驗數(shù)必定滿足令則有因而Y*是對偶問題的可行解又因而Y*是對偶問題的最優(yōu)解0σjIb0Cj2728定理5（互補松弛定理）原問題及其對偶問題的可行解X(0)和Y(0)是最優(yōu)解的充要條件是：

Y(0)XS=0，YSX(0)=0XS,YS分別為原問題松弛向量和對偶問題剩余向量該定理說明：一對對偶問題達到最優(yōu)，當(dāng)且僅當(dāng)松約束(變量)對應(yīng)的對偶變量(約束)必定是緊的證明29AX+Xs=b=>Xs=AX-bYA-Ys=C=>Ys=YA-CYAX+YXs=YbYAX-YsX=CX必要性Y(0)Xs=0，YsX(0)=0=>CX(0)=Y(0)b充分性CX(0)=Y(0)b=>Y(0)Xs-YsX(0)=0Y(0)Xs=CBB-1Xs30y1

…

yi

…

ym

ym+1

…ym+j

…

yn+mx1

…xj

…

xn

xn+1

…xn+i

…xn+m

對偶問題的變量

對偶問題的剩余變量原始問題的變量

原始問題的松弛變量xjym+j=0 yixn+i=0

(i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于0互補松弛定理——松緊定理31如果LP原問題的某一約束為緊約束(松弛變量取值=0,或約束條件為=),則該約束對應(yīng)的對偶變量應(yīng)>=0。如果LP原問題的某一變量=0，則該變量對應(yīng)的對偶約束可能是緊約束(=)，也可能是松約束(><)

。32互補松弛定理——松緊定理如果LP原問題的某一約束為松約束(松弛變量取值>0,或不等式約束取嚴格不等號><),則對應(yīng)的對偶變量取值為緊約束(=0)如果LP原問題的某一變量為松約束(><)，則對應(yīng)的對偶約束為緊約束(=)利用互補松馳定理，可以在知道一個問題的最優(yōu)解時，求解其對偶問題的最優(yōu)解例：minz=2x1+3x2+5x3+2x4+3x5s.t.X1+x2+2x3+x4+3x5≥42x1-2x2+3x3+x4+x5≥3xj≥0,j=1,…,5maxw=4y1+3y2s.t.y1+2y2≤2y1-2y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3y1,y2≥0對偶問題y1*=4/5,y2*=3/5對偶問題的最優(yōu)解4/5-2*3/5=-2/5<3約束條件是松的也即ys>0,由互補松弛定理知X(0)ys=0所以x2=0同理，x3=0,x4=0又y1*>0,而Y(0)xs=0,知xs＝0，即原問題第一個約束取等式同理，第2個約束也取等式=<<<=解得x1=1,x5=13334定理6對偶解存在性若原問題最優(yōu)解存在，則原問題最優(yōu)單純形表的檢驗數(shù)行中，松弛變量檢驗數(shù)的相反數(shù)和剩余變量的檢驗數(shù)即為對偶問題最優(yōu)解CjCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1bσj0CN-CBB-1N

-CBB-1CBB-1bExample35PrimalProblemmaxz=50x1+100x2s.t.x1+x2≤3002x1+x2

≤400x2≤250x1,x2≥0DualProblemminw=300y1+400y2+250y3s.t.y1+2y2≥

50y1+y2+y3

≥

100y1,y2,y3≥036cjbθCBXBX1X2X3X4X5500100X1X4X25050250z27500DP最優(yōu)解501000001010-100-2110100100-500-50-y1*-y2*-y3*x3,x4,x5為松弛變量。原問題最優(yōu)解為:X*=(50,250)T,z*=27500對偶問題的最優(yōu)解為:Y*=(50,0,50)T,w*=2750037對偶最優(yōu)解的經(jīng)濟意義——影子價格由對偶定理求z*對bi的偏導(dǎo)數(shù)shadowpricesshadowprofits38影子價格的意義對偶最優(yōu)解為原問題各資源的影子價格,即實際存在而又看不見的真實價值。影子價格非資源的市場價格，而是指系統(tǒng)達到最優(yōu)狀態(tài)時，資源的單位變化引起目標(biāo)最優(yōu)值的變化。影子價格>市場價格，則買入，否則賣出互補松弛定理的經(jīng)濟解釋如果某資源在系統(tǒng)內(nèi)的對偶解>0，則該資源必為緊(稀)缺資源，對應(yīng)的約束為緊約束(=).如果某資源在系統(tǒng)內(nèi)有剩余，也即其資源約束為松約束(<)時，其對偶解必為0.39檢驗數(shù)和邊際貢獻40檢驗數(shù)為非基變量單位改變量引起目標(biāo)函數(shù)的改變量Y：

影子價格Pj: 產(chǎn)品j的各種資源消耗系數(shù)YPj: 按影子價格核算的產(chǎn)品成本檢驗數(shù)為產(chǎn)品對目標(biāo)函數(shù)的邊際貢獻增加該產(chǎn)品的單位生產(chǎn)量給目標(biāo)函數(shù)帶來的貢獻41對偶單純形法對偶單純形法是求解LP的另一個基本方法，它是根據(jù)對偶原理和單純形法原理而設(shè)計的。在單純形表中進行迭代時，在b列中得到的是原問題的基可行解，而在檢驗數(shù)行得到的是對偶問題的基解，通過逐步迭代，當(dāng)在檢驗數(shù)行得到對偶問題的解也是基可行解時，便得到最優(yōu)解。對偶單純形法42

也就是說，求解原問題LP時，可以從LP的一個基解（并不一定是基可行解）開始，逐步迭代，使目標(biāo)函數(shù)值（Z=Yb=CBB-1b=CX）減少，當(dāng)?shù)絏B=B-1b≥0時，即找到了LP的最優(yōu)解，這就是對偶單純形法。

同原始單純形求法一樣，求解對偶問題DP，也可以從DP的一個基可行解開始，即Cj-CBB-1P0，從一個基可行解（迭代）到另一個基可行解，使目標(biāo)函數(shù)值減少。例一、用對偶單純形法求解：解：將模型轉(zhuǎn)化為cj-9-12-15000bcBxBx1x2x3x4x5x60x4-2-2-1100-100x5-2-3-1010-120x6-1-1-5001-14σ-9-12-150000θ-9/-1-12/-1-15/-5---cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/5-9/5010-1/5-36/50x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5σ-6-9000-342θ-30/-9-45/-14----15/-1cj-9-12-15000bcBxBx1x2x3x4x5x60x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7-15x31/140101/14-3/1415/7σ-3/14000-45/14-33/14501/7θ-3/-9----45/-9-33/-1cj-9-12-15000bcBxBx1x2x3x4x5x6-9x1100-14/911/92-12x20101-102-15x30011/90-2/92σ000-1/3-3-7/3-72bi≥0

所以，

X*=（2,2,2,0,0,0），

-z*=－72，原問題z*=72

其對偶問題的最優(yōu)解為：

Y*=(1/3,3,7/3)，w*=724647小結(jié)——對偶單純形算法步驟尋找初始正側(cè)基,列對應(yīng)的初始單純形表若bi≥0且σj≤0,則已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下一步確定出基變量.由min{bi|bi≤0}=br,則知br

所在行對應(yīng)的變量xr為出基變量。若br所在行對應(yīng)的arj≥0,則問題無可行解，此時可停止計算，否則轉(zhuǎn)下一步確定進基變量.由θ=min{σj/arj|arj<0}=σk/ark,則知xk為進基變量以ark為主元素，按原始單純形法進行迭代計算，得到新的正側(cè)基，并轉(zhuǎn)入步驟②練習(xí)：48cj-2-3-400bcBxBx1x2x3x4x50x4-1-2-110-30x5-21-301-4σ-2-3-4000θ-2/-2--4/-3--cj-2-3-400bcBxBx1x2x3x4x50x40-5/21/21-1/2-1-2x11-1/23/20-1/22σ0-4-10-14θ--8/-5---2/-149cj-2-3-400bcBxBx1x2x3x4x5-3x201-1/5-2/51/52/5-2x1107/5-1/5-2/511/5σ00-3/5-8/5-1/5-28/5Y*=（8/5,1/5）X*=（2/5,11/5,0）Z*=28/55051小結(jié)——對偶單純形法適應(yīng)情況適于形如minz=CX,AX≥b,X≥0,且C≥0的LP問題，原問題的初始解不一定要是基可行解當(dāng)變量多于約束條件時，用對偶單純形法可減少計算工作量在靈敏度分析中，利用它可簡化問題524.SensitivityAnalysisofLP

為什么要進行靈敏度分析？

前面對線性規(guī)劃的討論，價值系數(shù)c，資源系數(shù)b和技術(shù)系數(shù)矩陣A都是已知常數(shù)。但現(xiàn)實中，這些系數(shù)可能只是估計量，存在誤差或隨著時間的推移可能有些許變化糟糕！這個月產(chǎn)品市場價格與原計劃時發(fā)生變化了。年初安排的生產(chǎn)計劃還是最優(yōu)的么？53價值系數(shù)變化的靈敏度分析設(shè)只有一個價值系數(shù)cj發(fā)生變化，其它系數(shù)不變，那么cj在什么范圍內(nèi)變化而最優(yōu)解不變呢？例(生產(chǎn)計劃問題)maxz=70x1+120x2s.t.9x1＋4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0模型54考慮C2發(fā)生變化價值系數(shù)變化的靈敏度分析設(shè)只有一個價值系數(shù)cj發(fā)生變化，其它系數(shù)不變，那么cj在什么范圍內(nèi)變化而最優(yōu)解不變呢？例(生產(chǎn)計劃問題)最優(yōu)單純形表Cj70120000bCBXBX1X2X3X4X5

070120X3X1X2001-3.121.161000.4-0.2010-0.120.16842024σj000-13.6-5.2428055價值系數(shù)變化的靈敏度分析設(shè)價值系數(shù)C2發(fā)生變化，其它系數(shù)不變，那么C2在什么范圍內(nèi)變化而最優(yōu)解不變呢？例(生產(chǎn)計劃問題)最優(yōu)單純形表Cj70

C2

000bCBXBX1X2X3X4X5

070C2X3X1X2001-3.121.161000.4-0.2010-0.120.16842024σj000-28+0.12c2

14-0.16c2

1400+24c2顯然只要檢驗數(shù)滿足最優(yōu)性準則-28+0.12c2≤014-0.16c2≤0

成立，則最優(yōu)解不變！

即

87.5≤c2≤233.3356價值系數(shù)變化的靈敏度分析57(1)Cj是非基變量xj的系數(shù)=>當(dāng)Cj變化?Cj后?Cj的變化范圍價值系數(shù)變化的靈敏度分析58(2)Cr是基變量xr的系數(shù)當(dāng)Cr變化?Cr后當(dāng)?Cr的變化范圍Example.59右端項變化的靈敏度分析考察單純形表b變化只影響因此，只要B-1b≥0,則最優(yōu)基不變從而對偶最優(yōu)解不變，也即影子價格不變CjCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1bσj0CN-CBB-1N

-CBB-1CBB-1b例如生產(chǎn)計劃問題,考慮b3變化的靈敏度分析最優(yōu)單純形表maxz=70x1+120x2s.t.9x1＋4x2＋x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0cj70

120

000bCBXBX1X2X3X4X5

070120X3X1X2001-3.121.161000.4-0.2010-0.120.16842024σj000-13.6-5.2428060由此可見，(p3,p1,p2)是最優(yōu)基，即B-1b≥0解得227.586≤b3≤40061右端項變化的靈敏度分析62br發(fā)生變化，即b’r=br+?br=>右端項變化的靈敏度分析63當(dāng)=>當(dāng)=>Example.右端項變化的靈敏度分析6465生產(chǎn)計劃問題(Excel)利用軟件進行靈敏度分析利用軟件進行靈敏度分析生產(chǎn)計劃問題(OR)6667多個參數(shù)變化的靈敏度分析百分之百法則：(1)對于所有變化的目標(biāo)函數(shù)系數(shù)，當(dāng)其所有允許增加百分比和允許減少百分比之和不超過100％時，則最優(yōu)解不變(2)對于所有變化的右端項系數(shù)，當(dāng)其所有允許增加百分比和允許減少百分比之和不超過100％時，則對偶最優(yōu)解不變68允