整数规划习题

1、第五章整数规划习题5.1 考虑下列数学模型且满足约束条件(1)或 X1 -10,或 X2 -10 ；(1) 下列各不等式至少有一个成立：(3) x1 一刈=0或 5 或 10(4) x1 之0, x2 之0其中20+5x1，如 X1 > 0f1(x1)= 0，如 =0将此问题归结为混合整数规划的模型。解.min z =10y1 5x1 12y2 6x25.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题1 ，当 x2 =x3 =1解：令y = 0，否则23一故有x2x3 =y，又x1 , 为分别与X1,小等价，因此题中模型可转换为5.3某科学实验卫星拟从下列仪器装置中选若干件

2、装上。有关数据资料见表5-1表5-1仪器装置代号体积重量实验中的价值AViwC1AV2w2C2AV3W3C3AV4W4C4AV5W5C5AV6W6C6要求：(1)装入卫星的仪器装置总体积不超过 V,总质量不超过 W (2) A与A中最多 安装一件；(3) A2与A中至少安装一件；(4) A同A或者都安上，或者都不安。总的 目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学 模型。解：5.4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用 最小。若10个井位的代号为S1 , S2, S10,相应的钻探费用为C1 , C2,C10,并且井位 选择上要

3、满足下列限制条件：(1)或选择S1和S7,或选才?钻探S8；(2)选择了 S3或S4就不能选择S5,或反过来也一样；(3)在S5,S6,S7,S8,中最多只能选两个；试建立这个问题的整数规划模型。解：5.5 用割平面法求解下列整数规划问题 maxz = 7x1 9x2（b） minz =4x1 +5x2（c） maxz =4x1 +6x2十2x3由此711-x3 - x4 S:一22222 max z =11x1 +4x2XiX2X3X4x2 7/2017/221/22x1 9/210-1/223/22Cj-Zj00-28/11-15/11解：（a）不考虑整数约束，用单纯形法求解相应线性给华问

4、题得最终单纯形表，见表 5A-1。表 5A-1从表中第1行得x2 3=12722x3122x4 _ 0X1X2X3X4S1X2 7/2017/221/220X1 9/210-1/223/220S1 -1/200-7/22-1/221Cj-Zj00-28/11-15/110X2 301001X1 32/71001/7-1/7X3 11/70011/7-22/7Cj-Zj000-1-8即将此约束加上，并用对偶单纯形法求解得表5A-2。表 5A-2由表5A-2的x行可写出又得到一个新的约束再将此约束加上，并用对偶单纯形法求解得表5A-3。表 5A-3X1X2X3X4S1S2X2 3010010x 1

5、 32/71001/7-1/70X3 11/70011/7-22/70s 2 -4/7000-1/7-6/71Cj -Zj000-1-80X2 3010010X1 41000-11X3 10010-41X4 4000P 16-7Cj-zj0000-2-7因此本题最优解为xi=4, X2=3, z=55(b)本题最优解为Xi=2, X2=1, z=13(c)本题最优解为 xi=2, X2=1, X3=6, z=26(d)本题最优解为Xi=2, X2=3, z=345.6分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表5-2所。 由于任务数多于人数，故规定其中有一个人可兼完成两项任

6、务，其余三人每人完成一项。试确定总花费时间为最少的指派方案表5-2任务ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解：加工假设的第五个人是戊，他完成各项工作时间去甲、乙、丙、丁中最小者，构造表为 5A-4表 5A-4任务ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032对表5A-4再用匈牙利法求解，得最优分配方案为甲-B,乙-D和C,内-E, 丁-A,总计 需要131小时。5.7 某航空公司经营A, B, C三个城市之间的航线，这些航线每天班机起飞与到达时I可如表5-3所

7、小表5-3航班号起飞城巾起飞时间到达城巾到达时间101a9: 00B12: 00102A10: 00B13: 00103A15: 00B18: 00104A20: 00C24: 00105A22: 00C2: 00106B4: 00A7: 00107B11: 00A14: 00108B15: 00A18: 00109C7: 00A11: 00110C15: 00A19: 00111B13: 00C18: 00112B18: 00C23:00113C15: 00B20:00114C7: 00B12:00设飞机在机场停留的损失费用大致与停留时间的平方成正比，又每架飞机从降落到下班起飞至少需要2小时

8、准备时间，试决定一个使停留费用损失为最小的飞行方案。解：把从某城市起飞的飞机当作要完成的任务，到达的飞机看作分配去完成任务的人。只要飞机到达后两个小时，即可分配去完成起飞的任务。这样可以分别对城市A, B, C各列出一个指派问题。各指派问题效率矩阵的数字为飞机停留的损失的费用。设飞机 在机场停留一小时损失为a元，则停留2小时损失为4a元，停留3小时损失为9a,依 次类推。对A, B, C三个城市建立的指派问题得效率矩阵分别见表 5A-6,表5A-7,表5A-8。表5A-5 城市A起飞1011021031041051064a9a64a169a225a107361a400a625a36a64a10

