對偶理論與靈敏度分析

關(guān)于對偶理論與靈敏度分析第一頁，共四十二頁，2022年，8月28日

第一章例1中：美佳公司利用自身資源生產(chǎn)兩種家電產(chǎn)品，其線形規(guī)劃問題表示為：maxz=2x1+x2

5x2≤15

St.6x1+2x2≤24

x1

＋x2≤5

x1、x2≥0

現(xiàn)假定有某公司想把美佳公司的資源買過來，它至少應(yīng)付出多大代價，才能使美佳公司愿意放棄生產(chǎn)活動，出讓自己的資源。設(shè)y1、y2和y3代表單位時間設(shè)備A、設(shè)備B和調(diào)試工序的出讓代價，則6y2＋y3≥2、5y1+2y2+y3≥1；另外要求，minz=15y1+24y2+5y3，且y1、y2、y3≥0即minz=15y1+24y2+5y36y2＋y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.§2.1線性規(guī)劃的對偶問題對偶問題的提出第二頁，共四十二頁，2022年，8月28日maxz=2x1+x2

5x2≤156x1+2x2≤24

x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.對稱形式的對偶問題對稱形式變量非負，求極大時約束條件取≤號、求極小時約束條件取≥號.Maxz=(2,1)x1x205211x1x2≤15245(x1x2)T≥0

minw=(15,24,5)y1y2y3061521y1y2y3≥21(y1y2y3)T≥0

第三頁，共四十二頁，2022年，8月28日Maxz=CXAX≤bX≥0st.minw=YTbATY≥CTY≥0st.Maxz=c1

x1+c2

x2+…….+cnxna11x1+a12

x2+……..+a1n

xn≤b1

a21x1+a22

x2+……..+a2n

xn≤b2

…………………am1x1+am2

x2+……..+amnxn≤bmx1,x2,……xn≥0Minw=b1

y1+b2

y2+…….+bmyma11y1+a21

y2+……..+am1

ym≥c1

a12y1+a22

y2+……..+am2

ym≥c2…………………a1ny1+a2n

y2+……..+amn

ym≥cny1,y2,……ym≥0對稱形式的對偶問題第四頁，共四十二頁，2022年，8月28日1,若原問題目標是求極大化，則對偶問題的目標是極小化，反之亦然。2,原問題的約束系數(shù)矩陣與對偶問題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣。3,極大化問題的每個約束對應(yīng)于極小化問題的一個變量，其每個變量對應(yīng)于對偶問題的一個約束。4,原問題與對偶問題互為對偶問題。對偶問題的特點Maxz=CXAX≤bX≥0St.Minz'=-CX-AX≥-bX≥0st.Maxw'=-YTb-ATY≤-CTY≥0st.minw=YTbATY≥CTY≥0st.求對偶標準化求對偶標準化第五頁，共四十二頁，2022年，8月28日非對稱形式的對偶問題maxz=2x1+x2

5x2≤156x1+2x2≤24

x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.第六頁，共四十二頁，2022年，8月28日原問題對偶問題目標函數(shù)maxmin目標函數(shù)約束條件≤≥=≥≤無約束變量變量≥≤無約束≥≤

=約束條件非對稱形式的對偶問題第七頁，共四十二頁，2022年，8月28日若互為對偶的線性規(guī)劃分別有可行解則其相應(yīng)的目標函數(shù)值滿足性質(zhì)1弱對偶性§2.2對偶問題的基本性質(zhì)第八頁，共四十二頁，2022年，8月28日推論1

極大化問題的任意一個可行解所對應(yīng)的目標函數(shù)值是其對偶問題最優(yōu)目標函數(shù)值的一個下界。

推論2

極小化問題的任意一個可行解所對應(yīng)的目標函數(shù)值是其對偶問題最優(yōu)目標函數(shù)值的一個上界。推論推論3

