运筹学习题集答案

第一套

一、解：设代表第i种原料混入第j种产品中的数量，其中i=1，2，3；j=1，2，3；则

33i13i23i331j32jmaxZ?9003?xi?1?1200?xi?1?1500?xi?1?600?xj?1?900?xj?1?1400?xj?13j?xj?131j?2000?xj?132j?1000?xj?13j?500362x11?78x21?90x31?70?xi1i?1362x12?78x22?90x32?80?xi2i?1362x13?78x23?90x33?85?xi3i?131.5x11?0.8x21?0.2x31?1.5x12?0.8x22?0.2x32?1.5x13?0.8x23?0.2x33?xij?0,i?1,2,3,j?1,2,3?xi?13i?13i1?x?xi?1i2i3二、解：原问题可化为：

maxZ?2x1?x2x1?x2?x3?52x2?x3?x4?5?4x2?x3?x5??9xi?0,i?1,2?5

b1 2 x1 0 x42 1 0 0 0 x1 x2 x3 x4 x5 5 5 -9 1 1 1 0 0 0 2 1 1 0 0 -4 -6 0 1 0 -1 -2 0 0 0 x5 rj rj/aij - 1/4 1/3 - - 1 0 1/2 0 1/4 2 x1 0 x4 0 0 -2 1 1/2 0 1 3/2 0 -1/4 0 0 -1/2 0 -1/4 0 x5 rj -31/4

?XZ**?(x1,x2)314T?(119T,)44

三、解：将原问题改成产销平衡问题，并用沃格尔法给出初始解得： 销 B3 B5 B1 B2 B4 产 A1 A2 A3 ?产 50 100 130 20 300 vj 10 5 20 10 30 5 0 15 25 20 15 50 40 10 35 65 M M-10 115 30 20 20 15 60 40 20 0 5 60 15 20 5 30 30 55 20 0 -10 30 30 40 35 30 10 25 65 0 5 70 20 -15 0 5 -20 A '销 ui 此方案还不是最优，需要调整 销 B1 B2 产 A1 A2 A3 B3 B4 B5 产 50 100 130 20 300 vj 10 15 20 25 30 15 0 10 25 15 50 40 0 35 65 M M-10 115 20 30 15 60 40 30 0 15 60 20 15 30 15 55 30 0 15 30 40 35 30 0 25 65 0 5 70 -25 0 -5 -30 A '销 ui *20 40 15 30 30 此时检验数均大于或等于0，为最优解 Z?25*20?15*50?65*35?60*15?30*15?65*25?6500

四、解：

10 5 15 20 M 8 3 10 12 M 5 0 7 9 M-3 2 10 5 15 0 0 8 0 7 0 0 8 0 7 0 3 15 14 13 0 ~ 1 13 9 5 0 ~ 1 13 9 5 0 ~ 15 2 7 M 0 13 0 2 M-8 0 13 0 2 M-8 0 9 4 15 8 0 7 2 10 0 0 7 2 10 0 0

4 0 6 8 M-3 0 9 0 7 1 0 13 8 4 0 12 0 1 M-9 0 7 3 10 0 1 此时，费用最小，Z?3?5?5?8?21

其中，丙 一， 甲 二， 乙 三， 戌 四

五、解：

v1 v2 v3 v4 v5 v6 v7 0* ?? ?? ?? ?? ?? ?? 11 9* 10 ?? ?? ?? 11 10* ?? 20 ?? 11* 21 20 ?? 21 21* ?? 21* 28 25*

?v1?v2 11 ： v1?v2

* v1?v3 9 ： v1?v3 v1?v4 10 ： v1?v4 v1?v5 21 ： v1?v4?v5 v1?v6 20 ： v1?v3?v6

v1?v7 25 ： v1?v4?v5?v7

六、解：

阶段：以向某一项目投资作为一个阶段，如此可划分为三个阶段。

状态变量：以可以提供的投资额作为状态变量si ，其范围为0，1，2，3，4百万

决策变量：以给某项目投资的金额作为决策变量xi，则 xi?si 状态转移方程：si?1?si?di

k?3,0?s3?4

s3 0 1 2 3 4 x3 0 1 2 3 4 38 41 48 60 66 f3(s3) x3* 38 41 48 60 66 0 1 2 3 4 k?2,0?s2?4 s2 0 1 2 3 4 k?1,s1?4 x2 0 1 2 3 4 40+38 40+41 42+38 40+48 42+41 50+38 40+60 42+48 50+41 60+38 40+66 42+60 50+48 60+41 66+38 f2(s2) x2* 78 81 88 100 106 0 0 0，2 0 0 s1 4

x1 0 1 2 3 4 38+106 64+100 68+88 78+81 76+78 f1(s1) x1* 164 1 ?总效益最大值为164，其中x1?1,x2?0,x3?3。

七、解：

a?01、无可行解：最终表人工变量不为零；或右侧常数 bi?0，对应的ij；

2、有多重解：

rj?0（非基变量）且至少有一个为零。

rj?03、有无界解：非基变量的检验数 ，且对应的系数列向量

aij?0。

第二套

一、解：设xi代表第i月正常生产的柴油机数量， yi代表第i月加班生产的柴油机数量， zi代表第i月末的库存量，则zi=4

44i4minZ?5000x1?y1?3000?xi?1?6500?i?1yi?200?zi?1iz1?x2?y2?4500z2?x3?y3?3500z3?x4?y4?5000 xi,yi,zi?0,i?1,2,3,4

二、解：

minW?5y1?2y2y1?2y2?52y1?y2?12y1?3y2?4

1、 对偶模型 y1?0,y2无约束

2、 由

单

纯

形

表

可

看

出

，

y1*??(?295)?295由于

ys1?x1?0;ys2?x2?0,而x1?0,x2?0?ys1?0,ys2?0

14152则对偶问题的第一、二个约束是紧的，可解出y2??5

T292将y1,y2代入第三个约束，满足约束条件，则y*?(y1,y2)?(5,?5),w*?3、5和2

4、B

5、如果原问题增加一个变量，则对偶问题就增加一个约束条件，它的可行域要么减少，要么不变，绝对不会变大。

三、解：此题可看作指派问题求解：

5 6 10 1 2 5 0 1 4 0 0 3 8 10 12 ~ 4 6 7 ~ 0 2 3 ~ 0 1 2 4 4 5 0 0 0 0 0 0 1 0 0

?最优解x21?1,x12?1,x33?1,其余为0，Z*?19 '?1?2/5????1/5?1/5??2/5??

四、解：将最大化问题化为极小化问题，并将系数转为正，即令xi?1?xi，整理得

minZ?5x1?7x2?10x3?3x4?x5?26x1?3x2?5x3?x4?4x5??2?2x1?6x2?3x3?2x4?2x5?1?2x2?2x3?x4?x5??3''''''''''''''''''''' xj'?0或1(j?1,2,?5)'