运筹学整数规划

1、第7章 整数规划1 整数规划的基本特点 在前面的线性规划问题中，它的解都假设为可以取连续数值。但是在许多实际问题中，决策变量仅仅取整数值时才有意义，比如变量表示的是工人的人数、机器的台数、货物的箱数、装货的车皮数等等。 为了满足整数解的要求，比较自然的简便方法似乎就是把用线性规划方法所求得的非整数解进行“四舍五入”取整或“舍尾取整”处理。当然这样做有时确实也是有效的，可以取得与整数最优解相近的可行整数解，因此它是实际工作中经常采用的方法。但是实际问题中并不都是如此，有时这样处理得到的解可能不是原问题的可行解，有的虽是原问题的可行解，但却不是整数最优解。（详见后面例1）。因而有必要专门研究只取整

2、数解的线性规划的解法问题。 在线性规划问题中，如果最优解必须是整数，则把这类LP问题称为整数规划（IP）。 在一个LP中要求所有变量取整数值的，称为纯整数（线性）规划；只要求一部分变量值取整数的，称为混合整数（线性）规划。 在整数规划中，如果变量的取值只限于0和1，则称这样的IP为0-1规划。例1 现有甲、乙两种货物拟用集装箱托运，每件货物的体积、重量、可获利润，以及集装箱的托运限制如下表：试确定集装箱中托运甲、乙货物的件数，使托运利润最大。 例2.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制入下表所示。甲种货物至多托运4件，问两种货物各托运多少件，

3、可使获得利润最大。货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140 分析：设x1,x2分别为甲、乙两种货物托运的件数，这是一个纯整数规划问题，其数学模型为为整数21211212121,0,41404041365273195. .32maxxxxxxxxxxtsxxz该问题的图解如下所示，12312340 x2x1 2x1+3x2=62x1+3x2=14.66 2x1+3x2=14(4,2)(2.44,3.26)4x1+40 x2=140 性质: 任何求最大目标函数值的

4、纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值； 任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。2 分枝定界法（ branch & bound method ） 分枝定界法是基于“枚举”思想的一种求解整数规划的常用方法。它先求与该整数规划相对应的线性规划问题。如果其最优解不符合整数规划条件，则求出整数规划的上、下界用增加约束条件的方法，并把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后求得整数规划的最优解。典例：且均取整数值最

5、优解：求下述整数规划问题的, 0,5 . 45 . 01432. .23max21212121xxxxxxtsxxz 第一步：寻找替代问题并求解，替代问题必须是原问题的松弛问题。典例的松弛问题是一个线性规划问题，记作L0:0,5 . 45 . 01432. .23max212121210 xxxxxxtsxxzL ： L0的最优解为（3.25，2.5）,不是原问题的可行解。 第二步：分枝定界。方法是将替代问题分成若干子问题，然后对各子问题求最优解。 如该解满足原问题的约束，即找到了一个原问题的可行解，否则该解为所属分枝的边界值（对求极大化问题该边界值为上界，对求极小化问题，该边界值为下界）；

6、如果所有子问题的最优解均非原问题的可行解，则选取其边界值最大（求极大时）或最小（求极小时）的子问题进一步再细分成子问题求解。 本例中L0的最优解均不是整数，从中任选一个，设选x2进行分枝，分成两个子问题L1和L2：035 . 45 . 01432. .23max:0,25 . 45 . 01432. .23max:1221212122122121211xxxxxxtsxxzLxxxxxxxtsxxzL 求得L1的最优解为（3.5，2），z=14.5。L2的最优解为（2.5，3），z=13.5。均非原问题的最优解，选取边界较大的子问题L1继续分枝。0425 . 45 . 01432. .23ma

