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

1、對偶線性規(guī)劃,對偶的定義對偶問題的性質(zhì)原始對偶關(guān)系目標(biāo)函數(shù)值之間的關(guān)系最優(yōu)解之間的互補(bǔ)松弛關(guān)系對偶單純形法對偶的經(jīng)濟(jì)解釋,DUAL,,2,線性規(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ī)劃問題為：,maxZ=4

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

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

4、 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,Max Z=CX s.t.

5、 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,6,舉例：,maxZ=3x1+2x2 s.t.

6、 -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,第一種資源,第二種資源,第三種資源,第一種產(chǎn)品,第二種產(chǎn)品,x1,x2,,7,原始

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,原始問題是極小化問題原始問題的約束全為≥原始問題有3個(gè)變量，2個(gè)約束原始問題的變量全部

8、為非負(fù),對偶問題是極大化問題對偶問題的約束全為≤對偶問題有2個(gè)變量，3個(gè)約束原始問題的變量全部為非負(fù),原始問題變量的個(gè)數(shù)(3)等于對偶問題約束條件的個(gè)數(shù)(3)原始問題約束條件的個(gè)數(shù)(2)等于對偶問題變量的個(gè)數(shù)(2),8,對偶問題的對偶,max z=6x1+9x2s.t. x1+2x2≤2 2x1- 3x2≤3 x1+2x2≤-1 x1, x2≥0,minw=2y1+3y2-y3

9、s.t. y1+2y2+y3≥6 2y1-3y2+2y3≥9 y1, y2, y3≥0,對偶問題的對偶就是原始問題。兩個(gè)問題中的任一個(gè)都可以作為原始問題。另一個(gè)就是它的對偶問題。,根據(jù)定義寫出對偶問題,根據(jù)定義寫出對偶問題,max u=6w1+9w2s.t. w1+2w2≤2 2w1- 3w2≤3 w1+2w2≤-1 w1, w2≥0,9,maxZ=x1+4x2

10、+2x3 s.t. 5x1-x2+2x3≤8 x1+3x2-3x3≤5 x1,x2,x3≥0,minw=8y1+5y2 s.t. 5y1+y2≥1 -y1+3y2≥4 2y1-3y2 ≥2 y1,y2≥0,10,三、非對稱形式的原—對偶問題,minz=2x1+3x2-5x3+x4

11、 s.t. x1+x2-3x3+x4≥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-3

12、x3+(x4’-x4”)≥5 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’

13、 ≤-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,11,maxw=5y1-4y2’+6(y3’-y3”) s.t.-y1+2y2’

14、≤-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,設(shè)y2=-y2’,y3=y3’-y3”,則y2≤0,y3無約束此時(shí)對偶問題變?yōu)?maxw=5y1+4y2+6y3

15、 s.t. y1+2y2 ≥2 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

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

17、x3s.t. 3x1- x2+2x3 6 -x1+2x2-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

18、 w1 0,w2 ,w3 0,w4 0,≤,≥,=,≥,Free,≤,≥,≥,=,≤,≥,x1≥0,x2≤0,x3: Free,原始問題變量的個(gè)數(shù)(3)等于對偶問題約束條件的個(gè)數(shù)(3)；原始問題約束條件的個(gè)數(shù)(4)等于對偶問題變量的個(gè)數(shù)(4)。原始問題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)。原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)。,寫對偶問題的練習(xí)（1）,15,寫對偶問題的練習(xí)（2）,原始

19、問題,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 y=12w1+8w2+15w3s.t. w1 - 2w2 + 3w3≥2 3w1 + w2 - 4w3=-1 -2w1

20、 +5w3≤3 w1 - 3w2 - w3≥-2 w1≥0,w2≤0, w3:Free,對偶問題,16,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. 2y

21、1+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 x1+4x2+3x3=5 x1 ≥0, x2≤0,maxw=2y1+3y2

