運籌學第二章作業(yè)參考答案(DOC)

1、運籌學第二章作業(yè)的參照答案.(DOC)運籌學第二章作業(yè)的參照答案.(DOC)20/20運籌學第二章作業(yè)的參照答案.(DOC)第二章作業(yè)的參照答案P734、將下面的線性規(guī)劃問題化成標準形式maxx1x22x3s.t.x12x23x362x1x2x330 x131x26解：將max化為min，x3用x4x5代替，則minx1x22(x4x5)s.t.x12x23(x4x5)62x1x2(x4x5)30 x13x26x4,x50令x2x21，則minx1x212(x4x5)s.t.x12(x21)3(x4x5)62x1(x21)(x4x5)30 x130 x27x4,x50將線性不等式化成線性等式，

2、則可得原問題的標準形式1minx1x22x42x51s.t.x12x23x43x5x642x1x2x4x5x74x1x83x2x97x1,x2,x4,x5,x6,x7,x8,x90P735、用圖解法求解下列線性規(guī)劃問題：X2minx13x2法線方向s.t.x1x220等值線6x18（1）12x22o1220X1圖2.1解：圖2.1的陰影部分為此問題的可行地域。將目標函數(shù)的等值線x13x2c（c為常數(shù)）沿它的負法線方向（TT1，3）移動到可行地域的邊界上。于是交點（12，8）就是該問題的最優(yōu)解，其最優(yōu)值為36。注：用圖解法求解線性規(guī)劃問題的步驟比較正確地畫出可行地域；確定等值線及其法線方向；由m

3、ax或min確定等值線的移動方向，并將其移動到可行地域的邊界上；得出結(jié)論。2P7412、對于下面的線性規(guī)劃問題，以B(A2,A3,A6)為基寫出對應(yīng)的典式。minx12x2x3s.t.3x1x22x3x472x14x2x5124x13x28x3x610 xj0,j1,6解：先將方程組中基變量x2,x3,x6的系數(shù)向量化成單位向量minx12x2x3s.t.5x1x31x41x554281x1x21x532425x14x47x5x63924xj0,j1,6利用線性方程組的典式，把x2,x3用x1,x4,x5表示，再帶入目標函數(shù)，則可得原問題相應(yīng)于基B(A2,A3,A6)的典式min15x1x3x

4、412485s.t.5xx1x1x541324851xx1x32124525x4x7xx39214456xj0,j1,63P7516、用單純形法求解下列線性規(guī)劃問題：minz2x1x2x3s.t.3x1x2x360 x1x22x310(1)x1x2x320 xj0,j1,2,3注（零行元素的獲得）：解：將此問題化成標準形式minz2x1x2x3先將目標函數(shù)化成求s.t.3x1x2x3x460最小值的形式，再把所x1x22x3x510有變量移到等式左邊，x1x2x3x620 xj0,j1,2,3,4,5,6常數(shù)移到等式右邊。則以x4,x5,x6為基變量，可得第一張單純形表為變量前的系數(shù)為零行對應(yīng)

5、的元素。x1x2x3x4x5x6RHSz21-10000注意單純形表x431110060的格式！x51-1201010注：要用記號把x611-100120轉(zhuǎn)軸元標出來以x1為進基變量，x5為離基變量旋轉(zhuǎn)得4以x2為得所以最優(yōu)優(yōu)值為x1x2x3x4x5x6z03-50-20 x404-51-30 x11-12010 x602-30-11x1x2x3x4x5z0010122x40011-1x11010122x20130122RHS注：要記住在單-20純形表的左邊，30用進基變量代替離基變量10進基變量，x6為離基變量旋轉(zhuǎn)10 x6RHS3-352-210115215解為x*(15,5,0)T，最2

6、-35。注：用單純形法求解線性規(guī)劃問題的步驟、將問題化成標準形式；、找出初始解；、寫出第一張單純形表，并化成典式；、判斷和迭代。判斷：最優(yōu)解（查驗數(shù)向量0）；問題無界（某個非基變量xk的查驗數(shù)k0，且x在典式中的系數(shù)向量A0）kk迭代步驟：確定進基變量xk（查驗數(shù)向量T中最大的正分量）；確定轉(zhuǎn)軸元ark（進基變量所在的這一列中的正分量與右端向量中對應(yīng)元素比值最小的）；5確定離基變量xr（轉(zhuǎn)軸元所在的這一行對應(yīng)的基變量）；迭代計算（利用初等行變換，將轉(zhuǎn)軸元變?yōu)?，轉(zhuǎn)軸元所在的這一列其余元素全部變?yōu)?）；用進基變量xk代替離基變量xr。minzx1x2x3x5x6s.t.3x3x5x66x22x3

