線性規(guī)劃的對(duì)偶理論

1、2.1 寫出線性規(guī)劃問題的對(duì)偶問題，并進(jìn)一步寫出其對(duì)偶問題的對(duì)偶問題(a) min z=2x1+2x2+4x3(b) max z=5x1+6x2+3x3s.t. x1+3x2+4x32s.t. x1+2x2+2x3=52x1+x2+3x33-x1+5x2-3x33x1+4x2+3x3=54x1+7x2+3x38x1, x20, x3無約束x1無約束,x20, x30解：(a)對(duì)偶問題的原問題為max w=2y1+3y2+5y3s.t. y1+2y2+y32 3y1+y2+4y32 4y1+3y2+3y3=4y10, y20, y3無約束(b)原問題的對(duì)偶問題為min w=5y1+3y2+8y3

2、s.t. y1-y2+4y3=5 2y1+5y2+7y36 2y1-3y2+3y33y1無約束, y20, y302.3 已知線性規(guī)劃問題：max z=x1+x2s.t. -x1+ x2+ x32-2x1+x2- x31x1, x2, x30試應(yīng)用對(duì)偶理論證明上述線性規(guī)劃問題最優(yōu)解為無界。解：原問題的對(duì)偶問題為min w=2y1+ y2s.t. -y1- 2y2 1 2y1+ 5y2 1 y1- y2 0 y1, y20由于約束條件3可得y1-y2 0 y1y2 -y1-y2 且y20所以-y1-2y2 -3y20（1）由于約束條件1可得-y1- 2y2 1（2）（1）（2）不等式組無解所以其

3、對(duì)偶問題無可行解,又知點(diǎn)X=(1,1,1)為原問題一個(gè)可行解,即原問題有可行解,現(xiàn)在其對(duì)偶問題無可行解。根據(jù)對(duì)偶理論性質(zhì)3原問題無界.2.4 已知線性規(guī)劃問題：max z=2x1+4x2+ x3+x4s.t. x1+ 3x2 +x482x1+ x26 x2+ x3 +x46x1+ x2+ x39xj0 (j=1,4)要求(a)寫出其對(duì)偶問題;(b)已知原問題最優(yōu)解X=(2,2,4,0),試根據(jù)對(duì)偶理論,直接求出對(duì)偶問題的最優(yōu)解.解:對(duì)偶問題:min w=8y1+ 6y2+6y3+9 y4s.t. y1+ 2y2 +y42 3y1+ y2 +y3 +y4 4 y3+ y4 1y1 +y3 1 y

4、1, y2,y3, y40將最優(yōu)解X=(2,2,4,0)代入原問題的約束條件得:x1+ 3x2 +x4=82x1+ x2=6x2+ x3 +x4=6x1+ x2+ x3=8<9根據(jù)對(duì)偶理論性質(zhì)5，如果，則。于是從第四個(gè)約束方程計(jì)算可有將性質(zhì)5應(yīng)用于其對(duì)偶問題，這時(shí)有：如果，則因?yàn)楸绢}中x1=2 >0，x2=2>0， x3=4>0.所以得到約束方程組（其中）y1+ 2y2 +y4=2 3y1+ y2 +y3+ y4=4 y3+ y4 =1解此方程組得Y=(4/5 ,3/5 , 1, 0).（對(duì)偶問題的最優(yōu)解）2.8 已知線性規(guī)劃問題：max z=2x1-x2+ x3s.t

5、. x1+ x2 +x36-x1+ 2x24x1, x2 ,x30先用單純形法求出最優(yōu)解，再分別就下列情形進(jìn)行分析：(a) 目標(biāo)函數(shù)中變量x1, x2 ,x3的系數(shù)分別在什么范圍內(nèi)變化，問題的最優(yōu)解不變；(b) 兩個(gè)約束的右端項(xiàng)分別在什么范圍內(nèi)變化，問題的最優(yōu)基不變；解：將此問題化成標(biāo)準(zhǔn)形式，max z=2x1-x2+x3+0x4s.t. x1+x2+x3+x4 =6-x1+2x2 +x5=4x1, x2, x3, x4, x50其約束系數(shù)矩陣：單純形法求解的過程見表如下單純形法的求解過程Cj2-1100CB基bX1X2X3X4X50X46111100X54-12001Cj-zj2-1100由

6、于2>1, 選擇x1作為換入基的變量。對(duì)于P1有：=min b1/a11 | a11>0 =min6/1 =6. 確定x4為換出基變量。a11=1為主元素單純形法的求解過程Cj2-1100CB基bX1X2X3X4X52X16111100X51003111Cj-zj0-3-1-20至此，所有檢驗(yàn)數(shù)j0，表明現(xiàn)有對(duì)應(yīng)的基可行解為最優(yōu)解x1=6, x2=0, x3=0, x4=0，x5=10。原線性規(guī)劃問題的最優(yōu)解為x1=6, x2=0, x3=0,相應(yīng)目標(biāo)函數(shù)值max z=2x1-x2+x2=12。(a)若要目標(biāo)函數(shù)中變量x1, x2 ,x3的系數(shù)變化，而問題的最優(yōu)解不變分析下面已知線

7、性規(guī)劃問題：max z=（2+1）x1+（-1+2）-x2+（1+3） x3s.t. x1+ x2 +x36-x1+ 2x24x1, x2 ,x301，2和3分別在什么范圍變化，問題的最優(yōu)解不變解：當(dāng)2=3=0時(shí)上述線性規(guī)劃問題的最終單純性表為Cj2+1-1100CB基bX1X2X3X4X52+1X16111100X51003111Cj-zj0-3-1-1-1-2-10要使所有檢驗(yàn)數(shù)j0，則需-3-10，-1-10，-2+1 0解得1-1。當(dāng)1=3=0時(shí)上述線性規(guī)劃問題的最終單純性表為Cj2-1+2100CB基bX1X2X3X4X52X16111100X51003111Cj-zj02-3-1-

8、20要使所有檢驗(yàn)數(shù)j0，則需2-30，解得23。當(dāng)1=2=0時(shí)上述線性規(guī)劃問題的最終單純性表為Cj2-11+300CB基bX1X2X3X4X52X16111100X51003111Cj-zj0-33-1-20要使所有檢驗(yàn)數(shù)j0，則需3-10，解得31。綜合上述結(jié)果：c1+12-1=1，c2+2-1+3=2， c3+31+1=2，即x1, x2 ,x3的系數(shù)分別在1，2，2范圍內(nèi)，問題的最優(yōu)解不變。（b）Cj2-1100CB基bX1X5X2X3X4X52X161011100X510013111Cj-zj00-3-1-20有這個(gè)線性規(guī)劃問題最終單純性表可知：為方便改寫初始單純性表：Cj20-1100CB基bX1X5X2X3X4X50X461011100X54-112001Cj-zj20-1100所以分析下