[學(xué)習(xí)]對(duì)偶理論和靈敏度分析(新)

1、1,對(duì)偶理論和靈敏度分析,對(duì)偶的定義原始對(duì)偶關(guān)系目標(biāo)函數(shù)值之間的關(guān)系最優(yōu)解之間的互補(bǔ)松弛關(guān)系對(duì)偶問(wèn)題的性質(zhì)對(duì)偶的經(jīng)濟(jì)解釋對(duì)偶單純形法靈敏度分析,DUAL,,2,第3節(jié) 線性規(guī)劃對(duì)偶問(wèn)題的提出,現(xiàn)有甲乙兩種原材料生產(chǎn)A1，A2兩種產(chǎn)品，所需的原料，甲乙兩種原料的可供量，以及生產(chǎn)A1,A2兩種產(chǎn)品可得的單位利潤(rùn)見(jiàn)表。問(wèn)如何安排生產(chǎn)資源使得總利潤(rùn)為最大？,3,解：設(shè)生產(chǎn)A1為x1件，生產(chǎn)A2為x2件，則線性規(guī)劃問(wèn)題為：,max

2、Z=4.5x1+5x2 s.t. 3x1+2x2≤24 4x1+5x2≤40 x1,x2≥0,假設(shè)現(xiàn)在不考慮生產(chǎn)產(chǎn)品，而是把甲乙兩種原材料賣掉，則問(wèn)題變成對(duì)于甲乙兩種原材料企業(yè)以多少最低價(jià)愿意出讓？,解：設(shè)甲資源的出讓價(jià)格為y1,乙資源的出讓價(jià)格為y2,minw=24y1+40y2 s.t. 3y1+4y2≥4.5 2y1+5

3、y2≥5 y1,y2≥0,,,,,,,,4,第4節(jié) 線性規(guī)劃的對(duì)偶理論——對(duì)偶問(wèn)題的一般形式 一般認(rèn)為變量均為非負(fù)約束的情況下，約束條件在目標(biāo)函數(shù)取極大值時(shí)均取“≤”號(hào)；當(dāng)目標(biāo)函數(shù)求極小值時(shí)均取“≥“號(hào)。則稱這些線性規(guī)劃問(wèn)題具有對(duì)稱性。,max z=c1x1+c2x2+……+cnxns.t. a11x1+a12x2+……+a1nxn ≤b1 a21x1+a22x2+……+a2nxn

4、 ≤b2 …… am1x1+am2x2+……+amnxn ≤bm x1, x2, ……, xn ≥0,min w=b1y1+b2y2+……+bmyms.t. a11y1+a21y2+……+am1ym ≥c1 a12y1+a22y2+……+am2ym ≥ c2 …… a1ny1+a2ny2+……+amnym ≥ cn y1, y2, ……, ym ≥0

5、,Max Z=CX s.t. AX≤b X≥0,Minw=Y’b s.t. A’Y≥C’ Y≥0,5,原始問(wèn)題max z=CXs.t. AX≤b X ≥0,對(duì)偶問(wèn)題min w=Y’bs.t. A’Y≥C’Y ≥0,,,,≥,max,b,A,C,,,,C,AT,b,≤,min,,,,,,,,,,,,,m,n,m,n,4.1原問(wèn)題與對(duì)偶問(wèn)題的

6、關(guān)系,6,舉例：,maxZ=3x1+2x2 s.t. -x1+2x2≤4 3x1+2x2≤14 x1-x2 ≤3 x1,x2≥0,minw=4y1+14y2+y3 s.t. -y1+3y2+y3≥3 2y1+2x2-y3≥2 y1,y2,y3≥0,y1,y2,y3,第一種資源,第二種

7、資源,第三種資源,第一種產(chǎn)品,第二種產(chǎn)品,x1,x2,,7,原始問(wèn)題為min z=2x1+3x2-x3s.t. x1+2x2+x3≥6 2x1-3x2+2x3≥9 x1, x2, x3≥0,根據(jù)定義，對(duì)偶問(wèn)題為max y=6y1+9y2s.t. y1+2y2≤2 2y1- 3y2≤3 y1+2y2≤-1 y1, y2≥0,原始問(wèn)題是極小化問(wèn)題原始問(wèn)

