運籌學(xué) 03 對偶理論及靈敏度分析

1、1.對偶理論 Dual Theory2.影子價格 Shadow price3.對偶單純形法 Dual Simplex Method 4.靈敏度分析 Sensitivity Analysis5.參數(shù)線性規(guī)劃Parameter LP 對偶問題的提出原問題與對偶問題的數(shù)學(xué)模型原問題與對偶問題的對應(yīng)關(guān)系對偶問題的基本性質(zhì)影子價格對偶單純形法例1：某廠利用現(xiàn)有資源(設(shè)備A、設(shè)備B、調(diào)試工序)生產(chǎn)兩種產(chǎn)品(產(chǎn)品、產(chǎn)品)，有關(guān)數(shù)據(jù)如下表。問如何安排生產(chǎn)，使廠家利潤最大？產(chǎn)品 產(chǎn)品 資源限量設(shè)備A0515設(shè)備B6224調(diào)試工序115單位利潤21分析：設(shè)產(chǎn)品的產(chǎn)量為x1，產(chǎn)品的產(chǎn)量為x2；又設(shè)利潤為z。則該問題

2、的線性規(guī)劃數(shù)學(xué)模型為：max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20換一種思路：廠家的資源只出讓而不自己生產(chǎn)，該如何解決？設(shè)備A出讓單價為y1，設(shè)備B出讓單價為y2，調(diào)試工序出讓單價為y3。收購收購代價收購代價最小最小廠家出讓所得應(yīng)不低出讓所得應(yīng)不低于用同等數(shù)量的于用同等數(shù)量的資源自己生產(chǎn)的資源自己生產(chǎn)的利潤。利潤。廠家接受的條件：利潤需要保證，即 6y2+y32 5y1+2y2+y31收購方接受的條件：收購成本最低，即 min w=15y1+24y2+5y3于是得到一個線性規(guī)劃模型min w=15y1+24y2+5y3 6y2+y32 5y1+2y2+y

3、31 y1,y2,y30原問題max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20v 對偶問題v min w=15y1+24y2+5y3 6y2+y32 5y1+2y2+y31 y1,y2,y30互為對偶問題廠家收購-wy1y2y3y4y5y6y7bmin17.5003.5 M-3.51.5 M-1.5 -8.5y2-1.2510 -0.250.25 0.25-0.25 0.25y37.5010.5-0.5 -1.51.50.5-z x1x2x3x4x5bmax 1000 -0.25 -0.5 -8.5x30011.25 -7.57.5x11000.25 -0.

4、53.5x2010 -0.251.51.5嘗試求解上述兩個線性規(guī)劃問題，你會發(fā)現(xiàn) 目標(biāo)函數(shù)值一致 兩個問題的解都出現(xiàn)在單純形法表格中 其他規(guī)律結(jié)論 原問題與其對偶問題實質(zhì)上一樣 兩個問題互為對方的另一種表達形式原問題對偶問題對稱數(shù)學(xué)模型 vmax z=CXAXbX0vmin f=bTYATYCTY0目標(biāo)函數(shù)取值max zmin f變量X=(x1,x2,xn)TY=(y1,y2,ym)T目標(biāo)函數(shù)系數(shù) C=(c1,cn)bT =(b1,bn)常數(shù)b=(b1,bn)TCT=(c1,cn)T約束條件系數(shù) A=(aij)mnAT=(aij)nm變量 - 約束變量(n,0,0,任意)約束(n,=)約束 -

5、 變量約束(m,=)變量(m,0,0,任意)例2：將下述線性規(guī)劃作為原問題，請轉(zhuǎn)換為對偶問題max z=5x1+3x2+2x3+4x4 5x1+x2+x3+8x48 2x1+4x2+3x3+2x4=10 x10,x20,x3任意,x4任意解法1：將原問題寫成對稱形式的線性規(guī)劃問題。得到max z=5x1+3x2+2(x3-x3)+4(x4-x4) 5x1+x2+(x3-x3)+8(x4-x4)8 2x1+4x2+3(x3-x3)+2(x4-x4)10 -2x1-4x2-3(x3-x3)-2(x4-x4)-10 x10,x20,x30,x30,x40,x40設(shè)對偶問題變量y1,y2,y20，直接

6、轉(zhuǎn)換，得min f=8y1+10y2-10y2 5y1+2y2-2y25 y1+4y2-4y23 y1+3y2-3y22 -y1-3y2+3y2-2 8y1+2y2-2y24 -8y1-2y2+2y2-4 y1,y2,y20令y2=y2-y2(即y2取值任意)，合并第3、4個約束條件和第5、6個約束條件，得到原問題的對偶問題min f=8y1+10y2 5y1+2y25 y1+4y23 y1+3y2=2 8y1+2y2=4 y10,y2任意解法2：也可以根據(jù)原問題與對偶問題的對應(yīng)關(guān)系，直接得到對偶問題：min f=8y1+10y2 5y1+2y25 y1+4y23 y1+3y2=2 8y1+2