7、x410（3）x1x60 x3x6x76xj0,j1,2,3,4,5,6,7解：在第三個等式兩端同乘以-1，并以x5,x2,x1,x7為基變量可得其單純形表為x1x2x3x4x5x6x7RHSz-11-10-1100 x500301106x2012-100010注：必須先將線性方程組和目標函數(shù)化成典式，再用單純形方法開始判斷、迭代！x110000-100將第0行x700100116的元素化為查驗數(shù)可得6x1x2x3x4x5x6x7RHSz0001010-4x500301106x2012-100010 x110000-100 x700100116由于x4410，并且的查驗數(shù)x4在典式中的系數(shù)向量

8、A4(0,1,0,0)T0，所以問題無界。P7517、用兩階段法求解下列線性規(guī)劃問題：minz2x14x2s.t.2x13x22（2）x1x23x1,x20解：將此問題化為標準形式minz2x14x2s.t.2x13x2x32x1x2x43x1,x2,x3,x40增添人工變量x5,x6獲得輔助問題7mingx5x6s.t.2x13x2x3x52x1x2x4x63x1,x2,x3,x4,x5,x60以x5,x6為基變量，可得輔助問題的單純形表為x1x2x3x4x5x6RHSz-2-400000g0000-1-10 x52-3-10102x6把g所-110-1013在的這一行的元素化成查驗數(shù)x1x

9、2x3x4x5x6RHS注：必須先將線z性方程組和目標-2-400000g1-2-1-1005函數(shù)化成典式，x52-3-10102才可以開始判x6-110-1013定、迭代！以x1為進基變量，x5為離基變量旋轉(zhuǎn)得8x1x2x3x4x5x6RHSz0-7-1010211310101222x6011-1114222所以，輔助問題的最優(yōu)解為x*(1,0,0,0,0,4)T，其最優(yōu)值為g*40。因此，原問題沒有可行解。maxz2x14x25x36x4s.t.x14x22x38x42（4）x12x23x34x41x1,x2,x3,x40解：將此問題化成標準形式minz2x14x

10、25x36x4s.t.x14x22x38x42x12x23x34x41x1,x2,x3,x40增添人工變量x5,x6獲得輔助問題9mingx5x6s.t.x14x22x38x4x52x12x23x34x4x61x1,x2,x3,x4,x5,x60以x5,x6為基變量，可得輔助問題的單純形表為x1x2x3x4x5x6RHSz2-45-6000g0000-1-10 x514-28102x6-1234011把g所在的這一行的元素化成查驗數(shù)x1x2x3x4x5x6RHSz2-45-6000g06112003x514-28102x6-1234011以x4為進基變量，x5為離基變量旋轉(zhuǎn)得10zgx4以x3

11、為x6轉(zhuǎn)得zgx4所以，輔x1x2x3x4x5x6RHS11-1703034242304030022111110182484304011022x1x2x3x4x5x6RHS651973-1008161620000-1-10110131132232164進基變量，x6為離基變量旋助問題的最優(yōu)解為x3其最優(yōu)值為g31110(0,0,0,1004,0,0)T88x，40。因此，原問題的初始解為x0(0,0,0,1)T，其第一張單純形表為4x1x2x3x4RHS65-1003z216x411011322430100 x38以x1為進基變量，x4為離基變量旋轉(zhuǎn)得11x1x2x3x4RHSz0-660-1

12、30-31x11160328x3061123因此，原問題的最優(yōu)解為x*(8,0,3,0)T，最優(yōu)值為31。P7618、寫出下列線性規(guī)劃問題的對偶規(guī)劃：minzx12x24x3s.t.2x13x24x322x1x26x33x13x25x35x1,x20,x3為自由變量解：先將此問題化成一般形式minzx12x24x3s.t.2x13x24x322x1x26x33x13x25x35x1,x20,x3為自由變量所以，其對偶規(guī)劃為max213253s.t.21223131233241625341,30,2為自由變量123注：要先將問題化成一般形式，再按規(guī)則寫出它的對偶問題。要記住判斷對偶變量是自由變量

13、仍是非負變量12P7720、給定線性規(guī)劃問題minzx1x3s.t.x12x251x2x332x1,x2,x30記為（P）1）用單純形算法解P;2）寫出P的對偶問題D;3）寫出P的互補松緊條件,并利用它們解對偶D;解：(1)把問題（P）化為標準形式minzx1x3s.t.x12x2x451x2x332x1,x2,x3,x40以x1,x3為基變量，可獲得其單純形表為:x1x2x3x4RHSz-10-100 x112015x3011032把第0行化成查驗行，得13x1x2x3x4RHSz050182x112015x301103進基變量，x1為離基變量，旋轉(zhuǎn)得以x2為2x1x2x3x4RHS5z40