若原始問題可行，則其目標函數(shù)無界的充要條件是對偶問題沒有可行解。第九頁，共四十二頁，2022年，8月28日若X和Y分別是互為對偶的線性規(guī)劃的可行解，且使CX=Yb，則X和Y分別是相應(yīng)線性規(guī)劃問題的最優(yōu)解。性質(zhì)2：最優(yōu)性準則若原始問題和對偶問題兩者均可行，則兩者均有最優(yōu)解，且此時目標函數(shù)值相同。若原問題最優(yōu)基為B，則其對偶問題最優(yōu)解Y*=CBB-1性質(zhì)3：強對偶性（對偶定理）第十頁，共四十二頁，2022年，8月28日性質(zhì)4：互補松弛性最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。maxz=2x1+x2

5x2≤156x1+2x2≤24

x1+x2≤5x1、x2≥0St.最優(yōu)解X*=(x1,x2,x3,x4,x5)

＝(7/2,3/2,15/2,0,0)minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.最優(yōu)解y*=(y1,y2,y3,y4,y5)

＝(0,1/4,1/2,0,0)y1＝0y2＝1/4y3＝1/2x1＝7/2x2＝3/2第十一頁，共四十二頁，2022年，8月28日§2.3影子價格maxz=2x1+x2

5x2≤156x1+2x2≤24

x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.最優(yōu)解X*=(x1,x2,x3,x4,x5)＝(7/2,3/2,15/20,0)，最優(yōu)值:Z*=17/2最終表21000CB

基bx1

x2x3x4x5021x3

x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cj－zj000-1/4-1/2原問題對偶問題最終表-15-24-500CB

基by1

y2y3y4y5-24-5y2

y31/41/2-5/415/21001-1/41/21/4-3/2cj－zj-15/200-7/2-3/2最優(yōu)解y*=(y1,y2,y3,y4,y5)＝(0,1/4,1/2,0,0)，最優(yōu)值:Z*=17/2第十二頁，共四十二頁，2022年，8月28日當線形規(guī)劃原問題與對偶問題同時取得最優(yōu)解時，其對偶最優(yōu)解y＊i

代表在資源最優(yōu)利用條件下對單位第i種資源的估價，這個估價稱為這種資源的影子價格。其經(jīng)濟意義是：在其它條件不變的情況下，單位資源變化所引起的目標函數(shù)的最優(yōu)值的變化。第十三頁，共四十二頁，2022年，8月28日原問題是利潤最大化的生產(chǎn)計劃問題Maxz=c1

x1+c2

x2+…….+cnxna11x1+a12

x2+……..+a1n

xn+xn+1=b1

a21x1+a22

x2+……..+a2n

xn+xn+2=b2

……………..……am1x1+am2

x2+……..+amnxn+xn+m=bmx1,x2,……xn+m≥0總利潤（元）單位產(chǎn)品的利潤（元/件）產(chǎn)品產(chǎn)量（件）消耗的資源（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）資源限量（噸）第十四頁，共四十二頁，2022年，8月28日Minw=b1

y1+b2

y2+…….+bmyma11y1+a21

y2+……..+am1

ym–ym+1=c1

a12y1+a22

y2+……..+am2

ym–ym+2=c2…………….…a1ny1+a2n

y2+……..+amn

ym–ym+n=cny1,y2,……ym+n≥0資源價格（元/噸）資源限量（噸）總利潤（元）對偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價格（ShadowPrice）原始和對偶問題都取得最優(yōu)解時，最大利潤maxz=miny對偶問題是資源定價問題第十五頁，共四十二頁，2022年，8月28日1、影子價格依賴于資源的利用情況，各企業(yè)不同。影子價格的經(jīng)濟解釋2、影子價格表示的是資源的一種邊際價格。影子價格越大，說明這種資源越是相對緊缺；影子價格越小，說明這種資源相對不緊缺若某種資源影子價格為零，則說明此資源未得到充分利用；若不為零，則表明該資源得到充分利用。第十六頁，共四十二頁，2022年，8月28日y1y2ym增加單位資源可以增加的利潤減少一件產(chǎn)品可以節(jié)省的資源3、影子價格代表一種機會成本機會成本a1jy1+a2jy2+……aijyi+……amjym表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤第十七頁，共四十二頁，2022年，8月28日機會成本利潤差額成本4、產(chǎn)品的差額成本（ReducedCost）差額成本=機會成本-利潤第十八頁，共四十二頁，2022年，8月28日在利潤最大化的生產(chǎn)計劃中（1）邊際利潤大于0的資源沒有剩余（2）有剩余的資源邊際利潤等于0（3）安排生產(chǎn)的產(chǎn)品機會成本等于利潤（4）機會成本大于利潤的產(chǎn)品不安排生產(chǎn)影子價格的經(jīng)濟含義第十九頁，共四十二頁，2022年，8月28日在單純形法中，原問題的最優(yōu)解滿足：

