运筹学答案熊伟.doc

1、运筹学 习题答案 1 1.9 设线性规划 4,1,06024503225m ax42132121jxxxxxxxxxZj取基1 1 3 22 1 2 0( P ) 4 0 4 1BB ， P、 ，分别指出B B1 2和对应的基变量和非基变量，求出基本解，并说明 1 2、是不是可行基 【解】 B1： x1， x3为基变量， x2， x4为非基变量 ,基本解为 X=（ 15， 0， 20， 0） T， B1是可行基。 B2： x1,x4是基变量， x2,x3为非基变量，基本解 X=（ 25， 0， 0， 40） T， B2不是可行基。 1.10分别用图解法和 单纯形法求解下列线性规划，指出单纯形法

2、迭代的每一步的基可行解对应于图形上的那一个极点 (1)12121212max 3222 3 12,0Z x xxxxxxx 【解】图解法 单纯形法： C(j) 1 3 0 0 b Ratio C(i) Basis X1 X2 X3 X4 0 X3 -2 1 1 0 2 2 0 X4 2 3 0 1 12 4 C(j)-Z(j) 1 3 0 0 0 3 X2 -2 1 1 0 2 M 0 X4 8 0 -3 1 6 0.75 运筹学 习题答案 2 C(j)-Z(j) 7 0 -3 0 6 3 X2 0 1 0.25 0.25 7/2 1 X1 1 0 -0.375 0.125 3/4 C(j)-

