运筹学基础及应用第四版胡运权主编课后练习答案

习题一 P46 (a)

x2 4x12x244 3 2 1 0 1 2 3 4x16x26x1

1的所有x1,x2，此时目标函数值2该问题有无穷多最优解，即满足4x16x26且0x2z3。 (b)

x2 3 2 0 1 4 x1

用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。

(a) 约束方程组的系数矩阵

1236300A814020

300001基 p1 p2 p3 p1 p2 p4 p1 p2 p5 基解 x1 x2 x3 x4 x5 x6 1670 - 0 0 0 36是否基可行解 否 是 是 目标函数值 0 10 0 7 0 0 70 3 0 0 0 210 3 p1 p2 p6 p1 p3 p4 p1 p3 p5 p1 p3 p6 p1 p4 p5 p1 p4 p6 721 4 0 0 0 4450 0  8 0 0 230 0 0 8 0 211 0  0 0 3 2否 否 是 否 是 否 3 0 0 0 0 3 5 0 515 0 0 2 0 44最优解x0,10,0,7,0,0T。 (b) 约束方程组的系数矩阵

1234A2212 基 p1 p2 p1 p3 p1 p4 p2 p3 p2 p4 p3 p4 基解 x1 x2 x3 x4 114 0 0 2是否基可行解 否 是 否 是 否 是 目标函数值 211 0 0 55111 0 0 3610 2 0 210  0 2 243 5 5 0 0 1 1 5 211最优解x,0,,0。

55T

(a)

(1) 图解法

x2 4 3 2 1 0 1 2 3 x1

最优解即为3x14x29353的解x1,，最大值z

25x2x8221(2)单纯形法

首先在各约束条件上添加松弛变量，将问题转化为标准形式 max z10x15x20x30x43x4x2x39s.t. 15x12x2x48

则P3,P4组成一个基。令x1x20

得基可行解x0,0,9,8，由此列出初始单纯形表 cj cB 基 b 10 5 0 0 x1 x2 x3 x4 0 x3 9 0 x4 8 3 4 1 0 [5] 2 0 1 10 5 0 0 cjzj 12。min, cj cB 基 b 89538 510 5 0 0 x1 x2 x3 x4 3140  1  55 210 x3 5810 x1 52 11 0 55cjzj 0 1 0 2

20，min新的单纯形表为 cj cB 基 b 35 x2 22183, 142210 5 0 0 x1 x2 x3 x4 530 1  141410 x1 1 1 21 0  770 0 525  14143235 2cjzj

1,20，表明已找到问题最优解x11, x2 , x30 , x40。最大值 z*(b) (1) 图解法 6x12x224x2 12 9 x1x256 3 0 3 6 9 x1

最优解即为6x12x2241773的解x,，最大值z

222x1x25(2) 单纯形法

首先在各约束条件上添加松弛变量，将问题转化为标准形式

max z2x1x20x30x40x55x2x315s.t. 6x12x2x424xxx5125

则P3，P4，P5组成一个基。令x1x20

得基可行解x0,0,15,24,5，由此列出初始单纯形表 cj cB 基 b 2 1 0 0 0 x1 x2 x3 x4 x5 0 5 1 0 0 [6] 2 0 1 0 1 1 0 0 1 2 1 0 0 0 0 x3 15 0 x4 24 0 x5 5 cjzj

12。min,cj cB 基 b 245,4 612 1 0 0 0 x1 x2 x3 x4 x5 0 5 1 0 0 1 0 x3 15 2 x4 4 0 x5 1 cjzj 11 0 0 360  0  1 6321110 0 0 333315,24,

22520，min新的单纯形表为 cj cB 基 b 2 1 0 0 0 x1 x2 x3 x4 x5 0 0 1 15x0 3 2 515  427x2 4 2 30 x5 2cjzj 11 42310 1 0  24110 0 0 421 0 0 1,20，表明已找到问题最优解x11， x2值 z