8、題的約束全為≥原始問(wèn)題有3個(gè)變量，2個(gè)約束原始問(wèn)題的變量全部為非負(fù),對(duì)偶問(wèn)題是極大化問(wèn)題對(duì)偶問(wèn)題的約束全為≤對(duì)偶問(wèn)題有2個(gè)變量，3個(gè)約束原始問(wèn)題的變量全部為非負(fù),原始問(wèn)題變量的個(gè)數(shù)(3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù)(3)原始問(wèn)題約束條件的個(gè)數(shù)(2)等于對(duì)偶問(wèn)題變量的個(gè)數(shù)(2),8,非對(duì)稱形式的原—對(duì)偶問(wèn)題,minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x4≥5 2x1

9、 +2x3-x4≤4 x2+x3+x4=6 x1≤0,x2,x3≥0,x2+x3+x4≥6x2+x3+x4≤6,,,-x1=x1’ ，x1’≥0;x4’-x4”=x4,x4’ ≥0,x4” ≥0,,minz=-2x1’+3x2-5x3+(x4’-x4”) s.t.-x1’+x2-3x3+(x4’-x4”)≥5 2x1’ -2x

10、3+(x4’-x4”)≥-4 x2+x3 +(x4’-x4”) ≥6 -x2-x3-(x4’-x4”) ≥-6 x1’,x2,x3 ,x4’,x4” ≥0,y1,y2’,y3’,y3”,maxw=5y1-4y2’+6(y3’-y3”) s.t.-y1+2y2’ ≤-2 y1 +(y3’-y3”)

11、 ≤3 -3y1-2y2’ +(y3’-y3”) ≤ -5 y1+y2’+(y3’-y3”) ≤ 1 -y1-y2’-(y3’-y3”) ≤-1 y1,y2’ ,y3’,y3”≥0,9,maxw=5y1-4y2’+6(y3’-y3”) s.t.-y1+2y2’ ≤-2 y1 +(y3’-y3”) ≤3

12、 -3y1-2y2’ +(y3’-y3”) ≤ -5 y1+y2’+(y3’-y3”) ≤ 1 -y1-y2’-(y3’-y3”) ≤-1 y1,y2’ ,y3’,y3”≥0,設(shè)y2=-y2’,y3=y3’-y3”,則y2≤0,y3無(wú)約束此時(shí)對(duì)偶問(wèn)題變?yōu)?maxw=5y1+4y2+6y3 s.t. y1+2y2 ≥2

13、 y1 +y3 ≤3 -3y1+2y2+y3 ≤ -5 y1 -y2 +y3 = 1 y1≥0 ,y2≤0,y3無(wú)約束,minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x4≥5 2x1 +2x3-x4≤ 4 x2+x3+x4

14、 = 6 x1≤0,x2,x3≥0,,,,,,,10,原 始 對(duì) 偶 表,,,,,,,11,對(duì)偶關(guān)系,1、極大與極小的對(duì)偶2、價(jià)值系數(shù)與資源系數(shù)的對(duì)偶3、約束條件系數(shù)矩陣的對(duì)偶是矩陣的轉(zhuǎn)置4、反向不等式與非正的決策變量的對(duì)偶5、等式與非負(fù)限制的決策變量的對(duì)偶6、最優(yōu)解與檢驗(yàn)數(shù)的對(duì)偶,12,min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2

15、x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max y=6w1+12w2+8w3+15w4s.t. 3w1- w2+2w3+ w4 2 -w1+2w2+ w3+3w4 4 2w1- 3w2+2w3- w4 -1 w1 0,w2 ,w3 0,w4 0,

16、≤,≥,=,≥,Free,≤,≥,≥,=,≤,≥,x1≥0,x2≤0,x3: Free,原始問(wèn)題變量的個(gè)數(shù)(3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù)(3)；原始問(wèn)題約束條件的個(gè)數(shù)(4)等于對(duì)偶問(wèn)題變量的個(gè)數(shù)(4)。原始問(wèn)題變量的性質(zhì)影響對(duì)偶問(wèn)題約束條件的性質(zhì)。原始問(wèn)題約束條件的性質(zhì)影響對(duì)偶問(wèn)題變量的性質(zhì)。,寫對(duì)偶問(wèn)題的練習(xí)（1）,13,寫對(duì)偶問(wèn)題的練習(xí)（2）,原始問(wèn)題,max z=2x1-x2+3x3-2x4s.t. x1 +3x2

