运筹学-第四章 整数规划与分配问题

4、整数规划与分配问题4.1整数规划的特点及作用在线性规划问题中,它的解都假设为具有连续型数值.但是在许多实际问题中,决策变量仅仅在取整数值时才有意义,比如变量表示的是工人的数量,机器的台数,货物的箱数等。实际问题中经过“四舍五入”处理得到的解可能不是原问题的可行解,有的虽是原问题的可行解,但却不是整数最优解.因而有必要研究整数规划问题的解法.例1某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：问两种货物各装运多少箱，可使获得利润最大？货物集装箱体积()重量(百斤)利润(百元)甲5220乙4510托运限制24133米设甲、乙两种货物装运箱数分别为x1和x2。显然，都要求为整数,于是可建立整数规划模型如下：1212121212max201054242513,0,zxxxxxxstxxxx为整数整数规划的一般模型此模型与一般线性规划的模型很相似，区别在于除变量的非负条件外，还加了整数解的要求。如何求解整数规划问题？例2：求下列问题：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整数值O1234567891054321x1x2I(2,4)B(9.2,2.4)AD可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4)Z0=58.8，而原整数规划最优解I(2,4)Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。•因此用图解法或单纯形法都无法找出整数规划的最优解，这就要研究整数规划问题的特殊方法。4.2分配问题与匈牙利法4.2.1问题的提出与数学模型在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每个人的专长不同，各人完成任务不同（或所费时间），效率不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最小）。这类问题称为指派问题或分派问题（Assignmentproblem）。例3有一份中文说明书，需翻译成英、日、德、俄四种文字，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？•效率矩阵甲乙丙丁译成英文译成日文译成德文译成俄文2109715414813141611415139引入0-1变量xij=1分配第i人去完成第j项任务，xij=0不分配第i人去完成第j项任务。xij=1(j=1,2……n)表示第j项任务只能由一人去完成。xij=1(i=1,2……n)第i人只能完成一项任务。分配问题的数学模型：MinZ=cijxijxij=1(j=1,2……n)xij=1(i=1,2……n)xij=0或1(i=1,2…..m;j=1,2……n)满足约束条件的解称为可行解可写成矩阵形式：X=0100001010000001称为解矩阵其各行各列元素之和为1。4.2.2匈牙利法匈牙利算法基本思想：对同一工作i来说，所有人的效率都提高或降低同一常数，不会影响最优分配；同样，对同一人j来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。分配问题性质：分配问题的最优解有这样的性质，若从系数矩阵C的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩阵B，那么B为系数矩阵求得的最优解和用原来的系数矩阵C求得的最优解相同。匈牙利算法：若系数矩阵中的元素可分为”0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数。甲乙丙丁译成英文译成日文译成德文译成俄文2109715414813141611415139匈牙利算法的步骤：第一步：使分配问题的系数矩阵经变换，在各行各列中都出现0元素：从系数矩阵的每行元素减去该行的最小元素。再从所得系数矩阵的每列元素减去该列的最小元素。若某行已经有0元素，就不必再减了。(cij)=24114087511010423500119552109715414813141611415139082511054230001145第二步：进行试分配，以寻找最优解。从只有一个0元素的行（或列）开始，给这个0元素加圈，记，然后划去所在的列（或行）的其他0元素，记作Ø。给只有一个0元素的列（或行）的0元素加圈，记，然后划去所在的行（或列）的其他0元素，记作Ø。反复进行上述两步，直到所有的0元素都被圈出和划掉为止。若还有没有划圈的0元素，且同行（或列）的0元素至少有二个，从剩有0元素最少的行（或列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的0元素加圈，然后划掉同行同列的其他0元素，可反复进行，直到所有的0元素都被圈出和划掉为止。若元素的数目m等于矩阵阶数n，那么这分配问题的最优解已得到。若mn，则转下一步。825115423ØØ1145第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素数。对没有的行，打；对已打行中所有含0元素的列打；再对打列中含元素的行打；重复上述两步，直到得不出新的打行列为止。对没有打行画横线，有打列画纵线，就得到覆盖所有0元素的最少直线数。825115423ØØ1145√√√第四步：在没有被直线覆盖的部分中找出最小元素，然后在打行各元素都减去这最小元素，而在打列中各元素都加上这最小元素，以保证原来0元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）。若得到n个独立的0元素，则已经得到最优解。否则回到第三步重复进行。06031305443000923Ø63135443Ø923Z=9+4+11+4=28例4:4个工人分派做4项工作，规定每人只能做1项工作，每项工作只能1个人做。现设每个工人做每项工作所消耗的时间如表所示，求总耗时最少的分派方案。工作工作时间/h工人123411518212421923221832617161941921231715182124192322182617161919212317036915401010324600269144010003236026914410Ø3236Ø26914410Ø3236Ø√√√0261003301000412502610033Ø10Ø41252610Ø33Ø10Ø4125√√√√√004100110120061030Ø410Ø1112Ø613Ø例3：求如下整数规划的最优解：Maxz=3x1+2x2s.t.2x1+3x2≤14x1+0.5x2≤4.5x1,x2≥0，且均取整数值4.3分支定界法•基本思路：用替代问题代替原问题，通过不断的分枝与定界、剪枝来求最优解。第一步：寻求替代问题并求解。方法：放宽或取消原问题的某些约束。替代问题的要求：容易求解，且原问题的解应无例外地包含在替代问题的解集中。Maxz=3x1+2x2s.t.2x1+3x2≤14x1+0.5x2≤4.5x1,x2≥01234567912345678（3.25,2.5）第二步：分枝与定界从不满足整数条件的基变量中任选一个x1进行分枝，它必须满足x1[x1]或xl1[x1]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。定界：把满足条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。•选取x2进行分枝，分成如下两个字问题：L1：Maxz=3x1+2x2L2：Maxz=3x1+2x2s.t.2x1+3x2≤14s.t.2x1+3x2≤14x1+0.5x2≤4.5x1+0.5x2≤4.5x2≤2x2≥3x1,x2≥0x1≥01234567912345678（3.25,2.5）x1x2L1L2L1的最优解为（3.5,2），z=14.5L2的最优解为（2.5,3），z=13.5•第三步：剪枝把那些子问题的最优值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。•分支L2被减去，分枝L1继续分枝如下：L11:Maxz=3x1+2x2L12:Maxz=3x1+2x2s.t.2x1+3x2≤14s.t.2x1+3x2≤14x1+0.5x2≤4.5x1+0.5x2≤4.5x2≤2x2≤2x1≤3x1≥4x1,x2≥0x2≥01234567912345678（3.25,2.5）x1x2L11L2L11的最优解为（3,2），z=13L12的最优解为（4,1），z=14L12故原问题的最优解为（4，1），z=14X1+0.5x2≤4.52x1+3x2≤14L0X1=3.25X2=2.5Z=14.75L1X1=3.5X2=2Z=14.5L2X1=2.5X2=3Z=13.5X2≤2X2≥3L11X1=3X2=2Z=13L12X1=4X2=1Z=14分枝定界整个过程x1≤3x1≥4一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若原问题无可行解，则原整数规划问题也无可行解，计算结束。例4用分枝定界法求解：MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20且为整数012344321x1x2用图解法求出的替代问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。分枝：X11,x12P1P2两个子问题：（L1）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x11x1,x20用图解法可解得相应的（L1）的最优解（1，9/4）Z=10(3/4)（L2）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x12x1,x20用单纯形法可解得相应的（l2）的最优解（2，1/2）Z=9(1/2)012344321x1x2再对（L1）分枝：X11（L11）x22（L12）x23P1P2P3P4（L1）两个子问题：（L11）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x11x22x1,x20且为整数用单纯形法可解得相应的（L11）的最优解（1，2）Z=10（L1）两个子问题：（L12）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x11x23x1,x20且为整数用图解法可解得相应的（L12）的最优解（0，3）Z=9L0X1=1.2X2=2.1Z=11.1L1X1=1X2=2.25Z=10.75L2X1=2X2=0.5Z=9.5X1≤1X1≥2L11X1=1X2=2Z=10L12X1=0X2=3Z=9原问题的最优解（1，2）Z=10x2≤2x1≥34.4割平面法割平面法是通过生成一系列的平面割掉非整数部分来得到最优整数解的方法。我们介绍Gomory割平面法（纯整数规划割平面法）例4：用割平面法求整数规划的最优解：Maxz=3x1+2x2s.t.2x1+3x2≤14x1+0.5x2≤4.5x1,x2≥0，且均取整数值第一步：把问题中所有约束条件的系数均化为整数，可得该整数规划的标准型如下：Maxz=3x1+2x2s.t.2x1+3x2+x3≤142x1+x2+x4≤9xj≥0且为整数Cj3200CB基bX1x2x3x40x3140x492310[2]101Cj-Zj32000x353x19/20[2]1-11½01/2Cj-Zj0½0-3/22x25/23x113/401½-1/210-1/43/4Cj-Zj00-1/4-5/4第二步：找出非整数解变量中分数部分最大的一个基变量，并写出他的约束。212x21x21x432)212(x)211(x)210(x4324342x21x21212xx左端为整数，右端也必须为整数∵x3,x4≥0121x21x2121430x21x212143∴Maxz=3x1+2x2s.t.2x1+3x2+x3=142x1+x2+x4=9xj≥