*715，x40，x50。最大 ，x32217 2''''''x2 x20,x20(a) 在约束条件中添加松弛变量或剩余变量，且令x2x2，

'x3x3, z'z

该问题转化为

''''max z'3x1x2x22x30x40x5''''2x13x23x24x3x412''''4x1x2x22x3x58s.t. ''''3x1x2x23x36''''x1,x2,x2,x3,x4,x50

其约束系数矩阵为

233410A411201

311300在A中人为地添加两列单位向量P7,P8 2334100041120110 31130001''''x22x30x40x5Mx6Mx7 令max z'3x1x2得初始单纯形表

cj cB 基 b 3 1 1 2 0 0 M M ''''x1 x2 x2 x3 x4 x5 x6 x7 0 x4 12 M x6 8 M x7 6 2 3 3 4 1 0 0 0 4 1 1 -2 0 -1 1 0 3 1 1 -3 0 0 0 1 cjzj 37M 1 1 25M 0 M 0 0 '''(b) 在约束条件中添加松弛变量或剩余变量，且令x3x3x3 x30,x30该问题转化为

'''max z'3x15x2x3x30x40x5'''x12x2x3x3x46'''2x1x23x33x3x516s.t. '''xx5x5x101233'''x1,x2,x3,x3,x4,x50'''， z'z

其约束系数矩阵为

121110

A213301115500在A中人为地添加两列单位向量P7,P8

1211101021330100 11550001令max z'3x15x2x3x30x40x5Mx6Mx7 得初始单纯形表 cj cB 基 b '''3 -5 1 -1 0 0 -M M  x3 x4 x5 x6 x7 x1 x2 x3M x6 6 0 x5 16 M x7 10 cjzj 1 2 1 -1 -1 0 1 0 2 1 3 -3 0 1 0 0 1 1 5 -5 0 0 0 1 32M 53M 1+6M -1-6M -M 0 0 0

(a)解1：大M法

在上述线性规划问题中分别减去剩余变量x4,x6,x8,再加上人工变量x5,x7,x9,得

maxz2x1x22x30x4Mx50x6Mx70x8Mx9

x1x2x3x4x562x1x3x6x72 s,t,2x2x3x8x90x1,x2,x3,x4,x5,x6,x7,x8,x90

其中M是一个任意大的正数。据此可列出单纯形表 cj 2x11x22x30x4Mx50x6Mx70x8M x9 i cb基 b Mx56Mx72 Mx90cjzj 1202M10[2]111100M1000010M0100001M00 10 6 0 3M12MMx56Mx72 1x20cjzj 1202M00103/2[1]1/25M322100M1000010M01001/21/200 42  1/21/2M113M 2222Mx532x32 1x21cjzj [4]210010101001003/23/2111/21/21/21/200 1/21/23/4 4M500M03M35M3M113M 22222x13/42x37/2 1x27/4cjzj 1000001001001/41/21/41/41/21/43/83/81/41/81/41/81/81/41/4 3/89M 8 1/83/839M885/4M53/84 由单纯形表计算结果可以看出，40且ai40(i1,2,3)，所以该线性规划问题有无界解 解2：两阶段法。

现在上述线性规划问题的约束条件中分别减去剩余变量x4,x6,x8,再加上人工变量

x5,x7,x9,得第一阶段的数学模型

据此可列出单纯形表 cj 0x10x20x30x41x50x61x70x81 x9 i cb基 b 1x561x72 1x90cjzj 120110[2]311111001100001010100001100 10 6 0 1x561x72 0x20cjzj 120100103/2[1]1/25/210011000010101001/21/20124 03 21/21/22  10x53x21cjzj [4]210010101001003/23/2111/21/21/21/200 1/21/23/4 0x32 000010101 2x13/42x37/2 1x27/4cjzj 1000*001001001/41/21/40T1/41/21/413/83/81/41/801/81/81/41/4 3/81 1/41/83/81*0 第一阶段求得的最优解X(,,,0,0,0,0,0,0),目标函数的最优值0。