17、- 2x3 + x4≤12 -2x1 + x2 -3x4≥8 3x1 - 4x2 +5x3 - x4 = 15 x1≥0, x2:Free, x3≤0, x4≥0,min y=12w1+8w2+15w3s.t. w1 - 2w2 + 3w3≥2 3w1 + w2 - 4w3=-1 -2w1 +5w3≤3 w1 - 3w2 - w3≥-2 w

18、1≥0,w2≤0, w3:Free,對(duì)偶問(wèn)題,14,maxZ=x1-2x2+3x3 s.t. 2x1+4x2+3x3≥100 3x1-2x2+6x3≤200 5x1+3x2+4x3=150 x1, x3≥0,練習(xí),minw=100y1+200y2+150y3 s.t. 2y1+3y2+5y3≥1 4y1-2y2+3y3= -2

19、 3y1+6y2+4y3≥3 y1≤0,y2≥0,minZ=2x1+2x2+4x3 s.t. x1+3x2+4x3≥2 2x1+ x2+3x3≤3 x1+4x2+3x3=5 x1 ≥0, x2≤0,maxw=2y1+3y2+5y3 s.t. y1+2y2+ y3≤2

20、 3y1+ y2+4y3≥ 2 4y1+3y2+3y3≥4 y1≥0,y2≤0,15,原始和對(duì)偶問(wèn)題可行解目標(biāo)函數(shù)值比較,min z=2x1+3x2s.t. x1+3x2≥3 2x1+x2 ≥4 x1, x2 ≥0,max w=3y1+4y2s.t. y1+2y2≤2 3y1+y2 ≤3 y1, y2 ≥0,16,單純形法

21、計(jì)算的矩陣描述,Max Z=CX AX≤b X≥0其中X＝(x1,x2……xn)T,Max Z=CX+0Xs AX+IXs=b X,Xs≥0其中Xs＝(xn+1,xn+2……xn+m)TI 為m×m的單位矩陣,17,對(duì)應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1；初始單純形表中基變量Xs=b，迭代后的

22、表中為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’。,18,當(dāng)B為最優(yōu)基時(shí)，XB為最優(yōu)解時(shí)，則有：,CN-CBB-1N≤0,-CBB-1≤0,∵CB-CBI=0,代入得：CN－CBB-1N+CB-CBI≤0C－CBB-1(B+N)≤0,整理得：C－CBB-1 A≤0

23、 -CBB-1≤0,令CBB-1為單純形乘子，Y‘＝CBB-1,則：C－Y’ A≤0 -Y’≤0,Y’ A≥C’ Y’ ≥0,,W＝Y(jié)’b=CBB-1b=Z,所以當(dāng)原問(wèn)題為最優(yōu)解時(shí)，對(duì)偶問(wèn)題為可行解且具有相同的目標(biāo)函數(shù)值。,19,maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 4x1+5x2≤40 x1,x2≥0,minw=24y

24、1+40y2 s.t. 3y1+4y2≥4.5 2y1+5y2≥5 y1,y2≥0,y1,y2,x1,x2,maxZ=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,≥0,minw=24y1+40y2 s.t. 3y1+4y

25、2-y3=4.5 2y1+5Y2-y4=5 y1,y2,y3,y4≥0,,20,,,解原問(wèn)題：,,21,,,,22,,,,23,,,Z=4.5×40/7＋5×24/7=300/7,,24,解對(duì)偶問(wèn)題：,w=24×5/14＋40×6/7=300/7,25,,,,,,,(x3,x4)=(0,0),,,,(y3,y4)=(0,0),,,,-y1,-

26、y2,-y4,-y3,x1,x2,x4,x3,,26,（1）對(duì)稱性：對(duì)偶問(wèn)題的對(duì)偶,max z=6x1+9x2s.t. x1+2x2≤2 2x1- 3x2≤3 x1+2x2≤-1 x1, x2≥0,minw=2y1+3y2-y3s.t. y1+2y2+y3≥6 2y1-3y2+2y3≥9 y1, y2, y3≥0,對(duì)偶問(wèn)題的對(duì)偶就是原始問(wèn)題。兩個(gè)問(wèn)題中的任一個(gè)都

27、可以作為原始問(wèn)題。另一個(gè)就是它的對(duì)偶問(wèn)題。,根據(jù)定義寫出對(duì)偶問(wèn)題,根據(jù)定義寫出對(duì)偶問(wèn)題,max u=6w1+9w2s.t. w1+2w2≤2 2w1- 3w2≤3 w1+2w2≤-1 w1, w2≥0,4.2對(duì)偶問(wèn)題的基本性質(zhì),27,maxZ=x1+4x2+2x3 s.t. 5x1-x2+2x3≤8 x1+3x2-3x3≤5

