运筹学习题集答案

第一套

一、解：设代表第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)'

综上，该0-1规划无可行解

五、解：按三个变量划分为三个阶段，状态转移方程

第三阶段： f3(s3)?max?x3??s3,x3*?s2 0?x3?s3

第二阶段：f2(s2)?maxx2(s3)?maxx2(s2?x2)? 0?x2?s2 0?x2?s2 其中 x2*?'12?''??''?14s2

2''s2 (x2?1?x2)

第一阶段：f1(s1)?maxx1? 其中 x1*??最优解x1*?2323?

14s22??max?x1?14(2?x1)2?2?827

0?x1?2 0?x1?2

,x2*?1?x2*?1?'23?13,x3*?238Z*?27

六、解：依题意，首先给出一个可行流

在初始流上增流到不能再增，得到如下结果：

此时已不能再增流，流量 f?105 ，不能满足市场的需求量。应修改仓库3到市场3和4的容量，分别增流10和5即能满足需求。

七、解：3、5正确。

第三套

一、解：将原问题化为标准形得

maxZ?4x1?x2?x1?x2?x3?2x1?4x2?x4?4x1?2x2?x5?8 xi?0,i?1,2,?5

4 1 0 0 0 bi bi/aik x1 x2 x3 x4 x5 0 x3 -1 1 1 0 0 2 - 0 x4 1 -4 0 1 0 4 4 0 x5 1 -2 0 0 1 8 8 rj 4 1 0 0 0 0 x3 0 -3 1 1 0 6 - 4 x1 1 -4 0 1 0 4 - 0 x5 0 2 0 -1 1 4 2

rj 0 17 0 -4 0

0 x3 0 0 1 -1/2 3/2 12 4 x1 1 0 0 -1 2 12 1 x2 0 1 0 -1/2 1/2 2

rj 0 0 0 9/2 -17/2

由于r4?0而对应的ai4?0 ? 此线性规划问题无界

二、解

（1）X2的价值系数由-7变为3。

r2?3??2?1?0???3???1?0??

?最优解发生变化，继续迭代。 2 3 1 0 0 x1 x2 x3 x4 x5 bi bi/aik 2 x1 0 x5 rj1 1 1 1 0 0 3 1 1 1 0 1 -1 -2 0 1 0 2/3 2/3 -1/3 0 1 1/3 1/3 1/3 0 0 -4/3 -2 -1/3 6 10 6 10/3 2 x1 3 x2 rj8/3 10/3 -46/3 此时最优解为 ?XZ**?(x1,x2)463B?1T810T?(,)33?

?1???1?0??1??

0??3??3????????0?????1??5??8?

T（2）

?1'?1b?Bb???1?

此时不影响解的最优性，只改变解的值及目标函数值

?X*?(x1,x5)Z*?6T?(3,8)

（3） 最优解不满足新增加的约束条件?x1?2x3?2

?最优解要发生改变 将约束条件改写为

x1?2x3?x6??2 加入最优表中继续迭代。 2 -7 1 0 0 0 x1 x2 x3 x4 x5 x6 2 x1 0 x5 0 x6 rjbi 6 10 -8 10/3 22/3 8/3 -28/3 1 1 1 1 0 0 0 3 1 1 1 0 0 -1 -3 -1 0 1 0 -9 -1 -2 0 0 rj/aik- 9 1/3 2 - - 1 2/3 0 2/3 0 1/3 0 8/3 0 2/3 1 4/3 0 1/3 1 1/3 0 -1/3 0 -26/3 0 -5/3 0 -1/3 X*?(x1,x3)Z*?283T2 x1 0 x5 1 x3 rj ?(10,8)33T

三、解：建立运输问题模型并给出初始方案得： 销 1 2 3 产 1 1’ 2 2’ 3 10 300 15 1 M M M 13 17 18 18 10 700 15 17 M 16 200 21 1 13 -7 18 0 15 700 200 ?新的最优解为

