對(duì)偶線性規(guī)精品課件

1、對(duì)偶線性規(guī)第1頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三本章學(xué)習(xí)要求掌握對(duì)偶理論及其性質(zhì)掌握影子價(jià)格的應(yīng)用掌握對(duì)偶單純形法熟悉靈敏度分析的概念和內(nèi)容掌握右側(cè)常數(shù)，價(jià)值系數(shù)，工藝系數(shù)的變換對(duì)原最優(yōu)解的影響掌握增加新變量和增加新約束條件對(duì)原最優(yōu)解的影響，并求出相應(yīng)因素的靈敏度范圍第2頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/162浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.1線性規(guī)劃的對(duì)偶問題問題的提出對(duì)稱形式下對(duì)偶問題的一般形式非對(duì)稱形式下的原問題與對(duì)偶問題的關(guān)系第3頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/163浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)

2、院管工系一、對(duì)偶問題的提出每一個(gè)LP問題，都伴隨著另一個(gè)LP，而且二者有密切關(guān)系，互為對(duì)偶，另其中一個(gè)問題為原問題，另一個(gè)問題為對(duì)偶問題，只要得到了其中一個(gè)問題的解（目標(biāo)值），也得到另一問題的解，因此通常只求解一個(gè)問題就可以了。例1：（美佳公司）美佳公司應(yīng)如何生產(chǎn)安排，使已有資源利潤最大化。某公司至少該出多大代價(jià)，使美佳公司愿意放棄自己的資源，產(chǎn)品資源資源約束A0515B6224調(diào)試工序115單位產(chǎn)品利潤21產(chǎn)品資源AB調(diào)試工序單位資源利潤06125211資源量15245第4頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/164浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系數(shù)學(xué)模型Cj2

3、1000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2cj-15-24-500-MCBYBby1y2y3y4y5y6-My62061-1011/3-15y11/512/51/50-1/505/2j06M-18M-2-M-30-24y21/3011/6-1/601/62-15y11/5102/151/15-1/5-1/151/2j001-3-3-M+8-24y21/4-5/410-1/41/41/2-5y31/215/2011/2-3/2-3j-15/200-7/2-3/2-M-3Z*=

4、8.5W*=8.5第5頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/165浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系二、對(duì)偶問題的一般形式 一般認(rèn)為變量均為非負(fù)約束的情況下，約束條件在目標(biāo)函數(shù)取Max時(shí)均取“”號(hào)；當(dāng)目標(biāo)函數(shù)求Min值時(shí)均取“號(hào)。則稱這些線性規(guī)劃問題具有對(duì)稱性。max z=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0min w=b1y1+b2y2+bmyms.t. a11y1+a21y2+am1ym c1 a12y1+a

5、22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1, y2, , ym 0Max Z=CX s.t. AXb X0Minw=Yb s.t. AYC Y0第6頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/166浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系原問題max z=CXs.t. AXb X 0對(duì)偶問題min w=Ybs.t. AYCY 0maxbCCATbminmnmnA第7頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/167浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系舉例：maxZ=3x1+2x2 s.t. -x1+2x24 3x1+2x214

6、 x1-x2 3 x1,x20minw=4y1+14y2+y3 s.t. -y1+3y2+y33 2y1+2x2-y32 y1,y2,y30y1y2y3第一種資源第二種資源第三種資源第一種產(chǎn)品 第二種產(chǎn)品x1x2第8頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/168浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系原始問題為min z=2x1+3x2-x3s.t. x1+2x2+x36 2x1-3x2+2x39 x1, x2, x30根據(jù)定義，對(duì)偶問題為max y=6y1+9y2s.t. y1+2y22 2y1- 3y23 y1+2y2-1 y1, y20原始問題是極小化問題原始問題的約

7、束全為原始問題有3個(gè)變量，2個(gè)約束原始問題的變量全部為非負(fù)對(duì)偶問題是極大化問題對(duì)偶問題的約束全為對(duì)偶問題有2個(gè)變量，3個(gè)約束原始問題的變量全部為非負(fù)第9頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/169浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系對(duì)偶問題的對(duì)偶max z=6x1+9x2s.t. x1+2x22 2x1- 3x23 x1+2x2-1 x1, x20minw=2y1+3y2-y3s.t. y1+2y2+y36 2y1-3y2+2y39 y1, y2, y30對(duì)偶問題的對(duì)偶就是原始問題。兩個(gè)問題中的任一個(gè)都可以作為原始問題。另一個(gè)就是它的對(duì)偶問題。根據(jù)定義寫出對(duì)偶問題根據(jù)