28、 x1,x2,x3≥0,minw=8y1+5y2 s.t. 5y1+y2≥1 -y1+3y2≥4 2y1-3y2 ≥2 y1,y2≥0,28,4.2 對(duì)偶問(wèn)題的基本性質(zhì),原始問(wèn)題max z=CXs.t. AX≤b X ≥0,對(duì)偶問(wèn)題min w=Y’bs.t. A’Y≥C’Y ≥0,（2）弱對(duì)偶性若X為原問(wèn)題的可行解

29、，Y為對(duì)偶問(wèn)題的可行解，則恒有CX≤Y’b,29,推論：原問(wèn)題任一可行解的目標(biāo)函數(shù)是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界，反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)是其原問(wèn)題目標(biāo)函數(shù)的上界。（3）無(wú)界性 如原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則其對(duì)偶問(wèn)題無(wú)可行解；反之對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)無(wú)界，則原問(wèn)題無(wú)可行解。（對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題無(wú)界解或無(wú)可行解。推論：若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解時(shí)，原問(wèn)題目標(biāo)函數(shù)無(wú)界

30、若對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解時(shí)，對(duì)偶問(wèn)題目標(biāo)函數(shù)無(wú)界。,30,maxZ=x1+x2 s.t. -x1+x2+x3 ≤2 -2x1+x2+x3 ≤ 1 x1,x2,x3,≥0,minw=2y1+y2 s.t. -y1-2y2 ≥ 1 y1+y2 ≥1 y1-y2 ≥0

31、y1,y2≥0,試用對(duì)偶理論證明上述線性規(guī)劃問(wèn)題無(wú)最優(yōu)解,例。已知線性規(guī)劃問(wèn)題,證：首先該問(wèn)題存在可行解。,可知對(duì)偶問(wèn)題無(wú)可行解，因原問(wèn)題有可行解，故無(wú)最優(yōu)解。,31,（4）最優(yōu)性若X為原問(wèn)題的可行解，Y為對(duì)偶問(wèn)題的可行解，且CX＝Y(jié)’b則X，Y分別為原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。,（5）強(qiáng)對(duì)偶性若原問(wèn)題和對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等。,32,（6）互補(bǔ)松弛定理在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)

32、某一約束條件的對(duì)偶變量值為0，則該約束條件取嚴(yán)格等式，既松弛變量或剩余變量為0；反之如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值不為0，則該約束條件取嚴(yán)格不等式，既松弛變量或剩余變量不為0.,若yi’ ＞0,則∑aijxj=bi，即xsi=0若yi’ ＝0,則∑aijxj＜bi，即xsi＞0即xsi·yi=0,同理若xj’ ＞0,則∑aijyi=cj，即ysj=0若xj’ ＝0,則∑aijyi＜cj，即ysj＞0即ysj&

33、#183;xj=0,33,maxZ=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,≥0,minw=24y1+40y2 s.t. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y4≥0,X3=0, 3x1+2x

34、2=24,y1=14/5X4=0,4x1+5x2=40,y2=6/7,y3=0, 3y1+4y2=5,x1=40/7y4=0, 2y1+5y2=5,x2=24/7,34,,利用互補(bǔ)松弛關(guān)系求解線性規(guī)劃,min z=6x1+8x2+3x3s.t. x1+ x2 ≥1 x1+2x2+x3 ≥-1 x1, x2, x3 ≥0,max w=y1-y2s.t. y1+ y2 ≤6 y

35、1+2y2 ≤8 y2 ≤3 y1,y2≥0,原始問(wèn)題,對(duì)偶問(wèn)題,,,,,最優(yōu)解為(y1, y2)=(6, 0)max y=6,先用圖解法求解對(duì)偶問(wèn)題。,35,min z=6x1+8x2+3x3s.t. x1+ x2 ≥1 x1+2x2+x3 ≥-1 x1, x2, x3 ≥0,max w=y1-y2s.t. y1+ y2 ≤6

