整数规划习题.doc

第五章 整数规划习题5.1 考虑下列数学模型 且满足约束条件（1）或，或；（2）下列各不等式至少有一个成立： （3）或5或10（4），其中 = 将此问题归结为混合整数规划的模型。解： 5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题 解：令故有，又，分别与，等价，因此题中模型可转换为 5.3 某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1表 5-1仪器装置代号体积重量实验中的价值A1A2A3A4A5A6v1v2v3v4v5v6w1w2w3w4w5w6c1c2c3c4c5c6要求：（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或s4就不能选择s5，或反过来也一样；（3）在s5,s6,s7,s8,中最多只能选两个；试建立这个问题的整数规划模型。解： 5.5 用割平面法求解下列整数规划问题（a） （b） （c） （d） 解：（a）不考虑整数约束，用单纯形法求解相应线性给华问题得最终单纯形表，见表5A-1。表5A-1x1x2x3x4x2 7/2x1 9/201107/22-1/221/223/22cj-zj00-28/11-15/11从表中第1行得 由此 即 将此约束加上，并用对偶单纯形法求解得表5A-2。表5A-2x1x2x3x4s1x2 7/2x1 9/2s1 -1/20101007/22-1/22-7/221/223/22-1/22001cj-zj00-28/11-15/110x2 3 x1 32/7x3 11/701010000101/71/71-1/7-22/7cj-zj000-1-8由表5A-2的x行可写出 又得到一个新的约束 再将此约束加上，并用对偶单纯形法求解得表5A-3。表5A-3x1x2x3x4s1s2x2 3 x1 32/7 x3 11/7 s2 -4/701001000001001/71/7-1/71-1/7-22/7-6/70001cj-zj000-1-80x2 3x1 4x3 1x4 401001000001000011-1-46011-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所。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。表5-2任务人ABCDE甲乙丙丁2539342429382742312628364220402337333245解：加工假设的第五个人是戊，他完成各项工作时间去甲、乙、丙、丁中最小者，构造表为5A-4表5A-4任务人ABCDE甲乙丙丁戊25393424242938274227312628362642204023203733324532对表5A-4再用匈牙利法求解，得最优分配方案为甲-B，乙-D和C，丙-E，丁-A，总计需要131小时。5.7 某航空公司经营A，B，C三个城市之间的航线，这些航线每天班机起飞与到达时间如表5-3所示。表5-3航班号起飞城市起飞时间到达城市到达时间101102103104105106107108109110111112113114AAAAABBBCCBBCC9：0010：0015：0020：0022：004：0011：0015：007：0015：0013：0018：0015：007：00BBBCCAAAAACCBB12：0013：0018：0024：002：007：0014：0018：0011：0019：0018：0023：0020：0012：00设飞机在机场停留的损失费用大致与停留时间的平方成正比，又每架飞机从降落到下班起飞至少需要2小时准备时间，试决定一个使停留费用损失为最小的飞行方案。解：把从某城市起飞的飞机当作要完成的任务，到达的飞机看作分配去完成任务的人。只要飞机到达后两个小时，即可分配去完成起飞的任务。这样可以分别对城市A，B，C各列出一个指派问题。各指派问题效率矩阵的数字为飞机停留的损失的费用。设飞机在机场停留一小时损失为a元，则停留2小时损失为4a元，停留3小时损失为9a，依次类推。对A，B，C三个城市建立的指派问题得效率矩阵分别见表5A-6，表5A-7，表5A-8。表5A-5 城市A起飞到达1011021031041051061071081091104a361a225a484a196a9a400a256a529a225a64a625a441a16a400a169a36a4a81a625a225a64a16a121a9a表5A-6 城市B起飞到达106107108111112101102103113114256a225a100a64a256a529a484a289a225a529a9a4a441a361a9a625a576a361a289a625a36a25a576a484a36a表5A-7城市C起飞到达10911011311410410511111249a25a169a64a225a169a441a256a225a169a441a256a49a25a169a64a对上述指派问题用匈牙利法求解，即可得到一个使停留费用损失最小的方案。5-8 需制造2000件的某种产品，这种产品可利用A，B，C设备的任意一种加工，已知每种设备的生产准备结束费用，生产该产品时的单件成本，以及每种设备的最大加工量如表5-4所示，试对此问题建立整数规划模型并求解。表5-4设 备准备结束费（元）生产成本（元/件）最大加工数（件）ABC10030020010256008001200设x为在第j台设备上生产的产品数，j=A，B，C，则问题的数学模型可表为： 最优解为x1=0，x2=800，x3=1200，z=81005-9 运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其它几个城市去推销商品，规定每个城市均须到达而且只到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为dij，问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试对此问题建立整数规划模型。解：设由此可写出其整数规划模型为 5.10 有三个不同产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用tij表示在第j机床上加工第i个产品的时间，问应如何安排，使三个产品总的加工周期为最短。试建立这个问题的数学模型。解：用xij表示第i中产品在j机床上开始加工的时刻，则问题的数学模型可表示为： 5.11 某电子系统由三种元件组成，为使系统正常运转，每个元件都必须工作良好。如一个或多个元件安装几个备用件将提高系统的可靠性。已知系统运转可靠性为各元件可靠性的乘积，而每一元件的可靠性则是备用件数量的函数，具体数值见表5-5。表 5-5备用件数元件可靠性1230123450.50.60.70.80.91.00.60.750.951.01.01.00.70.91.01.01.01.0又三种元件分别的价格和重量如表5-6所示。已知全部备用件的费用预算限制为150元，重量限制为20千克，问每个元件各安装多少备用件（每个元件备用件不得超过5个），是系统可靠性为最大。试列出这个问题的整数规划模型。表 5-6元件每件价格（元）重量（千克/件）123203040246解：用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 下述线性规划问题 说明能否用先求解相应的线性规划问题然后凑整的办法来求得该整数规划的一个可行解。解：当不考虑整数约束，求解相应线性规划得最优解为x1=10/3,x2=x3=0。用凑整法时令x1=3,x2=x3=0,其中第2个约束无法满足，故不可行。5.14 某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表5-7所示，问为覆盖所有小区至少应建多少所小学，要求建模并求解。表5-7备选校址代号覆盖的居民小区编号ABCDEF1,5,71,2,51,3,52,4,53,64,6解：令 答案为在A，D，E三个备选校址建校。5.15 已知下列五名运动员各种姿势的游泳成绩（各为50米）如表5-8所示，试问如何从中选拔一个参加200米混合泳的接力队，使语气比赛成绩为最好。表5-8 单位：秒赵钱张王周仰泳蛙泳蝶泳自由泳37.743.433.329.232.933.128.526.433.842.238.929.637.034.730.428.535.441.833.631.1解：由下列运动员组成混合接力队：张游仰泳，王游蛙泳，钱游蝶泳，赵游自由泳，预期总成绩为126.2秒。5-16 用匈牙利法求解下述指派问题，已知效率矩阵分别如下：（a） （b） 解：（a）最优指派方案为x13=x22=x34=x41=1, 最优值为48； （b）最优指派方案为x15=x23=x32=x44=x51=1；最优值为215-17 从甲、乙、丙、丁、戊五人中挑选四人去完成四项工作。已知每人完成各项工作的时间如表5-9所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务。在满足上述条件下，如何分配工作，使完成四项工作总的花费时间为最少。表5-9人工作甲乙丙丁戊1234105152021051531514131527694158解：先增加一种假想工作5，再据题中给的条件列出表5A-9表5A-8人工作甲乙丙丁戊12345105152021051503151413015270941580对表5A-9用匈牙利法求解得最优分配方案为：甲-2，乙-3，丙-1，戊-4，对丁不分配工作。5-18