運籌學(xué)二章對偶線性規(guī)課件

第二章對偶理論與靈敏度分析2.1線性規(guī)劃的對偶問題2.2對偶問題的基本性質(zhì)2.3影子價格2.4對偶單純形法2.5靈敏度分析DUAL3/17/20231本章學(xué)習(xí)要求掌握對偶理論及其性質(zhì)掌握影子價格的應(yīng)用掌握對偶單純形法熟悉靈敏度分析的概念和內(nèi)容掌握右側(cè)常數(shù)，價值系數(shù)，工藝系數(shù)的變換對原最優(yōu)解的影響掌握增加新變量和增加新約束條件對原最優(yōu)解的影響，并求出相應(yīng)因素的靈敏度范圍3/17/20232浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系2.1線性規(guī)劃的對偶問題問題的提出對稱形式下對偶問題的一般形式非對稱形式下的原問題與對偶問題的關(guān)系3/17/20233浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系數(shù)學(xué)模型Cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj000-1/4-1/2cj-15-24-500-MCBYBby1y2y3y4y5y6θ-My62061-1011/3-15y11/512/51/50-1/505/2σj06M-18M-2-M-30-24y21/3011/6-1/601/62-15y11/5102/151/15-1/5-1/151/2σj001-3-3-M+8-24y21/4-5/410-1/41/41/2-5y31/215/2011/2-3/2-3σj-15/200-7/2-3/2-M-3①②Z*=8.5W*=8.53/17/20235浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系二、對偶問題的一般形式一般認為變量均為非負約束的情況下，約束條件在目標(biāo)函數(shù)取Max時均取“≤”號；當(dāng)目標(biāo)函數(shù)求Min值時均取“≥“號。則稱這些線性規(guī)劃問題具有對稱性。maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2……am1x1+am2x2+……+amnxn≤bmx1,x2,……,xn≥0minw=b1y1+b2y2+……+bmyms.t.a11y1+a21y2+……+am1ym≥c1a12y1+a22y2+……+am2ym

≥c2……a1ny1+a2ny2+……+amnym

≥cny1,y2,……,ym≥0MaxZ=CXs.t.AX≤bX≥0Minw=Y’bs.t.A’Y≥C’Y≥03/17/20236浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系原問題maxz=CXs.t.AX≤b X≥0對偶問題minw=Y’bs.t.A’Y≥C’ Y≥0≥maxbCCATb≤minmnmnA3/17/20237浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系原始問題為minz=2x1+3x2-x3s.t.x1+2x2+x3≥62x1-3x2+2x3≥9x1,x2,x3≥0根據(jù)定義，對偶問題為maxy=6y1+9y2s.t.y1+2y2≤22y1-3y2≤3y1+2y2≤-1y1,y2≥0原始問題是極小化問題原始問題的約束全為≥原始問題有3個變量，2個約束原始問題的變量全部為非負對偶問題是極大化問題對偶問題的約束全為≤對偶問題有2個變量，3個約束原始問題的變量全部為非負3/17/20239浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系對偶問題的對偶maxz=6x1+9x2s.t.x1+2x2≤22x1-3x2≤3x1+2x2≤-1x1,x2≥0minw=2y1+3y2-y3s.t.y1+2y2+y3≥62y1-3y2+2y3≥9y1,y2,y3≥0對偶問題的對偶就是原始問題。兩個問題中的任一個都可以作為原始問題。另一個就是它的對偶問題。根據(jù)定義寫出對偶問題根據(jù)定義寫出對偶問題maxu=6w1+9w2s.t.w1+2w2≤22w1-3w2≤3w1+2w2≤-1w1,w2≥03/17/202310浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系對偶問題的性質(zhì)總結(jié)對偶的對偶就是原始問題maxz=CXs.t.AX≤bX≥0minw=Y’bs.t.ATY≥

C’ Y≥0對偶的定義maxu=CWs.t.AW≤C W≥03/17/202311浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系三、非對稱形式的原—對偶問題minz=2x1+3x2-5x3+x4s.t.x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1≤0,x2,x3≥0minz=-2x1’+3x2-5x3+(x4’-x4”)s.t.-x1’+x2-3x3+(x4’-x4”)≥52x1’