36、y1+2y2 ≤8 y2 ≤3 y1, y2≥0,max w=y1-y2s.t. y1+y2+y3 =6 y1+2y2 +y4 =8 y2 +y5=3 y1, y2, y3, y4, y5≥0,(y1, y2)=(6,0),(y1,y2,y3,y4,y5)=(6, 0, 0, 2,

37、3),min z=6x1+8x2+3x3s.t. x1+ x2 -x4 =1 x1+2x2+x3 -x5 =-1 x1, x2, x3 ,x4, x5≥0,(x1, x2, x3 | x4, x5)(y1, y2 | y3, y4, y5),x2=x3=x4=0,x1=1, x5=2,,,(x1, x2, x3, x4, x5)=(1, 0, 0, 0, 2

38、),,36,第5節(jié) 對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋——資源的影子價(jià)格(Shadow Price),影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0,yi’=△w/△bi=最大利潤(rùn)的增量/第i種資源的增量=第i種資源的邊際利潤(rùn),w=b1y1+b2y2+…+biyi+…+bmym,w+△w=b1y1+b2y2+…+(bi+△bi)yi+…+bmym,△w=△

39、biyi,37,,,,,,,,,,,,,Z*=8.5X=(7/2,3/2),Z*=8.75X=(15/4,5/4),Z=9X=(3,3),maxZ=2x1+x2 s.t. 2x2≤15 6x1+2x2≤24 x1+x2≤5 x1,x2≥0,,思考:如果第一種資源增加1，也就是把15變?yōu)?6,目標(biāo)函數(shù)值將怎么變化?為什么?,38

40、,資源的影子價(jià)格是一種機(jī)會(huì)成本根據(jù)互補(bǔ)松弛定理,若yi’ ＞0,則∑aijxj=bi，若yi’ ＝0,則∑aijxj＜bi，,某種資源bi未得到充分利用時(shí)，該種資源的影子價(jià)格為0；當(dāng)資源的影子價(jià)格不為0，表示該種資源在生產(chǎn)中已消耗完畢。,σj=cj-zj=cj-CBB-1Pjcj表示第i種產(chǎn)品的產(chǎn)值，∑aijyi表示生產(chǎn)該種產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格的總和，即產(chǎn)品的隱含成本。,39,Maxz=4x1+10x2 s.t

41、. 3x1+6x2≤5 x1+3x2≤2 2x1+5x2≤4 x1,x2≥0,已知原問(wèn)題為：,則對(duì)偶問(wèn)題為：,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3≥4 6y1+3y2+5y3≥10 y1,y2,y3≥0,,Maxz=4x1+10x2 s.t. 3x1+6x2+

42、x3=5 x1+3x2 +x4=2 2x1+5x2 +x5=4 xj≥0(j=1,2,…,5),,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi≥0(i=1,2,…,5),40,初始單純形表為：,此時(shí)對(duì)偶問(wèn)題

43、的解為Y＝（0，0，0，－4，－10）代入,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi≥0(i=1,2,…,5),不是對(duì)偶問(wèn)題的可行解,,41,初始單純形表為：,此時(shí)對(duì)偶問(wèn)題的解為Y＝（0，0，0，－4，－10）代入,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3-y4=

44、4 6y1+3y2+5y3-y5=10 yi≥0(i=1,2,…,5),不是對(duì)偶問(wèn)題的可行解,,,,42,對(duì)原問(wèn)題進(jìn)行迭代得：,此時(shí)對(duì)偶問(wèn)題的解為Y＝（0，10/3，0，-2/3，0）代入,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi≥0(i=1,2,…,5

45、),不是對(duì)偶問(wèn)題的可行解,,43,對(duì)原問(wèn)題進(jìn)行迭代得：,此時(shí)對(duì)偶問(wèn)題的解為Y ＝（0，10/3，0，-2/3，0 ）代入,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi≥0(i=1,2,…,5),不是對(duì)偶問(wèn)題的可行解,,,,44,對(duì)原問(wèn)題進(jìn)行迭代得：,此時(shí)對(duì)偶問(wèn)題的解為Y＝（2/3，2，0，0，0）代入,M

46、inw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi≥0(i=1,2,…,5),是對(duì)偶問(wèn)題的可行解,45,單純形法求解的過(guò)程，從對(duì)偶的觀點(diǎn)來(lái)看，是在始終保持原始可行解的條件下，不斷改進(jìn)對(duì)偶可行性的過(guò)程。一個(gè)從對(duì)偶不可行的解，經(jīng)過(guò)幾次疊代，逐步向?qū)ε伎尚薪饪繑n，一旦得到的解既是原始可行的，又是對(duì)偶可行的，這個(gè)解就分別