（1）是基本解；

（2）可行；

（3）檢驗數(shù)≤0（YA≥C），即對偶解可行。單純形算法是從滿足（1）、（2）的一個基可行解出發(fā)，轉(zhuǎn)換到另一個基可行解，一直迭代到（3）得到滿足，即對偶解可行為止。對偶單純形法則是從滿足（1）、（3）的一個對偶可行解出發(fā)，以基變量值是否全非負為檢驗數(shù)，連續(xù)迭代到（2）得到滿足，即原問題的基解可行為止。兩種算法結(jié)果是一樣的，區(qū)別是對偶單純形法的初始解不一定可行，只要求所有檢驗數(shù)都非正，在保證所得解始終是對偶可行解的前提下，連續(xù)迭代到原問題的基解可行，從而取得問題的最優(yōu)解§2.4對偶單純形法第二十頁，共四十二頁，2022年，8月28日單純形法與對偶單純形法比較第二十一頁，共四十二頁，2022年，8月28日單純形法的步驟第二十二頁，共四十二頁，2022年，8月28日對偶單純形法的步驟第二十三頁，共四十二頁，2022年，8月28日如何用？第二十四頁，共四十二頁，2022年，8月28日例: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/5第二十五頁，共四十二頁，2022年，8月28日如何用？第二十六頁，共四十二頁，2022年，8月28日對應(yīng)B的基解：存在檢驗數(shù)>0不可行單純形法對偶單純形法？××第二十七頁，共四十二頁，2022年，8月28日用大M法求解或用兩階段法求解第二十八頁，共四十二頁，2022年，8月28日靈敏度分析的兩把尺子：σj=Cj-CBB-1pj≤0；

xB=B-1b≥0假設(shè)每次只有一種系數(shù)變化■價值系數(shù)C變化（單位產(chǎn)品利潤變化）■右端常數(shù)b變化（資源擁有量變化）§2.5靈敏度分析（Lindo求解）當系數(shù)A，b，C發(fā)生改變時，目前最優(yōu)基是否還最優(yōu)？為保持目前最優(yōu)基不變，系數(shù)A，b，C的允許變化范圍是什么？第二十九頁，共四十二頁，2022年，8月28日第一章例1中，若家電Ⅰ的利潤降至1.5元/件，家電Ⅱ的利潤增至2元/件，最優(yōu)生產(chǎn)計劃是否改變；原最終表1.52000CB

基bx1

x2x3x4x501.52x3

x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cj－zj0001/8-9/41.52000CB

基bx1

x2x3x4x501.52x4

x1x26230100014/5-1/51/5100-610cj－zj00-1/100-3/2價值系數(shù)變化C第三十頁，共四十二頁，2022年，8月28日右端常數(shù)變化b第一章例1中，若其它資源不變，而設(shè)備B的能力增加到32h，分析公司最優(yōu)計劃的變化；△b′=B-1△b=15/4-15/201/4-1/20-1/43/2080102-2=21000CB

基bx1

x2x3x4x5021x3

x1x215/2+107/2+23/2-20100011005/41/4-1/4-15/2-1/23/2cj－zj000-1/4-1/2020x3

x1x4155201051-410000101-6cj－zj0-100-2第三十一頁，共四十二頁，2022年，8月28日靈敏度分析Lindo第一章例1，美佳公司生產(chǎn)狀況如下表項目ⅠⅡ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤（元）21LPOPTIMUMFOUNDATSTEP2

OBJECTIVEFUNCTIONVALUE

1)8.500000

VARIABLEVALUEREDUCEDCOSTX13.5000000.000000X21.5000000.000000

ROWSLACKORSURPLUSDUALPRICES2)7.5000000.0000003)0.0000000.2500004)0.0000000.500000