3、Z(j) 0 0 -0.375 -0.875 11.25 对应的顶点： 基可行解 可行域的顶点 X(1)=（ 0， 0， 2， 12） 、 X(2)=（ 0， 2， 0， 6，） 、 X(3)=（ )0,0,27,43 、 （ 0， 0） （ 0， 2） )27,43( 最优解 445),27,43( ZX (2) 1212121212m in 3 5264 1040, 0Z x xxxxxxxxx 【解】图解法 单纯形法： C(j) -3 -5 0 0 0 b Ratio Basis C(i) X1 X2 X3 X4 X5 X3 0 1 2 1 0 0 6 3 X4 0 1 4 0 1 0

4、10 2.5 运筹学 习题答案 3 X5 0 1 1 0 0 1 4 4 C(j)-Z(j) -3 -5 0 0 0 0 X3 0 0.5 0 1 -0.5 0 1 2 X2 -5 0.25 1 0 0.25 0 2.5 10 X5 0 0.75 0 0 -0.25 1 1.5 2 C(j)-Z(j) -1.75 0 0 1.25 0 -12.5 X1 -3 1 0 2 -1 0 2 M X2 -5 0 1 -0.5 0.5 0 2 4 X5 0 0 0 -1.5 0.5 1 0 0 C(j)-Z(j) 0 0 3.5 -0.5 0 -16 X1 -3 1 0 -1 0 2 2 X2 -5 0

5、 1 1 0 -1 2 X4 0 0 0 -3 1 2 0 C(j)-Z(j) 0 0 2 0 1 -16 对应的顶点： 基可行解 可行域的顶点 X(1)=（ 0， 0， 6， 10， 4） 、 X(2)=（ 0， 2.5， 1， 0， 1.5，） 、 X(3)=（ 2， 2， 0， 0， 0） X(4)=（ 2， 2， 0， 0， 0） （ 0， 0） （ 0， 2.5） (2， 2) （ 2， 2） 最优解： X=（ 2， 2， 0， 0， 0）；最优值 Z 16 运筹学 习题答案 4 该题是退化基本可行解， 5 个基本可行解对应 4 个极点。 1.11用单纯形法求解下列线性规划 (1)1

6、 2 31 2 31 2 3m a x 3 42 3 12 2 30 , 1, 2 , 3jZ x x xx x xx x xxj 【解】单纯形表： C(j) 3 4 1 0 0 R. H. S. Ratio Basis C(i) X1 X2 X3 X4 X5 X4 0 2 3 1 1 0 1 1/3 X5 0 1 2 2 0 1 3 3/2 C(j)-Z(j) 3 4 1 0 0 0 X2 4 2/3 1 1/3 1/3 0 1/3 1/2 X5 0 -1/3 0 4/3 -2/3 1 7/3 M C(j)-Z(j) 1/3 0 -1/3 -4/3 0 -4/3 X1 3 1 3/2 1/2

7、 1/2 0 1/2 X5 0 0 1/2 3/2 -1/2 1 5/2 C(j)-Z(j) 0 -1/2 -1/2 -3/2 0 -3/2 最优解： X=（ 1/2， 0， 0， 0， 5/2）；最优值 Z 3/2 (2) 1 2 3 41 2 3 41 2 3 41 2 3 4m a x 2 3 55 3 7 303 102 6 4 200 , 1 , , 4jZ x x x xx x x xx x x xx x x xxj 运筹学 习题答案 5 【解】单纯形表： C(j) 2 1 -3 5 0 0 0 R. H. S. Ratio Basis C(i) X1 X2 X3 X4 X5 X6

8、 X7 X5 0 1 5 3 -7 1 0 0 30 M X6 0 3 -1 1 1 0 1 0 10 10 X7 0 2 -6 -1 4 0 0 1 20 5 C(j)-Z(j) 2 1 -3 5 0 0 0 X5 0 9/2 -11/2 5/4 0 1 0 7/4 65 M X6 0 5/2 1/2 5/4 0 0 1 -1/4 5 10 X4 5 1/2 -3/2 -1/4 1 0 0 1/4 5 M C(j)-Z(j) -1/2 17/2 -7/4 0 0 0 -5/4 X5 0 32 0 15 0 1 11 -1 120 M X2 1 5 1 5/2 0 0 2 -1/2 10 10

9、 X4 5 8 0 7/2 1 0 3 -1/ 20 M 运筹学 习题答案 6 2 C(j)-Z(j) -43 0 -23 0 0 -17 3 因为 7 30 并且 ai70(i=1,2,3)，故原问题具有无界解，即无最优解。 (3)11 2 381 2 3131 2 31 2 3m a x 3 22 3 44 2 1 23 8 4 1 0, , 0Z x x xx x xxxx x xx x x 【解】 C(j) 3 2 -0.125 0 0 0 R. H. S. Ratio Basis C(i) X1 X2 X3 X4 X5 X6 X4 0 -1 2 3 1 0 0 4 M X5 0 4

10、0 -2 0 1 0 12 3 X6 0 3 8 4 0 0 1 10 3.3333 C(j)-Z(j) 3 2 -0.125 0 0 0 0 X4 0 0 2 2.5 1 0.25 0 7 3.5 X1 3 1 0 -0.5 0 0.25 0 3 M X6 0 0 8 5.5 0 -0.75 1 1 0.125 C(j)-Z(j) 0 2 1.375 0 -0.75 0 9 X4 0 0 0 1.125 1 0.4375 -0.25 6.75 6 运筹学 习题答案 7 X1 3 1 0 -0.5 0 0.25 0 3 M X2 2 0 1 0.6875 0 -0.0938 0.125 0.1

11、25 0.181818 C(j)-Z(j) 0 0 0 0 -0.5625 -0.25 9.25 X3进基、 X2出基，得到另一个基本最优解。 C(j) 3 2 -0.125 0 0 0 R. H. S. Ratio Basis X1 X2 X3 X4 X5 X6 X4 0 0 -1.6 0 1 0.5909 -0.4545 6.5455 6 X1 3 1 0.73 0 0 0.1818 0.0909 3.0909 M X3 -0.125 0 1.45 1 0 -0.1364 0.1818 0.1818 0.1818 C(j)-Z(j) 0 0 0 0 -0.5625 -0.25 9.25 原

12、问题具有多重解。 基本最优解 ( 1 ) ( 2 )1 2 7 3 4 2 7 2 3 7( 3 , , 0 , , 0 ) ( , 0 , , , 0 ) ;8 4 1 1 1 1 1 1 4TX X Z 及,最优解的通解可表示为 )2()1( )1( XaaXX 即 3 4 1 1 2 2 7 2 7 2( , , , , 0 ) , (0 1 )1 1 1 1 8 1 1 1 1 1 1 1 1 TX a a a a a 运筹学 习题答案 8 (4) 1 2 3 41 2 3 42 3 41 2 3 4m i n 2 42 3 82 102 7 5 10 200 , 1 , , 4jZ

13、x x x xx x x xx x xx x x xxj 【解】单纯形表： C(j) -2 -1 -4 1 0 0 0 R. H. S. Ratio Basis C(i) X1 X2 X3 X4 X5 X6 X7 X5 0 1 2 1 -3 1 0 0 8 8 X6 0 0 -1 1 2 0 1 0 10 10 X7 0 2 7 -5 -10 0 0 1 20 M C(j)-Z(j) -2 -1 -4 1 0 0 0 X3 -4 1 2 1 -3 1 0 0 8 M X6 0 -1 -3 0 5 -1 1 0 2 0.4 X7 0 7 17 0 -25 5 0 1 60 M C(j)-Z(j)

14、 2 7 0 -11 4 0 0 X3 -4 2/5 1/5 1 0 2/5 3/5 0 46/5 23 X4 1 -1/5 -3/5 0 1 -1/5 1/5 0 2/5 M X7 0 2 2 0 0 0 5 1 70 35 C(j)-Z(j) -1/5 2/5 0 0 9/5 11/5 0 X1 -2 1 1/2 5/2 0 1 3/2 0 23 运筹学 习题答案 9 X4 1 0 -1/2 1/2 1 0 1/2 0 5 X7 0 0 1 -5 0 -2 2 1 24 C(j)-Z(j) 0 1/2 1/2 0 2 5/2 0 最优解： X=（ 23， 0， 0， 5， 0， 0， 24

15、）；最优值 Z 41 （ 5）1 2 31 2 31 2 3m a x 3 25 4 6 2 58 6 3 2 40 , 1, 2 , 3jZ x x xx x xx x xxj 【解】单纯形表： C(j) 3 2 1 0 0 R. H. S. Ratio Basis C(i) X1 X2 X3 X4 X5 X4 0 5 4 6 1 0 25 5 X5 0 8 6 3 0 1 24 3 C(j)-Z(j) 3 2 1 0 0 0 X4 0 0 0.25 4.125 1 -0.625 10 X1 3 1 0.75 0.375 0 0.125 3 C(j)-Z(j) 0 -0.25 -0.125

16、0 -0.375 9 最优解： X=（ 3， 0， 0， 9， 0）；最优值 Z 9 (6)1 2 31 2 31 2 31 2 3m a x 5 6 83 2 5 04 3 8 00 , 0 , 0Z x x xx x xx x xx x x 【解】单纯形表： 运筹学 习题答案 10 C(j) 5 6 8 0 0 R. H. S. Ratio Basis C(i) X1 X2 X3 X4 X5 X4 0 1 3 2 1 0 50 25 X5 0 1 4 3 0 1 80 26.6667 C(j)-Z(j) 5 6 8 0 0 0 X3 8 1/2 3/2 1 1/2 0 25 50 X5 0

17、 -1/2 -1/2 0 -3/2 1 5 M C(j)-Z(j) 1 -6 0 -4 0 -200 X1 5 1 3 2 1 0 50 X5 0 0 1 1 -1 1 30 C(j)-Z(j) 0 -9 -2 -5 0 -250 最优解： X=（ 50， 0， 0， 0， 0， 30）；最优值 Z 250 1.12 分别用大 M 法和两阶段法求解下列线性规划： (1) 1 2 31 2 31 2 3m a x 1 0 55 3 1 05 1 0 1 50 , 1, 2 , 3jZ x x xx x xx x xxj 【解】大 M 法。数学模型为 1 2 3 51 2 3 51 2 3 4m a x 1 0 55 3 1 05 1 0 1 50 , 1 , 2 , , 5jZ x x x M xx x x xx x x xxj C(j) 10 -5 1 0 -M R. H. S. Ratio Basis C(i) X1 X2 X3 X4 X5