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

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

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

3、y2≥5 y1,y2≥0,,,,,,,,4,第4節(jié) 線性規(guī)劃的對偶理論——對偶問題的一般形式 一般認(rèn)為變量均為非負(fù)約束的情況下，約束條件在目標(biāo)函數(shù)取極大值時均取“≤”號；當(dāng)目標(biāo)函數(shù)求極小值時均取“≥“號。則稱這些線性規(guī)劃問題具有對稱性。,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,原始問題max z=CXs.t. AX≤b X ≥0,對偶問題min w=Y’bs.t. A’Y≥C’Y ≥0,,,,≥,max,b,A,C,,,,C,AT,b,≤,min,,,,,,,,,,,,,m,n,m,n,4.1原問題與對偶問題的

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,原始問題為min z=2x1+3x2-x3s.t. x1+2x2+x3≥6 2x1-3x2+2x3≥9 x1, x2, x3≥0,根據(jù)定義，對偶問題為max y=6y1+9y2s.t. y1+2y2≤2 2y1- 3y2≤3 y1+2y2≤-1 y1, y2≥0,原始問題是極小化問題原始問

8、題的約束全為≥原始問題有3個變量，2個約束原始問題的變量全部為非負(fù),對偶問題是極大化問題對偶問題的約束全為≤對偶問題有2個變量，3個約束原始問題的變量全部為非負(fù),原始問題變量的個數(shù)(3)等于對偶問題約束條件的個數(shù)(3)原始問題約束條件的個數(shù)(2)等于對偶問題變量的個數(shù)(2),8,非對稱形式的原—對偶問題,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無約束此時對偶問題變?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無約束,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,原 始 對 偶 表,,,,,,,11,對偶關(guān)系,1、極大與極小的對偶2、價值系數(shù)與資源系數(shù)的對偶3、約束條件系數(shù)矩陣的對偶是矩陣的轉(zhuǎn)置4、反向不等式與非正的決策變量的對偶5、等式與非負(fù)限制的決策變量的對偶6、最優(yōu)解與檢驗數(shù)的對偶,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,原始問題變量的個數(shù)(3)等于對偶問題約束條件的個數(shù)(3)；原始問題約束條件的個數(shù)(4)等于對偶問題變量的個數(shù)(4)。原始問題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)。原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)。,寫對偶問題的練習(xí)（1）,13,寫對偶問題的練習(xí)（2）,原始問題,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,對偶問題,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,原始和對偶問題可行解目標(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、計算的矩陣描述,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,對應(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)基時，XB為最優(yōu)解時，則有：,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)原問題為最優(yōu)解時，對偶問題為可行解且具有相同的目標(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,,,解原問題：,,21,,,,22,,,,23,,,Z=4.5×40/7＋5×24/7=300/7,,24,解對偶問題：,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）對稱性：對偶問題的對偶,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,對偶問題的對偶就是原始問題。兩個問題中的任一個都

27、可以作為原始問題。另一個就是它的對偶問題。,根據(jù)定義寫出對偶問題,根據(jù)定義寫出對偶問題,max u=6w1+9w2s.t. w1+2w2≤2 2w1- 3w2≤3 w1+2w2≤-1 w1, w2≥0,4.2對偶問題的基本性質(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 對偶問題的基本性質(zhì),原始問題max z=CXs.t. AX≤b X ≥0,對偶問題min w=Y’bs.t. A’Y≥C’Y ≥0,（2）弱對偶性若X為原問題的可行解

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

30、若對偶問題有可行解而其原問題無可行解時，對偶問題目標(biāo)函數(shù)無界。,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,試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解,例。已知線性規(guī)劃問題,證：首先該問題存在可行解。,可知對偶問題無可行解，因原問題有可行解，故無最優(yōu)解。,31,（4）最優(yōu)性若X為原問題的可行解，Y為對偶問題的可行解，且CX＝Y(jié)’b則X，Y分別為原問題和對偶問題的最優(yōu)解。,（5）強對偶性若原問題和對偶問題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等。,32,（6）互補松弛定理在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)

32、某一約束條件的對偶變量值為0，則該約束條件取嚴(yán)格等式，既松弛變量或剩余變量為0；反之如果對應(yīng)某一約束條件的對偶變量值不為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,,利用互補松弛關(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,原始問題,對偶問題,,,,,最優(yōu)解為(y1, y2)=(6, 0)max y=6,先用圖解法求解對偶問題。,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é) 對偶問題的經(jīng)濟解釋——資源的影子價格(Shadow Price),影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于0,yi’=△w/△bi=最大利潤的增量/第i種資源的增量=第i種資源的邊際利潤,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、,資源的影子價格是一種機會成本根據(jù)互補松弛定理,若yi’ ＞0,則∑aijxj=bi，若yi’ ＝0,則∑aijxj＜bi，,某種資源bi未得到充分利用時，該種資源的影子價格為0；當(dāng)資源的影子價格不為0，表示該種資源在生產(chǎn)中已消耗完畢。,σj=cj-zj=cj-CBB-1Pjcj表示第i種產(chǎn)品的產(chǎn)值，∑aijyi表示生產(chǎn)該種產(chǎn)品所消耗各項資源的影子價格的總和，即產(chǎn)品的隱含成本。,39,Maxz=4x1+10x2 s.t

41、. 3x1+6x2≤5 x1+3x2≤2 2x1+5x2≤4 x1,x2≥0,已知原問題為：,則對偶問題為：,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,初始單純形表為：,此時對偶問題

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),不是對偶問題的可行解,,41,初始單純形表為：,此時對偶問題的解為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),不是對偶問題的可行解,,,,42,對原問題進行迭代得：,此時對偶問題的解為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、),不是對偶問題的可行解,,43,對原問題進行迭代得：,此時對偶問題的解為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),不是對偶問題的可行解,,,,44,對原問題進行迭代得：,此時對偶問題的解為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),是對偶問題的可行解,45,單純形法求解的過程，從對偶的觀點來看，是在始終保持原始可行解的條件下，不斷改進對偶可行性的過程。一個從對偶不可行的解，經(jīng)過幾次疊代，逐步向?qū)ε伎尚薪饪繑n，一旦得到的解既是原始可行的，又是對偶可行的，這個解就分別

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