14、0 x21102根據(jù)最優(yōu)1x3401將問題（P）化為一般形式1744152217化準則知，問題（P）的最優(yōu)解為4(0,5,7)T,最優(yōu)值為74x*.244minzx1x3s.t.x12x2511x2x3322x1,x2,x30因此其對偶問題（D）為max5132s.t.112101222110(3)由問題（P）的最優(yōu)解為x*(0,5,7)T以及互補松緊性定律可得24142101221解得11，21.所以，對偶問題（D）的最優(yōu)解為*(1,1)T，最優(yōu)值為4745132.4P7722、用對偶單純形法解下列問題.minz2x13x24x3s.t.x12x2x33（1）2x1x23x34xi0,i1,

15、2,3.解：引入節(jié)余變量將原問題標準化minz2x13x24x3s.t.x12x2x3x432x1x23x3x54xi0,i1,2,3,4,5.再將拘束條件兩邊同時乘以1得minz2x13x24x3s.t.x12x2x3x432x1x23x3x54xi0,i1,2,3,4,5.以x4,x5為基變量，可得其單純形表為注：若問題存在一個基本解，并且該解的查驗數(shù)向量小于等于零，則可使用對偶單純形方法。特別地，要將問題典式化15x1x2x3x4x5RHSz-2-3-4000 x4-1-2-110-3以x5x5-21-301-4為離基變量，x1為進基變量，旋轉(zhuǎn)得x1x2x3x4x5RHSz0-4-10-

16、14x45110212-12以x4x1131為離基變量，x2為進基變量，旋轉(zhuǎn)102222得x1x2x3x4x5RHSz00981285555x21212015555根據(jù)最x171211優(yōu)化準則知，原問題的最優(yōu)解為105555(11,2,0)T,最優(yōu)值為28x*.555注：用對偶單純形方法求解線性規(guī)劃問題的步驟：、將問題化成標準形式；、找出初始解；、寫出第一張單純形表，并化成典式；、判斷和迭代。判斷：最優(yōu)解（右端向量b0）；沒有可行解（某個br0，并且在典式中br所在的這一行內(nèi)沒有負分量）16迭代步驟：確定離基變量xr（右端向量最小的負分量）arkT確定轉(zhuǎn)軸元（離基變量所在的這一行中的負分量與中

17、對應(yīng)元素比值最小的）確定進基變量xk（轉(zhuǎn)軸元所在的這一列對應(yīng)的非基變量）迭代計算（利用初等行變換，將轉(zhuǎn)軸元變?yōu)?，轉(zhuǎn)軸元所在的這一列其余元素全部變?yōu)?）；用進基變量xk代替離基變量xr。minz3x12x2x3s.t.x1x2x36（2）x1x34x2x33xi0,i1,2,3.解：先將原問題標準化minz3x12x2x3s.t.x1x2x3x46x1x3x54x2x3x63xi0,i1,2,3,4,5,6.在第2、3個等式的兩端同乘以-1，并以x4,x5,x6為基變量，可得其單純形表為17x1x2x3x4x5x6RHSz-3-2-10000 x41111006x5-101010-4以x5x6

18、0-11001-3x1為進基變量，旋轉(zhuǎn)為離基變量，得x1x2x3x4x5x6RHSz0-2-40-3012x40121102x110-10-104以x6為x6x1x2x3x4x5x6RHS0-11001-3離基變z量，x200-60-3-218x4為進基變量，旋轉(zhuǎn)得003111-1x110-10-104x201-100-13所以，原問題沒有可行解。(X4所在行)P7823、考慮第20題中的線性規(guī)劃（P），利用問題（P）的最優(yōu)單純形表持續(xù)求解下列問18題.(1)c1由1變?yōu)?；4解：因為只有非基變量x1的價值系數(shù)c1由1變?yōu)?P）的最優(yōu)單純,故只需要在問題（455形表中，把x1的查驗數(shù)按如下規(guī)則改變：1(c1c1)1(1()1，獲得44新問題的單純形表如下x2x3x4RHSx117z10044注：要先寫出變化規(guī)則，再由原問題的最優(yōu)單純形表獲得新問題的單純形表。x211015222以x1為117進基變量，x2為離基變量，旋轉(zhuǎn)得x340144x1x3x2x4RHSz25130044x112015根據(jù)最x