22、+5y3 s.t. y1+2y2+ y3≤2 3y1+ y2+4y3≥ 2 4y1+3y2+3y3≥4 y1≥0,y2≤0,17,原始和對偶問題可行解目標(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

23、 3y1+y2 ≤3 y1, y2 ≥0,18,對偶問題的基本性質(zhì),一、單純形法計(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的單位矩陣,19

24、,對應(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’。,20,當(dāng)B為最優(yōu)基時(shí)，XB為最優(yōu)解時(shí)，則有：,CN-CBB-1N≤0,-CBB-1≤0,∵CB-CBI=0,代入得：CN－CB

25、B-1N+CB-CBI≤0C－CBB-1(B+N)≤0,整理得：C－CBB-1 A≤0 -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)解時(shí)，對偶問題為可行解且具有相同的目標(biāo)函數(shù)值。,21,maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24

26、 4x1+5x2≤40 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

27、 x1,x2,x3,x4,≥0,minw=24y1+40y2 s.t. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y4≥0,,22,,,解原問題：,,23,,,,24,,,,25,,,Z=4.5×40/7＋5×24/7=300/7,,26,解對偶問題：,w=24×5/14＋40×6/7=300

28、/7,27,,,,,,,(x3,x4)=(0,0),,,,(y3,y4)=(0,0),,,,-y1,-y2,-y4,-y3,x1,x2,x4,x3,,28,二、對偶問題的基本性質(zhì),原始問題max z=CXs.t. AX≤b X ≥0,對偶問題min w=Y’bs.t. ATY≥C’Y ≥0,1.弱對偶性若X‘為原問題的可行解，Y’為對偶問題的可行解，則恒有CX’≤Y’b,29,推論：原問題任一可行解的目

29、標(biāo)函數(shù)是其對偶問題目標(biāo)函數(shù)值的下界，反之對偶問題任一可行解的目標(biāo)函數(shù)是其原問題目標(biāo)函數(shù)的上界。如原問題有可行解且目標(biāo)函數(shù)值無界，則其對偶問題無可行解；反之對偶問題有可行解且目標(biāo)函數(shù)無界，則原問題無可行解。（對偶問題無可行解時(shí)，其原問題無界解或無可行解。若原問題有可行解而其對偶問題無可行解時(shí)，原問題目標(biāo)函數(shù)無界 若對偶問題有可行解而其原問題無可行解時(shí)，對偶問題目標(biāo)函數(shù)無界。,30,2.最優(yōu)性若X‘為原問題的可行解，Y’為對偶問題的

30、可行解，且CX‘＝Y(jié)’b則X’，Y‘分別為原問題和對偶問題的最優(yōu)解。,3.強(qiáng)對偶性若原問題和對偶問題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標(biāo)值相等。,31,4.互補(bǔ)松弛定理在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為0，則該約束條件取嚴(yán)格等式，既松弛變量或剩余變量為0；反之如果對應(yīng)某一約束條件的對偶變量值不為0，則該約束條件取嚴(yán)格不等式，既松弛變量或剩余變量不為0.,若yi’ ＞0,則∑aijxj

31、=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·xj=0,32,maxZ=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,

32、≥0,minw=24y1+40y2 s.t. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y4≥0,X3=0, 3x1+2x2=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,33,,利用互補(bǔ)松弛關(guān)系求解線性規(guī)劃,min z

33、=6x1+8x2+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,原始問題,對偶問題,,,,,最優(yōu)解為(y1, y2)=(6, 0)max y=6,先用圖解法求解對偶問題。,34,min

34、z=6x1+8x2+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

35、 =8 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

36、≥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),,35,資源的影子價(jià)格(Shadow Price),影子價(jià)格越大，說明這種資源越是相對緊缺影子價(jià)格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0,yi’=△w/△b

37、i=最大利潤的增量/第i種資源的增量=第i種資源的邊際利潤,w=b1y1+b2y2+…+biyi+…+bmym,w+△w=b1y1+b2y2+…+(bi+△bi)yi+…+bmym,△w=△biyi,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+2x

38、2≤24 x1+x2≤5 x1,x2≥0,,思考:如果第一種資源增加1，也就是把15變?yōu)?6,目標(biāo)函數(shù)值將怎么變化?為什么?,37,資源的影子價(jià)格是一種機(jī)會(huì)成本根據(jù)互補(bǔ)松弛定理,若yi’ ＞0,則∑aijxj=bi，若yi’ ＝0,則∑aijxj＜bi，,某種資源bi未得到充分利用時(shí)，該種資源的影子價(jià)格為0；當(dāng)資源的影子價(jià)格不為0，表示該種資源在生產(chǎn)中已消耗完畢。,

39、σj=cj-zj=cj-CBB-1Pjcj表示第i種產(chǎn)品的產(chǎn)值，∑aijyi表示生產(chǎn)該種產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格的總和，即產(chǎn)品的隱含成本。,38,Maxz=4x1+10x2 s.t. 3x1+6x2≤5 x1+3x2≤2 2x1+5x2≤4 x1,x2≥0,已知原問題為：,則對偶問題為：,Minw=5y1+2y2+4y3 s.t. 3y

40、1+ y2+2y3≥4 6y1+3y2+5y3≥10 y1,y2,y3≥0,,Maxz=4x1+10x2 s.t. 3x1+6x2+x3=5 x1+3x2 +x4=2 2x1+5x2 +x5=4 xj≥0(j=1,2,…,5),,Minw=5y1+2y2+4y3 s.t.

