《整数规划习题.doc》由会员分享，可在线阅读，更多相关《整数规划习题.doc（11页珍藏版）》请在金锄头文库上搜索。
1、第五章整数规划习题5.1考虑以下数学模型minzf1(x1)f2(x2)且知足拘束条件（1）或x10，或x10；12（2）以下各不等式起码有一个成立：2x1x215x1x215x12x215（3）x0或5或101x2（4）x0，0x12此中205x,1如x10f=0,01(x1)如x1126x2,如x20f0,02(x2)如x2将此问题归纳为混淆整数规划的模型。解：minz10y15x112y26x2（）0x1y1?M；x2y?2M（1）x110y?3Mx210(1y)?3M（2）x1x215yM4x1x215y5Mx12x215yM6y4y5y62（3）x1x20y75y85y910y101
2、1y11y7y8y9y10y111(4)x10，x20;yi0或（1i1，.?，11）5.2试将下述非线性的0-1规划问题变换成线性的0-1规划问题23maxzxxxx12332x13x2x330或11,2,3x，（j）j1x2x3，当1解：令y不然0,故有xxy2，又32x，13x分别与1x，1x等价，因本题中模型可变换为3maxzxyx132x13x2x33yx2yx3x2x3y1,x1,x2,x3均为01y变量5.3某科学实验卫星拟从以下仪器装置中选若干件装上。相关数据资料见表5-1表5-1仪器装置代号体积重量实验中的价值A1v1w1c1A2v2w2c2A3v3w3c3A4v4w4c4A
3、5v5w5c5A6v6w6c6要求：（1）装入卫星的仪器装置整体积不超出V，总质量不超出W；（2）A1与A3中最多安装一件；（3）A2与A4中起码安装一件；（4）A5同A6或许都安上，或许都不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试成立这个问题的数学模型。解：6maxzcjxj1j6vjxjVj16wxWjjj1x1x31x2x41x5x6xj10,安装,不然A仪器j5.4某钻井队要从以下10个可供选择的井位中确立5个钻井探油，使总的钻探花费最小。若10个井位的代号为s1，s2,s10,相应的钻探花费为c1，c2,c10,而且井位选择上要知足以下限制条件：（1）或选择s
4、1和s7，或选择钻探s8；（2）选择了s3或s4就不可以选择s5，或反过来也同样；（3）在s5,s6,s7,s8,中最多只好选两个；试成立这个问题的整数规划模型。解：10minzcjxj1j10xj5j1x1x81x3x51x7x81x4x51x5x6x7x82x10,选择钻探第，不然s井位j5.5用割平面法求解以下整数规划问题（a）maxz7x19x2x13x267x1x235x,1x2,0且为整数（b）minz4x15x23x2x712x4x5123x1x22x,1x20且为整数（c）maxz4x16x22x34x14x25x16x25x1x2x35x,1x,2x3,0且为整数（d）max
5、z11x14x2x12x2145x12x2162x1x24x,1x2,0且为整数解：（a）不考虑整数拘束，用纯真形法求解相应线性给华问题得最后纯真形表，见表5A-1。表5A-1x1x2x3x4x27/2017/221/22x19/210-1/223/22cj-zj00-28/11-15/11从表中第1行得71x2xx34222272由此171x23x3x4222220711x3xs41即22222将此拘束加上，并用对偶纯真形法求解得表5A-2。表5A-2x1x2x3x4s1x27/2017/221/220x19/210-1/223/220s1-1/200-7/22-1/221cj-zj00-2
6、8/11-15/110x2301001x132/71001/7-1/7x311/70011/7-22/7cj-zj000-1-8由表5A-2的x行可写出16x1(0)x4(1)s177(447)又获得一个新的拘束176x4ss12747再将此拘束加上，并用对偶纯真形法求解得表5A-3。表5A-3x1x2x3x4s1s2x23010010x132/71001/7-1/70x311/70011/7-22/70s2-4/7000-1/7-6/71cj-zj000-1-80x23010010x141000-11x310010-41x4400016-7cj-zj0000-2-7所以本题最优解为x1=4，
7、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所。因为任务数多于人数，故规定此中有一个人可兼达成两项任务，其他三人每人达成一项。试确立总花销时间为最少的指派方案。表5-2任务ABCDE人甲2529314237乙3938262033丙丁34272840322442362345解：加工假定的第五个人是戊，他达成各项工作时间去甲、乙、丙、丁中最小者，构造表为5A-4表5A-4任务ABCDE人甲2529314237乙3938262033丙3427284032丁戊24423623452427262032对表5A-4再用匈牙利法求解，得最优分派方案为甲-B，乙-D和C，丙-E，丁-A，总计需要131小时。5.7某航空企业经营A，B，C三个城市之间的航线，这些航线每日班机腾飞与抵达时间如表5-3所示。表5-3航班号腾飞城市腾飞时间抵达城市抵达时间101A9：00B12：00102A10：00B13：00103A15：00B18：00104A20：00C24：00敏捷PDF变换器