8、定義寫出對(duì)偶問題max u=6w1+9w2s.t. w1+2w22 2w1- 3w23 w1+2w2-1 w1, w20第10頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1610浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系對(duì)偶問題的性質(zhì)總結(jié)對(duì)偶的對(duì)偶就是原始問題max z=CXs.t. AXb X 0min w=Ybs.t. ATY CY0對(duì)偶的定義max u=CWs.t. AWCW 0第11頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1611浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系maxZ=x1+4x2+2x3 s.t. 5x1-x2+2x38 x1+3x2-3x

9、35 x1,x2,x30minw=8y1+5y2 s.t. 5y1+y21 -y1+3y24 2y1-3y2 2 y1,y20第12頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1612浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系三、非對(duì)稱形式的原對(duì)偶問題minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x45 2x1 +2x3-x44 x2+x3+x4=6 x10,x2,x30minz=-2x1+3x2-5x3+(x4-x4”)1+x2-3x3+(x4-x4”)5 2x1 -2x3+(x4-x4”)-4 x2+x3 +(x4-x4”) 6 -x2-x3-(x4-

10、x4”) -6 x1,x2,x3 ,x4,x4” 0變?yōu)閷?duì)稱形式y(tǒng)1y2y3y3”maxw=5y1-4y2+6(y3-y3”)1+2y2 -2 y1 +(y3-y3”) 3 -3y1-2y2+(y3-y3”) -5 y1+y2+(y3-y3”) 1 - y1-y2-(y3-y3”) - 1 y1,y2 ,y3,y3”0寫出對(duì)偶問題maxw=5y1+4y2+6y3 s.t. y1+2y2 2 y1 +y3 3 -3y1+2y2+y3 -5 y1 -y2 +y3 = 1 y10 ,y20,y3無約束第13頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1613浙江科技學(xué)院經(jīng)濟(jì)

11、管理學(xué)院管工系結(jié)論LP(LD)MaxX0X0X無約束St st St=LD(LP)Minst St St=Y0Y0Y無約束第14頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1614浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=Fre

12、e=x10 x20 x3: Free原始問題變量的個(gè)數(shù)(3)等于對(duì)偶問題約束條件的個(gè)數(shù)(3)；原始問題約束條件的個(gè)數(shù)(4)等于對(duì)偶問題變量的個(gè)數(shù)(4)。原始問題變量的性質(zhì)影響對(duì)偶問題約束條件的性質(zhì)。原始問題約束條件的性質(zhì)影響對(duì)偶問題變量的性質(zhì)。寫對(duì)偶問題的練習(xí)（1）第15頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1615浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系寫對(duì)偶問題的練習(xí)（2）原始問題max z=2x1-x2+3x3-2x4s.t. x1 +3x2 - 2x3 + x412 -2x1 + x2 -3x48 3x1 - 4x2 +5x3 - x4 = 15 x10, x2:

13、Free, x30, x40min w=12y1+8y2+15y3s.t. y1 2y2 + 3y32 3y1 + y2 4y3=-1 -2y1 +5y33 y1 3y2 - y3-2 y10,y20, y3:Free對(duì)偶問題第16頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1616浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系maxZ=x1-2x2+3x3 s.t. 2x1+4x2+3x3100 3x1-2x2+6x3200 5x1+3x2+4x3=150 x1, x30練習(xí)minw=100y1+200y2+150y3 s.t. 2y1+3y2+5y31 4y1-2y2+3y3=

14、-2 3y1+6y2+4y33 y10,y20minZ=2x1+2x2+4x3 s.t. x1+3x2+4x32 2x1+ x2+3x33 x1+4x2+3x3=5 x1 0, x20maxw=2y1+3y2+5y3 s.t. y1+2y2+ y32 3y1+ y2+4y3 2 4y1+3y2+3y34 y10,y20第17頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1617浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系課后作業(yè)P74 2.1(4)第18頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1618浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.2 對(duì)偶問題的基本性