7、y2=4 y10,y2任意對稱性：對偶問題的對偶是原問題(對稱定理)。證明： 設(shè)原問題為max z=CX,AXb,X0；則其對偶問題為min f=bTY,ATYCT,Y0。 把對偶問題看作原問題，得到線性規(guī)劃模型為max f=-bTY,-ATY-CT,Y0。 將上述問題轉(zhuǎn)換為對偶問題，得到min z=-(CT)TX,-(AT)TX-(bT)T,X0，即max z=CX,AXb,X0。 所以對偶問題的對偶即為原問題。弱對偶性：若X是原問題的可行解，Y是其對偶問題的可行解，則恒有CXbTY。證明： 因為X為原問題的可行解，故AXb，且X0；因為Y為對偶問題的可行解，故ATYCT，且Y0。 由上述可

8、得CX=XTCTXTATY=YTAXYTb=bTY。原問題原問題對偶問題對偶問題CX*=bTY*CXbTY從弱對偶性可得到以下重要結(jié)論： (1)極大化問題(原問題)的任一可行解所對應(yīng)的目標(biāo)函數(shù)值是對偶問題最優(yōu)目標(biāo)函數(shù)值的下界。 (2)極小化問題(對偶問題)的任一可行解所對應(yīng)的目標(biāo)函數(shù)值是原問題最優(yōu)目標(biāo)函數(shù)值的上界。 (3)若原問題可行，但其目標(biāo)函數(shù)值無界，則對偶問題無可行解。 (4)若對偶問題可行，但其目標(biāo)函數(shù)值無界，則原問題無可行解。 (5)若原問題有可行解而其對偶問題無可行解，則原問題目標(biāo)函數(shù)值無界。 (6)對偶問題有可行解而其原問題無可行解，則對偶問題的目標(biāo)函數(shù)值無界。最優(yōu)性：若X是原問

9、題的可行解，Y是其對偶問題的可行解，且有CX=bTY，則X是原問題的最優(yōu)解，Y是其對偶問題的最優(yōu)解。證明： 根據(jù)弱對偶性及已知條件，對于對偶問題任意可行解Y*都有bTY*CX=bTY，故Y為對偶問題的最優(yōu)解。 根據(jù)弱對偶性及已知條件，對于原問題的任意可行解X*都有CX*bTY=CX，故X為原問題的最優(yōu)解。強對偶性：若原問題及其對偶問題都有可行解，則兩者都有最優(yōu)解，且最優(yōu)解的目標(biāo)函數(shù)值相等(對偶定理)。證明：根據(jù)弱對偶性可知，由于原問題與對偶問題都有可行解，故原問題目標(biāo)函數(shù)有上界且對偶問題目標(biāo)函數(shù)有下界，所以兩者都有最優(yōu)解。同時，原問題的影子價格即為對偶問題的一個可行解，這個可行解的目標(biāo)函數(shù)即為

10、原問題的目標(biāo)函數(shù)值，且為最優(yōu)。互補松弛性：在線性規(guī)劃問題的最優(yōu)解中，有以下結(jié)論成立：(1)若yi0，則aijxj=bi；(2)若aijxjbi，則yi=0。證明：由弱對偶性可知，CXYTAXYTb。且由CX=YTb=YTAX，得到Y(jié)T(AX-b)=0。這就說明了Y的第i個分量和AX-b的第i個分量若其中一個不為零，另外一個必定為零。結(jié)論得證。影子價格的定義影子價格的經(jīng)濟意義當(dāng)線性規(guī)劃原問題求得最優(yōu)解X*時，其對偶問題也得到最優(yōu)解Y*，且有z*=CX*=bTY*=f*式中b是線性規(guī)劃問題約束條件的右端項，表示各種資源的擁有量；對偶變量Y*的意義代表在資源最優(yōu)利用條件下對單位資源的估價。這種估價不

11、是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格(shadow price)(1)資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。(2)影子價格是一種邊際價格。在z*=bTY*中對b求導(dǎo)數(shù)，得到dz*/dbT=Y*，這說明Y*的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，b每增加一個單位時目標(biāo)函數(shù)z的增量。(3)資源的影子價格實際上又是一種機會成本。在純市場經(jīng)濟條件下，當(dāng)資源的市場價格低于影子價格時，可以買進這種資源；相反當(dāng)市場價格高于影子價格時，就會賣出這

