整数规划习题.doc

《整数规划习题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第五章整数规划习题5.1考虑下列数学模型且满足约束条件（1）或，或；（2）下列各不等式至少有一个成立：（3）或5或10（4），其中=将此问题归结为混合整数规划的模型。解：5.2试将下述非线性的0-1规划问题转换成线性的0-1规划问题解：令故有，又，分别与，等价，因此题中模型可转换为5.3某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1表5-1仪器装置代号体积重量实验中的价值A1A2A3A4A5A6v1v2v3v4v5v6w1w2w3w4w5w6c1c2c3c4c5c6要求：（

2、1）装入卫星的仪器装置总体积不超过V，总质量不超过W；（2）A1与A3中最多安装一件；（3）A2与A4中至少安装一件；（4）A5同A6或者都安上，或者都不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。解：5.4某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号为s1，s2,…s10,相应的钻探费用为c1，c2,…,c10,并且井位选择上要满足下列限制条件：（1）或选择s1和s7，或选择钻探s8；（2）选择了s3

3、或s4就不能选择s5，或反过来也一样；（3）在s5,s6,s7,s8,中最多只能选两个；试建立这个问题的整数规划模型。解：5.5用割平面法求解下列整数规划问题（a）（b）（c）（d）解：（a）不考虑整数约束，用单纯形法求解相应线性给华问题得最终单纯形表，见表5A-1。表5A-1x1x2x3x4x27/2x19/201107/22-1/221/223/22cj-zj00-28/11-15/11从表中第1行得由此即将此约束加上，并用对偶单纯形法求解得表5A-2。表5A-2x1x2x3x4s1x27/

4、2x19/2s1-1/20101007/22-1/22[-7/22]1/223/22-1/22001cj-zj00-28/11-15/110x23x132/7x311/701010000101/71/71-1/7-22/7cj-zj000-1-8由表5A-2的x行可写出又得到一个新的约束再将此约束加上，并用对偶单纯形法求解得表5A-3。表5A-3x1x2x3x4s1s2x23x132/7x311/7s2-4/701001000001001/71/7[-1/7]1-1/7-22/7-6/70001

5、cj-zj000-1-80x23x14x310101000010001-1-4011x4400016-7cj-zj0000-2-7因此本题最优解为x1=4，x2=3，z=55（b）本题最优解为x1=2，x2=1，z=13（c）本题最优解为x1=2，x2=1，x3=6，z=26（d）本题最优解为x1=2，x2=3，z=345.6分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表5-2所。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最

6、少的指派方案。表5-2任务人ABCDE甲乙丙丁2539342429382742312628364220402337333245解：加工假设的第五个人是戊，他完成各项工作时间去甲、乙、丙、丁中最小者，构造表为5A-4表5A-4任务人ABCDE甲乙丙丁戊25393424242938274227312628362642204023203733324532对表5A-4再用匈牙利法求解，得最优分配方案为甲-B，乙-D和C，丙-E，丁-A，总计需要131小时。5.7某航空公司经营A，B，C三个城市之间的航线

7、，这些航线每天班机起飞与到达时间如表5-3所示。表5-3航班号起飞城市起飞时间到达城市到达时间101102103104105106107AAAAABB9：0010：0015：0020：0022：004：0011：00BBBCCAA12：0013：0018：0024：002：007：0014：00108109110111112113114BCCBBCC15：007：0015：0013：0018：0015：007：00AAACCBB18：0011：0019：0018：0023：0020：0012：0

8、0设飞机在机场停留的损失费用大致与停留时间的平方成正比，又每架飞机从降落到下班起飞至少需要2小时准备时间，试决定一个使停留费用损失为最小的飞行方案。解：把从某城市起飞的飞机当作要完成的任务，到达的飞机看作分配去完成任务的人。只要飞机到达后两个小时，即可分配去完成起飞的任务。这样可以分别对城市A，B，C各列出一个指派问题。各指派问题效率矩阵的数字为飞机停留的损失的费用。设飞机在机场停留一小时损失为a元，则停留2小时损失为4a元，停留3小时损失为9a，依次类推。对A，B，C三个城市建立的指派问题得效