内容发布更新时间 : 2024/12/25 10:34:53星期一 下面是文章的全部内容请认真阅读。

运筹学(第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 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 7/4 1 -1/4 1/4 0 0 -5/4 11 -1 2 -1/2 3 -1/2 -17 3 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运筹学(第3版) 习题答案 17

示为X?aX(1)?(1?a)X(2)即

X?(

3411227272?a,a,?a,?a,0)T,(0?a?1) 1111811111111maxZ?3x1?2x2?x3?5x1?4x2?6x3?25（4）?

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 1/4 1 X3 6 3 1 33/8 3/8 0 X4 1 0 0 1 0 0 0 X5 0 1 0 -5/8 1/8 -3/8 R. H. S. 25 24 0 10 3 9 Ratio 5 3 C(j)-Z(j) 0 -1/8 最优解：X=（3，0，0，10，0）；最优值Z＝9

1.11 分别用大M法和两阶段法求解下列线性规划：

3/4 -1/4 maxZ?10x1?5x2?x3 (1) ??5x1?3x2?x3?10??5x1?x2?10x3?15?x?0,j?1,2,3?j

【解】大M法。数学模型为

maxZ?10x1?5x2?x3?Mx5?5x1?3x2?x3?x5?10???5x1?x2?10x3?x4?15?x?0,j?1,2,L,5?jC(j) Basis X5 X4 C(j)-Z(j) * Big M X1 X4 C(j)-Z(j) * Big M 10 0 C(i) -M 0 10 5 -5 10 5 1 0 0 0

-5 3 1 -5 3 4 -11 0 1 X3 1 -10 1 1 -9 -1 0 0 X4 0 1 0 0 0 1 0 0 -M X5 1 0 0 0 X1 X2 R. H. S. Ratio 10 15 0 0 2 25 20 0 2 M 3/5 1/5 1/5 1 -2 -1 运筹学(第3版) 习题答案 18

最优解X＝(2,0,0)；Z=20 两阶段法。

第一阶段：数学模型为

minw?x5?5x1?3x2?x3?x5?10 ??5x?x?10x?x?15?1234?x?0,j?1,2,L,5?jC(j) Basis X5 X4 C(j)-Z(j) X1 X4 C(j)-Z(j) 第二阶段 C(j) Basis X1 X4 C(j)-Z(j) 最优解X=(2,0,0)；Z=20

C(i) 10 0 0 0 C(i) 1 0 0 X1 [5] -5 -5 1 0 0 10 X1 1 0 0 0 X2 3 1 -3 4 0 -5 X2 4 0 X3 1 -10 -1 -9 0 1 X3 -9 0 X4 0 1 0 0 1 0 0 X4 0 1 0 1 X5 1 0 0 R. H. S. 10 15 2 25 R. H. S. 2 25 Ratio 2 M Ratio 2 M 3/5 1/5 1/5 1 1 3/5 1/5 -11 -1 minZ?5x1?6x2?7x3?x1?5x2?3x3?15?(2) ?5x1?6x2?10x3?20

??x1?x2?x3?5?xj?0,j?1,2,3?【解】大M法。数学模型为

minZ?5x1?6x2?7x3?MA1?MA3?x1?5x2?3x3?S1?A1?15?5x?6x?10x?S?20?1232??x1?x2?x3?A3?5??所有变量非负C(j) 5 -6 Basis C(i) X1 X2 A1 M 1 [5] S2 0 5 -6 A3 M 1 1 C(j)-Z(j) 5 -6

-7 X3 -3 10 1 -7 0 S1 -1 0 0 0 0 S2 0 1 0 0 M A1 1 0 0 0 M A3 0 0 1 0 R.H.S. Ratio 15 20 5 3 M 5 运筹学(第3版) 习题答案 19

* Big M X2 S2 A3 C(j)-Z(j) * Big M X2 S2 X3 -6 0 -7 -6 0 M -2 1/5 31/5 4/5 31/5 -4/5 1/2 3 1/2 -6 1 0 0 0 0 1 0 0 0 2 -3/5 32/5 [8/5] -53/5 -8/5 0 0 1 0 0 1 -1/5 -6/5 1/5 -6/5 -1/5 -1/8 -2 1/8 1/8 0 0 0 1 0 0 0 0 1 0 0 0 0 1/5 6/5 -1/5 6/5 6/5 1/8 2 -1/8 -1/8 1 0 0 0 1 0 0 3/8 -4 5/8 53/8 1 30 5/4 38 2 3 M 95/16 5/4 15/4 C(j)-Z(j) 23/2 0 * Big M 0 两阶段法。 第一阶段：数学模型为

minw?A1?A3?x1?5x2?3x3?S1?A1?15?5x?6x?10x?S?20 ?1232??x1?x2?x3?A3?5??所有变量非负C(j) 0 0 0 Basis C(i) X1 X2 X3 A1 1 1 [5] -3 S2 0 5 -6 10 A3 1 1 1 1 C(j)-Z(j) -2 -6 2 X2 0 1/5 1 -3/5 S2 0 31/5 0 32/5 A3 1 4/5 0 [8/5] C(j)-Z(j) -4/5 0 -8/5 X2 0 1/2 1 0 S2 0 3 0 0 X3 0 1/2 0 1 C(j)-Z(j) 0 0 0 第二阶段： C(j) Basis X2 S2 X3 C(j)-Z(j) 最优解：X?(0,C(i) -6 0 -7 5 X1 1/2 3 1/2 -6 X2 1 0 0 -7 X3 0 0 1 0 0 S1 -1/8 -2 1/8 1/8 0 S2 0 1 0 0 R.H.S. Ratio 15/4 3 30 5/4 M 5 0 S1 -1 0 0 1 -1/5 -6/5 1/5 -1/5 -1/8 -2 1/8 0 0 S2 0 1 0 0 0 1 0 0 0 1 0 0 1 A1 1 0 0 0 1/5 6/5 -1/5 6/5 1/8 2 -1/8 1 1 A3 0 0 1 0 0 0 1 0 3/8 -4 5/8 1 R.H.S. Ratio 15 20 5 3 M 5 M 95/16 5/4 3 38 2 30 5/4 15/4 23/2 0 155T125,),Z?? 444运筹学(第3版) 习题答案 20

maxZ?10x1?15x2?5x1?3x2?9?(3)??5x1?6x2?15??2x1?x2?5??x1、x2、x3?0

【解】大M法。数学模型为

maxZ?10x1?15x2?Mx6?5x1?3x2?x3?9??5x?6x?x?15?124??2x1?x2?x5?x6?5?xj?0,j?1,2,L,6?15 0 0 0 X2 X3 X4 X5 3 1 0 0 6 0 1 0 1 0 0 -1 15 0 0 0 1 0 0 -1 3/5 0 0 1/5 9 1 1 0 -1/5 -2/5 0 -1 9 -2 0 0 -1/5 -2/5 0 -1

C(j) Basis C(i) X3 X4 X6 0 0 -M 10 X1 [5] -5 2 10 2 1 0 0 0 -M X6 0 0 1 0 0 0 0 1 0 0 R. H. S. Ratio 9 15 5 0 0 9/5 24 7/5 18 0 1.8 M 2.5 C(j)-Z(j) * Big M X1 X4 X6 10 0 -M C(j)-Z(j) * Big M 0 因为X6>0,原问题无可行解。 两阶段法

第一阶段：数学模型为

minZ?x6?5x1?3x2?x3?9??5x?6x?x?15 ?124??2x1?x2?x5?x6?5?xj?0,j?1,2,L,6?0 0 0 0 X2 X3 X4 X5 3 1 0 0 6 0 1 0 1 0 0 -1 -1 0 0 1 3/5 0 0 1/5 9 1 1 0 C(j) Basis C(i) X3 X4 X6 X1 X4 0 0 1 0 0 0 X1 [5] -5 2 -2 1 0 1 X6 0 0 1 0 0 0 R. H. S. Ratio 9 15 5 5 9/5 24 1.8 M 2.5 14 C(j)-Z(j)