运筹学1至5章习题参考答案

maxZ?y??x1??)?4x2?y?3(x1?y?x??x???x?x1123????x1???2x2?x3?30 ?x1???x1??)?x2?2x3?15?4(x1?9(x1??x1??)?x2?6x3??5??,x1??,x2、x3?0??x1标准型为

maxZ?y??3x1???4x2?x4?0?y?3x1?y?x??x???x?x?x?011235????x1???2x2?x3?x6?30 ?x1???4x1???x2?2x3?x7?15?4x1??9x1??9x1???x2?6x3?x8?5??,x1??,x2,x3,x4,x5,x6,x7,x8?0??x1

1.9 设线性规划

maxZ?5x1?2x2?2x1?3x2?x3?50 ?4x?2x?x?60?124?x?0,j?1,?,4?j?21??20?取基B1?(P1，P3)??分别指出B1和B2对应的基变量和非基变量，?、B2＝?41?，40????求出基本解，并说明B1、B2是不是可行基．

【解】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分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．

maxZ?x1?3x2 (1)???2x1?x2?2

?2x1?3x2?12?x,x?0?12【解】图解法

单纯形法： C(j) C(i) 0 0 3 0 3 1 对应的顶点： Basis X3 X4 X2 X4 X2 X1 1 X1 -2 2 1 -2 [8] 7 0 1 0 基可行解 3 X2 [1] 3 3 1 0 0 1 0 0 0 X3 1 0 0 1 -3 -3 0.25 -0.375 -0.375 0 X4 0 1 0 0 1 0 0.25 0.125 -0.875 b 2 12 0 2 6 6 7/2 3/4 45/4 Ratio 2 4 M 0.75 C(j)-Z(j) C(j)-Z(j) C(j)-Z(j) 可行域的顶点 、X(1)=（0，0，2，12） 、X(2)=（0，2，0，6，） （0，0） （0，2） 37,,0,0)、 423745最优解X?(,),Z?

424X(3)=（

37(,) 42minZ??3x1?5x2

?x1?2x2?6? (2) ?x1?4x2?10?

?x1?x2?4??x1?0,x2?0

【解】图解法

单纯形法： C(j) Basis X3 X4 X5 C(j)-Z(j) X3 X2 X5 C(j)-Z(j) X1 X2 X5 C(j)-Z(j) X1 X2 X4 C(j)-Z(j) -3 -5 0 -3 -5 0 0 -5 0 C(i) 0 0 0 -3 X1 1 1 1 -3 [0.5] 0.25 0.75 -1.75 1 0 0 0 1 0 0 0 -5 X2 2 [4] 1 -5 0 1 0 0 0 1 0 0 0 1 0 0 0 X3 1 0 0 0 1 0 0 0 2 -0.5 -1.5 3.5 -1 1 -3 2 0 X4 0 1 0 0 -0.5 0.25 -0.25 1.25 -1 0.5 [0.5] -0.5 0 0 1 0 0 X5 0 0 1 0 0 0 1 0 0 0 1 0 2 -1 2 1 b 6 10 4 0 1 2.5 1.5 -12.5 2 2 0 -16 2 2 0 -16

Ratio 3 2.5 4 2 10 2 M 4 0 对应的顶点： 基可行解 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 该题是退化基本可行解，5个基本可行解对应4个极点。

1.11用单纯形法求解下列线性规划

maxZ?3x1?4x2?x3?2x1?3x2?x3?1(1)??x1?2x2?2x3?3?x?0,j?1,2,3?j【解】单纯形表： C(j) Basis X4 X5 C(j)-Z(j) X2 X5 C(j)-Z(j) X1 X5 C(j)-Z(j) 3 0 4 0 C(i) 0 0 3 X1 2 1 3 [2/3] -1/3 1/3 1 0 0

4 X2 [3] 2 4 1 0 0 3/2 1/2 -1/2 1 X3 1 2 1 1/3 4/3 -1/3 1/2 3/2 -1/2 0 X4 1 0 0 1/3 -2/3 -4/3 1/2 -1/2 -3/2 0 X5 0 1 0 0 1 0 0 1 0 R. H. S. 1 3 0 1/3 7/3 -4/3 1/2 5/2 -3/2 Ratio 1/3 3/2 1/2 M 最优解：X=（1/2，0，0，0，5/2）；最优值Z＝3/2

maxZ?2x1?x2?3x3?5x4?x1?5x2?3x3?7x4?30? (2) ?3x1?x2?x3?x4?10??2x1?6x2?x3?4x4?20?xj?0,j?1,,4?【解】单纯形表： C(j) Basis X5 X6 X7 C(i) 0 0 0

2 X1 1 3 2 1 X2 5 -1 -6 -3 X3 3 [1] -1 5 X4 -7 1 [4] 0 X5 1 0 0 0 X6 0 1 0 0 X7 0 0 1 R. H. S. Ratio 30 10 20 M 10 5