运筹学(第3版) 习题答案 11
maxZ???9x1?3x2?5x3?6x1?7x2?4x3?x4?20??6x?7x?4x?x?201235? ?x?x?5?16??x?8x?82?1??x1,x2,x3,x4,x5,x6?0maxZ?2x1?3x2?1?x1?5 (3)???x1?x2??1?x?0,x?02?1【解】方法1：
maxZ?2x1?3x2?x1?x3?1?x?x?5 ?14??x1?x2?1??x1,x2,x3,x4?0??x1?1,有x1＝x1??1,x1??5?1?4 方法2：令x1??1)?3x2maxZ?2(x1??4?x1???1)?x2??1??(x1?x,x?0?12则标准型为
??3x2maxZ?2?2x1??x3?4?x1???x2?0??x1?x?,x,x?0?123
maxZ?min(3x1?4x2,x1?x2?x3)?x1?2x2?x3?30?(4) ?4x1?x2?2x3?15
??9x1?x2?6x3??5?x1无约束,x2、x3?0?【解】令y?3x1?4x2,y?x1?x2?x3,x1?x1??x1??，线性规划模型变为
运筹学(第3版) 习题答案 12
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.8 设线性规划
maxZ?5x1?2x2?2x1?2x2?x3?40 ?4x?2x?x?60?124?x?0,j?1,,4?j?21??20?取基B1??分别指出B1和B2对应的基变量和非基变量，求出基本?、B2＝??21?，40????解，并说明B1、B2是不是可行基．
【解】B1：x1、x3为基变量，x2、x4为非基变量,基本解为X=（15，0，10，0）T，B1是可行基。B2：x2、x4是基变量，x1、x3为非基变量，基本解X=（0，20，0，100）T，B2是可行基。
1.9分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．
maxZ?x1?3x2 (1)???2x1?x2?2
?2x1?3x2?12?x,x?0?12【解】图解法
运筹学(第3版) 习题答案 13
单纯形法： 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(,) 42运筹学(第3版) 习题答案 14
minZ??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 运筹学(第3版) 习题答案 15
对应的顶点： 基可行解 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.10用单纯形法求解下列线性规划
maxZ?3x1?4x2?x3?2x1?3x2?x3?4(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. 4 3 0 4/3 1/3 －16/3 2 1 -6 Ratio 4/3 3/2 2 M 最优解：X=（2，0，0，0，1）；最优值Z＝6
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