《管理运筹学》习题4解答

《管理运筹学》习题4解答

1.某钻井队要从10个可供选择的井位S1、S2，…，S10中确定5个钻井采油，目的是使总的钻探费用最小。这十个井位对应的钻控费用分别为c1、c2，…，c10，并且井位选择要满足：或选择S1和S7，或选择钻探S8；选择了S3或S4就不能选S5，或反过来也一样；在S2、S6、S9、S10中最多只能选两个。试建立该问题的数学模型（只建模，不求解）。

?1选择第Sj个井位 解：设xj?? ?0不选第Sj个井位 min z??xj?110j?x1?x8?1?x?x?18该问题的整数规划模型如下： ?7?x3?x5?1??x4?x5?1s.t.??x2?x6?x9?x10?2?10??xj?5?j?1?xj?0或（1j?1,2,?,10)?2.有如下整数规划问题，已知初始整数可行解X=(3,1)T

用分枝定界法求其最优解的过程如下： L0：z*=29/6 x1=3/2,x2=10/3 x1≤1 x1≥2 *L1：zL2：z*=41/9 =10/3 x1=1,x 2=7/3 x1=2,x2=23/9 ╳ L3：z*=61/14 x1=33/14,x2=2 x1≥3 x1≤2 5：z*=4 LL6：z*=4 1=2,x2=2 xx1=3,x2=1 ╳ ╳

要求回答：

z=4 ; 29/6

z=4; 41/9

L4： 无可行解 ╳ z=4 z=4; 61/14

（1）请写出每一层z的上界和下界z。依据上界和下界关系，在什么时候停止迭代？

（2）请写出L3问题的所有约束条件。（3）问题L1、L4、L5为什么被剪枝？ （4）请写出最优解和最优目标函数值。 解：（1）每一层z的上界和下界z填写在图中。初始，可取原模型任一整数可行解对应的目标函数值为下界，如X=(3,1)T对应的z=4，即初始下界z=4，上界取L0对应的目标函数值29/6；以后计算中，如果未得到整数可行解，下界就不变，否则下界就调整为整数可行解对应的z值；而如果当前所有分枝问题的z值（存在的话）小于上界，上界就减小为这些z值中的最大值（但是不得小于此时的z才行）。最后，当=z时，就停止分枝计算，在分枝末就可以找到最优解，或无可行解，或有多个最优解。

951x2?14?x1?14?1?2x?x?123?TT?**t?x1?2（2）s.. （4）X1??2,2?,X2??3,1?,max z?4 ?x?2?2??x1,x2?0（3）L1被剪枝，因为它对应的z*=10/3

（单位：小时）如下表所示。如果：（1）任务E必须完成，其他4项中可任选3项完成；或者（2）其中一人完成两项，其他人每人完成一项。要求：对于问题（1）请给出标准化以后的效率矩阵并用匈牙利法求出最优分配方案；对于问题（2）请写出标准化以后的效率矩阵不必求解。但需要说明如何从最优矩阵中判断出是哪一个人承担了两项任务。（两问都不必建模） 人 任务 A B C D E 25 29 31 42 37 甲 39 38 26 20 33 乙 34 27 28 40 32 丙 24 42 36 23 45 丁 解：（1）标准化以后的效率矩阵为： C D E 任务 A B 人 25 29 31 42 37 甲 39 38 26 20 33 乙 34 27 28 40 32 丙 24 42 36 23 45 丁 0 0 0 0 M 戊 -min?046171712??186013?0?19186?01135???0113?7??1191301913022??000M????0000 -min 0 0 0 0 5 ? +1?25?39??34??24??04237?25?0?1938262033?20??27284032? 27??7??42362345?23?1?000M??0?02931467??8???1∵ m=4<5 ?0? 17???1试指派不?成功 M??T 由于任务数5多于人数4，所以增添一名假想的

人，设为戊。因为工作E必须完成，也就是说它不能由虚拟的戊来完成，所以戊完成该项工作的时间设为M（M为非常大的正数），完成其余工作的假想时间为0。

求解过程如下：

?002187???4??507???4∵m=4<5 ?18131?? ?11011140?试指派不?12016???4成功

?0148??40 1M?00?? ? ?+4 +4?04??1817?0?7?018???006183??03?∵m=5=n

指派 ?180?结束

?012?5M??

结论：最优分配方案：甲――B；乙――D；丙――E；丁――A；C任务放弃。最少的时间为：

29+20+32+24=105小时

（2）增加一个虚拟的人戊。由于所有任务都必须由甲、乙、丙、丁完成，所以戊的效率对每项工作而言，应该都是完成效率最高。标准化后的效率矩阵如下所示：

C D E 任务 A B 人 25 29 31 42 37 甲 39 38 26 20 35 乙 34 27 28 40 32 丙 24 42 36 23 45 丁 24 27 26 20 32 戊

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