9、8225a256a441a4a16a109484a529a16a81a121a110196a225a400a625a9a表5A-6 城市B起飞106107108111112101256a529a9a625a36a102225a484a4a576a25a103100a289a441a361a576a11364a225a361a289a484a114256a529a9a625a36a表5A-7城市C起飞109110113114M0449a225a225a49a10525a169a169a25a111169a441a441a169a11264a256a256a64a对上述指派问题用匈牙利法求解，即可

10、得到一个使停留费用损失最小的方案。5-8 需制造2000件的某种产品，这种产品可利用 A, B, C设备的任意一种加工，已 知每种设备的生产准备结束费用，生产该产品时的单件成本，以及每种设备的最大加 工量如表5-4所示，试对此问题建立整数规划模型并求解。表5-4设备准备结束费（元）生产成木（刀:/件）取大加工数（件）A10010600B3002800C20051200设x为在第j台设备上生产的产品数，j=A, B, C,则问题的数学模型可表为：最优解为 xi=0, X2=800, X3=1200, z=81005-9 运筹学中着名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市 出发

11、，到其它几个城市去推销商品，规定每个城市均须到达而且只到达一次，然后回 到原出发城市。已知城市i和城市j之间的距离为dj ,问该商贩应选择一条什么样的 路线顺序旅行，使总的旅程为最短。试对此问题建立整数规划模型。1 ，旅行商贩从i直接去jXi =一解：设 0 5日八由此可写出其整数规划模型为5.10 有三个不同产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2, 3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用tj表示在第j机床上加工第i个产品的时间，问应如何安排，使三个产品总的加工周期 为最短。试建立这个问题的数学模型。解：用Xij表示第i中产品在j机床上开始

12、加工的时刻，则问题的数学模型可表示为： 5.11某电子系统由三种元件组成，为使系统正常运转，每个元件都必须工作良好。 如一个或多个元件安装几个备用件将提高系统的可靠性。已知系统运转可靠性为各元 件可靠性的乘积，而每一元件的可靠性则是备用件数量的函数，具体数值见表5-5。表5-5备用件数元件可靠性12300.50.60.710.60.750.920.70.951.030.81.01.040.91.01.051.01.01.0又三种元件分别的价格和重量如表 5-6所示。已知全部备用件的费用预算限制为150元，重量限制为20千克，问每个元件各安装多少备用件（每个元件备用件不得超过5个），是系统可靠性

13、为最大。试列出这个问题的整数规划模型。表5-6元件每件价格（元）重量（千克/件）1120223043406解：用x,x,x分别表示1, 2, 3三个元件安装的备用件数量。根据题中条件及费用、 重量的限制，元件1的备件最多安装5个，元件2备件最多5个，元件3的备件最多 安装3个。故问题的数学模型可表示为：5.12 用你认为合适的方法求解下述问题：解：将问题改写为求解得 X1=0,X2=0,X3=10,y=1,z=505.13 下述线性规划问题说明能否用先求解相应的线性规划问题然后凑整的办法来求得该整数规划的一个可行解：当不考虑整数约束，求解相应线性规划得最优解为Xi=10/3,X2=X3=0。用

14、凑整法时令xi=3,X2=X3=0,其中第2个约束无法满足，故不可行。5.14 某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代 号及其能覆盖的居民小区编号如表 5-7所示，问为覆盖所有小区至少应建多少所小学， 要求建模并求解。表5-7备选校址代号覆盖的居民小区编号A1,5,7B1,2,5C1,3,5D2,4,5E3,6F4,61 ，在第i备选校址建校x = L -解：令 0 ，小则答案为在A, D, E三个备选校址建校。5.15 已知下列五名运动员各种姿势的游泳成绩（各为 50米）如表5-8所示，试问如何从中选拔一个参加200米混合泳的接力队，使语气比赛成绩为最好。5.1

15、6 单位：秒赵钱张王周仰泳37.732.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1解：由下列运动员组成混合接力队：张游仰泳，王游蛙泳，钱游蝶泳，赵游自由泳, 预期总成绩为126.2秒。5-16用匈牙利法求解下述指派问题，已知效率矩阵分别如下:一791012一13 12 16 1715 16 14 15(a) J1 12 15 16 一3821038729764275184235(b) J9 10 6 9 10解：(a)最优指派方案为X13=X22=X34=X41=1,最优值为4

16、8;(b)最优指派方案为X15=X23=X32=X44=X51=1 ；最优值为215-17从甲、乙、丙、丁、戊五人中挑选四人去完成四项工作。已知每人完成各项工作 的时间如表5-9所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项 任务。又假定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第 4项任务 在满足上述条件下，如何分配工作，使完成四项工作总的花费时间为最少。表5-9人甲乙丙丁戊1102315925101524315514715420151368解：先增加一种假想工作5,再据题中给的条件列出表5A-9表 5A-8人甲乙丙丁戊11023159251015243155147154201513OO85OO0000对表5A-9用匈牙利法求解得最优分配方案为：甲-2,乙-3,丙-1 ,戊-4,对丁不分配5-18设有m个某种物资的生产点