12、種資源。隨著資源的買進賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。(4)在對偶問題的互補松弛性質(zhì)中有：當(dāng)ai1xi1+ai2xi2+ainxin0時，ai1xi1+ai2xi2+ainxin=bi，這表明生產(chǎn)過程中如果某種資源bi未得到充分利用時，該種資源的影子價格為零；又當(dāng)資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢。(5)從影子價格的含義上再來考察單純形表的計算。檢驗數(shù)j=cj-CBB-1Pj=cj-aijyi，式中cj代表第j種產(chǎn)品的產(chǎn)值，aijyi是生產(chǎn)該種產(chǎn)品所消耗各種資源的影子價格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品產(chǎn)值大于隱含

13、成本，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則，用這些資源來生產(chǎn)別的產(chǎn)品更為有利(準(zhǔn)確地說，出售更有利)，就不在生產(chǎn)計劃中安排。這就是檢驗數(shù)的經(jīng)濟意義。(6)一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價，這種估價直接涉及到資源的最有效利用。對偶單純形法的基本思路對偶單純形法的計算步驟對偶單純形法的應(yīng)用舉例當(dāng)一個線性規(guī)劃的約束條件中包含“”約束時，為了獲得初始可行基，必須用大M法，略嫌麻煩。若減去一個剩余變量，認定為基變量，則成為系數(shù)為-1的基變量，其基本解不可行。但是，若基本解滿足最優(yōu)性檢驗，也就是說其對偶問題所對應(yīng)的解可行，那么通過迭代，

14、可以使得原問題的解逐漸變得可行，也就得到了原問題的最優(yōu)解。這就是對偶單純形法的原理。優(yōu)點是不需要添加人工變量。對偶問題的可行解對偶問題最優(yōu)解判斷最優(yōu)解判斷最優(yōu)解判斷j=cj-zj0原問題基可行解原問題基可行解xB=B-1b0第一步：給出一組滿足最優(yōu)檢驗的基本解第二步：若當(dāng)前解可行，則得最優(yōu)解第三步：確定出基變量。選擇負數(shù)基本解中最小值所對應(yīng)的變量作為出基變量。即當(dāng) minbi|bi0=br時第r行對應(yīng)變量為出基變量第四步：確定入基變量。若第r行都大于等于0則無可行解，停止計算；否則計算=minj/arj|arj0,j0clminj/alj|alj0brmin-bi/ir|ir0時，aijj/y

15、i 當(dāng)yi0時，aijj/yi(5)增加新的變量 略(6)增加新的約束條件 略例5：某家電廠家利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表。產(chǎn)品 產(chǎn)品 資源限量設(shè)備A(臺時)0515設(shè)備B(臺時)6224調(diào)試工序(小時)115單位利潤(元/臺)21試問 問題1：如何安排生產(chǎn)，使廠家獲利最多？ 問題2：當(dāng)c1=1.5時，最優(yōu)生產(chǎn)計劃有何變化？ 問題3：當(dāng)c2=2時，最優(yōu)生產(chǎn)計劃有何變化？ 問題4：求原最優(yōu)解不變時c2的范圍。 問題5：b1和b2分別如何改變，原計劃不變？ 問題6：為保持最優(yōu)解不變，a11=0的變化范圍。 問題7：增加一個變量，最優(yōu)解的改變。 問題8：增加一個約束條件，最優(yōu)解的變化。解

16、：(1)設(shè)x1表示產(chǎn)品的產(chǎn)量，x2表示產(chǎn)品的產(chǎn)量，z為廠家利潤，則得到線性規(guī)劃模型 max z=2x1+x2 5x215 6x1+2x224 x1+x25 x1,x20解之，得到 最優(yōu)解x=(3.5,1.5)T 最優(yōu)值z=8.5(2)c1=1.5時，得到線性規(guī)劃模型 max z=1.5x1+x2 5x215 6x1+2x224 x1+x25 x1,x20解之，得到 最優(yōu)解x=(3.5,1.5)T 最優(yōu)值z=6.75結(jié)論：最優(yōu)解不變，最優(yōu)值減少(3)c2=2時，得到線性規(guī)劃模型 max z=2x1+2x2 5x215 6x1+2x224 x1+x25 x1,x20解之，得到 最優(yōu)解x=(3.5,

17、1.5)T 最優(yōu)值z=10結(jié)論：最優(yōu)解不變，最優(yōu)值增加(4)c2的變化范圍原問題的最終單純形表中alj和j見表，計算j/alj也在下表中結(jié)論：-1/3c21，或2/3c22Itemx1x2x3x4x5j000 -0.25 -0.5a2j010 -0.25 1.5j/a2j-0-1-1/3(5)略(6)略(7)略(8)略1.將參數(shù)的改變計算反映到最終單純形表上；2.檢查原問題是否仍為可行解；3.檢查對偶問題是否仍為可行解；4.按下表所列情況得出結(jié)論和決定繼續(xù)計算的步驟。某廠計劃生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品單位利潤及生產(chǎn)產(chǎn)品所需材料、勞動力如下表：單位產(chǎn)品 甲 乙 丙 可使用資源量勞動力1/