*因人工变量x5x7x90，所以X(,377442377,,0,0,0,0,0,0)T是原线性规划问题的基可442行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。 cjzj 2x11x22x30x40x60x8 0 i cb基 b 2x13/42x37/2 1x27/41000010101/41/21/43/81/41/81/4 1/83/8cjzj 0005/43/89/8 由表中计算结果可以看出，40且ai40(i1,2,3)，所以原线性规划问题有无界解。

(b)解1：大M法

在上述线性规划问题中分别减去剩余变量x4,x6,x8,再加上人工变量x5,x7,x9,得

minz2x13x2x30x40x5Mx6Mx7

x14x22x3x4x683x12x2x5x76 s,t,x1,x2,x3,x4,x5,x6,x7,x8,x90

其中M是一个任意大的正数。据此可列出单纯形表 cj 2x11x22x30x4Mx50x6Mx7 0M i cb基 b MMx6813[4]22010011001x76 cjzj 23 24M1/4[5/2]36M1012M1/21M1/41/2M0101/41/20 0 13x2Mx722 84/5 cjzj 55M4201010M1231M423/101/5M3M3240 3x22x19/54/5 3/52/51/103/101/10 2/51/52/5cjzj 000*1/21/2M1/2M1/2 由单纯形表计算结果可以看出，最优解X(,49,0,0,0,0,0)T，目标函数的最优解值55z*24937。X存在非基变量检验数30，故该线性规划问题有无穷多最优解。 55解2：两阶段法。

现在上述线性规划问题的约束条件中分别减去剩余变量x4,x5,再加上人工变量x6,x7,得第一阶段的数学模型minx6x7

x14x22x3x4x683x12x2x5x76 s,t,x1,x2,x3,x4,x5,x6,x7,x8,x90据此可列出单纯形表 cj 0x10x20x30x40x51x61 x7 i cb基 b 1x61x786 13[4]22010011001 23 cjzj 41/4[5/2]61021/2111/41/210101/41/20 0 10x21x722 84/5 cjzj 5/2 01013/52/51/213/23/101/50 1/10 2/500x2x19/54/5013/101/101/52/5cjzj 0*000011 49,0,0,0,0,0)T,目标函数的最优值*0。 5549T因人工变量x6x70，所以(,,0,0,0,0,0)是原线性规划问题的基可行解。于是可