15、質(zhì)單純形法的矩陣描述對(duì)偶問題的基本性質(zhì)第19頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1619浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系一、單純形法計(jì)算的矩陣描述Max Z=CX AXb X0Max Z=CX AX+Xs=b X 0,Xs0引入松弛變量令X=(XB,XN)T C=(CB,CN) A=(B,N) BXB+NXN+XS=bB-1BXB+B-1NXN+B-1XS=B-1bXB=B-1b-B-1NXN-B-1XS MaxZ=CB(B-1b-B-1NXN-B-1XS)+CNXN =CBB-1b（CN-CBB-1N)XN-CBB-1XS第20頁，共49頁，2022年，5月2

16、0日，1點(diǎn)58分，星期三2022/9/1620浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系某一決策變量xk系數(shù)列向量迭代前為Pk，迭代后為B-1Pk。當(dāng)B為最優(yōu)基時(shí)MaxZ=CBB-1b（CN-CBB-1N)XN-CBB-1XS令Y=CBB-1由此可以看出，當(dāng)X為最優(yōu)解時(shí)，Y為對(duì)偶問題的可行解。且該可行解對(duì)應(yīng)的目標(biāo)函數(shù)值W=Yb=CX*第21頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1621浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系非基變量基變量XBXNXs0XsbBNIcj-zjCBCN0基變量非基變量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1對(duì)

17、應(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。第22頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1622浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系二、對(duì)偶問題的基本性質(zhì)原始問題max z=CXs.t. AXb X 0對(duì)偶問題min w=Ybs.t. AY CY 01.弱對(duì)偶性若X0為原問題的可行解，Y0為對(duì)偶問題的可行解，則恒有CX0Y0b證

18、明：X0 0為LP的可行解，Y0 0為LD的可行解，則有： AX0 b AY0 C Y0AX0 Y0b (AY0)X0 (C)X0 Y0b Y0AX0 CX0第23頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1623浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系推論: (LP-Max LD-Min)1.LP任一可行解的目標(biāo)函數(shù)是其LD目標(biāo)函數(shù)值的下界，反之LD任一可行解的目標(biāo)函數(shù)是其LP目標(biāo)函數(shù)的上界。Z=CXMaxZ=MinW Yb2.如LP有可行解且目標(biāo)函數(shù)值無界，則其LD無可行解；反之LD有可行解且目標(biāo)函數(shù)無界，則LP無可行解。(對(duì)偶問題無可行解時(shí)，其原問題無界解或無可行解。)

19、Z=CX+ Yb W= Yb - CX3.若LP有可行解而其LD無可行解時(shí)，LP目標(biāo)函數(shù)無界反之，若LD有可行解而其LP無可行解時(shí)，LD目標(biāo)函數(shù)無界。第24頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1624浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.最優(yōu)性若X0為LP的可行解，Y0為LD的可行解，且CX0Y0b,則X0，Y0分別為LP和LD的最優(yōu)解。證明：設(shè)LP的最優(yōu)解為X*,LD的最優(yōu)解為Y*又因?yàn)椋篊X* CX0=Y0b Y*b又由弱對(duì)偶性定理：CX Yb則X0必為X*,Y0必為Y*3.強(qiáng)對(duì)偶性若原問題和對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等

20、。第25頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1625浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系4.互補(bǔ)松弛定理如果X*,Y*分別為LP,LD問題的可行解，則X*,Y*為最優(yōu)解的充要條件為：Y*XS*=0YS*X*=0 當(dāng)LP中第i個(gè)約束是嚴(yán)格不等式，則Y中的Yi必為0，如果Yi不為0,則LP中第i個(gè)約束為嚴(yán)格等式。 當(dāng)LD中第j個(gè)約束是嚴(yán)格不等式，則X中的xj必為0，如果xj不為0,則LD中第j個(gè)約束為嚴(yán)格等式。第26頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1626浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系課堂作業(yè)P74 2.3課后作業(yè)(P75-P76)

21、2.4 2.5 2.6 2.7第27頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1627浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.3 影子價(jià)格闡述對(duì)偶變量的經(jīng)濟(jì)意義，即對(duì)偶變量的經(jīng)濟(jì)解釋引例：美佳公司如果已知LP的X*=(7/2,3/2,15/2,0,0) Z*=8.5求解Y*,W*？由對(duì)偶問題的基本性質(zhì)知：W*=Z*=8.5 15Y1+24y2+5y3=8.5又因?yàn)閅*XS*=0 X*代入LP的約束條件中，知為嚴(yán)格不等式，則xS10，則y1=0由互補(bǔ)松弛定理：因?yàn)閅S*X*=0 X10,X20則yS1*=0, yS2*=0 ，即LD的，為嚴(yán)格等式6y2+y3=25y1+2y