4 19 24 1 16 -7 21 200 18 0 5 0 4 0 200 0 0 0 2 0 5 产 700 200 700 200 700 -1 ui 0 4 4 2 3’ 4 4’ 销 vj M M M 300 10 M M M 700 -4 20 0 M M 900 16 23 200 15 -8 20 -3 600 19 0 0 0 700 0 200 1100 -4 200 700 200 3600 4 4 4 检验数有负，重复调整，得如下解： 销 1 2 产 1 1’ 2 2’ 3 3’ 4 4’ 销 vj3 4 19 4 24 9 16 4 21 6 18 4 23 8 15 600 20 5 600 15 5 0 200 0 200 0 3 0 200 0 1 0 200 0 100 0 200 1100 0 产 700 200 700 200 700 200 700 200 3600 ui 10 300 15 5 M M M M M M 300 10 rij?0 13 0 18 5 10 700 15 2 M M M M 700 13 16 200 21 5 13 0 18 2 15 700 20 4 M M 900 16 0 0 -3 0 -1 0 0 0 此时检验数全，为最优解

Z*?300?10?700?10?200?16?700?15?600?15?32700(元)

分配计划如下：第一个月正常生产500件，分别给1月300件，3月200件。 第二个月正常生产700件，供给第二个月 第三个月正常生产700件，供给第三个月 第四个月正常生产600件，供给第六个月

?0，第i号码的人不入选yi???1，第i号码的人入选四、解：设

?maxZ?????????????13(193y4?191y5?187y6?186y7?180y8?185y9)y4?y5?y5?y7?y8?y9?3y5?y8?1y4?y5?1y5?y9?1y7?y9?1y8?y9?1yi?0或1

五、解：利用匈牙利法求解，增加一行元素 ?50??40?40??20? ?0

40303030060203020030302030010??40??20??2010??30??30??0??0?~?030102010050201010100

020000??0?0??10??0??40??20?30??0?~?10200100501000200100000?0?0??10??10?

0?此时方案最优，最少人数Z*?20?20?20?10?70人

方案为周一上美术课，周三上艺术课，周四上音乐课，周五上文学课。

六、解 七、解：

1、（1）x1?x2?x3?2

（2）x2?x4?2或x2?x4?0

2、运费还可以减少，此方案不是最优方案

3、在多阶段决策过程中，最优决策序列具有这种性质，即不管该序列上某状态以前的状态和决策如何，余下的决策序列必构成该状态的最优决策序列。

第四套

一、解：

（1） 首先将解代入约束条件，满足，说明是可行解 ??1?A??0??1?

?40?4?8???2?0?? A?0 线性相关，此解不是基可行解

（2） 选取 x1,x3,x4作为基变量， ??1?A??0??1?

?8?200???2??10?? A??36?0 ?线性无关。

x2?x5?x6?x7?0 令

得出一个基可行解

，解出

x1?9?0,x3?1?0,x4?0

即X?(9,0,1,0,0,0,0)。

二、解：写出原问题的对偶问题得

?maxZ'?4y1?6y2?y1?y2??2??y1?y2??1?y1?ky2?2??y1无约束，y2?0

①

由互补松弛定理：x1?ys1?0得ys1?0,?y1?y2??2

6?2k1?k?41?k

x3?ys3?0 得ys3?0,?y1?ky2??2 ② ①②联立得

y1*?,y2*? 而Z*??12?Z'*,将y1*,y2*代入③

?4y1*?6y2*??12 ③ 则k??3,y1*??6,y2*?2 综上，k??3，对偶问题最优解为Y*?(y1,y2)?(?6,2)

三、解：（1）表上作业法求解得： 销 B3 B5 B1 B2 B4 产 A1 A2 A3 TT产 50 100 150 300 ui 10 0 20 10 30 15 25 20 rij?0 15 50 40 15 35 65 115 25 20 15 15 60 40 25 60 15 20 0 30 30 55 15 30 30 40 35 30 15 25 70 70 15 -10 0 10 销 vj 检验数

，此方案最优Z*?200?450?750?2275?900?900?1750?7225

（2）增加虚拟产地A4 销 B1 产 A1 A2 A3 B2 B3 B4 B5 产 50 100 130 20 ui 10 15 20 25 30 15 0 10 15 50 40 0 35 65 M 20 30 15 60 40 30 0 15 20 15 30 15 55 30 0 15 40 35 30 0 25 65 0 5 -25 0 -5 -20 A4 销 vj25 20 115 40 60 15 30 30 70 30 300 r?0检验数ij，此方案最优Z*?500?750?2275?900?450?1625?6500

