运筹学习题集答案(2)

综上，该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号码的人入选四、解：设 …… 此处隐藏：480字，全部文档内容请下载后查看。喜欢就下载吧 ……