NO.ITERATIONS=2max2x1+x2st2)5x2<=153)6x1+2x2<=244)x1+x2<=5end第三十二頁，共四十二頁，2022年，8月28日RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX12.0000001.0000001.000000X21.0000001.0000000.333333RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE215.000000INFINITY7.500000324.0000006.0000006.00000045.0000001.0000001.000000max2x1+x2st2)5x2<=153)6x1+2x2<=244)x1+x2<=5endTHETABLEAU

ROW(BASIS)X1X2SLK2SLK3SLK41ART0.0000.0000.0000.2500.5008.5002SLK20.0000.0001.0001.250-7.5007.5003X11.0000.0000.0000.250-0.5003.5004X20.0001.0000.000-0.2501.5001.500第三十三頁，共四十二頁，2022年，8月28日DAKOTA家具公司制造書桌、餐桌和椅子，所用的資源有三種：木料、木工和漆工。若要求桌子的生產(chǎn)量不超過5件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤最大？

每個書桌每個餐桌每個椅子資源總數(shù)木料8單位6單位1單位48單位漆工4單位2單位1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價60單位30單位20

用DESKS、TABLES和CHAIRS分別表示三種產(chǎn)品的生產(chǎn)量，建立LP模型，輸入如下。MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)2DESKS+1.5TABLES+0.5CHAIRS<=85)TABLES<=5END第三十四頁，共四十二頁，2022年，8月28日LPOPTIMUMFOUNDATSTEP2

OBJECTIVEFUNCTIONVALUE

1)280.0000

VARIABLEVALUEREDUCEDCOSTDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)24.0000000.0000003)0.00000010.0000004)0.00000010.0000005)5.0000000.000000

NO.ITERATIONS=2MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)2DESKS+1.5TABLES+0.5CHAIRS<=85)TABLES<=5END第三十五頁，共四十二頁，2022年，8月28日RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEDESKS60.00000020.0000004.000000TABLES30.0000005.000000INFINITYCHAIRS20.0000002.5000005.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE248.000000INFINITY24.000000320.0000004.0000004.00000048.0000002.0000001.33333355.000000INFINITY5.000000MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)2DESKS+1.5TABLES+0.5CHAIRS<=85)TABLES<=5END第三十六頁，共四十二頁，2022年，8月28日THETABLEAU

ROW(BASIS)DESKSTABLESCHAIRSSLK2SLK3SLK4SLK51ART0.0005.0000.0000.00010.00010.0000.000280.0002SLK20.000-2.0000.0001.0002.000-8.0000.00024.0003CHAIRS0.000-2.0001.0000.0002.000-4.0000.0008.0004DESKS1.0001.2500.0000.000-0.5001.5000.0002.0005SLK50.0001.0000.0000.0000.0000.0001.0005.000MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)2DESKS+1.5TABLES+0.5CHAIRS<=85)TABLES<=5END第三十七頁，共四十二頁，2022年，8月28日

奶制品加工廠用牛奶生產(chǎn)A1,A2兩種奶制品，1桶牛奶可以在甲車間用12小時加工成3公斤A1，或者在乙車間用8小時加工成4公斤A2。根據(jù)市場需求，生產(chǎn)的A1,A2全部能售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動時間480小時，并且甲車間每天至多能加工100公斤A1，乙車間的加工能力沒有限制。

試為該廠制訂一個生產(chǎn)計劃，使每天獲利最大，并進一步討論以下3個附加問題：

1）若用35元可以買到1桶牛奶，應(yīng)否作這項投資？若投資，每天最多購買多少桶牛奶？

2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？

3）由于市場需求變化，每公斤A1的獲利增加到30元，應(yīng)否改變生產(chǎn)計劃？

補充問題設(shè)用x1桶牛奶加工A1，用x2桶牛奶加工A2；maxz=72x1+64x2x1+x2≤5012x1+8x2≤4803x1≤100x1,x2≥0St.max72x1+64x2stmilk)x1+x2<=50time)12x1+8x2<=480shop)3x1<=100end第三十八頁，共四十二頁，2022年，8月28日LPOPTIMUMFOUNDATSTEP2

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIAB