1、1,對(duì)偶線性規(guī)劃,對(duì)偶的定義對(duì)偶問(wèn)題的性質(zhì)原始對(duì)偶關(guān)系目標(biāo)函數(shù)值之間的關(guān)系最優(yōu)解之間的互補(bǔ)松弛關(guān)系對(duì)偶單純形法對(duì)偶的經(jīng)濟(jì)解釋靈敏度分析,DUAL,,dual linear programming,2,§2.1 線性規(guī)劃的對(duì)偶問(wèn)題,一、對(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)最大？,

2、3,解:設(shè)生產(chǎn)A1為x1單位，生產(chǎn)A2為x2單位,則線性規(guī)劃問(wèn)題為：,maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 4x1+5x2≤40 x1,x2≥0,解：設(shè)甲資源的出讓單價(jià)為y1,乙資源的出讓單價(jià)為y2,minw=24y1+40y2 s.t. 3y1+4y2≥4.5 2y1+5y2≥5

3、 y1,y2≥0,另一方面，假設(shè)另一公司想把資源買過(guò)來(lái)，它至少應(yīng)付出多大代價(jià)才能使原來(lái)公司放棄生產(chǎn)，出讓資源？,,4,解：設(shè)生產(chǎn)A1為x1件，生產(chǎn)A2為x2件，則線性規(guī)劃問(wèn)題為：,maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 4x1+5x2≤40 x1,x2≥0,解：設(shè)甲資源的出讓價(jià)格為y1,乙資源的出讓價(jià)格為y2,minw=24y1+40y2

4、 s.t. 3y1+4y2≥4.5 2y1+5y2≥5 y1,y2≥0,另一方面，假設(shè)另一公司想把資源買過(guò)來(lái)，它至少應(yīng)付出多大代價(jià)才能使原來(lái)公司放棄生產(chǎn)，出讓資源？,,,,5,解：設(shè)生產(chǎn)A1為x1件，生產(chǎn)A2為x2件，則線性規(guī)劃問(wèn)題為：,maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 4x1+5x2≤40

5、 x1,x2≥0,解：設(shè)甲資源的出讓價(jià)格為y1,乙資源的出讓價(jià)格為y2,minw=24y1+40y2 s.t. 3y1+4y2≥4.5 2y1+5y2≥5 y1,y2≥0,另一方面，假設(shè)另一公司想把資源買過(guò)來(lái)，它至少應(yīng)付出多大代價(jià)才能使原來(lái)公司放棄生產(chǎn)，出讓資源？,,二、對(duì)稱形式下對(duì)偶問(wèn)題的一般形式,,定義：變量均為非負(fù)約束的情況下，約束條件在目標(biāo)函

6、數(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 ≤b2 …… am1x1+am2x2+……+amnxn ≤bm x1, x2, ……, xn ≥0,min w=b1y1+b2y2+……+bmyms

7、.t. a11y1+a21y2+……+am1ym ≥c1 a12y1+a22y2+……+am2ym ≥ c2 …… a1ny1+a2ny2+……+amnym ≥ cn y1, y2, ……, ym ≥0,max Z=CX s.t. AX≤b X≥0,min w=bTY s.t. ATY≥CT Y≥0,原始問(wèn)題max

8、 z=CXs.t. AX≤b X ≥0,對(duì)偶問(wèn)題min w=bTYs.t. ATY≥CTY ≥0,,,,≥,max,b,A,C,,,,CT,AT,bT,≤,min,,,,,,,,,,,,,m,n,m,n,maxZ=3x1+2x2 s.t. -x1+2x2≤4 3x1+2x2≤14 x1-x2 ≤3 x1,x2≥0,min

9、w=4y1+14y2+3y3 s.t. -y1+3y2+y3≥3 2y1+2x2-y3≥2 y1,y2,y3≥0,y1,y2,y3,第一種資源,第二種資源,第三種資源,第一種產(chǎn)品,第二種產(chǎn)品,x1,x2,,舉例,原問(wèn)題：maxZ=x1+4x2+2x3 s.t. 5x1-x2+2x3≤8 x1+3x2-3x3≤5

10、 x1,x2,x3≥0,對(duì)偶問(wèn)題：minw=8y1+5y2 s.t. 5y1+y2≥1 -y1+3y2≥4 2y1-3y2 ≥2 y1,y2≥0,,練習(xí),結(jié)論：對(duì)偶問(wèn)題的對(duì)偶為原問(wèn)題,原始問(wèn)題max Z=CXs.t. AX≤b X ≥0,對(duì)偶問(wèn)題min w=YTbs.t. ATY≥CTY ≥0,令w?=-w,max

11、 w?=-YTbs.t. -ATY≤-CTY ≥0,對(duì)偶,min Z´=-CXs.t. -AX≥-bX ≥0,,,,令Z=-Z?,對(duì)偶問(wèn)題的對(duì)偶就是原始問(wèn)題。兩個(gè)問(wèn)題中的任一個(gè)都可以作為原始問(wèn)題，另一個(gè)就是它的對(duì)偶問(wèn)題。,11,對(duì)偶問(wèn)題的對(duì)偶,max z=6x1+9x2s.t. x1+2x2≤2 2x1- 3x2≤3 x1+2x2≤-1 x1, x2≥0,

12、minw=2y1+3y2-y3s.t. y1+2y2+y3≥6 2y1-3y2+2y3≥9 y1, y2, y3≥0,根據(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,minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x4≥

13、5 2x1 +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

14、2x1’ -2x3+(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

15、 +(y3’-y3”) ≤3 -3y1-2y2’ +(y3’-y3”) ≤ -5 y1+y2’+(y3’-y3”) ≤ 1 -y1-y2’-(y3’-y3”) ≤-1 y1,y2’ ,y3’,y3”≥0,三、非對(duì)稱形式的原—對(duì)偶問(wèn)題,引例,13,maxw=5y1-4y2’+6(y3’-y3”) s.t.-y1+2y2’ ≤-2

16、 y1 +(y3’-y3”) ≤3 -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

17、. y1+2y2 ≥2 y1 +y3 ≤3 -3y1+2y2+y3 ≤ -5 y1 -y2 +y3 = 1 y1≥0 ,y2≤0,y3無(wú)約束,14,maxw=5y1+4y2+6y3 s.t. y1+2y2 ≥2 y1

18、 +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 = 6

19、 x1≤0,x2,x3≥0,,,原問(wèn)題,對(duì)偶問(wèn)題,,比較后得出什么結(jié)論？,min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4

20、2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0,≤,≥,=,≥,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ì)偶

21、問(wèn)題約束條件的性質(zhì)。原始問(wèn)題約束條件的性質(zhì)影響對(duì)偶問(wèn)題變量的性質(zhì)。,寫對(duì)偶問(wèn)題的練習(xí)（1）,原始問(wèn)題,max z=2x1-x2+3x3-2x4s.t. x1 +3x2 - 2x3 + x4≤12 -2x1 + x2 -3x4≥8 3x1 - 4x2 +5x3 - x4 = 15 x1≥0, x2:Free, x3≤0, x4≥0,min w=12y1+8y2+15y3s.t. y1 –

22、 2y2 + 3y3≥2 3y1 + y2 – 4y3=-1 -2y1 +5y3≤3 y1 – 3y2 - y3≥-2 y1≥0,y2≤0, y3:Free,對(duì)偶問(wèn)題,寫對(duì)偶問(wèn)題的練習(xí)（2）,17,,,maxZ=x1-2x2+3x3 s.t. 2x1+4x2+3x3≥100 3x1-2x2+6x3≤200 5x1+3x2+4x3=150

23、 x1, x3≥0,練習(xí),minw=100y1+200y2+150y3 s.t. 2y1+3y2+5y3≥1 4y1-2y2+3y3= -2 3y1+6y2+4y3≥3 y1≤0,y2≥0,minZ=2x1+2x2+4x3 s.t. x1+3x2+4x3≥2 2x1+ x2+3x3≤3

24、 x1+4x2+3x3=5 x1 ≥0, x2≤0,maxw=2y1+3y2+5y3 s.t. y1+2y2+ y3≤2 3y1+ y2+4y3≥ 2 4y1+3y2+3y3=4 y1≥0,y2≤0,原問(wèn)題 Max Z=CX AX≤b

25、 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的單位矩陣,§2.2 對(duì)偶問(wèn)題的基本性質(zhì),一、單純性法計(jì)算的矩陣描述,其初始單純性表及經(jīng)過(guò)若干次迭代后的單純性表如下：,,20,(1)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1；(

26、2)初始單純形表中基變量Xs=b，迭代后的表中為XB=B-1b；(3)約束矩陣（A，I）＝（B，N，I），迭代后為 （B-1B，B-1N，B-1I）＝（I，B-1N，B-1)；(4)初始單純形表中xj的系數(shù)向量為Pj，迭代后為Pj’，且Pj’=B-1Pj。,21,(5),當(dāng)B為最優(yōu)基，XB為最優(yōu)解時(shí)，則有：,CN-CBB-1N≤0,-CBB-1≤0,CB-CBI=0,C－CBB-1 A≤0 -CBB-1≤0,令Y

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

28、4y1+40y2 s.t. 3y1+4y2≥4.5 2y1+5x2≥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+

29、4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y4≥0,,例題,24,,,,,,,(x3,x4)=(0,0),,,,(y3,y4)=(0,0),,,,-y1,-y2,-y4,-y3,x1,x2,x4,x3,,25,maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 4x1+5x2≤40

30、 x1,x2≥0,minw=24y1+40y2 s.t. 3y1+4y2≥4.5 2y1+5x2≥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

31、 s.t. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y4≥0,,例題,,原始問(wèn)題max Z=CXs.t. AX≤b X ≥0,對(duì)偶問(wèn)題min W=YTbs.t. ATY≥CTY ≥0,二、對(duì)偶問(wèn)題的基本性質(zhì),,二、對(duì)偶問(wèn)題的基本性質(zhì),1.弱對(duì)偶性,原問(wèn)題任一可行解的目標(biāo)函數(shù)是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之對(duì)

32、偶問(wèn)題任一可行解的目標(biāo)函數(shù)是其原問(wèn)題目標(biāo)函數(shù)的上界。如原問(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ú)界。若對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解時(shí)，對(duì)偶問(wèn)題目標(biāo)函數(shù)無(wú)界。,推論：,2.最優(yōu)性,,,若原問(wèn)題和對(duì)偶問(wèn)題均具有可行解，則二者均具有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)值相

33、等。,3.強(qiáng)對(duì)偶性（對(duì)偶性定理）,證：由于二者均有可行解，所以原問(wèn)題的目標(biāo)函數(shù)值具有上界，對(duì)偶問(wèn)題的目標(biāo)函數(shù)值具有下界，因此二者均具有最優(yōu)解。,當(dāng)原問(wèn)題有最優(yōu)解時(shí),對(duì)偶問(wèn)題的解Y=CBB-1為可行解,且 Z=CBB-1b=W,由最優(yōu)性知,二者的解均為最優(yōu)解。,在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非0，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則 對(duì)應(yīng)的對(duì)偶變量值為0。,若yi’ ＞0,則∑aij

34、xj，=bi，即xsi=0若∑aijxj，＜bi ，即xsi＞0 則 yi’ ＝0,同理若xj’ ＞0, 則∑aijyi，=cj若∑aijyi ，＞ cj，則 xj’ ＝0.,4.互補(bǔ)松弛定理,maxZ=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,≥0,minw=24y1+40y2 s.t

35、. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y4≥0,3x1+2x2=24， X3=0 4x1+5x2=40， X4=0,3y1+4y2=4.5， y3=0, 2y1+5y2=5 ， y4=0,,最優(yōu)解X=(40/7，24/7，0，0)T ，Y=(14/5，6/7，0，0)T,,利用互補(bǔ)松弛關(guān)系求解線性規(guī)劃,min z=6x1+8x

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

37、x2+3x3s.t. x1+ x2 ≥1 x1+2x2+x3 ≥-1 x1, x2, x3 ≥0,max w=y1-y2s.t. y1+ y2 ≤6 y1+2y2 ≤8 y2 ≤3 y1, y2≥0,max w=y1-y2s.t. y1+y2+y3 =6 y1+2y2 +y4 =8

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

39、 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),,§2.3 資源的影子價(jià)格(Shadow Price),yi=△w/△bi=最大利潤(rùn)的增量/第i種資源的增量=第i種資源的邊際利潤(rùn),w=b1y1+b2y2+…+biyi+…+bmym,w+△w=b1y1+b2y2

40、+…+(bi+△bi)yi+…+bmym,△w=△biyi,,Yi代表在資源最有利條件下對(duì)單位第i種資源的估價(jià)，稱為影子價(jià)格。,36,,,,,,,,,,,,,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

41、 x1,x2≥0,,思考:如果第一種資源增加1，也就是把15變?yōu)?6,目標(biāo)函數(shù)值將怎么變化?為什么?,最優(yōu)解X=(7/2, 3/2)T對(duì)偶問(wèn)題最優(yōu)解y=(0，1/4，1/2)T,由對(duì)偶問(wèn)題的互補(bǔ)松弛性質(zhì)當(dāng) 時(shí)， 當(dāng) 時(shí)， .表明生產(chǎn)過(guò)程中某資源bi未得到充分利用時(shí)，該資源的影子價(jià)格為

42、0；當(dāng)該資源的影子價(jià)格不為0時(shí)，表明該資源在生產(chǎn)過(guò)程中以耗費(fèi)完畢。,,影子價(jià)格是一種機(jī)會(huì)成本，在完全市場(chǎng)經(jīng)濟(jì)條件下，當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，則會(huì)賣出該資源；當(dāng)市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，則會(huì)買入該資源。即影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺；影子價(jià)格越小，說(shuō)明這種資源越充裕。,資源的影子價(jià)格有賴于資源的利用情況，因企業(yè)的生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況而變化。,maxz=4x1+10x2 s.t. 3x1+6x2≤5

43、 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+x3=5 x1+3x2

44、 +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),,§2.4 對(duì)偶單純形法,39,初始單純形表為：,此時(shí)對(duì)偶問(wèn)題的基

45、解為Y＝(0，0，0，－4，－10)T,不是對(duì)偶問(wèn)題的可行解,,40,初始單純形表為：,此時(shí)對(duì)偶問(wèn)題的基解為Y＝(0，0，0，－4，－10)T,不是對(duì)偶問(wèn)題的可行解,,,,41,迭代得：,此時(shí)對(duì)偶問(wèn)題的基解為Y＝(0，10/3，0，-2/3，0)T,不是對(duì)偶問(wèn)題的可行解,,42,迭代得：,此時(shí)對(duì)偶問(wèn)題的基解為Y ＝(0，10/3，0，-2/3，0 )T,不是對(duì)偶問(wèn)題的可行解,,,,43,迭代得：,此時(shí)對(duì)偶問(wèn)題的基解為Y＝(2/3，2，0

46、，0，0)T,是對(duì)偶問(wèn)題的可行解,44,◆單純形法求解的過(guò)程，從對(duì)偶的觀點(diǎn)來(lái)看，是在始終保持原始可行解的條件下，不斷改進(jìn)對(duì)偶可行性的過(guò)程。一個(gè)從對(duì)偶不可行的解，經(jīng)過(guò)幾次疊代，逐步向?qū)ε伎尚薪饪繑n，一旦得到的解既是原問(wèn)題可行的，又是對(duì)偶可行的，這個(gè)解就分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。,◆根據(jù)對(duì)偶問(wèn)題的對(duì)稱性，若保持對(duì)偶問(wèn)題的解是可行的，即檢驗(yàn)數(shù)≤0，而原問(wèn)題在非可行解的基礎(chǔ)上，不斷改進(jìn)其可行性，逐步達(dá)到基可行解，此時(shí)就達(dá)到原問(wèn)題和對(duì)偶問(wèn)題

47、的最優(yōu)解。,設(shè)有問(wèn)題 max Z=CX ， AX ＝b ， X ≥0 又設(shè)B是其一個(gè)基，當(dāng)非基變量都為0時(shí)，可以得到XB=B-1b。若在B-1b中至少有一個(gè)負(fù)分量，并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，這種情況就可以用對(duì)偶單純形法來(lái)進(jìn)行求解。,對(duì)偶單純形法適用的情況：,46,

48、step1.確定初始解 求初時(shí)基可行解,列出初始單純性表(一般取松弛變量為基變量)；若所有檢驗(yàn)數(shù)≦ 0，且所有的基變量值均≥0，則此解為線性規(guī)劃問(wèn)題的最優(yōu)解；若存在基變量的值≤0，則問(wèn)題還沒(méi)有達(dá)到最優(yōu)解，則進(jìn)行如下計(jì)算；step 2.改進(jìn) 選擇換出變量：min{ B-1bi | B-1 bi≤0},假設(shè)選取xr為換出變量； 選擇換入變量：θ＝min{(cj-zj)/arj|arj＜0},假設(shè)xl為換入變量；st

49、ep 4.迭代 使得alk＝1，其余aik為0。,對(duì)偶單純形法的計(jì)算步驟：,Minw=5y1+2y2+4y3 s.t. 3y1+ y2+2y3≥4 6y1+3y2+5y3≥10 y1,y2,y3≥0,,例1,Maxw’=-5y1-2y2-4y3 s.t. -3y1- y2-2y3≤-4 -6y1-3y2-5y3≤-10

50、 y1,y2,y3≥0,Maxw’=-5y1-2y2-4y3 s.t. -3y1- y2-2y3+y4=4 -6y1-3y2-5y3+y5=10 yi≥0(i=1,2,…,5),,48,,,Maxw’=-5y1-2y2-4y3 s.t. -3y1- y2-2y3+y4=4 -6y1-3y2-5y3+y5=10 yi

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

52、題的最優(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=4 -2x1 +x2-3x3 +x5=10 xi≥0(i=1,2,…,5),,

53、59,此時(shí)對(duì)偶問(wèn)題和原問(wèn)題都達(dá)到可行，所以均達(dá)到了最優(yōu)解 原問(wèn)題最優(yōu)解為:X=(11/5,2/5,0,0,0)T, W ’=-28/5, W=28/5對(duì)偶問(wèn)題最優(yōu)解為：Y=(8/5,1/5,0,0,9/5)T,,,(1)初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都≤時(shí)，就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以直接計(jì)算。(2)當(dāng)變量多于約束條件，對(duì)這樣的LP問(wèn)題，用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量。因此，對(duì)變量較少，而約束條件

54、很多的LP問(wèn)題，可以先將它變換成對(duì)偶問(wèn)題，然后用對(duì)偶單純形法求解。(3)在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法，這樣可使問(wèn)題的處理簡(jiǎn)化。,對(duì)偶單純形法的優(yōu)點(diǎn),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.

55、 -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=-4 x1- x2+x5=1 x1+ x2+x6=3

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

57、8/3,第五節(jié) 靈敏度分析,靈敏度分析的概念 對(duì)系統(tǒng)或事物（線性規(guī)劃問(wèn)題）因周圍條件的變化（如cj , bi, aij 的變化）顯示出來(lái)的敏感程度的分析,當(dāng)cj、bi、ai j變化時(shí)會(huì)引起哪些數(shù)字的變化？,(1) 參數(shù)A，b，C在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)前最優(yōu)方案無(wú)影響？,(2) 參數(shù)A，b，C中的一個(gè)變動(dòng)，對(duì)當(dāng)前最優(yōu)方案影響？,(3) 如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求新方案？,靈敏度分析所解決的問(wèn)題,例：佳美公司計(jì)劃制造Ⅰ、 Ⅱ兩種

58、家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)整工序時(shí)間及每天可用于這兩種家電的能力、各出售一件時(shí)的獲利情況，如下表。問(wèn)該公司應(yīng)制造兩種家電各生產(chǎn)多少, 可獲最大利潤(rùn)?,一、分析 cj 的變化,c j 的變化僅僅影響檢驗(yàn)數(shù),5x2 ? 15 6x1 + 2x2 ? 24 x1 + x2 ? 5 x1，x2 ? 0,,max Z=

59、 2x1 +x2,解:設(shè)兩種家電產(chǎn)量分別為變量x1 ， x2,s.t.,最終單純形表如下：,87,（1）若家電Ⅰ的利潤(rùn)降至1.5元/件，而家電Ⅱ的利潤(rùn)增至2元/件時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化？,,,88,,,,(2)若家電Ⅰ的利潤(rùn)不變，則家電Ⅱ的利潤(rùn)在什么范圍內(nèi)變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化？,設(shè)家電Ⅱ的利潤(rùn)為(1+λ)元，最終單純形變?yōu)椋?-1/4+1/4 λ≤0,-1/2- 3/2 λ≤0,,,- 1/3 ≤λ≤1,,

60、2/3 ≤c2≤2,二、分析 bi的變化bi 的變化僅僅影響b列 的變化,△b= B-1△b,∵XB= B-1b ，? b’=b+△b ∴ XB， = B-1b’= B-1(b+ △b) = B-1b+ B-1 △b,（3）若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32小時(shí)，分析公司最優(yōu)計(jì)劃的變化。,,,,,1 5/4 15/20 1/4 -1

61、/20 -1/4 3/2,B-1△b=,,,080,=,,,102-2,B-1,,,,,080,,102-2,,,,,（3）若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32小時(shí)，分析公司最優(yōu)計(jì)劃的變化。,,利用對(duì)偶單純形法迭代后得：,最優(yōu)計(jì)劃為只生產(chǎn)5件家電Ⅰ。,（4）若設(shè)備A和B每天能力不變，而調(diào)試工序在什么范圍內(nèi)變化，問(wèn)題的最優(yōu)基不變。,1 ≤λ≤14 ≤ b3≤6,增加一個(gè)變量xj

62、 相當(dāng)于增加一種新產(chǎn)品,三、增加一個(gè)變量x j 的分析,（5）公司計(jì)劃推出新產(chǎn)品Ⅲ，生產(chǎn)一件所需設(shè)備A,B及調(diào)試工序的時(shí)間分別為3小時(shí)、4小時(shí)、2小時(shí)，預(yù)期盈利3元/件，試分析該種產(chǎn)品是否值得投產(chǎn)，如投產(chǎn)，對(duì)該公司的最優(yōu)生產(chǎn)計(jì)劃有何影響。,1 5/4 15/20 1/4 -1/20 -1/4 3/2,,,P,6=B-1P6=,,,342,,,-702,=,σ6 ’ = C6

63、 - CBB-1 P6 = C6 - Y P6 3 =3-( 0, 1/4 , 1/2) 4 = 1 2,,,,,設(shè)該公司生產(chǎn)x6件家電Ⅲ ,有,,,,,四、分析 aij的變化,若aij對(duì)應(yīng)的變量xj為非基變量，則Pj和σj變化，參照增加一

64、個(gè)變量的情況。,若aij對(duì)應(yīng)的變量xj為基變量，即B-1變化，則常數(shù)列B-1b和檢驗(yàn)數(shù)σj變化。,（6）在佳美公司例子中，若家電Ⅱ每件需設(shè)備A，B和調(diào)試工時(shí)變?yōu)?h、4h、1h，該產(chǎn)品利潤(rùn)為3元/件，試重新確定該公司最優(yōu)生產(chǎn)計(jì)劃。,σ2’ = C2’ - CBB-1 P2’ = C2’ - Y P2’ 8 =3 -

65、 ( 0, 1/4 , 1/2) 4 = 3/2 1,,102,用單純形法將x’2替換基變量中的x 2并在下一張表中不再保留x2,103,用原問(wèn)題與對(duì)偶問(wèn)題均為非可行解，先設(shè)法使原問(wèn)題可行。,第一行約束可寫為：x3+4x4-24x5=-9,兩端乘(-1)并加人工變量得：-x3- 4x4+24x5+ x6=9,,（7

66、）若美佳公司家電產(chǎn)品還需一道環(huán)境試驗(yàn)工序，家電Ⅰ每件需環(huán)境試驗(yàn)3小時(shí)，家電Ⅱ每件需環(huán)境試驗(yàn)2小時(shí)，環(huán)境試驗(yàn)工序每天的生產(chǎn)能力為12小時(shí)，試重新確定該公司的最優(yōu)生產(chǎn)計(jì)劃。,maxZ=2X1 +X2,五、增加一個(gè)約束條件的分析,設(shè)備A設(shè)備B調(diào)試工序,,,,再利用對(duì)偶單純形法求解即可。,108,靈敏度分析總結(jié),目標(biāo)函數(shù)中價(jià)值系數(shù)發(fā)生變化,增加一個(gè)變量,aij發(fā)生變化,右端常數(shù)項(xiàng)發(fā)生改變,增加一個(gè)約束條件,用單純形法求解,用對(duì)偶單純形法

67、求解,若目標(biāo)函數(shù)或約束右端向量是某個(gè)參數(shù)的線性函數(shù)稱為參數(shù)線性規(guī)劃,第六節(jié) 參數(shù)規(guī)劃,分兩種情況：(1)目標(biāo)函數(shù)是參數(shù)λ的線性函數(shù)，即C+ λC*(2)約束右端向量是參數(shù)λ的線性函數(shù)，即b+ λb*,（1）令λ=0，求解得最終單純形表；（2）將λC*或λb*反映到最終單純形表中；（3）確定在最優(yōu)基不變情況下λ允許取值的范 圍；當(dāng)λ取值超出該范圍時(shí)，用單純形法或?qū)ε紗渭冃畏ㄇ笮碌淖顑?yōu)解；（4）,參數(shù)規(guī)劃 的分析步驟,5

68、x2 ? 15 6x1 + 2x2 ? 24 x1 + x2 ? 5 x1，x2 ? 0,,max Z(λ)= (2+ λ) x1 +(1+2 λ)x2,s.t.,當(dāng)λ=0時(shí)的最終單純形表如下：,例 求解下列參數(shù)線性規(guī)劃問(wèn)題,一、目標(biāo)函數(shù)是參數(shù)λ的線性函數(shù),112,將λ反映到最終單純形表中得,113,,114,當(dāng)-1/5≤ λ ≤1時(shí)，最