運(yùn)籌學(xué)作業(yè)的參考答案

1、第二章作業(yè)的參考答案P734、將下面的線性規(guī)劃問題化成標(biāo)準(zhǔn)形式maxx1-x22x3s.t.x1-2x2+3x3之62x1x2-x3M30Mxim3-1Mx2M6解：將max化為min,x3用x4一x5代替，則min-x1x2-2(x4-x5)s.t.x1-2x23(x4-x5)-62x1x2-(x4-x5)£30Hx1M3_1mx2M6乂4?5-0令x2=x2+1,貝umin-x1x2-1-2(x4-x5)s.t.x1-2(x2-1)3(x4-x5)-62x1(x2一1)一(x4一x5),30Mx1M30Mx2M7x4,x5-0將線性不等式化成線性等式，則可得原問題的標(biāo)準(zhǔn)形式min

2、-x1x2-2x42x5-1s.t.x1-2x23x4-3x5-x6=42x1x2-x4x5x7=4xix8=3x2x9=7xi,x2,x4,x5,x6,x7,x8,x9-0P735、用圖解法求解下列線性規(guī)劃問題:數(shù)）沿它的負(fù)法線方向（-1,-3）T移動到可行區(qū)域的邊界上。于是交點(diǎn)（12,8）,就是該問題的最優(yōu)解，其最優(yōu)值為36。注：用圖解法求解線性規(guī)劃問題的步驟比較準(zhǔn)確地畫出可行區(qū)域；確定等值線及其法線方向；由max或min確定等值線的移動方向，并將其移動到可行區(qū)域的邊界上；得出結(jié)論。minx1-2x2x3Is.t.3x1-x2+2x3+x4=7- 2x14x2x5=12- 4x13x28x

3、3x6=10xj-0,j=1,6解：先將方程組中基變量乂2,乂3,乂6的系數(shù)向量化成單位向量minst.x1-2x2x354x11一2x125一萬Xixj-0,F2x3j=1,12x4-4x418x514x57-4x5=5=3X6=-39,6利用線性方程組的典式，把x2,乂3用x1,x4,x5表示，再帶入目標(biāo)函數(shù)，則可得原問題相應(yīng)于基B=(A2,A3A)的典式mins.t.d51314x12x48x554X1X32x41x8x525X2-4x4lx4x57一X545二5二3x6-39Xj-0,j=1,6mins.t.z=-2x1-x2x33x1x2x360x1-x22x3m10Xix2-x3m

4、20Xj-0,j解：將此問題化成標(biāo)準(zhǔn)形式minz=-2x1-x2st.3x1+x2+x3x1-x22x3X1X2-X3=1,2,3X3X4X5=60=10X6=20Xj-0,j=1,2,3,4,5,6以X4,X5,X6為基變量，可得第一張單純形表為21-10000311100601-120101011-100120XizX4X5進(jìn)基變量,X6以X1為X2X3X4X5X6RHS注（零行元素的獲得）：先將目標(biāo)函數(shù)化成求最小值的形式，再把所有變量移到等式左邊,常數(shù)移到等式右邊。則變量前的系數(shù)為零行對應(yīng)的元素。注意單純形表的格式!注：要用記號把轉(zhuǎn)得XRHS以x2為得所以最優(yōu)優(yōu)值為ZX4XiX203-5

5、0-20-2004-51-30301-120101002-30-1110zX4XiX6X1X2X3x4X5X1X2X3X4X5注：要記住在單純形表的左邊，用進(jìn)基變量代替離基變量進(jìn)基變量，X6為離基變量旋轉(zhuǎn)X6RHS-1-1-32°22011-1-2-32-12-3510155.*T解為X=(15,5,0)，最-35。注：用單純形法求解線性規(guī)劃問題的步驟I、將問題化成標(biāo)準(zhǔn)形式；H、找出初始解；田、寫出第一張單純形表，并化成典式；IV、判定和迭代。判定：1最優(yōu)解（檢驗數(shù)向量自W0）；2問題無界（某個非基變量Xk的檢驗數(shù)0,且Xk在典式中的系數(shù)向量&40）迭代步驟：1確定進(jìn)基變量X

6、k（檢驗數(shù)向量,T中最大的正分量）；2確定轉(zhuǎn)軸元3rk（進(jìn)基變量所在的這一列中的正分量與右端向量中對應(yīng)元素比值最小的）；<3>確定離基變量xr（轉(zhuǎn)軸元所在的這一行對應(yīng)的基變量）；<4>迭代計算（利用初等行變換,其它元素全部變?yōu)?）；將轉(zhuǎn)軸元變?yōu)?,轉(zhuǎn)軸元所在的這一列<5>用進(jìn)基變量Xk代替離基變量Xrminz=x1-x2x3x5-x6s.t.3x3x5x6=6x22x3-x4=10(3)-xx6=0x3x6x7=6xj-0,j=1,2,3,4,5,6,7解：在第三個等式兩端同乘以-1,并以x5,x2,x1,x7為基變量可得其單純形表為將第0行zxx2xi頭7

