解答 運籌學(xué) 第一章 線性規(guī)劃及其單純形法習(xí)題

1、課后練習(xí)（一） 1 用圖解法求下列線性規(guī)劃問題，并指出問題具有唯一 最優(yōu)解、無窮多最優(yōu)解、無界界還是無可行解。 12 12 12 12 max32 22 . . 3412 ,0 Zxx xx stxx x x 12 12 1 2 max 610120 . .510 38 Zxx xx stx x 12 12 12 12 max56 22 . .232 ,0 Zxx xx s txx xx 12 12 12 12 min23 466 .424 ,0 Zxx xx s txx xx 無可行解 X*=(10, 6) 無界解 無窮多最優(yōu)解 唯一解 2、將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形式 123 123 1

2、23 123 min223 4 .26 0,0, Zxxx xxx stxxx xxx 無約束 12334 1233 12334 12334 max223()0 ()4 .2()6 00,00 Zxxxxx xxxx stxxxxx xxxxx 解： 3 對下述線性規(guī)劃問題找出所有基解，指出那些是基可行 解，并確定最優(yōu)值。 234 1234 1234 1 min5232 2347 . 2223 0(1,.,4) j Zxxxx xxxx stxxxx xj 關(guān)鍵：判斷2個列向量線性相關(guān)性，若線性無關(guān)，則成為基 1234 2212 A 1234 2212 A 序號向量組是否線性無關(guān)是否為基 1p

3、1 p2 2p1 p3 3p1 p4 4p2 p3 5p2 p4 6p3 p4 p1 p2 p3 p4 序號基基解是否為基可行解 1p1 p2 (-4, 11/2, 0 , 0) 2p1 p3 (2/5, 0, 11/5 , 0) 3p1 p4 (-1/3, 0, 0, 11/6) 4p2 p3 (0, 1/2, 2, 0) 5p2 p4 (0, -1/2, 0, 2) 6p3 p4 (0, 0, 1, 1) 4、已知線性規(guī)劃問題 : 12 13 124 25 15 max3 5 210 . 4 .0 Zxx xx xxx st xx xx 序號X1X2X3X4X5 A24300 B100-5

4、04 C30274 D14.540-0.5 E02562 F04520 下表中所列的解均滿足約束條件1-3，試指出表中哪些是可行 解，哪些是基解，哪些是基可行解。 1 2 3 4 10100 12010 01001 A p1 p2 p3 p4 p5 101 120 010 是基 110 100 001 是基 010 201 100 是基 基解有(a), (b), (f); 基可行解有(a) (f). 可行解有(a), (c), (e), (f); 5 已知某線性規(guī)劃問題的約束條件為 123 124 12345 12345 225 330 . 47285 0 xxx xxx st xxxxx x

5、xxxx 判斷下列各點是否為該線性規(guī)劃問題可行域上的頂點： (5,15,0,20,0)X (9,7,0,0,8)X (15,5,10,0,0)X 2 11 00 1 3 01 0 4 7121 A 210 131 472 不是基，故 不是基解，更不可能是基可行解 210 130 471 是基，故(9,7,0,0,8)X 是基解 又由于其每個分量非負(fù)，故為基可行解 (5,15,0,20,0)X 為非可行域上的點，故不是 (9,7,0,0,0)X 2 11 00 1 3 01 0 4 7121 A 211 130 471 不是基，故 不是基解，更不可能是基可行解 (15,5,10,0,0)X 課后

6、練習(xí)（二） 1、分別用圖解法和單純形法求解下述線性規(guī)劃問題，并 指出單純形法迭代的每一步相當(dāng)于圖解法可行域中的哪一 個頂點 12 12 12 12 max105 349 . 528 ,0 Zxx xx stxx x x 12 2 12 12 12 max2 515 6224 . 5 ,0 Zxx x xx st xx xx Cj比 值 CBXB b 檢驗數(shù)j x1x2x3x4 10500 93410 85201 x3 x4 0 0 9/3=3 8/5 0 10 5 0 0 檢驗數(shù)檢驗數(shù) j 8/512/501/5 21/5014/51-3/5 -80/5 010-2 x3 x1 0 10 3/

7、2 4 檢驗數(shù)檢驗數(shù) j 3/2015/14 -3/14 x2 x1 5 10 110-1/72/7 -175/10 00 -5/14-25/14 同理： （2） X*=(3.5, 1.5, 7.5, 0, 0) Z*=8.5 2 用單純形法求解下列線性規(guī)劃問題 123 123 123 123 max2 360 210 . 20 0(1,2,3) j Zxxx xxx xxx st xxx xj 1234 1234 1234 1234 max62108 564420 332825 . 42310 0(1,2,3,4) j Zxxxx xxxx xxxx st xxxx xj Cj 比比 值值