7、x:0,325 . 45 . 01432. .23max:21221212112211221212111xxxxxxxtsxxzLxxxxxxxxtsxxzL 求得L11的最优解为（3，2），z=13。L12的最优解为（4，1），z=14。这两个最优解均属原问题的可行解，保留可行解中较大的一个z=14。 第三步：剪枝。将各子问题边界值与保留的可行解的值进行比较，把边界值劣于可行解的分枝剪去。如果除保留下来的可行解外，其余分枝均被剪去，则该可行解就是原问题最优解。否则回到第二步，选取边界值最优的一个继续分枝。如果计算中又出现新的可行解时，则与原可行解比较，保留最优的，并重复上述步骤。此问题中，子

8、问题L12的最优解（4，1），z=14即为本问题的最优解。典例用分枝定界法计算的全过程可表示为：L0:x1=3.25 x2=2.5Z=14.75L12:x1=4 x2=1Z=14L11:x1=3 x2=2Z=13L2:x1=2.5 x2=3Z=13.5L1:x1=3.5 x2=2Z=14.5x22x14x23x133 割平面法 这是求解整数规划问题最早提出的一种方法，1958年由Gomory提出。 他的基本思想是在整数规划问题的松弛问题中依次引进线性约束条件，是可行域逐步缩小。但每次切割只割去问题的部分非整数解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样即可用线性规

9、划问题的方法找出这个最优解。 具体步骤如下： 第一步：把问题中所有约束条件的系数均化为整数，若不考虑变量的整数约束，可写出一般的线性规划问题G0：0,921432. .23max212121210 xxxxxxtsxxzG ：用单纯形法求得上述问题的最终单纯形表如下：迭代迭代次数次数基变基变量量CB x1 x2 x3 x4 b比值比值bi/aij 3 2 0 0 x2x123 0 1 1/2 -1/2 1 0 -1/4 3/4 5/213/4Cj-Zj 0 0 -1/4 -5/4 234234243424341112222111(0)( 1)(2)2221112222,01110222Gomo

