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

1、第二章作業(yè)的參考答案P73 4、將下面的線性規(guī)劃問題化成標(biāo)準(zhǔn)形式maxx1x22x3s.t.x12x23x3 62x1x2x3 30 x1 31 x2 6解：將 max 化為 min ， x3用 x4 x5代替，則minx1 x2 2(x4 x5 )s.t. x1 2x2 3(x4 x5) 6 2x1 x2 (x4 x5 ) 3 0 x1 31 x2 6 x4 ,x5 0令 x2 x2 1 ，則minx1 x212(x4 x5)s.t.x12(x21)3(x4 x5) 62x1(x21)(x4 x5) 30x1 30x2 7x4,x5 0將線性不等式化成線性等式，則可得原問題的標(biāo)準(zhǔn)形式1min

2、x1 x2 2x4 2x5 1s.t. x12x23x43x5 x6 42x1x2x4x5 x7 4x1x83x2x97x1,x2,x4,x5,x6,x7,x8,x9P73 5、用圖解法求解下列線性規(guī)劃問題： 比較準(zhǔn)確地畫出可行區(qū)域； minx1 2x2 x3到可行區(qū)域的4邊x界1 上；3x2 8x3x6 10 得出x j結(jié)論0。, j 1, ,6解：先將方程組中基變量 x2, x3 , x6的系數(shù)向量化成單位向量xj 0, j 1,6利用線性方程組的典式，把x2,x3用 x1 , x 4 , x 5表示，再帶入目標(biāo)函數(shù)，則可得原問題相應(yīng)于基 B (A2 ,A3,A6 ) 的典式513min1

3、x1x4x541248511s.t.x1x3x4x541248511x1x2x521452572 x14x44x5 x6xj 0,j1,65339minx1 2x2x3511s.t.x1x3 x4x55413 2 485112 x1x2x5453257x14x4x5 x639214 5 65minz2x1 x2 x3s.t.3x1x2 x3 60x1x2 2x3 10(1)x1x2 x3 20xj0, j 1, 2,3解：將此問題化成標(biāo)準(zhǔn)形式P75 16、用單純形法求解下列線性規(guī)劃問題：注（零行元素的獲得） ： 先將目標(biāo)函數(shù)化成求 最小值的形式， 再把所 有變量移到等式左邊， 常數(shù)移到等式右邊

4、。 則minz2x1x2x3s.t.3x1x2x3x460x1x22x3x510x1x2x3x6 20xj 0, j 1, 2, 3, 4,5,6以 x1以 x2 為得xz5所以最優(yōu)x64為-35。x1注：用單步驟x6x4、將 、找 、寫 成典式；、判x4數(shù)向量x1某個x2x1x2x3 x4 x5 x6RHS21-1 0 0 003 x11 x21 1 0 0 x3 x4 x5 x6R6H0S10-31-250 -120-1201014-1501 -03 102301-12 0 1 01002-3 0 -1 110以 x4,x5,x6 為基變量，可得第一張單純形表為z解為 xx1 x2x3x4

5、x5x6RHS注 意單純 形表進(jìn)基變量，的注格：x進(jìn)基變量，要用記要為式離用！基記軸：元要標(biāo)記單 x6 為離基變量旋轉(zhuǎn) 純形表的左邊，用（進(jìn)15基, 5變, 0量）T代，最替優(yōu)值純形法求離解基線變性規(guī)量劃問題的問題化成標(biāo)準(zhǔn)形式；出初始解；出第一張單純形表，并化1 1 30 0 02 2 2-1-2-3510定和迭代。判定： <1> 最優(yōu)解（檢驗(yàn)1212150 ）； <2> 問題無界非 基變 量 xk 的檢驗(yàn) 數(shù)且 xk 在典式中的系數(shù)向量 Ak 0 ） 迭代步驟：<1> 確定進(jìn)基變量 xk （檢驗(yàn)數(shù)向量 T 中最 大的正分量）；<2> 確定轉(zhuǎn)軸元

6、 ark （進(jìn)基變量所在的這一 列中的 正分量與右端向量中 對應(yīng)元素比值 最小 的）；<3> 確定離基變量 xr （轉(zhuǎn)軸元所在的這一 行對應(yīng)的基變量）；-1，并以 x5,x2,x1,x7 為基變量可得其單純形表為x1x2x3x4x5x6x7RHSz-11-10-1100x500301106x2012-100010x110000-100x700100116x1x2x3x4x5x6x7RHSz0001010-4x500301106x2012-100010x110000-100x700100116將第 0 行 由 于 x4x 4 在的檢驗(yàn)數(shù)典式中的系的元素化為檢驗(yàn)數(shù)可41注：必須先將線