22、2+y3=1 Y1=0 Y2=1/4 y3=1/2第28頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1628浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系1.定理：根據(jù)對(duì)偶問題的基本性質(zhì)對(duì)LP為生產(chǎn)問題而言： bi表示LP中第i種資源的擁有量； Cj表示第j種產(chǎn)品的利潤或產(chǎn)值其中Yi*可用下面數(shù)學(xué)式求得：1）yi*可解釋為第i種資源的邊際價(jià)格，即在其他條件不變的情況下，只增加單位第i種資源所引起的目標(biāo)函數(shù)最優(yōu)值的變化，bibi+1, bi=1， Z*的值為yi*。2） yi*也可解釋為出讓單位第i種資源的收益；3）yi*的取值隨cj,xj,Aij的變化而變化，因此企業(yè)不同，產(chǎn)業(yè)不同，

23、資源擁有量不同，yi*的值不同，是具體企業(yè)，具體產(chǎn)品和具體資源擁有量的特定價(jià)格。第29頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1629浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例：美佳公司X*=(7/2,3/2,15/2,0,0) Z*=8.5由1）可知：y1*為變?yōu)?x216時(shí)Z*的增量，y1* Z*0Y2*為變?yōu)?x12x225時(shí)Z*的增量所以當(dāng)A的資源增加時(shí)，Z*無變化，Y1*0LP中約束為嚴(yán)格的不等式，表明A沒有被充分利用。第30頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1630浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.影子價(jià)格的應(yīng)用（對(duì)偶問題的應(yīng)

24、用）1）yi*實(shí)際上是一種機(jī)會(huì)成本，當(dāng)A的單位市場價(jià)格無論多低時(shí)，還應(yīng)賣出A資源，直到15/2；當(dāng)B的單位市場價(jià)格0表明該資源已充分利用，因此該資源的增加或減少均會(huì)引起Z*的變動(dòng)，Yi*越大，變動(dòng)越大。由美佳可得：Y1=0表明A沒有充分利用，y2=1/4,y3=1/2表明y3的變動(dòng)對(duì)美佳公司利益的影響要大。 3）新產(chǎn)品是否投產(chǎn)以及合理定價(jià)的問題例：美佳考慮生產(chǎn)電器，要耗A 3 ，B 2，調(diào)試1個(gè)單位，市場價(jià)格2元，問是否值得生產(chǎn)。又如果美佳決定生產(chǎn)該種產(chǎn)品，則要定價(jià)多少該公司才不會(huì)虧本。第31頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1631浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院

25、管工系4）合理調(diào)配資源因?yàn)橛白觾r(jià)格是資源在特點(diǎn)環(huán)境下的價(jià)值，隨環(huán)境的變化而變化，同一資源在有些使用中價(jià)值低，有些使用中價(jià)值高。例：美佳公司有兩個(gè)子公司（1）A0 B 1/4 C 1/2(2) A2 B 0 C 1因此： （1） （2） A A B B C C第32頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1632浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系課后作業(yè)P76 2.8第33頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1633浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.4 對(duì)偶單純形法一、基本思路從LP的一個(gè)基解出發(fā)，轉(zhuǎn)換到另一個(gè)基解；在轉(zhuǎn)換過程中，保持對(duì)

26、應(yīng)的LD的解Y的可行性（相當(dāng)于LP的j0），逐步消除該基解的不可行性，直到基解變成可行解，就獲得了最優(yōu)解。注：該方法不是求解LD的單純形法，而是利用對(duì)偶關(guān)系求解LP的另一種方法。第34頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1634浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系二、計(jì)算步驟：1.假定已給一對(duì)偶可行基單位陣B（對(duì)應(yīng)LD問題的解可行），相應(yīng)的基解XBb。2.若b的各個(gè)分量均非負(fù)，則這個(gè)解就是最優(yōu)解，停止迭代。3.如果XB有分量xl0，且xl所在行的所有系數(shù)alj0，則LP無可行解，停止迭代。 如果XB有分量xl0，且該分量所在行的系數(shù)alj有負(fù)分量，則該解不是LP的最