10、ry1122xxxxxxxxxxx xxx 第二步：找出非整数解变量中分数部分最大的一个基变量，并写下这一行的约束将上式中所有常数写成整数与一个正分数值之和得分数项移到等式右端，整数项移到等式左端得到右端也必须取整数值，又因，因此有加上松弛变量后得约束345102xxx 第三步：将Gomory约束加到G0中得到新的线性规划问题G1如下：)5 , 1(0212121921432. .23max543421321211jxxxxxxxxxxtsxxzGj： 第四步：重复第一至第三步直到找出最优的整数解为止。求解G1可以采用对偶单纯形法：迭代次数基变量CB x1 x2 x3 x4 x5 b比值bi/

11、aij 3 2 0 0 0 x2x1x5230 0 1 1/2 -1/2 0 1 0 -1/4 3/4 0 0 0 -1/2 -1/2 12（1/2）3（1/4）-1/2Cj-Zj 0 0 -1/4 -5/4 0 x2x1x3230 0 1 0 -1 1/2 1 0 0 1 -1/2 0 0 1 1 -223（1/2）1Cj-Zj 0 0 0 -1 -1/2021210212121213213212132165555415541541xxxGomoryxxxxxxxxxxx加入松弛变量后得约束为：由此得新的移项后得数部分将系数分成整数与非整。先从表中写出非整数解，重复第二步由于表中得出的解仍为

12、将松弛变量加到G1中得到LP问题G2:)6 , 1(02121212121921432. .23max65543421321212jxxxxxxxxxxxxtsxxzGj：采用对偶单纯形法求解:迭代次数基变量CB x1 x2 x3 x4 x5 x6 b 3 2 0 0 0 0 x2x1x3x62300 0 1 0 -1 1/2 0 1 0 0 1 -1/4 0 0 0 1 1 -1 0 0 0 0 0 -1/2 12（1/2）3（1/2）1-1/2Cj-Zj 0 0 -1/4 -5/4 0 x2x1x3x52300 0 1 0 -1 0 2 1 0 0 1 0 -1 0 0 1 1 0 -4

13、0 0 0 0 1 -21431Cj-Zj 0 0 0 -1 0 -1 由于从表中已经找到变量的整数解x1=4,x2=1。求解过程到此结束。练习：4 分配问题及其解法1.问题的提出与数学模型2.匈牙利法3.两点说明1、问题的提出与数学模型 分配问题也称指派问题（assignment problem），是一种特殊的整数规划问题。假定有m项任务分配给n个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率最高。 例例1 有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成，因个人专长不同，他们完成翻译不同文字所需的时间（小时）如下表所示。应如何

14、分配，使这四个人分别完成这四项任务总的时间为最小。人人工作工作甲甲乙乙丙丙丁丁译成英文译成英文译成日文译成日文译成德文译成德文译成俄文译成俄文2151341041415914161378119 设用aij表示分配问题的效率矩阵，令), 1;, 1( 1011. .min1111mjmiorxxxtsxazijmiijmjijmimjijij）（项任务个人去完成第，不分配第项任务个人去完成第，分配第mjmijijixij, 1;, 1012、匈牙利法 可以用解运输问题的表上作业法来解分配问题，但通常用更有效的匈牙利法求解。 基本思想：如果效率矩阵的所有元素大于等于零，则只要令对应于这些零元素位置

15、的xij=1,其余的xij=0，则 就是原问题的最优解。如效率矩阵为：mimjijijxaz110823314309120201402390 如何寻找效率矩阵中这些位于不同行， 不同列的零元素是一个非常重要的问题。匈牙利数学家Konig证明了下面两个基本定理，为解决这个问题奠定了基础。 定理定理1 如果从分配效率矩阵aij的每一行元素中分别减去（或加上）一个常数ui(被称为该行的位势），从每一列分别减去（或加上）一个常数vj（称为该列的位势），得到一个新的效率矩阵bij，若其中bij=aij-ui-vj，则二者的最优解相等。 定理定理2 若矩阵A的元素可分为“0”与非“0”两部分，则覆盖“0”

16、元素的最少直线数等于位于不同行不同列的”0”元素的最大个数。匈牙利法的计算步骤：第一步：每一行均减去该行的最小值，每一列均减去该列的最小值，使每行每列至少有一个零元素（变换效率矩阵）21097087508251541481101041105413141611235023004151390119501145第二步：试求最优解*082511054230001145 第三步：第三步：作覆盖所有零元素的最少直线集合作覆盖所有零元素的最少直线集合1.1.对没有对没有 的行打的行打2.2.对打了对打了的行上的行上0 0元素所在的列打元素所在的列打3.3.对打了对打了的列上的列上 所在的行打所在的行打4.4

17、.对打了对打了的行上的行上0 0元素所在的列打元素所在的列打 直至打不出新的行和新的列直至打不出新的行和新的列 对没有打对没有打的行划横线，对打了的行划横线，对打了的列划的列划竖线，这样就得到能够覆盖所有零元素的最少竖线，这样就得到能够覆盖所有零元素的最少直线组合。直线组合。*0*0第四步:继续变换效率矩阵，试求最优解，回到第二步。从未被直线覆盖的所有元素中找出一个最小元素，然后将效率矩阵未划横线的行均减去这个最小元素，划竖线的列均加上这个最小元素。 最优解为*0603130544300092300100100()00011000ijxmin94 11 428,min24 11 4522228

18、zz 或者2、两点说明 分配问题中如果人数和工作任务数不相等时的处理办法。如人数大于任务数。 如果目标函数为最大化问题。转化为最小化问题，按定理1处理，使效率矩阵各元素大于等于零。 例如，有四项工作分配给六个人去完成，每个人完成各项工作的时间如下表所示。规定每个人完成一项工作，每项工作只交给一个人去完成。应从这六个人中挑选哪四个人去完成，花费的总时间为最少。工作工作人人 123456 3 6 2 6 3 6 2 6 7 1 4 4 7 1 4 4 3 6 5 8 3 6 5 8 6 4 3 7 6 4 3 7 5 2 4 3 5 2 4 3 5 7 6 2 5 7 6 2 增添两项假想的工作，

19、每个人完成这两项工作的时间都为零。工作工作人人 123456 3 6 2 6 3 6 2 6 0 00 0 7 1 4 4 7 1 4 4 0 00 0 3 6 5 8 3 6 5 8 0 00 0 6 4 3 7 6 4 3 7 0 00 0 5 2 4 3 5 2 4 3 0 00 0 5 7 6 2 5 7 6 2 0 00 0 如果目标函数为最大化问题。转化为最小化问题，按定理1处理，使效率矩阵各元素大于等于零。 例如，如果前面翻译的例子中，不是求用时最少而是求翻译的文字最多，则相应的目标函数应该写作：mimjijijxaz11max因为上述目标函数等价于：11min ()mmijij

20、ijzax再根据定理1，使效率矩阵中全部元素变为0，就可以用匈牙利法进行求解。作业1.用匈牙利法解下列系数矩阵的最小化指派问题：791012131216171516141511 121516 2.分配甲、乙、丙、丁四个人去完成5项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。4523364224丁3240282734丙3320263839乙3742312925甲EDCBA任务人5 整数规划的应用举例 例例1 红星日用化工厂为发运产品，下一年度需要6种不同容积的包装箱。每种包装箱的需求量及生产

21、一个的可变费用如下表所示： 由于生产不同容积包装箱时需要进行专门准备、下料等，生产某一容积包装箱的固定费用均为1200元。又若某一容积包装箱数量不够时，可用比它容积大的代替。试问该工厂应定做哪几种代号的包装箱各多少个，使费用最节省？包装箱代号123456容积（m3）0.080.10.120.150.20.25需求量（个）500550700900450400可变费用（元/个）581012.116.318.2 解解：设xj(j=1,.6)为代号j包装箱的定做数量，yj=1,定做第j种包装箱；0，否则。则本例的数学模型为：)6 , 1( 10, 0)6 , 1(3000245017508504003

22、500. .2 .183 .161 .1210851200min65432654365465665432161654321jyxjMyxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxyzjjjjjj或 本题最优决策为：生产包装箱1500个，31250个，4900个，6850个，不生产代号为2、5的包装箱，总计费用为46160元。Lindo求解程序：Min 1200y1+1200y2+1200y3+1200y4+1200y5+1200y6+5x1+8x2+10 x3+12.1x4+16.3x5+18.2x6Stx1+x2+x3+x4+x5+x6=3500 x6=400 x5+x6=8

23、50 x4+x5+x6=1750 x3+x4+x5+x6=2450 x2+x3+x4+x5+x6=3000 x1-100000y1=0 x2-100000y2=0 x3-100000y3=0X4-100000y4=0X5-100000y5=0X6-100000y6=0Endgin x1gin x2gin x3gin x4gin x5gin x6Int y1Int y2Int y3Int y4Int y5Int y6 例例2 春江市计划为新建的5个居民小区中的两个分别各设立一所小学。下表给出了各小区及各小区内及各小区间的平均步行时间及各小区的小学生人数。要求为该市提供决策建议，两所小学应分别建于哪两个居民小区，以及各居民小区学生应分别到那所小学上学，使学生总的上学步行时间最少。小学小学位于位于该区该区小学小学生数生数至其他区步行时间至其他区步行时间 1 2 3 4 512345200180300160350 5 20 15 25 10 20 4 20 15 25 15 20 6 25 15 25 15 25 4 12 10 25 15 12 5 先将表中每行数字分别乘上该行学生数，表中数字表明该居民区小学生到可能设于各区的小学上学的总的步行时间，用kij表示。至至j由由i 1 2 3 4 512345 1000 400