7、，性并方且程組和目標(biāo)再用單純形方法開始判定、迭代！<4> 迭代計(jì)算 （利用初等行變換， 將轉(zhuǎn)軸元變?yōu)?1，轉(zhuǎn)軸元所在的這一列 其它元素 全部 變?yōu)?0）；<5> 用進(jìn)基變量xk 代替離基變量xr 。min zx1x2 x3 x5x6s.t.3x3x5 x66x22x3 x4103)x1x60x3x6 x76xj0,j 1,2,3,4,5,6,7解：在第三個等式兩端同乘以A4 （0, 1, 0,0）T 0 ，所以問題無界。P75 17、用兩階段法求解下列線性規(guī)劃問題：min z2x13x2x2s.t. 2x1 x1 x1 ,x2 0解：將此問題化為標(biāo)準(zhǔn)形式2)4x2231

8、9min z 2x1 4x2s.t. 2x1 3x2 x32x1 x2x43x1 ,x2,x3,x4 0添加人工變量 x5 , x6得到輔助問題min g x5 x6s.t. 2x1 3x2 x3x52x1 x2 x4x63x1 ,x2,x3,x4,x5,x60以 x5,x6 為基變量，可得輔助問題的單純形表為把 g 所 在的這一行的元素化成檢驗(yàn)數(shù) x1 x2 x3 x4 x5x6 RHSz-2-400000g0000-1-10x52-3-10102x6-110-1013以 x1 為所以，輔最優(yōu)值為沒有可行（4）-2-400000Sx11-2x 2-1 x3-1x40x5 0x6RH20-37

9、-1 -1001 00111-01120 2-121031110012221110-114222z g xz5 xg6x1x6x1g解。變 助x2 x3 x4 x5 x6 RHS 進(jìn)基變注：必須先將線 量， x5 為離基變量旋轉(zhuǎn)得 性問方題程的組和最目優(yōu)標(biāo)解 函數(shù)（1,化0,成0,0典,0式,4，）T ，才4可 以0 。開因此始，原判問題定、迭代！max z2x14x25x36x4s.t. x14x22x38x42x12x23x34x41x1 ,x2,x3,x40解：將此問題化成標(biāo)準(zhǔn)形式min z2x14x25x36x4s.t. x14x22x38x42x12x23x34x41x1 ,x2,x

