熊伟第二版 运筹学1-6章参考答案 1(4)

对应的顶点： 基可行解 、X(1)=（0，0，6，10，4） 可行域的顶点 （0，0） 、X=（0，2.5，1，0，1.5，） X(3)=（2，2，0，0，0） X(4)=（2，2，0，0，0） 最优解：X=（2，2，0，0，0）；最优值Z＝－16 该题是退化基本可行解，5个基本可行解对应4个极点。

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

maxZ?3x?4x?x?2x1?3x2?x3?1(1)??x1?2x2?2x3?3?x?0,j?1,2,3?j【解】单纯形表： (2)（0，2.5） (2，2) （2，2）

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?2x?6x2?x3?4x4?20?1?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 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 0 7/4 -1/4 1/4 -5/4 5 5 120 10 20 10 M M 0 1 0 11 -1 2 -1/2 3 -1/2 -17 3 10 M 因为λ7＝3>0并且ai7<0(i=1,2,3)，故原问题具有无界解，即无最优解。

maxZ?3x1?2x2?1x83??x1?2x2?3x3?4 (3)??4x1?2x3?12??3x1?8x2?4x3?10?x,x,x?0?123

【解】 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 34112720 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 T0 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 374R. 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 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 182742 X2 -18/11 8/11 16/11 0 -0.125 X3 0 0 1 0 (2) 0 3 -0.125 Ratio 6 M 0.1818 C(j)-Z(j) 原问题具有多重解。 基本最优解X(1)?(3,,0,,0)及X?(,0,1111,,0);Z?,最优解的通解可表

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

a,18a,211?211a,7211?7211a,0),(0?a?1)

T?111

maxZ?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 0 C(i) 0 0 3 X1 5 [8] 3 0 2 X2 4 6 2 1/4 1 X3 6 3 1 33/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 X1 3 1 3/4 3/8 C(j)-Z(j) 0 -1/4 -1/8 最优解：X=（3，0，0，10，0）；最优值Z＝9

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

maxZ?10x1?5x2?x3?5x1?3x2?x3?10 (1) ?

??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,?,5?j

C(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 最优解X＝(2,0,0)；Z=20 两阶段法。

第一阶段：数学模型为 minw?x5?5x1?3x2?x3?x5?10 ???5x1?x2?10x3?x4?15?x?0,j?1,2,?,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

minZ?5x1?6x2?7x3C(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 ?x1?5x2?3x3?15?(2) ?5x1?6x2?10x3?20

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

minZ?5x1?6x2?7x3?MA1?MA3?x1?5x2?3x3?S1?A1?15??5x1?6x2?10x3?S2?20??x1?x2?x3?A3?5?所有变量非负?

C(j) Basis A1 S2 A3 C(j)-Z(j) C(i) M 0 M 5 X1 1 5 1 5 -6 X2 [5] -6 1 -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 * 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 3 38 2 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??5x1?6x2?10x3?S2?20 ??x1?x2?x3?A3?5?所有变量非负?C(j) Basis A1 S2 A3 C(j)-Z(j) X2 S2 A3 C(j)-Z(j) X2 S2 X3 C(j)-Z(j) 第二阶段： C(j) Basis X2 S2 X3 C(j)-Z(j) 最优解：X?(0,C(i) -6 0 -7 0 0 0 0 0 1 C(i) 1 0 1 0 X1 1 5 1 -2 1/5 31/5 4/5 -4/5 1/2 3 1/2 0 5 X1 1/2 3 1/2 23/2 0 X2 5 -6 1 -6 1 0 0 0 1 0 0 0 -6 X2 1 0 0 0 0 X3 -3 10 1 2 -3/5 32/5 [8/5] -8/5 0 0 1 0 -7 X3 0 0 1 0 0 S1 -1 0 0 1 -1/5 -6/5 1/5 -1/5 -1/8 -2 1/8 0 0 S1 -1/8 -2 1/8 1/8 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 0 S2 0 1 0 0 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 15/4 30 5/4 R.H.S. Ratio 15/4 3 30 5/4 M 5 155T125,),Z?? 444

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库熊伟第二版 运筹学1-6章参考答案 1(4)在线全文阅读。