18、3 1/3 1/31材料1/3 4/3 7/33利潤(元)231(1)確定最優(yōu)的生產(chǎn)方案；(2)當(dāng)c3增大至多少時，丙產(chǎn)品安排生產(chǎn)；(3)增加3個勞動力，最優(yōu)解是否改變？(4)勞動力在哪個范圍內(nèi)變化，對利潤值的改變有利；(5)增加新的產(chǎn)品丁，需1個勞動力，1個單位原料，利潤3元。確定最優(yōu)的生產(chǎn)方案。(6)添加新約束：x1+2x2+x310，最優(yōu)解是否改變？概念模型步驟舉例 目標(biāo)函數(shù)的系數(shù)含有參數(shù)的線性規(guī)劃問題 約束條件右端的常數(shù)項含有參數(shù)的線性規(guī)劃問題當(dāng)參數(shù)cj或bi沿某一方向連續(xù)變動時，目標(biāo)函數(shù)值z將隨cj或bi的變動而呈線性變動，z是這個變動參數(shù)的線性函數(shù)，因而稱為參數(shù)線性規(guī)劃。(1)目標(biāo)

19、函數(shù)的系數(shù)含有參數(shù)的LP模型設(shè)C：價值不變向量；C*：資源變動向量；：參數(shù)，則有模型max z()=(C+C*)X AX=b X0(2)約束條件右端的常數(shù)項含有參數(shù)的LP模型設(shè)b：資源不變向量；b*：資源變動向量；：參數(shù)，則有模型max z=CX AX=b+b* X0(1)令=0求解得最終單純形表(2)將C*或b*項反映到最終單純形表中去(3)值增大或減小，觀察原問題或?qū)ε紗栴} 確定現(xiàn)有解(基)允許的的變動范圍 當(dāng)?shù)淖儎映鲞@個范圍時，用單純形法或?qū)ε紗渭冃畏ㄇ笮碌慕?4)重復(fù)第(3)步，直到值繼續(xù)增大或減小時，表中的解(基)不再出現(xiàn)變化時為止例6：目標(biāo)函數(shù)的系數(shù)含有參數(shù)的線性規(guī)劃問題。分析值

20、變化時，下述參數(shù)線性規(guī)劃問題最優(yōu)解的變化。max z()=(2+)x1+(1+2)x2 5x115 6x1+2x224 x1+x25 x1,x20解：(1)先令=0求得最優(yōu) 解，見下表。BV -z x1x2x3x4x5b121000 x350100153x462010244x51100155101-0.400-6x1100.2003-x402-1.21063x501-0.20122100-0.20-1 -8x1100.2003x400-0.81-22x201-0.2012(2)然后將反映在最終單純形表中，見下表BV -zx1x2x3x4x5b12+1+20000 x350100153x4620

21、10244x51100155101+2-0.4-0.200-6-3x1100.2003-x402-1.21063x501-0.20122100-0.2+0.20-1-2-8-7x1100.2003x400-0.81-22x201-0.2012(3)為保持原問題解不變，則-0.2+0.20，且-1-20，即-1/21。解不變，值變z=8+7(4)增加，即1。繼續(xù)。解變，值變z=5+10BV -zx1x2x3x4x5b100-0.2+0.20-1-2-8-7x1100.200315x400-0.81-22-x201-0.2012-11-000-1-2-5-10 x35010015x44001-21

22、4x2110015(5)減少，即-2-1/2。繼續(xù)。解變，值變z=6+3。見下表。(6)減少，即-2。初始單純形表即達最優(yōu)z=0BV -zx1x2x3x4x5b12+1+20000 x350100153x462010244x51100155101+2-0.4-0.200-6-3x1100.2003x402-1.2106x501-0.2012xz(0,5,15,14,0)T5+101,)(3,2,0,2,0)T8+7-0.5,1(3,0,0,6,2)T6+3-2,-0.5(0,0,15,24,5)T0(-,-2-2-1/2-1124.51525z()0例7：目標(biāo)函數(shù)的右端的常數(shù)項含有參數(shù)的線性規(guī)劃問題。分析值變化時，下述參數(shù)線性規(guī)劃問題最優(yōu)解的變化。max z()=2x1+x2 x1+x210+2 2x1+4x224- 3x1+x218+ x1,x20(1)