10、3,x4添加人工變量 x5 ,x6 得到輔助問題min gs.t.x1x1x54x22x2x62x3 8x43x3 4x4x1 ,x2,x3,x4,x5,x6x5,x6 為基變量，可得輔助問題的單純形表為g所x4 為x3 為所以，輔gzxg5x65x6優(yōu)值為始解為一張單純x5x6以 x1進(jìn)基量，x4為離基變 量旋轉(zhuǎn)得 因此，原 問題的最 優(yōu)解為x*z(8,0,3x,30，最優(yōu)值 為 31。x21 -x42 x53-x64x0 x056RH0 S0 0 00-1 -102 -4 5-60 0001 64 -1218210 0023-1 24 -328401 1012-1 2 340 11RHS助

11、x1 x2 x3 x4 x5 x6在的這一行的元素化成檢驗(yàn)數(shù)進(jìn)基變量， x5 為離基變量旋轉(zhuǎn)得進(jìn)基變量， x6 為離基變量旋轉(zhuǎn)得x1x2x3x4x5x6RHS11-1703034242330400022111110182484304011022g形表為x60 xx4651973-1001616820000-1-10x11x21x3x4RH3S1101T03 22 -660-130164T310100181603284061123x1x3x4x1x2x3 x4x5x6RHS問題的最優(yōu)解為1(0,0,0,41,0,0)T，其最0 。因此，原問題的初1T(0,0,0, )T ，其第4x165x4x3

12、16132x2 x3 x4 RHS-1 0 0P76 18、寫出下列線性規(guī)劃問題的對偶規(guī)劃：minz x1 2x2 4x3s.t.2x13x24x322x1x26x33x13x25x35x1,x2 0,x3為自由變量先將此問題化成一般形式minzx1 2x24x3s.t.2x13x24x322x1x26x33x13x25x35x1,x2 0,x3為自由變量所以，其對偶規(guī)劃為max2132 5 3s.t.2122 3 13123 3 24162 5 3 4123注：要先將問題化成一般形 式，再按規(guī)則寫出它的對偶 問題。要記住判定對偶變量 是自由變量還是非負(fù)變量0, 2為自由變量P77 20、給定

13、線性規(guī)劃問題min z x1 x3s.t. x1 2x2x1,12x2x2,x3x3 3記為（ P）（ 1）用單純形算法解 P;（2）寫出 P 的對偶問題 D;（3）寫出 P 的互補(bǔ)松緊條件 ,并利用它們解對偶 D;解： （1） 把問題（ P）化為標(biāo)準(zhǔn)形式minz x1 x3s.t.x1 2x2x451x2 x32 2 33x1, x2, x3 , x40以 x1,x3 為基變量，可得到其單純形表為把第 0 行化成檢驗(yàn)行，得x1 以 x2 為x11根據(jù)最優(yōu) z -1zxx2 x20501x3x3-1x4x40RHSRHS0(2) 將 問10x301221201 10進(jìn)基變量， x1 為離基變量

14、，旋轉(zhuǎn)得 化準(zhǔn)則知，問題（P）的最優(yōu)解為* 5 7 T 7x （0, , ） , 最優(yōu)值為 .2 4 4題（ P）化為一般形式517004441101522210117444x1 x2 x3 x4 RHSzx2x3minzx1x3s.t.x12x2511x3 3x2222x1, x2, x30因此其對偶問題（D）為max 5 1 3 2s.t. 1 112 1 2 022110(3) 由問題( P)的最優(yōu)解為 x*(0, 5, 7)T 以及互補(bǔ)松緊性定律可得24121 2 2 021解得11 4 ，2 1. 所以，對偶問題(D)51 3 27 .1 2 .4P7722、用對偶單純形法解下列問題

15、minz 2x13x24x3s.t.x1 2x2x33(1)2x1 x23x34xi 0, i1, 2,3.解：引入剩余變量將原問題標(biāo)準(zhǔn)化min z2x1 3x24x3s.t. x12x2 x3x42x1x2 3x3x5xi0, i 1, 2, 3, 4,5.再將約束條件兩邊同時乘以1得的最優(yōu)解為* 1 T(4,1) ，最優(yōu)值為34注：若問題存在一個 基本解，并且該解的 檢驗(yàn)數(shù)向量小于等于 零，則可使用對偶單 純形方法。特別地， 要將問題典式化min z 2x1 3x2 4x3s.t.x1 2x2x3x42x1 x23x3x54xi 0, i 1, 2,3, 4,5.以 x4 , x5為基變量

16、，可得其單純形表為以 x5x1 x2 x3 x4 x5 RHS 為離基變量， x1 為進(jìn)基變量，旋轉(zhuǎn)得x4根據(jù)最注：用步驟 ：-x21 -3x 2-4 x3 0 x4 0 x5 0 RHS-01 -2-4-1- 1 1 0 0 -1 -3 4-02 1 52-3 1 0 1 1 -1 224-11 1231 0222zxz4x5x4為離基變量， x2 為進(jìn)基變量，旋轉(zhuǎn)優(yōu)化準(zhǔn)則知，原問題的最優(yōu)解為* 11 2 T 28x （ , ,0） , 最優(yōu)值為 .5 5 5對偶單純形方法求解線性規(guī)劃問題的、x1x2x3x4x5RHS、98128z00、55551212x201555571211x11055

17、55、x1將問題化成標(biāo)準(zhǔn)形式；找出初始解；寫出第一張單純形表，并化成典式； 判定和迭代。判 定 ： <1> 最 優(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> 迭代計(jì)算 （利用初等行變換， 將轉(zhuǎn)軸元變?yōu)?1，轉(zhuǎn)軸元所在

18、的這一列其它元素 全 部變?yōu)?0）；<5> 用進(jìn)基變量 x k 代替離基變量 x r 。minz3x12x2x3s.t.x1x2x36x1x342）x2x33xi0, i1, 2, 3.解：先將原問題標(biāo)準(zhǔn)化minz3x12x2 x3s.t.x1x2x3 x46x1x3x54x2x3x63xi0, i1, 2, 3, 4,5, 6.在第 2、 3個等式的兩端同乘以 -1，并以 x4, x5, x6為基變量，可得其單純形表為以 x5 為得以 x6 為轉(zhuǎn)得 所以，原P78（P），利 求解下列（1）x1 x2 x3 x4 x5 x6離基變量， x1 為進(jìn)基變量， 旋轉(zhuǎn)離基變量， x2 為進(jìn)基變量，旋問題沒有可行解。 （X4 所在行 ）23、考