-2x3+(x4’-x4”)≥-4x2+x3+(x4’-x4”)≥6-x2-x3-(x4’-x4”)≥-6x1’,x2,x3,x4’,x4”

≥0變?yōu)閷ΨQ形式y(tǒng)1y2’y3’y3”maxw=5y1-4y2’+6(y3’-y3”)s.t.-y1+2y2’≤-2y1+(y3’-y3”)≤3-3y1-2y2’+(y3’-y3”)≤-5y1+y2’+(y3’-y3”)≤1-y1-y2’-(y3’-y3”)≤-1y1,y2’,y3’,y3”≥0寫出對偶問題maxw=5y1+4y2+6y3s.t.y1+2y2≥2y1+y3≤3-3y1+2y2+y3≤-5y1-y2+y3=1y1≥0,y2≤0,y3無約束3/17/202313浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系結(jié)論LP(LD)MaxX≥0X≤0X無約束St≤st≥St=LD(LP)Minst≥St≤St=Y≥0Y≤0Y無約束3/17/202314浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≤≥=≥Free≤≥≥=≤≥x1≥0x2≤0x3:Free原始問題變量的個數(shù)(3)等于對偶問題約束條件的個數(shù)(3)；原始問題約束條件的個數(shù)(4)等于對偶問題變量的個數(shù)(4)。原始問題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)。原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)。寫對偶問題的練習(xí)（1）3/17/202315浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系maxZ=x1-2x2+3x3s.t.2x1+4x2+3x3≥1003x1-2x2+6x3≤2005x1+3x2+4x3=150x1,x3≥0練習(xí)minw=100y1+200y2+150y3s.t.2y1+3y2+5y3≥14y1-2y2+3y3=-23y1+6y2+4y3≥3y1≤0,y2≥0minZ=2x1+2x2+4x3s.t.x1+3x2+4x3≥22x1+x2+3x3≤3x1+4x2+3x3=5x1≥0,x2≤0maxw=2y1+3y2+5y3s.t.y1+2y2+y3≤23y1+y2+4y3≥24y1+3y2+3y3≥4y1≥0,y2≤03/17/202317浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系課后作業(yè)P742.1(4)3/17/202318浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系2.2對偶問題的基本性質(zhì)單純形法的矩陣描述對偶問題的基本性質(zhì)3/17/202319浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系某一決策變量xk系數(shù)列向量迭代前為Pk，迭代后為B-1Pk。當(dāng)B為最優(yōu)基時MaxZ=CBB-1b＋（CN-CBB-1N)XN-CBB-1XS令Y’=CBB-1由此可以看出，當(dāng)X為最優(yōu)解時，Y為對偶問題的可行解。且該可行解對應(yīng)的目標(biāo)函數(shù)值W=Y’b=CX*3/17/202321浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系非基變量基變量XBXNXs0XsbBNIcj-zjCBCN0……基變量非基變量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1對應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1；初始單純形表中基變量Xs=b，迭代后的表中為XB=B-1b；約束矩陣（A，I）＝（B，N，I），迭代后為（B-1B，B-1N，B-1I）＝（I，B-1N，B-1)；初始單純形表中xj的系數(shù)向量為Pj，迭代后為Pj’，且Pj’=B-1Pj’。3/17/202322浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系二、對偶問題的基本性質(zhì)原始問題maxz=CXs.t.AX≤b X≥0對偶問題minw=Y’bs.t.A’Y≥C’ Y≥01.弱對偶性若X0為原問題的可行解，Y0為對偶問題的可行解，則恒有CX0≤Y0’b證明：X0≥0為LP的可行解，Y0≥0為LD的可行解，則有：AX0≤bA’Y0≥C’→Y0’AX0≤Y0’b(A’Y0)’X0≥(C’)’X0→Y0’b≥Y0’AX0≥CX03/17/202323浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系2.最優(yōu)性若X0為LP的可行解，Y0為LD的可行解，且CX0＝Y(jié)0’b,則X0，Y0分別為LP和LD的最優(yōu)解。證明：設(shè)LP的最優(yōu)解為X*,LD的最優(yōu)解為Y*又因為：CX*≥CX0=Y0’b≥Y*’b又由弱對偶性定理：CX≤Y’b則X0必為X*,Y0必為Y*3.強對偶性若原問題和對偶問題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等。3/17/202325浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系4.互補松弛定理如果X*,Y*分別為LP,LD問題的可行解，則X*,Y*為最優(yōu)解的充要條件為：Y*’XS*=0YS*’X*=0