41、 3y1+ y2+2y3-y4=4 6y1+3y2+5y3-y5=10 yi≥0(i=1,2,…,5),39,初始單純形表為：,此時(shí)對偶問題的解為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)

42、,不是對偶問題的可行解,,40,初始單純形表為：,此時(shí)對偶問題的解為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,對原問題進(jìn)行迭代得：,此時(shí)對偶問題的解為Y＝（0，10/3，0，-2/3，0）代入,Minw=

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

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

45、，從對偶的觀點(diǎn)來看，是在始終保持原始可行解的條件下，不斷改進(jìn)對偶可行性的過程。一個(gè)從對偶不可行的解，經(jīng)過幾次疊代，逐步向?qū)ε伎尚薪饪繑n，一旦得到的解既是原始可行的，又是對偶可行的，這個(gè)解就分別是原始問題和對偶問題的最優(yōu)解。,45,對偶單純形法,對于對偶單純形法剛好和單純形法的思路相反，就是在始終保持對偶問題可行的條件下，不斷改進(jìn)原問題可行性的過程。一個(gè)從原問題不可行的解，經(jīng)過幾次疊代，逐步向原問題可行解靠攏，一旦得到的解既是原始可行的，

46、又是對偶可行的，這個(gè)解就分別是原始問題和對偶問題的最優(yōu)解。,46,步驟：1.確定初始解一般設(shè)松弛變量為初時(shí)基可行解2.判斷 若所有的基變量值均≥0，則此解為線性規(guī)劃問題的最優(yōu)解，若存在基變量的值≤0，則問題還沒有達(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.迭代

47、。使得alk＝1，其余aik為0,47,Minw=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≤-4 -6y1-3y2-5y3≤-10 y1,y2,y3≥0,Maxw’

48、=-5y1-2y2-4y3 s.t. -3y1- y2-2y3+y4=4 -6y1-3y2-5y3+y5=10 yi≥0(i=1,2,…,5),,48,,,49,,50,,,,51,,,,52,53,,54,,,55,,,56,57,此時(shí)對偶問題和原問題都達(dá)到可行，所以均達(dá)到了最優(yōu)解Y＝（2/3.2,0,0,0)W’=-22/3W=22/3,58,Minw=2x1+3x2

49、+4x3 s.t. x1+2x2+ x3≥3 2x1- x2+3x3≥4 x1,x2,x3≥0,,練習(xí):用單純形法求解并求出對偶變量的最優(yōu)解,Maxw’=-2x1-3x2-4x3 s.t. -x1- 2x2-x3≤-3 -2x1 +x2-3x3≤-4 x1,x2,x3≥0,Maxw’=-2x1-3x2-4x3

50、 s.t. -x1-2x2-x3+x4=4 -2x1 +x2-3x3 +x5=10 xi≥0(i=1,2,…,5),,59,此時(shí)對偶問題和原問題都達(dá)到可行，所以均達(dá)到了最優(yōu)解Y＝（11/5.2/5,0,0,0)W’=-28/5W=28/5,60,Maxz=3y1+2y2 s.t. y1+2y2≤2 2y1 -y2≤3

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

52、62,Maxz=3x1-4x2 s.t. x1+2x2≥2 3x1+ x2≥4 x1- x2≤1 x1+ x2≤3 x1,x2≥0,Maxz=3x1+ s.t. -x1-2x2≤-2 -3x1- x2≤-4 x1- x2≤1 x1+ x2≤

53、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 xj≥0,,,63,可以看出，這時(shí)候原問題和對偶問題都不可行,列出初始單純形表：,64,,65,,,,66,,,,67,68,69,70,,7

54、1,,,,72,,,,73,74,75,76,,77,,,,78,,,,79,80,81,82,此時(shí)對偶問題和原問題都達(dá)到可行，所以均達(dá)到了最優(yōu)解X＝（4/3.1/3,0,1/3,0,4/3)Z=8/3,83,第一二三章總結(jié),線性規(guī)劃問題的引出線性規(guī)劃的一般模型線性規(guī)劃的標(biāo)準(zhǔn)形式單純形法的原理單純形法大M法和兩階段法,84,對偶問題的提出根據(jù)原問題寫對偶問題對偶問題的基本性質(zhì)對偶單純形表靈敏度分析,85,習(xí)題,1.

55、研究線性規(guī)劃問題,Maxz=4x1+4x2 s.t. 2x1+7x2≤21 7x1+2x2≤49 xj≥0 (j=1,2),問：1）用圖解法求該問題的最優(yōu)解2）使（寫x1*,x2*）保持最優(yōu)情況下目標(biāo)函數(shù)系數(shù)的比值范圍是多少？,86,2.研究方程組,x1+2x2-3x3+5x4+x5=45x1-2x2 -6x4+x6=82x1+3x2-2x3+3x4+x