7、xix2x3乂4x5x6x7RHS-11001106000100-1000116-11-100030012-110000010的元素化為檢驗數(shù)可得注：必須先將線性方程組和目標(biāo)函數(shù)化成典式，再用單純形方法開始判定、迭代!由于x4X4在XiX2X3X4X5XX7RHS0001010-400301106012-10001010000-10000100116zX5X2XiX7的檢驗數(shù)%=1a0,并且典式中的系數(shù)向量TA4=(0,1,0,0)<0,所以問題無界。P7517、用兩階段法求解下列線性規(guī)劃問題：minz=2x4x2Is.t.2x1-3x2-2(2) X1X2-3x1,x2-0解：將此問題

8、化為標(biāo)準(zhǔn)形式minz=2x14x2Is.t.2x1-3x2-x3=2-x1x2-X4=3Xi,X2,X3,X4之0添加人工變量X5,X6得到輔助問題ming=X5%s.t.2x1-3x2-x3-X1x2一x4xi,x2,x3,x4,x5,x6乂5,乂6為基變量，可得輔助問題的單純形表為x1為x6xX5RHS-2-4000000000-1-102-3-10102-110-1013%在的這一行的元素化成檢驗數(shù)zgx1x2x3x4乂2x3x4x5x6RHSz-2-400000g1-2-1-1005乂52-3-10102x6-110-1013xiX6=3注：必須先將線性方程組和目標(biāo)函數(shù)化成典式,才可以

9、開始判定、迭代!進(jìn)基變量，x5為變量旋轉(zhuǎn)得所以，輔0-7-10102-i-i-i0-104222-3-ii10012220-i-i-1i14222X2XX3zgXiX6助問題的最優(yōu)解為X=(1,0,0,0,0,4)t,其*最優(yōu)值為g=4>0。因此，原問題沒有可行解。maXz=2X1-4x25x3-6X4s.t.X1+4x2-2x3+8x4=2Xi2X23X34x4=1Xi,X2,X3,X4上0解：將此問題化成標(biāo)準(zhǔn)形式minz=-2x14x2-5x36x4s.t.X1+4x2-2x3+8x4=2-X12x23x34x4=1Xi區(qū)名區(qū)-0添加人工變量X5,X6得到輔助問題ming二X5X6s

10、.t.x14x2-2x38x4x5=2-x12x23x34x4x6=1x,x2,x3,x4,x5,x6-0xRHS以乂5,乂6為基變量，可得輔助問題的單純形表為2-45-60000000-1-1014-28102-1234011xix2x3x4乂5zgx%在的這一行的元素化成檢驗數(shù)xRHS以x4為2-45-60000611200314-28102-1234011xix2x3x4x5zg乂5%進(jìn)基變量,x5為離基變量旋轉(zhuǎn)得11-1X4以X3為轉(zhuǎn)得所以，輔其最優(yōu)值為gX4X6-32-32-1進(jìn)基變量,X6為離基變量旋65-10016-719816320000-1-101101322-3010831

11、3216-1184140X2X3X4X1X5X6RHSzgX4X3助問題的最優(yōu)解為1Tx'=(0,0,0；0,0)T,401Tg=0。因此，原問題的初始解為x=(0,0,0,一),其第一張單純形表為4X2X3X4RHSZX4X36516132-100一301008進(jìn)基變量,X4為離基變量旋轉(zhuǎn)得因此，原0-660-130-311160320611283X3X4RHSzXiX3問題的最優(yōu)解為(8,0,3,0)t,最優(yōu)102注：要先將問題化成一般形式，再按規(guī)則寫出它的對偶問題。要記住判定對偶變量是自由變量還是非負(fù)變量值為31。?618、寫出下列線性規(guī)劃問題的對偶規(guī)劃：minz=X12x24x

12、3s.t.2x1+3x2+4x3>22x1x26x3=3X1+3x2+5x3w5X1,x2一0,x3為自由變量解：先將此問題化成一般形式minz=X1+2x2+4x3s.t.2x1+3x2+4x3之22x1x26x3=3_Xi-3X2_5X3-_5X1,x20,x3為自由變量所以，其對偶規(guī)劃為max2132-53s.t.281+2切2一缶3w1312-33-24«1+6切25切3=4I238。3之0,。2為自由變量P7720、給定線性規(guī)劃問題mins.t.z=X1X3x12x2三512X2X3=3Xi,X2,記為(P)(1)用單純形算法解P；(2)寫出P的對偶問題D;(3)寫出