47、是原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。,46,第6節(jié) 對(duì)偶單純形法,對(duì)于對(duì)偶單純形法剛好和單純形法的思路相反，就是在始終保持對(duì)偶問(wèn)題可行的條件下，不斷改進(jìn)原問(wèn)題可行性的過(guò)程。一個(gè)從原問(wèn)題不可行的解，經(jīng)過(guò)幾次疊代，逐步向原問(wèn)題可行解靠攏，一旦得到的解既是原始可行的，又是對(duì)偶可行的，這個(gè)解就分別是原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。,47,步驟：1.確定初始解一般設(shè)松弛變量為初時(shí)基可行解2.判斷 若所有的基變量值均≥0，則此解為線性規(guī)劃問(wèn)題

48、的最優(yōu)解，若存在基變量的值≤0，則問(wèn)題還沒(méi)有達(dá)到最優(yōu)解，需要進(jìn)行改進(jìn)。3.改進(jìn)選擇換出變量min{ bi’/ bi≤0}假設(shè)選取xk為換出變量選擇換入變量θ＝min{(cj-zj)arj|arj＜0,cj-zj＜0}則假設(shè)選取xl為換出變量4.迭代。使得alk＝1，其余aik為0,48,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3≥4 6y1+3y2+5y3≥10

49、 y1,y2,y3≥0,,舉例：,Maxw’=-5y1-2y2-4y3 s.t. -3y1- y2-2y3≤-4 -6y1-3y2-5y3≤-10 y1,y2,y3≥0,Maxw’=-5y1-2y2-4y3 s.t. -3y1- y2-2y3+y4=4 -6y1-3y2-5y3+y5=10 yi≥0(

50、i=1,2,…,5),,49,,,50,,51,,,,52,,,,53,54,,55,,,56,,,57,58,此時(shí)對(duì)偶問(wèn)題和原問(wèn)題都達(dá)到可行，所以均達(dá)到了最優(yōu)解Y＝（2/3.2,0,0,0)W’=-22/3W=22/3,59,Minw=2x1+3x2+4x3 s.t. x1+2x2+ x3≥3 2x1- x2+3x3≥4 x1,x2,x3≥0,,練習(xí):用對(duì)偶單純形法求

51、解并求出對(duì)偶變量的最優(yōu)解,Maxw’=-2x1-3x2-4x3 s.t. -x1- 2x2-x3≤-3 -2x1 +x2-3x3≤-4 x1,x2,x3≥0,Maxw’=-2x1-3x2-4x3 s.t. -x1-2x2-x3+x4=-3 -2x1 +x2-3x3 +x5=-4 xi≥0(i=1,

52、2,…,5),,60,此時(shí)對(duì)偶問(wèn)題和原問(wèn)題都達(dá)到可行，所以均達(dá)到了最優(yōu)解Y＝（11/5.2/5,0,0,0)W’=-28/5W=28/5,61,Maxz=3y1+4y2 s.t. y1+2y2≤2 2y1 -y2≤3 y1+3y2≤4 y1,y2≥0,Maxz=3y1+2y2 s.t. y1+2y2+y3＝2

53、 2y1 -y2+y4＝3 y1+3y2+y5＝4 yi≥0,62,對(duì)偶單純形法的特點(diǎn)：當(dāng)約束條件為“≥”時(shí)，不需要引入人工變量，從而使計(jì)算更為簡(jiǎn)便。用對(duì)偶單純形法求解時(shí)，目標(biāo)函數(shù)必須是求極大化的。,63,Maxz=3x1-4x2 s.t. x1+2x2≥2 3x1+ x2≥4 x1- x2≤1

54、 x1+ x2≤3 x1,x2≥0,Maxz=3x1-4x2 s.t. -x1-2x2≤-2 -3x1- x2≤-4 x1- x2≤1 x1+ x2≤3 x1,x2≥0,Maxz=3x1-4x2 s.t. -x1-2x2+x3=-2 -3x1- x2+x4=-

55、4 x1- x2+x5=1 x1+ x2+x6=3 xj≥0,,,64,可以看出，這時(shí)候原問(wèn)題和對(duì)偶問(wèn)題都不可行,列出初始單純形表：,65,,66,,,,67,,,,68,69,70,71,,72,,,,73,,,,74,75,76,77,,78,,,,79,,,,80,81,82,83,此時(shí)對(duì)偶問(wèn)題和原問(wèn)題都達(dá)到可行，所以均達(dá)到了最優(yōu)解X＝（4/3.1/3

56、,0,1/3,0,4/3)Z=8/3,84,第7節(jié) 靈敏度分析,前提條件:原線性規(guī)劃問(wèn)題已取得了最優(yōu)解；每次只討論一種參數(shù)的變化，而參數(shù)之間的變化互不關(guān)聯(lián)。,85,某廠準(zhǔn)備用甲乙兩種原料生產(chǎn)A，B，C，D四種產(chǎn)品，相關(guān)參數(shù)見(jiàn)表。問(wèn)如何安排生產(chǎn)總利潤(rùn)為最大。,Maxz=9x1+8x2+50x3+19x4 s.t. 3x1+2x2+10x3+4x4≤18 2x3+1

57、/2x4≤3 xj≥0 (j=1,2,3,4),Maxz=9x1+8x2+50x3+19x4 s.t. 3x1+2x2+10x3+4x4+x5=18 2x3+1/2x4+x6=3 xj≥0 (j=1,2,…,6),86,用單純形法對(duì)該線性規(guī)劃進(jìn)行求解，得初始單純行表和最優(yōu)單純形表,Z*=88,-y1,-y2,-y3,-y

58、4,-y5,-y6,87,7.1資源系數(shù)（右端常數(shù)項(xiàng)bi ） 發(fā)生變化的分析X=(XB,0)T其中XB=B-1bZ=CBB-1b當(dāng)bi 發(fā)生變化時(shí)：bi’=b+(0,…△bi, …0) T=b+△b則: XB’=B-1b’=B-1(b+△b)=B-1b+B-1△b＝XB+ B-1△b如果XB’=XB+ B-1△b≥0，則原最終單純形表中的基變量不變 ，基變量的值將發(fā)生變化如果XB’=XB+ B-1△b＜0，則需采用對(duì)偶單

59、純形表進(jìn)行重新求解。,88,假設(shè)：甲原材料的供給量從18變?yōu)?，則b’=(6,3) T,可以看出甲的供給量發(fā)生變化后，x4的值=-4＜0，所以用對(duì)偶單純形表求新解。,89,,90,,91,92,,,93,,94,當(dāng)右端常數(shù)項(xiàng)發(fā)生變化時(shí)，主要考慮在最優(yōu)單純行表中基變量的值是否仍然大于等于0，如果仍然大于等于0，則線性規(guī)劃問(wèn)題的基變量不變，但是基變量的值將發(fā)生變化；如果右端常數(shù)項(xiàng)發(fā)生變化時(shí)，最優(yōu)單純行表中基變量的值小于0，則將用對(duì)偶單純形

60、法對(duì)原最優(yōu)單純形表進(jìn)行繼續(xù)求解。,95,7.2目標(biāo)函數(shù)中cj發(fā)生變化的分析1.非基變量的cj發(fā)生變化x1的利潤(rùn)值由9變?yōu)?+△c1則：σ1= 9+△c1-2×19+25=-4+ △c1如果σ1=-4+ △c1≤0，最優(yōu)解不發(fā)生變化； σ1=-4+ △c1＞0，最優(yōu)解將發(fā)生變化。所以當(dāng)△c1 ≤4時(shí)，最優(yōu)解不發(fā)生變化。 對(duì)于某一非基變量可以看出，它的價(jià)值系數(shù)發(fā)生變化時(shí)，只影響最優(yōu)單純行表中該非基

61、變量的檢驗(yàn)數(shù)，而基變量的檢驗(yàn)數(shù)都不會(huì)發(fā)生變化，所以只需要考慮該非基變量的價(jià)值系數(shù)變化后的檢驗(yàn)數(shù)是否仍然小于等于0，如果仍然小于等于0，則最優(yōu)解不發(fā)生變化。,96,思考：如果x2的系數(shù)發(fā)生變化，△c2在什么范圍內(nèi)變化，最優(yōu)解不變？,97,2.基變量的cj發(fā)生變化假設(shè)x4的利潤(rùn)由19變?yōu)?9+△c4,-4-2△c4,-2/3-4/3△c4,-13/3-2/3△c4,-10/3+10/3△c4,當(dāng)且僅當(dāng)所有的非基變量的檢驗(yàn)數(shù)都仍然小于等

62、于0則最優(yōu)解不變。,98,當(dāng)目標(biāo)函數(shù)中cj發(fā)生變化，將影響最終單純形表非基變量的檢驗(yàn)數(shù)。如果是非基變量的價(jià)值系數(shù)發(fā)生變化，只影響該非基變量的檢驗(yàn)數(shù)，如果變化后的檢驗(yàn)數(shù)仍然小于等于0，則最優(yōu)解不變；如果是基變量的價(jià)值系數(shù)發(fā)生變化，將影響所有非基變量的檢驗(yàn)數(shù)，只有當(dāng)所有的非基變量檢驗(yàn)數(shù)都仍然小于等于0，最優(yōu)解才不變。,99,7.3增加一個(gè)變量 假設(shè)用甲乙兩種原材料還可以生產(chǎn)新產(chǎn)品為E，需要甲原料3個(gè)單位，乙原料1個(gè)單位，利潤(rùn)為10，

63、問(wèn)該種新產(chǎn)品是否應(yīng)該生產(chǎn)？ 設(shè)生產(chǎn)E產(chǎn)品x7個(gè)，則線性規(guī)劃方程為：,Maxz=9x1+8x2+50x3+19x4+10x7 s.t. 3x1+2x2+10x3+4x4+3x7≤18 2x3+1/2x4+x7≤3 xj≥0 (j=1,2,3,4,7),Maxz=9x1+8x2+50x3+19x4+10x7 s.t. 3x1+2x

64、2+10x3+4x4+3x7+x5=18 2x3+1/2x4+x7+x6=3 xj≥0 (j=1,2,…,7),100,P7=(3,1)T,σ7’=c7-CBP7’=10-(19,50)(13/4,5/6)T=-19/3＜0,因?yàn)閤7的檢驗(yàn)數(shù)小于0，所以原最優(yōu)單純形表即為最優(yōu)單純形表，最優(yōu)解不變。,考慮影子價(jià)格：y1=13/3，y2=10/3則生產(chǎn)一件E

65、產(chǎn)品所需要的隱含成本為：13/3*3+10/3*1=49/3＞10(每件E產(chǎn)品的利潤(rùn)）所以也不生產(chǎn)。,101,增加一個(gè)變量也就是多生產(chǎn)一種產(chǎn)品，只須考慮該種產(chǎn)品的檢驗(yàn)數(shù)是否大于0，如果大于0則表示應(yīng)該生產(chǎn)，用單純形表進(jìn)行求解；如果小于0則該種產(chǎn)品不用生產(chǎn)，最優(yōu)解不發(fā)生變化。同時(shí)也可以考慮影子價(jià)格，如果該種新產(chǎn)品的利潤(rùn)大于隱含成本，則應(yīng)該生產(chǎn)用單純形表進(jìn)行求解；如果小于隱含成本則該種產(chǎn)品不用生產(chǎn)。,102,7.4增加一個(gè)約束條件假

66、設(shè)原線性規(guī)劃問(wèn)題變?yōu)?Maxz=9x1+8x2+50x3+19x4 s.t. 3x1+2x2+10x3+4x4≤18 2x3+1/2x4≤3 2x1+ x2+ x3+2x4≤8 xj≥0 (j=1,2,3,4),Maxz=9x1+8x2+50x3+19x4 s.t. 3x1+2x2+10x3+4x4+x

67、5=18 2x3+1/2x4+x6=3 2x1+ x2+ x3+2x4+x7=8 xj≥0 (j=1,2,…,7),103,104,此時(shí)x7的值＝3大于0，所以原問(wèn)題和對(duì)偶問(wèn)題都達(dá)到可行解，并分別為最優(yōu)解。不需要進(jìn)行下一步計(jì)算,105,增加一個(gè)約束條件，可能影響的只是該約束條件的松弛變量的值，如果該松弛變量的值大于等于0，則線性

68、規(guī)劃最優(yōu)解不變；如果該松弛變量的值小于0，則采用對(duì)偶單純形表進(jìn)行計(jì)算。,106,7.5技術(shù)系數(shù)aij發(fā)生變化,Maxz=9x1+8x2+50x3+19x4 s.t. 3x1+2x2+10x3+4x4≤18 2x3+1/2x4≤3 xj≥0 (j=1,2,3,4),3x1+x2+10x3+4x4≤18,則P2=(2,0)T,,P2’=(1,0)T,