27、優(yōu)解，繼續(xù)。4.如果min bi/ bi0bl，則xl為換出變量minj /alj|alj0= k/alk,則xk為換入變量5.以alk為主元，進(jìn)行系數(shù)行變換，得一新的對(duì)偶可行基解(也稱正則解），轉(zhuǎn)第2步。第35頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1635浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系比較單純形法和對(duì)偶單純形法單純形法：先從基解、可行解出發(fā)，通過若干次迭代使?jié)M足j0對(duì)偶單純形法:先從基解， 對(duì)偶可行解（等價(jià)于j0）出發(fā)，再通過若干次迭代使之可行。對(duì)偶單純形法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn):初始基解可為負(fù)，減少人工變量數(shù)量，使計(jì)算簡單；靈敏度分析時(shí)使用方便。缺點(diǎn)：不能保證所有的

28、Lp問題的初始單純形表中的j0。第36頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1636浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例:cj-2-3-400CBXBbx1x2x3x4x50X4-3-1-2-1100 x5-4-21-301j-2-3-40014/3 0 x4-2x112-1/23/20-1/2-10-5/21/21-1/2j0-2-10-14/52-3x2-2x1 12/50-1/5-2/51/511/5107/5-1/5-2/5j00-9/5-8/5-1/5所以：X*=(x1,x2)T=(11/5,2/5)T Z*=28/5第37頁，共49頁，2022年，5月2

29、0日，1點(diǎn)58分，星期三2022/9/1637浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系課后作業(yè)2.9（1）第38頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1638浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.5 靈敏度分析Cj變化時(shí)bi變化時(shí)增加一個(gè)變量xj時(shí)增加一個(gè)約束條件時(shí)技術(shù)系數(shù)Pj發(fā)生變化時(shí)第39頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1639浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系LP變化導(dǎo)致的變化可分為：X*不變，Z*改變X*中基變量不變，取值改變，Z*改變。X*中基變量改變，Z*改變XBXNXSXSBNIbXBIB-1NB-1B-1b0CN-CBB-1N

30、-CBB-1第40頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1640浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系一、分析cj變化當(dāng)CNj發(fā)生變化時(shí)， 對(duì)應(yīng)的Nj變化Nj0 X*,Z*不變Nj0 用單純形法進(jìn)行基變換XBXNXSXSBNIbXBIB-1NB-1B-1b0CN-CBB-1N-CBB-1當(dāng)CBi發(fā)生變化時(shí)， 所有Nj變化Nj0 X*不變,Z*變化Nj0 用單純形法進(jìn)行基變換第41頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1641浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例5：美佳公司1.當(dāng)C1由2變?yōu)?.5時(shí)， 當(dāng)C2由1變?yōu)?時(shí)，最優(yōu)解有什么變化？2.

31、當(dāng)C1不變，C2在什么范圍內(nèi)變換時(shí)，最優(yōu)解不變？Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2解：1Cj1.52000CBXBbx1x2x3x4x50 x46004/51-61.5x1210-1/5012x23011/500j00-1/100-3/21.51.51/8-9/4 22解：2Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2j000-1/4-1/2c2c2454=（

32、c2-2）/405=（23c2）/2 02/3c22第42頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1642浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系二、分析bi變化該變化只會(huì)引起右側(cè)常數(shù)的變化：B-1b0 則基變量不變，X*的取值變化，Z*變化B-1b 0 用對(duì)偶單純形法進(jìn)行基變換XBXNXSXSBNIbXBIB-1NB-1B-1b0CN-CBB-1N-CBB-1第43頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1643浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系例6：美佳公司1.當(dāng)其他能力不變，B設(shè)備由24變?yōu)?2時(shí)，最優(yōu)解有什么變化？2.當(dāng)A,B不變，調(diào)試工序能力在什么范圍內(nèi)變換時(shí)，基變量不變？Cj21000CBXBbx1x2x3x4x50 x335/20015/4-15/22x111/21001/4-1/21x2-1/2010-1/43/2j000-1/4-1/2解：1：Cj21000CBXBbx1x2x3x4x50 x315051002x15110010 x420-401-6j0-100-2 解：24b36第