运筹学习题集答案(4)

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

?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