當(dāng)LP中第i個約束是嚴格不等式，則Y中的Yi必為0，如果Yi不為0,則LP中第i個約束為嚴格等式。

當(dāng)LD中第j個約束是嚴格不等式，則X中的xj必為0，如果xj不為0,則LD中第j個約束為嚴格等式。3/17/202326浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系1.定理：根據(jù)對偶問題的基本性質(zhì)對LP為生產(chǎn)問題而言：bi表示LP中第i種資源的擁有量；Cj表示第j種產(chǎn)品的利潤或產(chǎn)值其中Yi*可用下面數(shù)學(xué)式求得：1）yi*可解釋為第i種資源的邊際價格，即在其他條件不變的情況下，只增加單位第i種資源所引起的目標(biāo)函數(shù)最優(yōu)值的變化，bi→bi+1,△bi=1，△Z*的值為yi*。2）yi*也可解釋為出讓單位第i種資源的收益；3）yi*的取值隨cj,xj,Aij的變化而變化，因此企業(yè)不同，產(chǎn)業(yè)不同，資源擁有量不同，yi*的值不同，是具體企業(yè)，具體產(chǎn)品和具體資源擁有量的特定價格。3/17/202329浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系例：美佳公司……①……②……③X*=(7/2,3/2,15/2,0,0)’Z*=8.5由1）可知：y1*為①變?yōu)?x2≤16時Z*的增量，y1*＝△Z*＝0Y2*為②變?yōu)?x1＋2x2≤25時Z*的增量所以當(dāng)A的資源增加時，Z*無變化，Y1*＝0LP中①約束為嚴格的不等式，表明A沒有被充分利用。3/17/202330浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系2.影子價格的應(yīng)用（對偶問題的應(yīng)用）1）yi*實際上是一種機會成本，當(dāng)A的單位市場價格無論多低時，還應(yīng)賣出A資源，直到15/2；當(dāng)B的單位市場價格<1/4時，應(yīng)該買進。2）對企業(yè)資源薄弱環(huán)節(jié)的分析由互補松弛定理：當(dāng)Yi*＝0表明bi沒有被充分利用；當(dāng)Yi*>0表明該資源已充分利用，因此該資源的增加或減少均會引起Z*的變動，Yi*越大，變動越大。由美佳可得：Y1=0表明A沒有充分利用，y2=1/4,y3=1/2表明y3的變動對美佳公司利益的影響要大。