8、CBXBb 檢驗數(shù)檢驗數(shù) j 2-11000 x1x2x3x4x5x6 60311100 101-12010 2011-1001 x4 x5 x6 0 0 0 02-11000 60/3=20 10/1=10 20/1=20 檢驗數(shù)檢驗數(shù) j x4 x1 x6 0 2 0 101-12010 3004-51-30 1002-30-11 -2001-30-20 30/4=7.5 - 10/2=5 檢驗數(shù)檢驗數(shù) j x4 x1 x6 0 2 0 101-12010 3004-51-30 1002-30-11 -2001-30-20 30/4=7.5 - 10/2=5 檢驗數(shù)檢驗數(shù) j 501-3/

9、20-1/21/2 x4 x1 x2 0 2 -1 15101/201/21/2 100011-1-2 -2500-3/20-3/2-1/2 同理： （2）為無界解 3 用單純形法中的大M法求解下列線性規(guī)劃問題，并指出屬 那一類解 化為標(biāo)準(zhǔn)式有 123 123 12 123 min23 428 . 326 ,0 Zxxx xxx stxx xxx 1234567 12346 1257 17 max2300 428 . 326 0 ZxxxxxMxMx xxxxx stxxxx x Cj比 值 CBXB b 檢驗數(shù)j x1 x2 x3 x4 x5 x6 x7 -2 -3 -1 0 0 -M -M

10、 8 1 4 2 -1 0 1 0 0 -2 -3 -1 0 0 -M -M x6 x7 -M -M6 3 2 0 0 -1 0 1 Cj比 值 CBXB b 檢驗數(shù)j x1 x2 x3 x4 x5 x6 x7 -2 -3 -1 0 0 -M -M 8 1 4 2 -1 0 1 0 14M 4M-2 6M-3 2M-1 -M -M 0 0 x6 x7 -M -M6 3 2 0 0 -1 0 1 Cj比 值 CBXB b 檢驗數(shù)j x1 x2 x3 x4 x5 x6 x7 -2 -3 -1 0 0 -M -M 8 1 4 2 -1 0 1 0 14M 4M-2 6M-3 2M-1 -M -M 0

11、 0 x6 x7 -M -M6 3 2 0 0 -1 0 1 2 3 Cj比 值 CBXB b 檢驗數(shù)j x1 x2 x3 x4 x5 x6 x7 -2 -3 -1 0 0 -M -M x2 x7 -3 -M 2 1/4 1 1/2 -1/4 0 1/4 0 2 5/2 0 -1 1/2 -1 -1/2 1 551333 2600 2422424 M MMMMM 8 4/5 Cj比 值 CBXB b 檢驗數(shù)j x1 x2 x3 x4 x5 x6 x7 -2 -3 -1 0 0 -M -M x2 x7 -3 -M 2 1/4 1 1/2 -1/4 0 1/4 0 2 5/2 0 -1 1/2 -

12、1 -1/2 1 551333 2600 2422424 M MMMMM 8 4/5 Cj比 值 CBXB b 檢驗數(shù)j x1 x2 x3 x4 x5 x6 x7 -2 -3 -1 0 0 -M -M x2 x1 -3 -2 9/5 0 1 3/5 -3/10 1/10 3/10 -1/10 4/5 1 0 -2/5 1/5 -2/5 -1/5 2/5 1111 7000 2222 MM 4、求解線性規(guī)劃問題當(dāng)某一變量的取值無約束時，通 常用 來替換，其中 ， 。 試說明，能否在基變量中同時出現(xiàn)，為什么？ jjj xxx 0 j x 0 j x 不可能。因為 jj PP 故 0 jj PP 5

13、、 下表為用單純形法計算時某一步的表格。已知該線 性規(guī)劃的目標(biāo)函數(shù)為 約束形式為 x3、x4為松弛變量，表中解代入目標(biāo)函數(shù)后得Z=10 12 max53Zxx X1X2X3x4 X3 2 X1 a c d 0 e 1 0 1/5 1 Cj-Zjb-1fg (1)ag的值 (2) 表中給出的解是否為最優(yōu)解 因為目標(biāo)函數(shù)值為10，而Z=5x1+3x2,由單純形表可知 x1=a, x2=0， 故a = 2 因為x1、x2為基變量，所以因當(dāng)滿足高斯消元的形式 (proper form from Gaussian elimination), 故c=0, d=1, b=0; f=0 由檢驗數(shù)的定義可知：