55第一阶段求得的最优解X(,以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。

cjzj 2x13x21x30x40 x5 i cb基 b 3x22x19/54/5 01103/52/53/101/51/102/5 cjzj 000*1/21/2 由单纯形表计算结果可以看出，最优解X(,49,0,0,0,0,0)T，目标函数的最优解值55z*249由于存在非基变量检验数30，故该线性规划问题有无穷多最优37。55解。

表1-23 x1 x2 x3 x4 x5 x4 6 x5 1 2 4 -2 1 0 1 3 2 0 1 3 1 2 0 0 cjzj 表1-24 x1 x2 x3 x4 x5 x1 3 x5 1 1 2 1 12 0 0 5 1 12 1 0 7 5 32 0 cjzj

5 x2 83 0 x5 143 0 x6 293 3 5 4 0 0 0 x1 x2 x3 x4 x5 x6 23 1 0 13 0 0 43 0 5 23 1 0 53 0 4 23 0 1 cjzj 13 0 4 53 0 0 5 x2 83 4 x3 1415 x1 x2 x3 x4 x5 x6 23 1 0 13 0 0 415 0 1 215 15 0 0 x6 8915 4115 0 0 215 45 1 cjzj 1115 0 0 1715 45 0 5 x2 5041 4 x3 6241 3 x1 8941 x1 x2 x3 x4 x5 x6 0 1 0 1541 841 1041 0 0 1 641 541 441 1 0 0 241 1241 1541 cjzj 0 0 0 4541 2441 1141 最后一个表为所求。

习题二 P76 写出对偶问题 (a)

min z2x12x24x3max w2y13y25y3y12y2y32x13x24x322xx3xy3 对偶问题为：3yy4y2

1234123s.t. s.t. 4y13y23y34x14x23x35y10,y20,y3无约束x1,x20,x3无约束(b)

max z5x16x23x3min w5y13y28y3y1y24y35x12x22x35x5xx3 对偶问题为： 2y5y7y6 123123s.t. s.t. 4x17x23x382y1y23y33x1无约束,x20,x30y1无约束,y20,y30

(a)错误。原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。

(b)错误。线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。 (c)错误。 (d)正确。

对偶单纯形法 (a)

min z4x112x218x3x1 3x33 s.t.  2x22x35x,x,x0123解：先将问题改写为求目标函数极大化，并化为标准形式

max z'4x112x218x30x40x5x1 3x3x4 3s.t.  2x22x3 x55x0i1,,5i

列单纯形表，用对偶单纯形法求解，步骤如下 cj cB 基 b 4 12 18 0 0 x1 x2 x3 x4 x5 0 x4 3 0 x5 5 1 0 3 1 0 0 2 2 0 1 cjzj 0 x4 3 12 x2 52 4 12 18 0 0 1 0  3 1 0 0 1 1 0 12 cjzj 4 0 6 0 6 18 x3 1 12 x2 32 11 0 1  033 111 1 0 332 2 0 0 2 6 Tcjzj 3最优解为x0,1,， 目标值z39。

2(b)

min z5x12x24x33x1x2 2x34 s.t. 6x13x25x310x,x,x0123解：先将问题改写为求目标函数极大化，并化为标准形式

max z'5x12x24x30x40x53x1 x2 2x3x4 4 s.t. 6x13x25x3 x510x0i1,,5i列单纯形表，用对偶单纯形法求解 cj 5 2 4 0 0 cB 基 b x1 x2 x3 x4 x5 0 x4 4 0 x5 10 3 1 2 1 0 6 3 5 0 1 cjzj 5 2 4 0 0 23 0 x4 111 0  1 33 102 x2 3 cjzj512 1 0 33 221 0  0 33 4 x3 2 2 x2 0 3 0 1 3 1 3 1 0 5 2 1 0 0 2 0 cjzj 最优解为x0,0,2T， 目标值z8。 将该问题化为标准形式：

max z2x1x2x30x40x5x1x2x3x46s.t. x12x2x54x0i1,5i

用单纯形表求解 cj cB 基 b 2 1 1 0 0 x1 x2 x3 x4 x5 0 x4 6 0 x5 4 [1 ] 1 1 1 0 1 2 0 0 1 2 1 1 0 0 cjzj 6 cB 基 b x1 x2 x3 x4 x5 2 x1 6 0 x5 10 1 1 1 1 0 0 3 1 1 1 0 3 -1 2 0 cjzj 由于j0，所以已找到最优解X*6,0,0,0,10，目标函数值z*12 (a) 令目标函数

max z（21）x1（-1+2）x2（1+3）x3

(1)令230，将1反映到最终单纯形表中 cj cB 基 b 21 1 1 0 0 x1 x2 x3 x4 x5 21 x4 6 0 x5 10 1 1 1 1 0 0 3 1 1 1 0 -3-1 - 1 -1 2-1 0 cjzj 表中解为最优的条件：-3-10，- 1 -10，2-10，从而11 (2)令130，将2反映到最终单纯形表中 cj cB 基 b 2 12 1 0 0 x1 x2 x3 x4 x5 2 x1 6 0 x5 10 1 1 1 1 0 0 3 1 1 1 0 2-3 - 1 2 0 cjzj 表中解为最优的条件：2-3 0， 从而23 (3) 令120，将3反映到最终单纯形表中 cj cB 基 b 2 1 13 0 0 x1 x2 x3 x4 x5 2 x1 6 0 x5 10 1 1 1 1 0 0 3 1 1 1 0 -3 3 - 1 2 0 cjzj 表中解为最优的条件：3-10， 从而31

(b) 令线性规划问题为

max z2x1x2x3x1x2x364s.t. x12x245x0i1,3 i(1)先分析的变化

1011bB1b110

1使问题最优基不变的条件是bb100，从而16

1(2)同理有610，从而210 1026(c) 由于x(6,0,0,0,10)代入x12x362，所以将约束条件减去剩余变量后的方程x12x3x62直接反映到最终单纯形表中 cj cB 基 b 2 -1 1 0 0 0 x1 x2 x3 x4 x5 x6 1 1 1 1 0 0 0 3 1 1 1 0 1 0 -2 0 0 1 2 x1 6 0 x5 10 0 x6 -2 cjzj 0 -3 -1 -2 0 0 对表中系数矩阵进行初等变换，得 cj cB 基 b 2 -1 1 0 0 0 x1 x2 x3 x4 x5 x6 2 x1 6 0 x5 10 1 1 1 1 0 0 0 3 1 1 1 0 0 x6 -8 cjzj 0 -1 [-3] -1 0 1 0 -3 -1 -2 0 0 cj cB 基 b 2 -1 1 0 0 0 x1 x2 x3 x4 x5 x6 1 23 0 23 0

2 x1 10 31 33 0 20 x5 22 0 833 1

1 30 x6 8 310 1 1 1 0  33cjzj 38510  0  0  333因此增加约束条件后，新的最优解为

x11082228，x3，x5，最优值为 3333

(a) 线性规划问题

max z3x1x24x36x13x25x345s.t. 3x14x25x330x1,x2,x30

单纯形法求解 cB 基 b x1 x2 x3 x4 x5 0 x4 45 0 x5 30 6 3 5 1 0 3 4 5 0 1 cjzj 0 x4 15 4 x3 6 3 1 4 0 0 3 1 0 1 1 341 1 0 555cjzj 3 x1 5 4 x3 3 3114  0 0  5551111  0  333120 1 1  55cjzj 130 2 0   55最优解为x1,x2,x35,0,3 ，目标值z27。 (a) 设产品A的利润为3，线性规划问题变为

max z3x1x24x36x13x25x345s.t. 3x14x25x330x1,x2,x30

单纯形法求解 基 b x4 45 x5 30 x1 x2 x3 x4 x5 6 3 5 1 0 3 4 5 0 1 cjzj x4 15 x3 6 3 1 4 0 0 3 1 0 1 1 341 1 0 5553114  0 0  5551111  0  333120 1 1  55cjzj x1 5 x3 3 cjzj 130 2 0    35353113139，，都小于等于0，解得。 3535355

为保持最优计划不变，应使2(b) 线性规划问题变为

max z3x1x24x33x46x13x25x38x445s.t. 3x14x25x32x430x1,x2,x3,x40

单纯形法求解

cB 基 b x1 x2 x3 x4 x5 x6 0 x5 45 0 x6 30 6 3 5 8 1 0 3 4 5 2 0 1 cjzj 0 x4 15 4 x3 6 3 1 4 3 0 0 3 1 0 6 1 1 3421 1 0 555531174  0 0  55551111  0 2  3334120 1 1   555cjzj 3 x1 5 4 x3 3 cjzj 50 x4 21130 2 0   5551111  0 1  266621318 1 0  5151515129717  0 0  101530304 x3 5 cjzj

此时最优解为x1,x2,x30,0,5，目标值z20，小于原最优值，因此该种产品不值得生产。

(c) 设购买材料数量为y，则规划问题变为

max z3x1x24x30.4y6x13x25x345s.t. 3x14x25x3y30x1,x2,x3,y0

单纯形法求解 cB 基 b x1 x2 x3 y x4 x5 0 x5 45 0 x6 30 6 3 5 0 1 0 3 4 5 1 0 1 cjzj 0 x4 15 23 1 4  0 0 53 1 0 1 1 1 4 x3 6 3411 1  0 555531124  0 0  555511111  0   3333cjzj 3 x1 5 4 x3 3 2120 1 1   555cjzj 1130 2 0   5550 y 15 4 x3 9 3 1 0 1 1 1 631 1 0 0 5553922  0 0   5555cjzj 此时最优解为x1,x2,x3,y0,0,9,15，目标值z30，大于原最优值，因此应该购进原材料扩大生产，以购材料15单位为宜。

第三章

表

产地 销地 A1 A2 A3 A4 销量 B1 B2 B3 B4 9 8 12 13 10 10 12 14 8 9 11 12 10 10 11 12 6 14 35 5 产量 18 24 6 12

用vogel法求解得

B A A1 A2 A3 A4 14 24 6 0 11 4 B1 B2 B3 B4

用位势法检验，把上表中有数字的地方换成运价

B A A1 A2 A3 A4 Vj B1 B2 B3 B4 8 13 12 8 11 11 12 1 0 4 5 Ui 8 8 7 7

令v1=1

则u1+v2=8 所以u3=7 u1+v4=13 v3=4 u2+v3=12 u4=7 u3+v1=8 v5=8 u3+v3=11 u2=8 u4+v3=11 v2=0 u4+v4=12

得检验数表

B A A1 A2 A3 A4 0 0 1 2 1 2 0 2 3 B1 B2 B3 B4 表中所有的数字均大于等于零，故所求方案为最优方案 解：（a）用运价代替表中有数字的地方，求出位势和检验数

B A A1 A2 A3 Vj 1 11 12 k 9 2 1 k-11 -2 k-1 12-k 11 1 B1 B2 B3 B4 Ui 令v1=1则u1+v2=1 故v3=-2

u1+v4=11 u2=11 u2+v1=12 v2=k-11 u2+v2=k u1=12-k u2+v3=9 v4=k-1 u3+v1=2 u3=1

得检验数表

B B1 B2 B3 B4 A A1 A2 A3 k-3 10-k 30-k 24-k 15 18-k 令表中所有的检验数均大于等于零，得3≤k≤10

(b)由表和表计算出位势和检验数，令C24=M

位势表 B B1 B2 B3 B4 Ui A A1 A2 A3 Vj

检验数表

B A A1 A2 A3 4 17 M-17 17 17 11 B1 B2 B3 B4 1 11 12 7 9 2 1 -4 -2 6 5 11 1

当存在某非基变量的检验数大于等于零的时候有无穷多最优解 则M-17=0 所以M=17 故运价C24=17 销地 A1 A2 A3 供应量 产地 B1 500 540 580 2 B1’ 570 610 650 3 B2 M 600 640 4 B2’ M 670 710 2 B3 M M 550 1 B3’ M M 620 3 S 40 80 120 2 销量

3 3 4 由于产大于销，设有一个理想的销地A4，则 销地 产地 B1 B1’ B2 B2’ B3 B3’ S 销量

A1 A2 A3 A4 500 540 580 0 570 610 650 0 M 600 640 0 M 670 710 0 M M 550 0 M M 620 0 40 80 120 0 3 3 4 7 供应量 2 3 4 2 1 3 2 第四章

略

第五章

解：

Min z=P1 d1- +P2(d2-+d2+) . 11x1+3x2≥25

100 x1+50x2 + d1- - d1+ =1900 10x1+16x2 + d2- - d2+ =200 x1,x2, d1- ,d1+ , d2- ,d2+ ≥0

解：

目标规划模型为

Min z = P1 d1- +P2(d2-+d2+) +P2(d3-+d3+) +P3(d4-+d4+) +P3d5+ . 300 x1+450x2 + d1- - d1+ =10000 x1+ d2- - d2+ =10

x2 + d3- - d3+ =15

4x1+6x2 + d4- - d4+ =150

3x1+2x2 + d5- - d5+ =75

x1,x2, d1- ,di+ , di- ≥0 ,i=1，…，5