第四章 整数规划与分配问题

运筹学演示课件第四章第四章整数规划与分配问题§1．整数规划的特点及作用§2．分配问题与匈牙利法§3．分枝定界法§4．割平面法§5．应用举例引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413两种货物各托运多少箱使利润最大？MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1(4.8,0)AZ=96(4.8,0)AZ=96MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1x1,x2为整数MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x1,x2为整数x2x1(4.8,0)AZ=96MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1(4.8,0)AZ=96x1,x2为整数(4,0)Z=80(5,0)(4,1)maxZ=90§1整数规划的特点及作用纯整数线性规划—线性规划中要求全部变量取整数值。（混合整数线性规划）求解方法：一般不能用线性规划的非整数解四舍五入（凑整）求得：工作量大或得不到最优解。例1求下述整数规划的最优解：（3.25，2.5）（3.25，2.5）的相邻整数点或不可行或不是最优解。最优解是（4，1）不是可行域顶点。用图解法或单纯形法无法求出。两个变量需讨论四个顶点，十个变量则需讨论顶点个，工作量相当大。可能还得不出最优解。需研究解整数规划的特殊方法。1024210逻辑变量在建立数学模型中的作用1。m个约束条件中只有k个起作用设m个约束条件可表为定义假定第i个约束条件不起作用假定第i个约束条件起作用mibxaijnjij,,11,0,1iy又M为任意大的整数，则表明m个约束条件中有（m-k）个右端项为不起作用。2。约束条件的右端项可能是r个值中的某一个，即定义假定约束右端项为否则上述约束条件可表示为：3。两组条件中满足其中一组定义假定第i组条件不起作用假定第i组条件起作用又M为任意大的整数，则问题可表达为：4。用以表示含固定费用的函数例用代表产品的生产数量，其生产费用函数通常可表示为：式中是同产量无关的生产准备费用。目标函数使所有产品的生产总费用为最小。即设置逻辑变量问题可表示为§2．分配问题与匈牙利法一、问题的提出与数学模型分配问题也称指派问题（assignmentproblem），是一种特殊的整数规划问题。假定有m项任务分配给m个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。在分配问题中，利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表，表格中数字组成效率矩阵。例2.有一份说明书，要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，使这四个人分别完成四项任务总的时间为最小。效率表如下：效率矩阵用[aij]表示，为9131541116141381441579102][ija定义逻辑变量）；（项任务个人去完成第，不分配第项任务个人去完成第，分配第mjmijijixij,,1,,101则分配问题的数学模型写为：),,1;,,1(10),,1(1),,1(1min1111mjmixmjxmixxazijmiijmjijmimjijij或二、匈牙利法用表上作业法来求解分配问题时，单位运价表即效率表，产销平衡表中产量和销量都设为1即可。匈牙利数学家克尼格（Konig）求解分配问题的计算方法被称为匈牙利法，他证明了如下两个定理：定理1如果从分配问题效率矩阵[aij]的每一行元素中分别减去（或加上）一个常数ui(被称为该行的位势)，从每一列分别减去（或加上）一个常数vj（被称为该列的位势），得到一个新的效率矩阵[bij]，若其中bij=aij-ui-vj，则[bij]的最优解等价于[aij]的最优解。定理2若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数。结合例2说明匈牙利法的计算步骤第一步：找出效率矩阵每行的最小元素，并分别从每行中减去。5911005324100115780411429131541116141381441579102min第二步：找出矩阵每列的最小元素，分别从各列中减去。0500min5411000324501152805911005324100115780第三步：经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。下面确定能否找出m个位于不同行不同列的零元素的集合（该例中m=4），也就是看要覆盖上面矩阵中的所有零元素，至少需要多少条直线。1.从第一行开始，若该行只有一个零元素，就对这个零元素打上（），对打括号的零元素所在的列画一条线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。2.从第一列开始，若该列只有一个零元素，就对这个零元素打上（）（同样不考虑已划去的零元素），再对打括号的零元素所在行画一条直线。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。3.重复上述步骤1、2，可能出现三种情况：①效率矩阵每行都有打括号的零元素，只要对应这些元素令xij=1就找到了最优解。②打括号的零元素个数少于m，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素打一个括号，然后对所有打括号的零元素所在行（或列）画一条直线，同样得到最优解。③矩阵中所有零元素或被划去，或打上括号，但打括号的零元素少于m，这时转入第四步。第四步：按定理1进行如下变换1.从矩阵未被直线覆盖的数字中找出一个最小的k；2.对矩阵中的每行，当该行有直线覆盖时，令ui=0，无直线覆盖的，令ui=k；3.对矩阵中有直线覆盖的列，令vj=-k，对无直线覆盖的列，令vj=0；4.从原矩阵的每个元素aij中分别减去ui和vj。第五步：回到第三步，反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方案。由于调整后的矩阵中新出现了一个零，因此对打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号元素所对应的决策变量取值为1，就得到最优解。该问题中，最优值为：4+4+9+11=28h习题4.3三、两点说明1.分配问题中人数和工作任务不相等时当人数多于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方法类似。2.当问题目标变为求极大时mimjijijxaz11max可改写为mimjijijxaz11)(min此时效率矩阵中元素都变为了负值，可利用定理1，使效率矩阵中全部元素都变为非负的，就可以利用匈牙利法进行求解。作业4.44.5§3．分枝定界法记待解的整数规划问题为A，相应的线性规划问题(去掉了整数约束，即松弛问题)为B，整数规划的最优解为z*。分枝定界法的基本思想：（1）先不考虑整数条件，即先求解相应线性规划B的最优解。若得到的是整数解，则问题得到解决;否则，这个非整数解必是原整数规划问题A的最优解z*的上界，记为；而A的任一整数解，可以看作的一个下界，记为。zz（2）从得到的B的最优解中，任选一个非整数的变量xk，在B中增加约束条件xk≤[xk]构成一个新的线性规划问题B1，它实际上是B的一个分枝；在B中增加另一约束条件xk≤[xk]+1，又得到一个B的分支，记为B2；分别求出B1和B2的最优解，判断这两个解是否是最优解，若是，问题得到解决；若不是，调整和，将它们再分枝，直到求出最优整数解为止。zz分枝定界法实质是将B的可行域分成若干子区域(称为分枝)，逐渐减小和增大，最终求出z*。zz例.用分枝定界法求解整数规划问题：取整数0,5.45.0143223max:21212121xxxxxxxxzA解：（1）求解对应的松弛问题B0,5.45.0143223max:21212121xxxxxxxxzB其最优解为：5.2,25.321xx最优值为：75.14z目前最优值为z=14.75，令=14.75；z现在还没有任何整数解，可以令（0，0）作为初始整数解，因此有=0。z（2）定界（3）分枝将线性规划问题B分为两枝。在B的最优解中，任选一个非整数变量，如x2=2.5；因x2的最优整数解只可能是x2≤2或x2≥3，故在B中分别增加约束条件：B加上约束条件x2≤2，记为B1；B加上约束条件x2≥3，记为B2。这样，将分解成两个子问题B1和B2（即两枝）。0,25.45.0143223max:2122121211xxxxxxxxxzB0,35.45.0143223max:2122121212xxxxxxxxxzB这样松弛问题B变为了求解下述两个问题：B分解为B1和B2：B1的最优解为：x1=3.5,x2=2,z=14.5B2的最优解为：x1=2.5,x2=3,z=13.5定界：这时两个问题的最优值中较大的一个是14.5，比原来的上界要小，因此修改上界，令。5.14z又由于目前没有出现更好的整数界，所以下界仍然是0。分枝：选取最优值教大的子问题优先进行分枝，将B1分解为B11和B12两个子问题。0,325.45.0143223max:211221212111xxxxxxxxxxzB0,425.45.0143223max:211221212112xxxxxxxxxxzBB11和B12两个子问题的可行域为：继续分枝定界，求解得最优解（4,1），最优解为14。§4．割平面法一、基本思想找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。二、割平面求解举例MaxZ=x1+x2-x1+x2≤13x1+x2≤4x1,x2≥0且为整数松弛问题MaxZ=x1+x2-x1+x2≤13x1+x2≤4x1,x2≥0-x1+x2+x3=13x1+x2+x4=4x1,x2≥0不考虑整数解约束，解松弛问题的最优单纯形表为：CBXBb1100x1x2x3x40x31-11100x443101σ1100…………………1x13/410-1/41/41x27/4013/41/4Z=5/2σ00-1/2-1/2找中真分数部分大的所对应的约束条件：b约束此约束条件即为要找得－即－移项得：变形为：Gomoryxxxxxxxxxxx,33,0414343,434143,43414143434331431将-3x3-x4+x5=-3（切割方程）代入最优表CBXBb11000x1x2x3x4x51x13/410-1/41/401x27/4013/41/400x5-300-3-11Z=5/2σ00-1/2-1/201x111001/31/121x2101001/40x310011-1/3Z=2σ000-1/3-1/3MaxZ=3x1