14、1 m jjiij i cc a 13 （00 e5） e=4/5 g=0（01/515） g=5 a=2, b=0, c=0, d=1, e=4/5, f=0, g=-5 由于所有檢驗非正，故該解是最優(yōu)解 這個表格為最終單純形表 綜上所述： 6、已知某線性規(guī)劃問題的初始單純形表和用單純刑法迭代 后得到的表如下所示，試求括弧中未知數(shù)al的值 項目 Cj-ZJ X1 X2 X3 X4 X5 X4 X5 6 1 (b) (c) (d) 1 0 -1 3 (e) 0 1 Cj-ZJ X1 X5 (f) 4 (g) 2 -1 1/2 0 (h) (i) 1 1/2 1 (a)-12 0 0 0 -7

15、(j)(k) (l) 首先由于x1、x5為基變量，故g=1, h=0, l = 0 再有 1 1/20 1/21 B 1/20121 1/211301 bcd ei 那么 b=1 c=2 d=-1 c+3=i d+e=1 b=2 c=4 d=-2 i=5 e=2 又有1 1/206 1/2114 f B b f=3 還剩下檢驗數(shù) a、j、k 1 m jjiij i cc a 檢驗數(shù)的定義為 如何求得c呢？ 對初始單純形表的檢驗數(shù)行即為目標(biāo)函數(shù)中的系數(shù)C。 12345 ,1,2,0ca cccc 對迭代后的單純形表有： 221 7(2*0* )cci a=c1=3 至此我們已獲得所有的目標(biāo)函數(shù)的

16、系數(shù) j=2（3101）5 1 m jjiij i cc a k=0（31/201/2）3/2 a=3, b=2, c=4, d=-2, e=2, f=3, g=1, h=0 i=5, j=5, k=-3/2, l=0 綜上所述： 7、設(shè) 是線性規(guī)劃問題 的最優(yōu)解。若目標(biāo)函數(shù)中用 代替 C后，問題的最 優(yōu)解變?yōu)?0 X 0,maxXbAXCXz C X 求證： 0)( 0 XXCC 證明：因為 0*0 *0*0 ()0 ,()0 CXCXC XX C XC XCXX 故 又有 （1） （2） 將（2）（1）有 0)( 0 XXCC 某廠生產(chǎn)I、II、III三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。

17、 設(shè)A工序可分別在設(shè)備A1或A2上完成，有B1、B2、B3三種 設(shè)備可用于完成B工序。 已知產(chǎn)品產(chǎn)品I可在A、B任何一種設(shè)備上加工； 產(chǎn)品產(chǎn)品II可在任何規(guī)格的A設(shè)備上加工，但完成B工序時， 只能在B1設(shè)備上加工； 產(chǎn)品產(chǎn)品III只能在A2和B2設(shè)備上加工。 設(shè)備 產(chǎn)品設(shè)備有 效臺時 設(shè)備加 工費 I II III A151060000.05 A27912100000.03 B16840000.06 B241170000.11 B3740000.05 原料費0.250.350.50 售價1.252.002.80 設(shè)備 產(chǎn)品設(shè)備有 效臺時 設(shè)備加 工費 I II III A151060000.0

18、5 A27912100000.03 B16840000.06 B241170000.11 B3740000.05 原料費0.250.350.50 售價1.252.002.80 產(chǎn)品I有6種加工方案（A1, B1）、(A1，B2)、(A1， B3) （A2, B1）、(A2，B2)、(A2， B3) 其各自產(chǎn)量分別用 111213 ,xxx 212223 ,xxx 設(shè)備 產(chǎn)品設(shè)備有 效臺時 設(shè)備加 工費 I II III A151060000.05 A27912100000.03 B16840000.06 B241170000.11 B3740000.05 原料費0.250.350.50 售價1.252.002.80 產(chǎn)品II有6種加工方案（A1, B1）、(A2，B1) 其各自產(chǎn)量分別用 代表 1121 ,yy 設(shè)備 產(chǎn)品設(shè)備有 效臺時 設(shè)備加 工費 I II III A151060000.05 A27912100000.03 B16840000.06 B241170000.11 B3740000.05 原料費0.250.350.50 售價1.252.002.80 產(chǎn)品III只有1種加工方案（A2, B2） 其各自產(chǎn)量用 代表 22 z 11121321222 11121311 2122