运筹学 习题答案 13

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 对应的顶点： 基可行解 可行域的顶点 运筹学 习题答案 14

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(j)-Z(j) X5 X6 X4 0 0 5 C(i) 0 0 0

2 X1 1 3 2 2 9/2 1 X2 5 -1 -6 1 -3 X3 3 [1] -1 -3 5 X4 -7 1 [4] 5 0 0 X5 1 0 0 0 1 0 0 0 X6 0 1 0 0 0 1 0 X7 0 0 1 0 R. H. S. Ratio 30 10 20 M 10 5 M 65 -11/2 5/4 5/2 1/2 [1/2] 5/4 -3/2 -1/4 0 1 0 7/4 -1/4 1/4 5 5 10 M 运筹学 习题答案 15

C(j)-Z(j) X5 X2 X4 C(j)-Z(j) 0 1 5 -1/2 17/2 -7/4 0 0 0 1 0 0 0 32 5 8 -43 0 1 0 0 15 5/2 7/2 -23 0 1 0 0 -5/4 11 -1 2 -1/2 3 -1/2 -17 3 120 10 20 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 -0.125 2.5 -0.5 5.5 1.375 1.125 -0.5 [0.6875] 0 X4 1 0 0 0 1 0 0 0 1 0 0 0 X5 0 1 0 0 0.25 0.25 -0.75 -0.75 0.4375 0.25 -0.0938 -0.5625 0 X5 0.5909 0.1818 -0.1364 -0.5625 0 X6 0 0 1 0 0 0 1 0 -0.25 0 0.125 -0.25 0 X6 -0.4545 0.0909 0.1818 -0.25 R. H. S. 4 12 10 0 7 3 1 9 6.75 3 0.125 9.25 Ratio M 3 3.3333 3.5 M 0.125 6 M 0.181818 Ratio 6 M 0.1818

C(j)-Z(j) 0 0 0 0 X3进基、X2出基，得到另一个基本最优解。 C(j) 3 2 -0.125 0 Basis X4 X1 X3 C(j)-Z(j) 原问题具有多重解。

(1)基本最优解X?(3,,0, 0 3 -0.125 X1 0 1 0 0 X2 -1.6 0.73 1.45 0 X3 0 0 1 0 X4 1 0 0 0 R. H. S. 6.5455 3.0909 0.1818 9.25 18273427237,0)及X(2)?(,0,,,0)T;Z?,最优解的通解可表示为41111114X?aX(1)?(1?a)X(2)即

X?(

3411227272?a,a,?a,?a,0)T,(0?a?1) 1111811111111运筹学 习题答案 16

minZ??2x1?x2?4x3?x4?x1?2x2?x3?3x4?8? (4) ??x2?x3?2x4?10

??2x1?7x2?5x3?10x4?20?xj?0,j?1,,4?【解】单纯形表： C(j) -2 Basis C(i) X1 X5 X6 X7 X3 X6 X7 X3 X4 X7 X1 X4 X7 0 0 0 -4 0 0 -4 1 0 -2 1 0 1 0 2 -2 1 -1 7 2 [2/5] -1/5 2 -1/5 1 0 0 0 -1 X2 2 -1 7 -1 2 -3 17 7 1/5 -3/5 2 -4 X3 [1] 1 -5 -4 1 0 0 0 1 0 0 1 X4 -3 2 -10 1 -3 [5] -25 -11 0 1 0 0 0 1 0 0 0 X5 1 0 0 0 1 -1 5 4 0 X6 0 1 0 0 0 1 0 0 0 X7 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 R. H. S. Ratio 8 10 20 8 10 M M 0.4 M 23 M 35 C(j)-Z(j) C(j)-Z(j) C(j)-Z(j) C(j)-Z(j) 2/5 0 1/2 5/2 -1/2 1/2 1 -5 1/2 1/2 2/5 -1/5 0 9/5 1 0 -2 2 3/5 1/5 5 11/5 3/2 1/2 2 5/2 8 2 60 46/5 2/5 70 23 5 24 最优解：X=（23，0，0，5，0，0，24）；最优值Z＝－41

maxZ?3x1?2x2?x3?5x1?4x2?6x3?25（5）?

8x?6x?3x?24?123?x?0,j?1,2,3?j【解】单纯形表： C(j) Basis X4 X5 C(j)-Z(j) X4 X1 0 3 C(i) 0 0 3 X1 5 [8] 3 0 1 2 X2 4 6 2 0.25 0.75 1 X3 6 3 1 4.125 0.375 -0.125 0 X4 1 0 0 1 0 0 0 X5 0 1 0 -0.625 0.125 -0.375 R. H. S. 25 24 0 10 3 9 Ratio 5 3 C(j)-Z(j) 0 -0.25 最优解：X=（3，0，0，9，0）；最优值Z＝9