56、7=3-x1 +x3+2x4+x8=0 xj≥0 (j=1,2,…,8),問：1）設(shè)(x5,x6,x7,x8)T為初始基變量，如果把x1換入為基變量，則應(yīng)該把初始基變量中的哪個(gè)變量換出？2）如果將x1換入，x5換出，將得到什么解？3）如果將x1換入，x8換出，將得到什么解？,87,3.用圖解法求下列線性規(guī)劃問題,Maxz=-x1

57、+2x2 s.t. x1+x2≥2 -x1+x2≥1 x2≤3 xj≥0 (j=1,2),Maxz=-x1+3x2 s.t. X1-2x2≤4 -x1+x2≤3 xj≥0 (j=1,2),88,4.研究以下線性規(guī)劃問題,已知線性規(guī)劃目標(biāo)函數(shù)為maxz=5x1+3x2,約束條件均為“≤“

58、，所有變量均≥0.,此時(shí)Z＝10，求a-g?,89,5.求線性規(guī)劃問題已知該問題約束條件均為“≤“，所有變量≥0.x3,x4,x5為松弛變量，根據(jù)以下單純形表求線性規(guī)劃問題,90,6.研究線性規(guī)劃問題,Maxz=5x1+2x2+3x3 s.t. x1+5x2+2x3≤b1 x1-5x2-6x3≤b2 xj≥0 (j=1,2,3),問：1）用兩種方法求b1,b22）求a-e

59、3）求對偶問題最優(yōu)解,91,在第k個(gè)約束條件兩邊同乘以λ，原問題和對偶問題的解有何變化？,7.線性規(guī)劃問題max z=CXs.t. AX≤b X ≥0,92,8.研究線性規(guī)劃問題,問：1）寫原問題2）寫出對偶問題3）c2在什么范圍內(nèi)變化最優(yōu)解不變4）增加一個(gè)約束條件 x2+x3≥2,最優(yōu)解是否發(fā)生變化，如果有求新解5）增加一個(gè)變量x6,P6=(1,2)T ,c6=4,最優(yōu)解是否發(fā)生變化，如果有求新解,9

60、3,9.線性規(guī)劃問題為Maxz=6x1+14x2+13x3 s.t. 1/2x1+2x2+x3≤24 x1+2x2+4x3≤60 xj≥0 (j=1,2,3)計(jì)算得最優(yōu)解,當(dāng)約束條件1變?yōu)閤1+4x2+2x3≤68最優(yōu)解有何變化？,94,10.線性規(guī)劃問題為Maxz=5x1+3x2+6x3 s.t. x1+2x2+x3≤18

61、 2x1+x2+3x3＝16 x1+x2+x3＝10 xj≥0 (j=1,2),Maxz=5x1+3x2+6x3’-6x3” s.t. x1+2x2+x3 -x3” +x4=18 2x1+x2+3x3 -3x3” =16 x1+x2+x’-x3”=10 xj≥0 (j=1,2,3),,

62、最優(yōu)解為：,求對偶問題最有解?,95,11.已知線性規(guī)劃問題max Z=3x1+2x2 -x1+2x2≤4 3x1+2x2≤14 x1-x2≤3 x1,x2≥01）寫出它的對偶問題2）應(yīng)用對偶理論證明原問題和對偶問題都存在最優(yōu)解,96,12.已知線性規(guī)劃問題min Z=2x1-x2+2x3 -x1+x2+x3=4 -x1+x2-kx3≤6 x1≤0,x2≥

63、0, x3 無約束其最優(yōu)解為x1= -5, x2=0, x3= -11）求k的值2）寫出并求出其對偶問題的最優(yōu)解,97,13.已知線性規(guī)劃問題min Z=8x1+6x2+3x3+6x4 x1+2x2 +x4≥3 3x1 +x2 +x3 +x4≥6 x3 +x4≥2 x1 + x3 ≥2 x1,x2 x3 ,x4 ≥01

64、）寫出其對偶問題2）已知原問題最優(yōu)解為X*＝（1，1，2，0），試根據(jù)對偶理論，直接求出對偶問題最優(yōu)解。,98,14.某農(nóng)場有100土地及15000元資金可用于發(fā)展生產(chǎn)。農(nóng)場勞動(dòng)力情況為秋冬季3500人日，春夏季4000人日，如勞動(dòng)力本身用不了時(shí)可外出干活，春夏季收入為2.1元人日, 秋冬季收入為1.8元/人日。該農(nóng)場種植三種作物：大豆、玉米、小麥，并飼養(yǎng)奶牛和雞。種作物時(shí)不需要專門投資，而飼養(yǎng)動(dòng)物時(shí)每頭奶牛投資400元，每只雞投資3