第五章整数规划

1、第五章 整数规划1 整数规划问题的提出2 分枝定界法3 割平面法4 0-1型整数规划5 指派问题第五章 整数规划（重点和难点）1、理解整数规划的数学模型2、了解整数规划模型的类型3、了解整数规划的求解方法4、掌握分枝的思想和步骤（重点和难点）5、理解割平面法的思想和步骤5、了解0-1规划的隐枚举法6、掌握指派问题的数学模型和求解方法（重点和难点）1 整数规划问题的提出理解整数规划的数学模型了解整数规划模型的类型了解整数规划的求解方法掌握分枝的思想和步骤了解0-1规划的隐枚举法掌握指派问题的数学模型和求解方法背包问题背包问题 一背有容量为一背有容量为250 cm3的背包的小偷进入库房（或的背包的

2、小偷进入库房（或某户人家或机房），他需要从若干物品中选择一定数量某户人家或机房），他需要从若干物品中选择一定数量装入背包带走。可选的物品有装入背包带走。可选的物品有7种，其价值、体积及最种，其价值、体积及最大的数量入下表大的数量入下表:物品物品 1 2 3 4 5 6 7价值（元）价值（元）200 150 15 50 80 30 500体积（体积（cm3)数量数量 5 5 2 6 12 2 4 2 15 18 14 8 4 1问小偷应如何选择物品才能使价值最大？问小偷应如何选择物品才能使价值最大？令令xi表示小偷选择物品表示小偷选择物品i的数量的数量，则则背包问题的数学模型为背包问题的数学模型

3、为为整数。iixixxxxxxxxxxxxxxxxxxxxxxz; 7 , 2 , 1, 014814181522504212625550030805015150200max765432176543217654321体积约束体积约束数量约束数量约束整数约束整数约束 例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5-1： 问两种货物各托运多少箱,可使利润最大?货物体积（每箱M3)重量(每箱50kg)利润(每箱百元)甲乙54252010托运限制 2413问题分析 设x1,x2分别为甲乙两种货物的托运箱数(非负整数),则 Max z=20 x1+10 x2 5x

4、1+4x224 2x1+5x2 13 x1，x20， x1，x2整数。求解线性规划的最优解得： x1=4.8，x2=0，Max z=96 。 四舍五入得x1=5，x2=0，但不是可行解，取整x1=4，x2=0是可行解，z=80,是不是最优解呢？不是，因为可行解x1=4，x2=1对应的z=90。 那么，如何求整数规划的最优解，这就是本章的主要内容。什么是整数规划？1、一个线性规划如果有某些决策变量是整数，则称为整数规划（Integer programming)；2、整数规划的类型：n 纯整数规划；n 混合整数规划；n 0-1（整数）规划。整数规划的可行解，最优解 x232 +1 + + + +

5、+ 1 2 3 4 5 6 7 x12 分枝定界法n 对于整数规划问题，如果是两个自变量则可以用图解法（要比线性规划难）。n 当可行区域有界时，整数可行解的个数为有限个，因此，可把所有的整数可行解求出来，目标函数值最大者对应的可行解就为最优解，这种方法称为枚举法。n 但是，当变量较多时，可行整数解的个数也很多，其计算量仍然很大。n 例如指派n人做n件事的问题就有n!个可行解，当n=10时，可行解超过300万个，当n=20时，可行解超过2*1018个，枚举法就不行了。因此，下面要给出整数规划的有效求解方法。求解整数规划的方法n 分枝定界法；n 割平面法；n 其它算法。分枝定界法 设有极大型的整数

6、线性规划问题，记为 ILP ，与之对应的普通线性规划问题记为 LP 。分枝定界法求解 ILP 问题的基本思路是： 1、先从求解LP 问题开始，如果 LP 的解不符合整数条件，那么 LP 的最优目标值必然构成ILP 最优目标值的一个上界，记为 ； 2、而 ILP 的任意可行解的目标值都将是最优目标值的一个下界，记为 z 。 所谓分枝定界法就是将LP 问题的可行域划分为两个子域（分枝，中间去掉了一块没有整数可行解的部分），使上界 逐步减小，而通过获得更好的整数可行解使下界 z 逐步增大，最终求得最优解 z* 。z例2 求解 A Max z=40 x1+90 x2 9x1+7x256 7x1+20