3）新產(chǎn)品是否投產(chǎn)以及合理定價的問題例：美佳考慮生產(chǎn)電器Ⅲ，要耗A3，B2，調(diào)試1個單位，市場價格2元，問是否值得生產(chǎn)。又如果美佳決定生產(chǎn)該種產(chǎn)品，則要定價多少該公司才不會虧本。3/17/202331浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系4）合理調(diào)配資源因為影子價格是資源在特點環(huán)境下的價值，隨環(huán)境的變化而變化，同一資源在有些使用中價值低，有些使用中價值高。例：美佳公司有兩個子公司（1）A→0B→1/4C→1/2(2)A→2B→0C→1因此：（1）（2）A→AB←BC→C3/17/202332浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系課后作業(yè)P762.83/17/202333浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系2.4對偶單純形法一、基本思路從LP的一個基解出發(fā)，轉(zhuǎn)換到另一個基解；在轉(zhuǎn)換過程中，保持對應(yīng)的LD的解Y的可行性（相當(dāng)于LP的δj≤0），逐步消除該基解的不可行性，直到基解變成可行解，就獲得了最優(yōu)解。注：該方法不是求解LD的單純形法，而是利用對偶關(guān)系求解LP的另一種方法。3/17/202334浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系二、計算步驟：1.假定已給一對偶可行基單位陣B（對應(yīng)LD問題的解可行），相應(yīng)的基解XB＝b。2.若b的各個分量均非負，則這個解就是最優(yōu)解，停止迭代。3.如果XB有分量xl<0，且xl所在行的所有系數(shù)alj≥0，則LP無可行解，停止迭代。如果XB有分量xl<0，且該分量所在行的系數(shù)alj有負分量，則該解不是LP的最優(yōu)解，繼續(xù)。4.如果min{bi/bi<0}＝bl，則xl為換出變量θ＝min{δj/alj|alj＜0}=δk/alk,則xk為換入變量5.以alk為主元，進行系數(shù)行變換，得一新的對偶可行基解(也稱正則解），轉(zhuǎn)第2步。3/17/202335浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系比較單純形法和對偶單純形法單純形法：先從基解、可行解出發(fā)，通過若干次迭代使?jié)M足δj≤0對偶單純形法:先從基解，對偶可行解（等價于δj≤0）出發(fā)，再通過若干次迭代使之可行。對偶單純形法的優(yōu)缺點：優(yōu)點:初始基解可為負，減少人工變量數(shù)量，使計算簡單；靈敏度分析時使用方便。缺點：不能保證所有的Lp問題的初始單純形表中的δj≤0。3/17/202336浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系例:cj-2-3-400CBXBbx1x2x3x4x50X4-3-1-2-1100x5-4-21-301σj-2-3-400θ14/3[]0x4-2x112-1/23/20-1/2-10-5/21/21-1/2σj0-2-10-1θ4/52-3x2-2x1[]12/50-1/5-2/51/511/5107/5-1/5-2/5σj00-9/5-8/5-1/5所以：X*=(x1,x2)T=(11/5,2/5)TZ*=28/53/17/202337浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系課后作業(yè)2.9（1）3/17/202338浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系2.5靈敏度分析Cj變化時bi變化時增加一個變量xj時增加一個約束條件時技術(shù)系數(shù)Pj發(fā)生變化時3/17/202339浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系LP變化導(dǎo)致的變化可分為：X*不變，Z*改變X*中基變量不變，取值改變，Z*改變。X*中基變量改變，Z*改變XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-13/17/202340浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系一、分析cj變化當(dāng)CNj發(fā)生變化時，對應(yīng)的δNj變化δNj≤0X*,Z*不變δNj＞0用單純形法進行基變換XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-1當(dāng)CBi發(fā)生變化時，所有δNj變化δNj≤0X*不變,Z*變化δNj＞0用單純形法進行基變換3/17/202341浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系例5：美佳公司1.當(dāng)C1由2變?yōu)?.5時，當(dāng)C2由1變?yōu)?時，最優(yōu)解有什么變化？2.當(dāng)C1不變，C2在什么范圍內(nèi)變換時，最優(yōu)解不變？Cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj000-1/4-1/2解：1Cj1.52000CBXBbx1x2x3x4x50x46004/51-61.5x1210-1/5012x23011/500σj00-1/100-3/21.51.51/8-9/4[]22解：2Cj21000CBXBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj000-1/4-1/2c2c2δ4δ5δ4=（c2-2）/4≤0δ5=（2－3c2）/2≤02/3≤c2≤23/17/202342浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系二、分析bi變化該變化只會引起右側(cè)常數(shù)的變化：B-1b≥0則基變量不變，X*的取值變化，Z*變化B-1b＜0用對偶單純形法進行基變換XBXNXSXSBNIbXBIB-1NB-1B-1bδ0CN-CBB-1N-CBB-13/17/202343浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系例6：美佳公司1.當(dāng)其他能力不變，B設(shè)備由24變?yōu)?2時，最優(yōu)解有什么變化？2.當(dāng)A,B不變，調(diào)試工序能力在什么范圍內(nèi)變換時，基變量不變？Cj21000CBXBbx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2σj000-1/4-1/2解：1：Cj21000CBXBbx1x2x3x4x50x315051002x15110010x420-401-6σj0-100-2[]解：24≤b3≤63/17/202344浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系三