四、解：用匈牙利法求解

020??3020??1?35412740??3???????4711??11037??9?47453251??15?39563643??715113??41280??2????????32512546??010???06?~?01006??~??~?0 ??最优方案为：肖恩 文字处理，伊恩 制作电脑图 安 材料准备， 琼 记录

00121201600??7?0??8??

最小时间Z*?32?45?27?43?147(小时）

五、解：按变量划分为三个阶段

si 可以提供第k到第 阶段的资源数，i?1,2,3 si?si?1?xi

第三阶段：f3(s3)?maxx3???s223

0?x3?s3 其中x3*?s3

f2(s2)?max4x2?s3?22??max??4x?22?( 第二阶段：

s22

?2)??4s2x2? s2 0?x2?s2 0?x2?s2 其中

第三阶段：

x2*?f1(s1)?max3x1?4s2?2?52?36?233?max?3x1???3?6?6x1??

0?x1?9 0?x1?9

其中x1*?2336

52 ?Z*?3?6?6，其中x1*?36，

x2*?322?6?16

?16

六、解：将奇数点变为偶数点得

经检验，重复边权小于等于非重复边权，此时为最优解

x3*?32?6

Z*?6?3?2?2?6?2?2?2?1?1?4?5?5?41

七、解

1、 b,a,a 2、 a,c 3、 ac 4、 ec

第五套

一、 ?1??0A???1??0?

解： ?30?400?203?8???2??10??3?? A?0，列向量线性相关，不是基可行解

选取 x1,x2,x3.,x7作为基变量， ?1??0A???1??0?

?30?400?2030??3?2??0?? ?线性无关。

T532 解出X'?(7,7,2,0,0,0,0)

二、

解：

1、 由题可知c4?c5?0,

0?12c3?16c1??41而0?3c1??2

12得c1?6,c2?10 此外，c2?B?112c3?12c1??4,得c2??2

?12????1?6?1'0??0'?A??1??13? ?0?????3???52?121??0?? b'?B?1b

?2?b?Bb???1? ??5??????10?5??? 2?1'?20??02???A?BA???13??1?1'?1???2 A?BA

?minZ??6x1?2x2?10x3?x2?2x3?5??原问题为?3x1?x2?x3?10??x1,x2,x3?0?

1??0????0???31?12??1??

?minw?5y1?10y2?3y2?6??y1?y2??2??2y1?y2?10??y1,y2?02、 对偶问题为?

3、 由于对偶问题的最优解是最终单纯形表中检验数的相反数，

则y*?(y1,y2)

三、 任务 机器 1 2 3 4 任务 vjT?(4,2)

T w*?40

解：利用表上作业法求解： 1 10 11 5 20 15 13 20 11 20 5 2 2 0 10 2 5 20 15 3 20 8 3 3 25 15 6 14 8 13 5 30 9 4 15 19 2 10 7 8 M 10 2 5 9 11 4 0 15 14 8 25 25 4 机器 25 30 20 30 105 ui -6 0 -3 4 rij?0检验数

，此方案最优Z*?75?100?20?100?65?200?560

四、

?1,生产第i种产品?x2，3 解：设i代表第i种产品的生产数量，?0，不生产第i种产品 i?1，?maxZ?4x1?5x2?6x3?100y1?150y2?200y3?2x1?4x2?8x3?500??2x1?3x2?4x3?300?x1?2x2?x3?100??x1?M1y1?x2?M2y2??x3?M3y3 ? xi?0,yi?0或1，i?1,2,3

其中Mi可取上界

M1?100,M2?50,M3?3

五、 解：B，CGL，H，K

100六、 解：建立网络图得：图中数字分别为最大流量和费用。 分别找出各步最小费用流，然后在此基础上增加流量得：

此时已满足需求量达到最优，

七、 解：灵敏度分析是指：当A，b，C的系统中一个或几个发生变化时，已求得

的最优解会有什么变化；这些系数在什么范围内改变时，规划问题的最优解或最优基不变；若最优解变化，如何用最简单的方法找到新的最优解。

Z*?40?4?40?5?10?8?20?5?20?5?50?6?940

本文来源：https://www.bwwdw.com/article/ozt8.html