7、x2 70 x1，x20 x1，x2整数 解 先不考虑整数约束,用求解线性规划B：返回 Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1，x20 得最优解得x1=4.81，x2=1.82,最优值 z0=356. 如果x1，x2是整数,则就是最优解,否则分枝定。如何分枝和定界 （定界） ,由于z0=356是原整数规划去掉整数约束的最大值，因此它就是原整数规划的目标函数值的上界,即 z 356(为什么)；找一个整数规划的可行解x1=0，x2=0,对应的目标函数值 0,则它是整数规划最优值的下界,因此0 z 356. （分枝）选择任一非整数变量(只选一个), x

8、1=4.81,将x14， x1 5分别添加到线性规划B得到两个新的原整数规划B1,B2: 每次对一个线性规划问题进行分枝一次，就定界一次。分枝 B1 Max z=20 x1+10 x2 x2 5x1+4x224 2x1+5x2 13 x1 4 x1，x20 B2 Max z=20 x1+10 x2 5x1+4x224 x1 2x1+5x2 13 x1 5 x1，x20LPB1B4x15B2解得 修改上界和下界,得 0 z max(z1,z2)= max(349,341)=349B1B2Z1=349X1=4X2=2.1Z2=341X1=5X2=1.57X22； X2 3X21； X2 2对B1和

9、B2再分枝定界 B1B3 B4 B2B5 B6B3,B4 B3 Max z=20 x1+10 x2 5x1+4x224 2x1+5x2 13 x1 4, X22； x1，x20 B4 Max z=20 x1+10 x2 5x1+4x224 2x1+5x2 13 x1 4, X2 3 x1，x20最优解X1=4,x2=2：整数可行解Z3=340最优解X1=1.42,x2=3Z4=327定界340 Zmax(z2,z3,z4)=z2=341由于B4的最优解小于目前的整数解340，因此分解已无必要。B5, B6 B5 Max z=20 x1+10 x2 5x1+4x224 2x1+5x2 13 x1

