整数规划习题

第五章整数规划习题考虑下列数学模型)()(min2211xfxfz且满足约束条件（1）或101x，或102x；（2）下列各不等式至少有一个成立：15215152212121xxxxxx（3）021xx或5或10（4）01x，02x其中)(11xf=0,00,520111xxx如如)(22xf0,00,612222xxx如如将此问题归结为混合整数规划的模型。解：2211612510minxyxyz），，＝（或，）（）（）（；）（11.110;00)4(111105503215215152)1(10101021111098711109872165462152142132312211iyxxyyyyyyyyyyxxyyyMyxxMyxxMyxxMyxMyxMyxMyxi试将下述非线性的0-1规划问题转换成线性的0-1规划问题333221maxxxxxz），（或3,2,110332321jxxxxj解：令y否则，当,01132xx故有yxx32，又21x，31x分别与1x，3x等价，因此题中模型可转换为31maxxyxz变量均为10,,,13323213232321yxxxyxxxyxyxxx某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1表5-1仪器装置代号体积重量实验中的价值A1A2A3A4A5A6v1v2v3v4v5v6w1w2w3w4w5w6c1c2c3c4c5c6要求：（1）装入卫星的仪器装置总体积不超过V，总质量不超过W；（2）A1与A3中最多安装一件；（3）A2与A4中至少安装一件；（4）A5同A6或者都安上，或者都不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。解：jjjxcz61max否则仪器安装,0,1116542316161jjjjjjjjAxxxxxxxWxwVxv某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号为s1，s2,…s10,相应的钻探费用为c1，c2,…,c10,并且井位选择上要满足下列限制条件：（1）或选择s1和s7，或选择钻探s8；（2）选择了s3或s4就不能选择s5，或反过来也一样；（3）在s5,s6,s7,s8,中最多只能选两个；试建立这个问题的整数规划模型。解：101minjjjxcz，否则井位选择钻探第0s,1211115j876554875381101jxxxxxxxxxxxxxxj用割平面法求解下列整数规划问题（a）2197maxxxz且为整数0,,35763212121xxxxxx（b）215x4xminz且为整数0x,x2x3x54xx72x3x21212121（c）321264maxxxxz且为整数0,,,5565443213212121xxxxxxxxxx（d）21411maxxxz且为整数0,,42162514221212121xxxxxxxx解：（a）不考虑整数约束，用单纯形法求解相应线性给华问题得最终单纯形表，见表5A-1。表5A-1x1x2x3x4x27/2x19/201107/22-1/221/223/22cj-zj00-28/11-15/11从表中第1行得27221227432xxx由此0221227213432xxx即21221227143sxx将此约束加上，并用对偶单纯形法求解得表5A-2。表5A-2x1x2x3x4s1x27/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行可写出)744()761()710(141sxx又得到一个新的约束747671214ssx再将此约束加上，并用对偶单纯形法求解得表5A-3。表5A-3x1x2x3x4s1s2x23x132/7x311/7s2-4/701001000001001/71/7[-1/7]1-1/7-22/7-6/70001cj-zj000-1-80x23011000001-101x14x31x4400001001-461-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=34分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表5-2所。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。表5-2任务人ABCDE甲乙丙丁2539342429382742312628364220402337333245解：加工假设的第五个人是戊，他完成各项工作时间去甲、乙、丙、丁中最小者，构造表为5A-4表5A-4任务人ABCDE甲乙丙253934293827312628422040373332丁戊24244227362623204532对表5A-4再用匈牙利法求解，得最优分配方案为甲-B，乙-D和C，丙-E，丁-A，总计需要131小时。某航空公司经营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，则问题的数学模型可表为：3213215210200300100minxxxyyyz1012000800060002000321321或jyyxyxyxxxx最优解为x1=0，x2=800，x3=1200，z=81005-9运筹学中著名的旅行商贩（货郎担）问题可以叙述如下：某旅行商贩从某一城市出发，到其它几个城市去推销商品，规定每个城市均须到达而且只到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为dij，问该商贩应选择一条什么样的路线顺序旅行，使总的旅程为最短。试对此问题建立整数规划模型。解：设，否则直接去旅行商贩从0ji,1ijx由此可写出其整数规划模型为ninjijijxdz1minjin...1jin...1i1),...,1(1),...,1(11，，，，），也可取整数值，，为连续变量（iijjinjijniijunnxuunixnjx有三个不同产品要在三台机床上加工，每个产品必须首先在机床1上加工，然后依次在机床2，3上加工。在每台机床上加工三个产品的顺序应保持一样，假定用tij表示在第j机床上加工第i个产品的时间，问应如何安排，使三个产品总的加工周期为最短。试建立这个问题的数学模型。解：用xij表示第i中产品在j机床上开始加工的时刻，则问题的数学模型可表示为：333323231313,,maxmintxtxtxz互斥性约束或加工顺序约束010;3,2,1;2,1)1()2,1;3,2,1(,1,1,11,ijiijjijiijiijijjiijijxjiMxtxMxtxjittx某电子系统由三种元件组成，为使系统正常运转，每个元件都必须工作良好。如一个或多个元件安装几个备用件将提高系统的可靠性。已知系统运转可靠性为各元件可靠性的乘积，而每一元件的可靠性则是备用件数量的函数，具体数值见表5-5。表5-5备用件数元件可靠性123012345又三种元件分别的价格和重量如表5-6所示。已知全部备用件的费用预算限制为150元，重量限制为20千克，问每个元件各安装多少备用件（每个元件备用件不得超过5个），是系统可靠性为最大。试列出这个问题的整数规划模型。表5-6元件每件价格（元）重量（千克/件）123203040246解：用x,x,x分别表示1，2，3三个元件安装的备用件数量。根据题中条件及费用、重量的限制，元件1的备件最多安装5个，元件2备件最多5个，元件3的备件最多安装3个。故问题的数学模型可表示为：)9.07.0()95.075.06.0()9.08.07.06.05.0(max13121110987654321yyyyyyyyyyyyyz)13,...,110)3,2,1(011120642150403020131110761321321iyjxyyyxxxxxxijiiiiii（或用你认为合适的方法求解下述问题：32152maxxxxz0,,10215310321321321xxxxxxxxx解：将问题改写为3