48、的最優(yōu)解，若存在基變量的值≤0，則問題還沒有達(dá)到最優(yōu)解，需要進行改進。3.改進選擇換出變量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,此時對偶問題和原問題都達(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í):用對偶單純形法求

51、解并求出對偶變量的最優(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,此時對偶問題和原問題都達(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,對偶單純形法的特點：當(dāng)約束條件為“≥”時，不需要引入人工變量，從而使計算更為簡便。用對偶單純形法求解時，目標(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,可以看出，這時候原問題和對偶問題都不可行,列出初始單純形表：,65,,66,,,,67,,,,68,69,70,71,,72,,,,73,,,,74,75,76,77,,78,,,,79,,,,80,81,82,83,此時對偶問題和原問題都達(dá)到可行，所以均達(dá)到了最優(yōu)解X＝（4/3.1/3

56、,0,1/3,0,4/3)Z=8/3,84,第7節(jié) 靈敏度分析,前提條件:原線性規(guī)劃問題已取得了最優(yōu)解；每次只討論一種參數(shù)的變化，而參數(shù)之間的變化互不關(guān)聯(lián)。,85,某廠準(zhǔn)備用甲乙兩種原料生產(chǎn)A，B，C，D四種產(chǎn)品，相關(guān)參數(shù)見表。問如何安排生產(chǎ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,用單純形法對該線性規(guī)劃進行求解，得初始單純行表和最優(yōu)單純形表,Z*=88,-y1,-y2,-y3,-y

58、4,-y5,-y6,87,7.1資源系數(shù)（右端常數(shù)項bi ） 發(fā)生變化的分析X=(XB,0)T其中XB=B-1bZ=CBB-1b當(dāng)bi 發(fā)生變化時：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，則需采用對偶單

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

60、法對原最優(yōu)單純形表進行繼續(xù)求解。,95,7.2目標(biāo)函數(shù)中cj發(fā)生變化的分析1.非基變量的cj發(fā)生變化x1的利潤值由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時，最優(yōu)解不發(fā)生變化。 對于某一非基變量可以看出，它的價值系數(shù)發(fā)生變化時，只影響最優(yōu)單純行表中該非基

61、變量的檢驗數(shù)，而基變量的檢驗數(shù)都不會發(fā)生變化，所以只需要考慮該非基變量的價值系數(shù)變化后的檢驗數(shù)是否仍然小于等于0，如果仍然小于等于0，則最優(yōu)解不發(fā)生變化。,96,思考：如果x2的系數(shù)發(fā)生變化，△c2在什么范圍內(nèi)變化，最優(yōu)解不變？,97,2.基變量的cj發(fā)生變化假設(shè)x4的利潤由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)所有的非基變量的檢驗數(shù)都仍然小于等

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

63、問該種新產(chǎn)品是否應(yīng)該生產(chǎn)？ 設(shè)生產(chǎn)E產(chǎn)品x7個，則線性規(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,因為x7的檢驗數(shù)小于0，所以原最優(yōu)單純形表即為最優(yōu)單純形表，最優(yōu)解不變。,考慮影子價格：y1=13/3，y2=10/3則生產(chǎn)一件E

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

66、設(shè)原線性規(guī)劃問題變?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,此時x7的值＝3大于0，所以原問題和對偶問題都達(dá)到可行解，并分別為最優(yōu)解。不需要進行下一步計算,105,增加一個約束條件，可能影響的只是該約束條件的松弛變量的值，如果該松弛變量的值大于等于0，則線性

68、規(guī)劃最優(yōu)解不變；如果該松弛變量的值小于0，則采用對偶單純形表進行計算。,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,