10、 5, X21； x1，x20 B6 Max z=20 x1+10 x2 5x1+4x224 2x1+5x2 13 x1 5, X2 2 x1，x20最优解X1=5.44,x2=1：整数可行解Z5=308无可行解 最终定界340 Zmax(z3,z4, z5)=340,Z=340为最优值，最优解X1=4,x2=2图5-4 B最优解X1=4.81,x2=1.82Z0=356 B1(x14）最优解X1=4,x2=2.1Z1=349 B2（x15）最优解X1=5,x2=1.57Z2=341定界0 Z356定界0 Z349 B3(x22）最优解X1=4,x2=2Z3=340 B4(x23）最优解X1=

11、1.42,x2=3Z4=327定界340 Z341 B5（x21）最优解X1=5,x2=1.57Z2=308 B6（x22）无可行解定界340 Z3403 割平面法割平面法 1、分枝定界法本质上是一种对线性规划可行域的分割方法，只是分割方式比较单一和规范。每次从对应线性规划的最优解出发，选定某个取非整数值的变量，挖掉其中的小数部分，将原可行域一分为二。如此反复进行，直到发现最优整数解为止。 2、割平面法的思路也是采用求解对应线性规划的方法去解整数规划的问题。通过增加适当的约束条件，从原可行域中切割掉不含整数解的部分。但其切割方式灵活多样，每次切割可以切一刀，也可以同时切几刀。旨在造成一个具有整

12、数坐标的顶点，恰好对应着原问题的最优解用割平面法求解纯整数规划问题 max z=3x1-x2 3x1-2x2=10 2x1+x2=0 x1,x2为整数割平面约束：-1/7x3-2/7x5=-6/73-1000CBXBbx1x2x3x4x53-10 x1x2x413/79/731/71000101/7-2/7-3/70012/73/722/700-5/70-3/73-1000CBXBbx1x2x3x4x5x63-100 x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/7000100-5/70-3/70割平面约束：-1/

13、4-1/4x60时时不采用第不采用第j种生产方式，即种生产方式，即xj=0时时于是目标为于是目标为Min Z =(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)上式这个规定可由下述三个线性约束条件表示上式这个规定可由下述三个线性约束条件表示xjyj M j=1,2,3暂不考虑其它条件暂不考虑其它条件 xj yj M，j=1,2,3 其其中中 M 是是个个充充分分大大的的常常数数。说说明明，当当 xj 0 时时yj必必须须为为 1；当当 xj= 0 时时只只有有 yj为为 0 时时才才有有意意义义，所所以以此此 3 式式完完全全可可以以代代替替上上式式。 Y=1,不同于目标

14、函数不同于目标函数例例 6 某服装厂可生产三种服装：西服、衬衫和羽绒服某服装厂可生产三种服装：西服、衬衫和羽绒服。生产不同种类的服装要使用不同种类的设备，该服。生产不同种类的服装要使用不同种类的设备，该服装厂可从专业租赁公司租用这些设备。设备租金和其装厂可从专业租赁公司租用这些设备。设备租金和其它经济参数如下：它经济参数如下：序序号号服装服装种类种类设备租设备租金元金元生产成本生产成本元元/件件销售价格销售价格元元/件件人工工时人工工时小时小时/件件设备工时设备工时小时小时/件件设备可设备可用工时用工时123西服西服衬衫衬衫羽绒羽绒服服50002000300028030200400403005

15、1430.52300300300 假定市场需求不成问题，服装厂每月可用的人假定市场需求不成问题，服装厂每月可用的人工工时为工工时为2000小时，该厂如何安排生产可使每月的小时，该厂如何安排生产可使每月的利润最大？利润最大？解：该问题需要两类决策变量，解：该问题需要两类决策变量，一类决定是否租赁一类决定是否租赁设备的决策变量设备的决策变量yi,另一类是反映个类服装生产数量另一类是反映个类服装生产数量的变量的变量xj。 这两类变量的关系为这两类变量的关系为xi0,yi应等于应等于1；若；若yi=0,xi也必须为也必须为0。不租设备就。不租设备就不能进行生产。不能进行生产。4.背包问题背包问题 一登

16、山队员做登山准备，他需要携带的物品有：食一登山队员做登山准备，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备。每品、氧气、冰镐、绳索、帐篷、照相机和通讯设备。每件物品的重要性系数和重量见下表，假定登山队员可携件物品的重要性系数和重量见下表，假定登山队员可携带的最大重量为带的最大重量为25千克。千克。序号序号 1 2 3 4 5 6 7物品物品食品食品 氧气氧气 冰镐冰镐 绳索绳索 帐篷帐篷 照相机照相机 通讯设备通讯设备重量（千克）重量（千克）重要系数重要系数 5 5 2 6 12 2 4 20 15 18 14 8 4 10 令令xi=1表示登山队员携带物品表示登山队员携

17、带物品i，xi=0表示不携带表示不携带物品物品i。则问题可写为：。则问题可写为：72101254212625510481418152076543217654321, ixxxxxxxxxxxxxxxnaxzi或或背包问题的一般形式：背包问题的一般形式： niiiniiibxatsxcz11.max一维背包问题一维背包问题体积限制：二维背包问题体积限制：二维背包问题 投资选择问题。已知每个项目的投资额和投资投资选择问题。已知每个项目的投资额和投资回报率的期望值，如何在资金有限的情况下选择投回报率的期望值，如何在资金有限的情况下选择投资回报期望值最大的投资方案？资回报期望值最大的投资方案？工件排序

18、问题产品1机床1(a11)机床3(a13)机床4(a14)产品2机床1(a21)机床2(a22)机床4(a24)产品3 机床2(a32)机床3(a33）例 6 1064 3 44225233213221321321321或或x,x,xxxxxxxxxxxxxxMaxz 4.2 0-1整数规划的解法整数规划的解法 隐枚举法隐枚举法通过检查变量取值的部分组合求得最优解的方法。通过检查变量取值的部分组合求得最优解的方法。23=8组变量组变量条条 件件 点点 满满足足条条件件? 是是( ) 否否( ) z值值 (0，0，0) (0，0，1) (0，1，0) (0，1，1) (1，0，0) (1，0，1

19、) (1，1，0) (1，1，1) 0 5 -2 3 3 8 1 6 -1 1 1 0 2 1 5 1 2 6 0 1 1 1 0 1 5 3 8 解解：试试探探x = (1，0，0)为为一一可可行行解解，z =3。得得过过滤滤条条件件 3x1 2x2 +5x3 3 枚枚举举所所有有解解， 按按辞辞典典序序列列表表， 先先检检查查过过滤滤条条件件， 后后检检查查约约束束条条件件是是否否成成立立，得得出出最最优优解解。 最最优优解解 x* = (1，0，1)T，z*= 8 若若计计算算过过程程中中不不断断改改进进过过滤滤条条件件(如如在在检检查查了了(0，0，1)后后将将过过滤滤条条件件改改进进

20、为为 3x1- -2x2 + 5x3 5)，可可减减少少计计算算量量。 条条 件件 点点 (x1,x2,x3) 满满足足条条件件? z值值 (0，0，0) (0，0，1) 0 5 -1 1 0 1 5 条条 件件 点点 (x1,x2,x3) 满满 足足 条条 件件 ? z值值 (0， 1， 0) (0， 1， 1) 3 8 0 2 1 1 8 条条 件件 点点 (x1,x2,x3) 满满 足足 条条 件件 ? z值值 (1， 0， 0) (1， 0， 1) (1， 1， 0) (1， 1， 1) 2 3 1 6 再再将将过过滤滤条条件件改改进进为为 3x1- -2x2 + 5x3 8 为进一步

21、减少运算量，常按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解较早出现。对于最大化问题，可按由小到大的顺序排列；对于最小化问题，则相反。4.2 0-1型整数规划的解法 解0-1型整数规划最容易想到的方法，和整数规划的情形一样，就是穷举法，求出所有的可行解，比较最优目标值以求得最优解，对于有n个变量的0-1规划，可行解可能有2n个，当n较大时，实际上难以做到。因此常设计一些方法，只检查变量取值的一部分，就能求出问题的最优解，这样的方法称为隐枚举法，分枝定界法也是一种隐枚举法，当然，对有些问题隐枚举法并不适用。例6 Max z=3x1-2x2+5x3 3x1-2x2+5x32 （1） x

22、1+4x2+x34 （2）x1+x23 （3） 4x2+x3 6 （4） x1，x2，x30 （5） 解 先观察法找一个可行解，容易看出 （x1，x2，x3）=（1，0，0）是一个可行解， z=3. 为求最优解，对于极大化问题，当然最优解必须满足3x1-2x2+5x3 3，于是3成为最优解的一个“擂台。可列表计算如下：表5-5点约条件是否满足条件过滤条件Z值(1)(2)(3)(4)（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）05-233816-111151011101z=0Z=5z=85 指派问题 在生活中经常遇到这样的问题，

23、某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同（或所费时间），效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最小）。这问题称为指派问题或分派问题（Assignment problem）。 例7 有一份中文说明书，需译成英、日、德、俄四种文字。分别记得E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示，问应指派何人去完成何工作，使所需总时间最少？表5-7 任务 人员EJGR甲乙丙丁2109715414813141611415139 类似有：有n项加工任务，怎样指派到

24、n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题等等。对应每个指派问题，需有类似表5-7那样的数表，称为效率矩阵或系数矩阵，其元素cij（）0（i,j=1,2.,n）表示指派第i人去完成第j项任务时的效率（或时间、成本等）。 解题时需引入变量xij；其取值只能是1或0。并令 1 当指派第i人去完成第j项任务 xij= 0 当不指派第i人去完成第j项任务当问题要求极小化时数学模型是： (5.19) xij=1或0 约束条件说明第j项任务只能由1人去完成；约束条件说明第i人只能完成1项任务。满足约束条件-的可行解xij也可写成表格或矩阵形式，称为解矩阵。iiijijxczMin ii

25、jnjx2 , 1, 1jijnix2 , 1, 1如例7的一个可行解（矩阵）是：1000000101000010)(ijx 显然，这不是最优。解矩阵(xij)中各行各列的元素之和都是1。 指派问题是0-1规划的特例，也是运输问题的特例；即n=m，ai=bj=1.当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法。 指派问题的最优解的性质:若从系数矩阵(cij)的一行（列）各元素中分别减去一个常数 ，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。指派问题求解的思想 利

26、用上面这个性质 可使原系数矩阵变换为非负但含有很多0元素的新系数矩阵，而最优解保持不变。 在系数矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。 若能在系数矩(bij)中找出n个独立的0元素。 则令解矩阵(xij)中对应这n个独立的0元素的元素（位置）取值为1，其它元素取值为0，将其代入目标函数中得到zb=0。 它一定是最小值。这就是以(bij)为系数矩阵的指派问题的最优解。也就是原问题的最优解。匈牙利算法 库恩(W.W.Kuhn)于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格(D.Konig)一个关于矩阵中0元素的定理： 系数矩阵中独立0元素的最多个

27、数等于能覆盖所有0元素的最少直线数。 这解法称为匈牙利算法。以后在方法上虽有不断改进，但仍沿用这名称。以下用例7来说明指派问题的解法。匈牙利算法的步骤 第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。 （1）从系数矩阵的每行元素减去该行的最小元素； （2）再从所得系数矩阵的每列元素中减去该列的最小元素。 若某行（列）已有0元素，那就不必再减例7的计算为 min 4 2 9118713161491514410413152)(ijc24104750111006211130ijb00102350960607130 第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。 经第一步变换后

28、，系数矩阵中每行每列都已有了0元素，但需找出n个独立的0元素。 若能找出，就以这些独立0元素对应解矩(xij)中的元素为1，其余为0，这就得到最优解。 当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找， 第二步 试指派常用的步骤为： （1） 从只有一个0元素的行（列）开始，给这个0元素加圈，记作。 这表示对这行所代表的人，只有一种任务可指派。 然后划去所在列（行）的其它0元素，记作。 这表示这列所代表的任务已指派完，不必再考虑别人了 （2）给只有一个0元素列（行）的0元素加圈，记作；然后划去所在行的0元素，记作 （3）反复进行（1），（2）两步，直到所有0

29、元素都被圈出和划掉为止。 （4）若仍有没有划圈的0元素，且同行（例）的0元素至少有两个（表示对这人可以从两项任务中指派其一）。 这可用不同的方案去试探。 从剩有0元素最少的行（列）开始，比较这行各0 元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少）。然后划掉同行同列的其它0元素。 可反复进行，直到所有0元素都已圈出和划掉为止。 （5）若元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。 若mn，则转入下一步(增加0元素)。 现用的例现用的例7的（的（bij）矩阵，按上述步骤进）矩阵，按上述步骤进行运算，按步骤行运算，按步骤(1)，选给，

30、选给b22加圈，加后加圈，加后给给b31加圈，划掉加圈，划掉b11,b41，按步骤（，按步骤（2），），给给b43，划掉，划掉b44,最后给最后给b14加圈，得到加圈，得到1235966713可见m=n=4，所以得最优解为0100000100101000ijx 这表示：指定甲译出俄文，乙译出日文，丙译出英文，丁译出德文。所需总时间最少 例8 求表5-8所示效率矩阵的指派问题的最小解。 任务人员ABCDE甲乙丙丁茂1287154791714109612677614610969109解题时按上述第一步，将这系数矩阵进行变换。 9107104106614159141217766698979712 经一次运算即得每行每列都有0 元素的系数矩阵， 56360400892751000003220205再按上述步骤运算，得到： 56364892751032225 这里的个数m=4，n5;所以解题没有完成，这时应按以下步骤继续进行。 第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以步骤进行： （1）对没有的行打号； （2）对已打号的行中所有含0 元素的列打号； （3）再对打有号的列中含元素的行打号； （4）重复（2），（3）直到得不出新的打号的行、列为止； （5）对没有打号的行画一横线，有打的列画一纵线，这就得到覆盖所有0元素的最少直