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

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

2、院管工系一、對偶問題的提出每一個LP問題，都伴隨著另一個LP，而且二者有密切關(guān)系，互為對偶，另其中一個問題為原問題，另一個問題為對偶問題，只要得到了其中一個問題的解（目標(biāo)值），也得到另一問題的解，因此通常只求解一個問題就可以了。例1：（美佳公司）美佳公司應(yīng)如何生產(chǎn)安排，使已有資源利潤最大化。某公司至少該出多大代價，使美佳公司愿意放棄自己的資源，產(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é)院管工系二、對偶問題的一般形式 一般認(rèn)為變量均為非負(fù)約束的情況下，約束條件在目標(biāo)函數(shù)取Max時均取“”號；當(dāng)目標(biāo)函數(shù)求Min值時均取“號。則稱這些線性規(guī)劃問題具有對稱性。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對偶問題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ù)定義，對偶問題為max y=6y1+9y2s.t. y1+2y22 2y1- 3y23 y1+2y2-1 y1, y20原始問題是極小化問題原始問題的約

7、束全為原始問題有3個變量，2個約束原始問題的變量全部為非負(fù)對偶問題是極大化問題對偶問題的約束全為對偶問題有2個變量，3個約束原始問題的變量全部為非負(fù)第9頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/169浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系對偶問題的對偶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對偶問題的對偶就是原始問題。兩個問題中的任一個都可以作為原始問題。另一個就是它的對偶問題。根據(jù)定義寫出對偶問題根據(jù)

8、定義寫出對偶問題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é)院管工系對偶問題的性質(zhì)總結(jié)對偶的對偶就是原始問題max z=CXs.t. AXb X 0min w=Ybs.t. ATY CY0對偶的定義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é)院管工系三、非對稱形式的原對偶問題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)閷ΨQ形式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寫出對偶問題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原始問題變量的個數(shù)(3)等于對偶問題約束條件的個數(shù)(3)；原始問題約束條件的個數(shù)(4)等于對偶問題變量的個數(shù)(4)。原始問題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)。原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)。寫對偶問題的練習(xí)（1）第15頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1615浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系寫對偶問題的練習(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對偶問題第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 對偶問題的基本性

15、質(zhì)單純形法的矩陣描述對偶問題的基本性質(zhì)第19頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1619浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系一、單純形法計算的矩陣描述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)基時MaxZ=CBB-1b（CN-CBB-1N)XN-CBB-1XS令Y=CBB-1由此可以看出，當(dāng)X為最優(yōu)解時，Y為對偶問題的可行解。且該可行解對應(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對

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é)院管工系二、對偶問題的基本性質(zhì)原始問題max z=CXs.t. AXb X 0對偶問題min w=Ybs.t. AY CY 01.弱對偶性若X0為原問題的可行解，Y0為對偶問題的可行解，則恒有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無可行解。(對偶問題無可行解時，其原問題無界解或無可行解。)

19、Z=CX+ Yb W= Yb - CX3.若LP有可行解而其LD無可行解時，LP目標(biāo)函數(shù)無界反之，若LD有可行解而其LP無可行解時，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*又因為：CX* CX0=Y0b Y*b又由弱對偶性定理：CX Yb則X0必為X*,Y0必為Y*3.強(qiáng)對偶性若原問題和對偶問題均具有可行解，則兩者均具有最優(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個約束是嚴(yán)格不等式，則Y中的Yi必為0，如果Yi不為0,則LP中第i個約束為嚴(yán)格等式。 當(dāng)LD中第j個約束是嚴(yán)格不等式，則X中的xj必為0，如果xj不為0,則LD中第j個約束為嚴(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 影子價格闡述對偶變量的經(jīng)濟(jì)意義，即對偶變量的經(jīng)濟(jì)解釋引例：美佳公司如果已知LP的X*=(7/2,3/2,15/2,0,0) Z*=8.5求解Y*,W*？由對偶問題的基本性質(zhì)知：W*=Z*=8.5 15Y1+24y2+5y3=8.5又因為Y*XS*=0 X*代入LP的約束條件中，知為嚴(yán)格不等式，則xS10，則y1=0由互補(bǔ)松弛定理：因為YS*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ù)對偶問題的基本性質(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)值的變化，bibi+1, bi=1， Z*的值為yi*。2） yi*也可解釋為出讓單位第i種資源的收益；3）yi*的取值隨cj,xj,Aij的變化而變化，因此企業(yè)不同，產(chǎn)業(yè)不同，

23、資源擁有量不同，yi*的值不同，是具體企業(yè)，具體產(chǎn)品和具體資源擁有量的特定價格。第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時Z*的增量，y1* Z*0Y2*為變?yōu)?x12x225時Z*的增量所以當(dāng)A的資源增加時，Z*無變化，Y1*0LP中約束為嚴(yán)格的不等式，表明A沒有被充分利用。第30頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1630浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系2.影子價格的應(yīng)用（對偶問題的應(yīng)

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

25、管工系4）合理調(diào)配資源因為影子價格是資源在特點(diǎn)環(huán)境下的價值，隨環(huán)境的變化而變化，同一資源在有些使用中價值低，有些使用中價值高。例：美佳公司有兩個子公司（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 對偶單純形法一、基本思路從LP的一個基解出發(fā)，轉(zhuǎn)換到另一個基解；在轉(zhuǎn)換過程中，保持對

26、應(yīng)的LD的解Y的可行性（相當(dāng)于LP的j0），逐步消除該基解的不可行性，直到基解變成可行解，就獲得了最優(yōu)解。注：該方法不是求解LD的單純形法，而是利用對偶關(guān)系求解LP的另一種方法。第34頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1634浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系二、計算步驟：1.假定已給一對偶可行基單位陣B（對應(yīng)LD問題的解可行），相應(yīng)的基解XBb。2.若b的各個分量均非負(fù)，則這個解就是最優(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ù)行變換，得一新的對偶可行基解(也稱正則解），轉(zhuǎn)第2步。第35頁，共49頁，2022年，5月20日，1點(diǎn)58分，星期三2022/9/1635浙江科技學(xué)院經(jīng)濟(jì)管理學(xué)院管工系比較單純形法和對偶單純形法單純形法：先從基解、可行解出發(fā)，通過若干次迭代使?jié)M足j0對偶單純形法:先從基解， 對偶可行解（等價于j0）出發(fā)，再通過若干次迭代使之可行。對偶單純形法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn):初始基解可為負(fù)，減少人工變量數(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變化時bi變化時增加一個變量xj時增加一個約束條件時技術(shù)系數(shù)Pj發(fā)生變化時第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ā)生變化時， 對應(yīng)的Nj變化Nj0 X*,Z*不變Nj0 用單純形法進(jìn)行基變換XBXNXSXSBNIbXBIB-1NB-1B-1b0CN-CBB-1N-CBB-1當(dāng)CBi發(fā)生變化時， 所有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時， 當(dāng)C2由1變?yōu)?時，最優(yōu)解有什么變化？2.

31、當(dāng)C1不變，C2在什么范圍內(nèi)變換時，最優(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變化該變化只會引起右側(cè)常數(shù)的變化：B-1b0 則基變量不變，X*的取值變化，Z*變化B-1b 0 用對偶單純形法進(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時，最優(yōu)解有什么變化？2.當(dāng)A,B不變，調(diào)試工序能力在什么范圍內(nèi)變換時，基變量不變？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第