13、P的互補(bǔ)松緊條件，并利用它們解對偶D;解：(1)把問題(P)化為標(biāo)準(zhǔn)形式minz=X1X3s.t.X12x2x4=51 QX2X3=32Xi,X2,X3,X4-0以Xi,X3為基變量，可得到其單純形表為：XiX2X3X4RHSzXiX3-10-10012015把第0行化成檢驗行，得以x2為進(jìn)基變量,X2X3X1為離基變量，旋轉(zhuǎn)得根據(jù)最優(yōu)_5_14004741101221140144|72|5X4RHSzX2X3化準(zhǔn)則知，問題（P）的最優(yōu)解為*57TX=(0,),取優(yōu)值為24（2）將問題（P）化為一般形式minz=Xi+X3s.t.X1-2x2-54 1*_ox2*x3=3X1,X2,X3-0因

14、此其對偶問題(D)為max-5®1+3切25 .t.一01M1一1,一-21-2-022E1®1至0J571（3）由問題（P）的最優(yōu)解為x一（0，二，一）以及互補(bǔ)松緊性定律可得241解得01=,82=1.所以，對偶問題（4，一，.=，*1T一，-，D）的最優(yōu)解為切=（,1）,最優(yōu)值為47-51.i3._,2-.4P7722、用對偶單純形法解下列問題minz=2x13x24x3st.x12x2x3-3（1）2x1-x23x3-4X-0,i=1,2,3.解：引入剩余變量將原問題標(biāo)準(zhǔn)化minz=2x13x24x3js.t.x1+2x2+x3-x4=32x1-x23x3-x5=4為

15、-0,i=1,2,3,4,5.再將約束條件兩邊同時乘以-1得minz=2x13x24x3st.-x1-2x2-x3x4=-3-2x1x2-3x3x5=4X-0,i=1,2,3,4,5.以x4,x5為基變量，可得其單純形表為注：若問題存在一個基本解，并且該解的檢驗數(shù)向量小于等于零，則可使用對偶單純形方法。特別地，要將問題典式化X5X4根據(jù)最-2-3-400X4X5X4Xi-1-2-110-2J1-301XiX2-4-3-4X3X4X5RHS-10-1-1為離基變量，X1為進(jìn)基變量，旋轉(zhuǎn)得為離基變量，X2為進(jìn)基變量，旋轉(zhuǎn)981nn一一一一一28005555/2/112015555271一11105

16、555zX2優(yōu)化準(zhǔn)則知，原問題的最優(yōu)解為*XXX2X3X4X5RHS228（一,一,0）,取優(yōu)值為一555注：用對偶單純形方法求解線性規(guī)劃問題的步驟I、將問題化成標(biāo)準(zhǔn)形式；n、找出初始解；出、寫出第一張單純形表，并化成典式；W、判定和迭代。判定：i最優(yōu)解（右端向量b之0）；2沒有可行解（某個br0,并且在典式中br所在的這一行內(nèi)沒有負(fù)分量）迭代步驟:< 1>確定離基變量xr（右端向量最小的負(fù)分量）T< 2>確定轉(zhuǎn)軸元ark（離基變量所在的這一行中的負(fù)分量與一中對應(yīng)元素比值最小的）< 3>確定進(jìn)基變量xk（轉(zhuǎn)軸元所在的這一列對應(yīng)的非基變量）<4>迭

17、代計算（利用初等行變換，將轉(zhuǎn)軸元變?yōu)?,轉(zhuǎn)軸元所在的這一列其它元素全部變?yōu)?）;<5>用進(jìn)基變量Xk代替離基變量minz=3x12x2s.t.x1x2x3一x1x3-(2)x2x-x3xi0,i=1,2,3.解：先將原問題標(biāo)準(zhǔn)化min3x12x2x3s.t.x2x3x4x1x3X5x2x3x6xi-0,i=1,2,3,4,5,6.在第2、3個等式的兩端同乘以-1,并以x4,x5,x6為基變量，可得其單純形表為X5-3-2-100001111006回01010-40-11001-3zX4X5X6離基變量，X1為進(jìn)基變量，旋轉(zhuǎn)X2X3X4X5X24RHSXiX2X3X4X5X6RHSX

18、6量，X2-2-40-3012X4XiX6為進(jìn)基變量，旋轉(zhuǎn)得2110-10-101001-3X4XiX2所以，原問題沒有可行解。（X4所在行）F7823、考慮第20題中的線T規(guī)劃（P）,利用問題（P）XiX2X3X4X5X6RHS00-60-3-218-1-1-1-1-1的最優(yōu)單純形表繼續(xù)求解下列問5（1）a由1變?yōu)椋?解：因為只有非基變量X1的價值系數(shù)G由1變?yōu)?5,故只需要在問題（P）的最優(yōu)單純4一，一.55形表中，把X1的檢驗數(shù)按如下規(guī)則改變：+（gc1）=+（1（）=1,得到44新問題的單純形表如下以Xi為根據(jù)最解為X2X3XiX2X3X4RHS50-204_13412010110253X2X4RHSZX1X35進(jìn)基變量,注：要先寫出變化規(guī)則，再由原問題的最優(yōu)單純形表得到新問題的單純形表。X2為離基變量，旋轉(zhuǎn)得優(yōu)化準(zhǔn)則知，修改后的