运筹学(第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 运筹学(第3版) 习题答案 16
C(j)-Z(j) X5 X6 X4 C(j)-Z(j) X5 X2 X4 C(j)-Z(j) 0 1 5 0 0 5 2 9/2 1 -3 5 0 0 1 0 0 0 1 0 0 0 0 0 1 0 65 M -11/2 5/4 5/2 1/2 -1/2 32 5 8 -43 [1/2] 5/4 -3/2 -1/4 17/2 -7/4 0 1 0 0 15 5/2 7/2 -23 0 1 0 0 0 1 0 0 0 11 -1 2 -1/2 3 -1/2 -17 3 7/4 -1/4 1/4 -5/4 5 5 120 10 20 10 M M 10 M 因为λ7＝3>0并且ai7<0(i=1,2,3)，故原问题具有无界解，即无最优解。
maxZ?3x1?2x2?18x3??x1?2x2?3x3?4? (3)?4x1?2x3?12??3x1?8x2?4x3?10??x1,x2,x3?0【解】 C(j) Basis X4 X5 X6 C(j)-Z(j) X4 X1 X6 C(j)-Z(j) X4 X1 X2 0 3 2 0 3 0 C(i) 0 0 0 3 X1 -1 [4] 3 3 0 1 0 0 0 1 0 2 X2 2 0 8 2 2 0 [8] 2 0 0 1 -0.125 X3 3 -2 4 -1/8 5/2 -1/2 11/2 11/8 9/8 -1/2 [11/16] 0 X4 1 0 0 0 1 0 0 0 1 0 0 0 0 X4 1 0 0 0 0 X5 0 1 0 0 1/4 1/4 -3/4 -3/4 7/16 1/4 -3/32 -9/16 0 X5 13/22 2/11 -3/22 -9/16 0 X6 0 0 1 0 0 0 1 0 -1/4 0 1/8 -1/4 0 X6 -5/11 1/11 2/11 -1/4 R. H. S. 4 12 10 0 7 3 1 9 27/4 3 1/8 Ratio M 3 10/3 3.5 M 1/8 6 M 0.181818 Ratio 6 M 0.1818
C(j)-Z(j) 0 0 0 X3进基、X2出基，得到另一个基本最优解。 37/4 R. H. S. 72/11 34/11 2/11 37/4 Basis X4 X1 X3 C(j) 3 X1 0 1 0 0 2 X2 -18/11 8/11 16/11 0 -0.125 X3 0 0 1 0 0 3 -0.125 C(j)-Z(j) 原问题具有多重解。 基本最优解X(1)1273427237?(3,,0,,0)及X(2)?(,0,,,0)T;Z?,最优解的通解可表
841111114