运筹学基础及应用第五版-胡运权第四章课件.ppt

1、第四章第四章 整数规划与分配问整数规划与分配问题题1 1整数规划的特点及作用整数规划的特点及作用 2 2分配问题与匈牙利法分配问题与匈牙利法 3 3分枝定界法分枝定界法 4 4割平面割平面法法 5 5解解0-10-1规划问题的隐枚举法规划问题的隐枚举法1 1整数规划的特点及应用整数规划的特点及应用 在实际问题中，全部或部分变量的取值必须是整在实际问题中，全部或部分变量的取值必须是整数。比如人或机器是不可分割的，选择建厂地点可以设置数。比如人或机器是不可分割的，选择建厂地点可以设置逻辑变量等。逻辑变量等。 在一个线性规划问题中要求全部变量取整数值的，在一个线性规划问题中要求全部变量取整数值的，称

2、纯整数线性规划或简称称纯整数线性规划或简称纯整数规划纯整数规划；只要求一部分变；只要求一部分变量取整数值的，称为量取整数值的，称为混合整数规划混合整数规划。 对整数规划问题求解，有人认为可以不考虑对变对整数规划问题求解，有人认为可以不考虑对变量的整数约束，作为一般线性规划问题求解，当解为非整量的整数约束，作为一般线性规划问题求解，当解为非整数时，用四舍五入或凑整方法寻找最优解，我们从下面的数时，用四舍五入或凑整方法寻找最优解，我们从下面的例子说明这样的方法是不合适的。例子说明这样的方法是不合适的。 例例1. 求下述整数规划问题的最优解求下述整数规划问题的最优解且均取整数值 , 0,5 . 45

3、 . 0 143 223max21212121xxxxxxxxz 解解：如果不考虑整数约束（称为整数规划问题的：如果不考虑整数约束（称为整数规划问题的松弛松弛问题问题）用图解法得最优解为（）用图解法得最优解为（3.25 , 2.5） 考虑到整数约束，用凑整法考虑到整数约束，用凑整法求解时，比较四个点（求解时，比较四个点（4 , 34 , 3）, ,（4 , 4 , 2 2）, ,（3 , 33 , 3）（）（3 , 23 , 2），前三个都），前三个都不是可行解，第四个虽然是可行解，不是可行解，第四个虽然是可行解，但但 z=13 z=13 不是最优。实际问题的最优不是最优。实际问题的最优解为（

4、解为（4 , 14 , 1）这时）这时 z z* *= 14= 14。逻辑逻辑（0-10-1）变量在建立数学模型中的作用变量在建立数学模型中的作用1. 1. m m 个约束条件中只有个约束条件中只有 k k 个起作用个起作用设设 m 个约束条件可以表示为：个约束条件可以表示为：), 1( 1mibxainjjij定义逻辑变量定义逻辑变量个约束条件起作用，假定第个约束条件不起作用，假定第 0 1iiyi又设又设 M M 为任意大的正数，则约束条件可以改写为：为任意大的正数，则约束条件可以改写为：kmyyyMybxamiinjjij211定义逻辑变量：定义逻辑变量：，其它，假定约束右端项为01ii

5、by此时约束条件可以改写为：此时约束条件可以改写为：12111rriiinjjijyyyybxa 2. 约束条件的右端项可能是约束条件的右端项可能是 r 个值中的某一个个值中的某一个rnjjijbbbxa或或或211即即 3. 3. 两组条件满足其中一组两组条件满足其中一组 若若 x x1 144，则，则 x x2 211（第一组条件第一组条件）；否则当）；否则当 x x1 1 4 4 时，时，x x2 233（第二组条件第二组条件）. . 定义逻辑变量：定义逻辑变量：）（组条件起作用，第组条件不起作用，第2 , 1 0 1iiiyi又设又设 M 为任意大正数，则问题可表达为：为任意大正数，则

6、问题可表达为：112112221241431xy Mxy Mxy Mxy Myy 需注意，当约束需注意，当约束为大于时，右端为大于时，右端项中用减号。项中用减号。 4. 4. 用以表示含固定费用的函数用以表示含固定费用的函数 用用 x xj j 代表产品代表产品 j j 的生产数量，其生产费用函的生产数量，其生产费用函数表示为数表示为)0( 0)0( )(jjjjjjjxxxcKxC其中其中 K Kj j 是同产量无关的生产准备费用，问题的目标是是同产量无关的生产准备费用，问题的目标是使所有产品的总生产费用为最小，即使所有产品的总生产费用为最小，即1min()njjjzCx定义逻辑变量（表示是

7、否生产产品定义逻辑变量（表示是否生产产品 j ）0001jjjxxy，又设又设 M 为任意大正数，为了表示上述定义，引入约束：为任意大正数，为了表示上述定义，引入约束：jjMyx 显然，当显然，当 x xj j 0 0 时，时，y yj j= =1 1。将目标函数与约束条件合起来考虑有：将目标函数与约束条件合起来考虑有：1 00min1或jjjnjjjjjyMyxyKxcz由此看出，当由此看出，当 x xj j = = 0 0 时，为使时，为使 z z 极小化，应有极小化，应有 y yj j = 0= 02 2分配问题与匈牙利法分配问题与匈牙利法 一、问题的提出与数学模型 分配问题分配问题也称

8、也称指派问题指派问题（assignment assignment problemproblem），是一种特殊的整数规划问题。假定有），是一种特殊的整数规划问题。假定有 m m 项任项任务分配给务分配给 m m 个人去完成，并指定每人完成其中一项，每个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最项只交给其中一个人去完成，应如何分配使总的效率为最高。高。 如果完成任务的效率表现为资源消耗，考虑的是如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率表现如何分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则

9、考虑的是如何分配使得目标函数极为生产效率的高低，则考虑的是如何分配使得目标函数极大化。大化。 在分配问题中，利用不同资源完成不同计划活动在分配问题中，利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表，表格中数字组成的效率通常用表格形式表示为效率表，表格中数字组成效率矩阵效率矩阵。 例例2 2. . 有一份说明书，要分别翻译成英、日、德、有一份说明书，要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，使这四个人分别完成四项任务总的时间为最小。长不同，使这四个人分别完成四项任务总的时间为最小。效率表如下：

10、效率表如下：效率矩阵用效率矩阵用aij 表示，为表示，为9131541116141381441579102ija定义逻辑变量定义逻辑变量 ）；（项任务个人去完成第，不分配第项任务个人去完成第，分配第mjmijijixij, 1, 1 0 1则分配问题的数学模型写为：则分配问题的数学模型写为：), 1;, 1( 1 0), 1( 1), 1( 1min1111mjmixmjxmixxazijmiijmjijmimjijij或二、匈牙利法 用表上作业法来求解分配问题时，单位运价表即用表上作业法来求解分配问题时，单位运价表即效率表，产销平衡表中产量和销量都设为效率表，产销平衡表中产量和销量都设为 1

11、 1 即可。即可。 匈牙利数学家克尼格（匈牙利数学家克尼格（ Konig Konig ）求解分配问题）求解分配问题的计算方法被成为的计算方法被成为匈牙利法匈牙利法，他证明了如下两个定理：，他证明了如下两个定理： 定理定理1 1 如果从分配问题效率矩阵如果从分配问题效率矩阵 a aijij 的每一的每一行元素中分别减去（或加上）一个常数行元素中分别减去（或加上）一个常数 u ui i ( (被称为该行被称为该行的位势的位势) )，从每一列分别减去（或加上）一个常数，从每一列分别减去（或加上）一个常数 v vj j（被（被称为该列的位势），得到一个新的效率矩阵称为该列的位势），得到一个新的效率矩阵

12、 b bijij ，若其，若其中中 b bij ij = = a aijij- -u ui i- -v vj j，则，则 b bijij 的最优解等价于的最优解等价于 a aijij 的的最优解。最优解。 定理定理2 2 若矩阵若矩阵 A A 的元素可分成的元素可分成“ “ 0 ”0 ”与非与非“ “ 0 ”0 ”两部分，则覆盖两部分，则覆盖“ “ 0 ”0 ”元素的最少直线数等于位元素的最少直线数等于位于不同行不同列的于不同行不同列的“ “ 0 ”0 ”元素的最大个数。元素的最大个数。 结合例结合例2 2 说明说明匈牙利法的计算步骤匈牙利法的计算步骤 第一步：找出效率矩阵每行的最小元素，并第

13、一步：找出效率矩阵每行的最小元素，并分别从每行中减去。分别从每行中减去。5911005324100115780411429131541116141381441579102min 第二步：找出矩阵每列的最小元素，分别从各列第二步：找出矩阵每列的最小元素，分别从各列中减去。中减去。0 5 0 0 min5411000324501152805911005324100115780 第三步：经过上述两步变换后，矩阵的每行每列第三步：经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。下面确定能否找出至少都有了一个零元素。下面确定能否找出 m m 个位于不个位于不同行不同列的零元素的集合（该例中同行不

14、同列的零元素的集合（该例中 m m=4=4），也就是看要），也就是看要覆盖上面矩阵中的所有零元素，至少需要多少条直线。覆盖上面矩阵中的所有零元素，至少需要多少条直线。 1. 1. 从第一行开始，若该行只有一个零元素，就从第一行开始，若该行只有一个零元素，就对这个零元素打上（对这个零元素打上（ ），对打括号的零元素所在的列画），对打括号的零元素所在的列画一条线，若该行没有零元素或者有两个以上零元素（已划一条线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。去的不算在内），则转下一行，依次进行到最后一行。 2. 2. 从第一列开始，若该列只有一个零元素，

15、就从第一列开始，若该列只有一个零元素，就对这个零元素打上（对这个零元素打上（ ）（同样不考虑已划去的零元素），）（同样不考虑已划去的零元素），再对打括号的零元素所在行画一条直线。若该列没有零元再对打括号的零元素所在行画一条直线。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一素或有两个以上零元素，则转下一列，依次进行到最后一列为止。列为止。 3. 3. 重复上述步骤重复上述步骤 1 1、2 2，可能出现三种情况：，可能出现三种情况： 效率矩阵每行都有打括号的零元素，只要对应效率矩阵每行都有打括号的零元素，只要对应这些元素令这些元素令 x xijij= 1 = 1 就找到了最优解

16、。就找到了最优解。 打括号的零元素个数少于打括号的零元素个数少于 m m ，但未被划去的，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素打一个括号，然后对所有打括号的零元素所间隔的零元素打一个括号，然后对所有打括号的零元素所在行（或列）画一条直线，同样得到最优解。在行（或列）画一条直线，同样得到最优解。 矩阵中所有零元素或被划去，或打上括号，但矩阵中所有零元素或被划去，或打上括号，但打括号的零元素少于打括号的零元素少于 m m ，这时转入第四步。，这时转入第四步。 第四步：按定理第四步：按定理 1 1 进行如下变换进

17、行如下变换 1. 1. 从矩阵未被直线覆盖的数字中找出一个最小从矩阵未被直线覆盖的数字中找出一个最小的的 k k ； 2. 2. 对矩阵中的每行，当该行有直线覆盖时，令对矩阵中的每行，当该行有直线覆盖时，令 u ui i= 0= 0，无直线覆盖的，令，无直线覆盖的，令 u ui i= = k k ； 3. 3. 对矩阵中有直线覆盖的列，令对矩阵中有直线覆盖的列，令 v vj j= -= -k k，对，对无直线覆盖的列，令无直线覆盖的列，令 v vj j= 0 = 0 ； 4. 4. 从原矩阵的每个元素从原矩阵的每个元素 a aijij中分别减去中分别减去 u ui i 和和 v vj j 。

18、第五步：回到第三步，反复进行，直到矩阵的每第五步：回到第三步，反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方案。一行都有一个打括号的零元素为止，即找到最优分配方案。 由于调整后的矩阵中新出现了一个零，因此对打由于调整后的矩阵中新出现了一个零，因此对打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号元素所对应的决策变量取值为括号元素所对应的决策变量取值为1 1，就得到最优解。，就得到最优解。 该问题中，最优值为：该问题中，最优值为：4+4+9+11=28h4+4+9+11=28h可编辑 三、两点说明 1. 1. 分配

19、问题中人数和工作任务不相等时分配问题中人数和工作任务不相等时 当人数多于工作任务数时，可以添加假想任务使当人数多于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，因此得人数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，可添加完成这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方法类似。假想的人。这样的方法和运输问题中处理的方法类似。 2. 2. 当问题目标变为求极大时当问题目标变为求极大时mimjijijxaz11max可改写为可改写为mimjijijxaz11)(min 此时效率矩阵中

20、元素都变为了负值，可利用定理此时效率矩阵中元素都变为了负值，可利用定理1 1，使效率矩阵中全部元素都变为非负的，就可以利用匈，使效率矩阵中全部元素都变为非负的，就可以利用匈牙利法进行求解。牙利法进行求解。3 3分枝定界法分枝定界法 记待解的整数规划问题为记待解的整数规划问题为 L L ，相应的线性规划，相应的线性规划问题问题( (去掉了整数约束，即松弛问题去掉了整数约束，即松弛问题) )为为 L L0 0 ，整数规划的，整数规划的最优值为最优值为 z z* *。 分枝定界法的基本思想：分枝定界法的基本思想： （1）先不考虑整数条件，即先求解相应线性规划）先不考虑整数条件，即先求解相应线性规划

21、L0的最优解。若得到的是整数解，则问题得到解决的最优解。若得到的是整数解，则问题得到解决;否则，否则，这个非整数解必是原整数规划问题这个非整数解必是原整数规划问题 L 的最优解的最优解 z* 的上界，的上界，记为记为 ；而；而 L的任一整数解，可以看作一个下界，记的任一整数解，可以看作一个下界，记为为 。 zz （2）从得到的）从得到的 L0的最优解中，任选一个非整数的变的最优解中，任选一个非整数的变量量 xk ，在，在 L0中增加约束条件中增加约束条件 xk xk 构成一个新的线性构成一个新的线性规划问题规划问题 L1，它实际上是，它实际上是 L0 的一个分枝；在的一个分枝；在 L0中增加另

22、中增加另一约束条件一约束条件 xk xk +1，又得到一个，又得到一个 L0 的分支，记为的分支，记为 L2；分别求出分别求出 L1 和和 L2的最优解，判断这两个解是否是最优解，的最优解，判断这两个解是否是最优解，若是，问题得到解决；若不是，调整若是，问题得到解决；若不是，调整 和和 ，将它们再分，将它们再分枝，直到求出最优整数解为止。枝，直到求出最优整数解为止。 zz 分枝定界法实质是将分枝定界法实质是将 L0 的可行域分成若干子区域的可行域分成若干子区域(称称为分枝为分枝)，逐渐减小，逐渐减小 和增大和增大 ，最终求出，最终求出 z*。 zz 例例. . 用分枝定界法求解整数规划问题：用

23、分枝定界法求解整数规划问题：12121212 max322314 0.54.5,0 Lzxxxxxxx x取整数 解解：（1 1）求解对应的松弛问题）求解对应的松弛问题 L L0 0012121212: max322314 0.54.5,0 Lzxxxxxxx x其最优解为：其最优解为：5 . 2 , 25. 321xx最优值为：最优值为：75.14z 目前最优值为目前最优值为 z=14.75 ，令，令 =14.75；z 现在还没有任何整数解，可以令（现在还没有任何整数解，可以令（0，0）作为初始整）作为初始整数解，因此有数解，因此有 =0 。z （2）定界）定界 （3）分枝）分枝 将线性规划

24、问题将线性规划问题 L0分为两枝。分为两枝。 在在 L0的最优解中，任选一个非整数变量，如的最优解中，任选一个非整数变量，如 x2=2.5 ；因因 x2 的最优整数解只可能是的最优整数解只可能是 x22 或或 x23 ，故在，故在 L0中分中分别增加约束条件：别增加约束条件： L0加上约束条件加上约束条件 x22 ，记为，记为 L1； L0加加上约束条件上约束条件 x23 ，记为，记为 L2 。这样，将分解成两个子问题。这样，将分解成两个子问题 L1 和和 L2（即两枝）。（即两枝）。1121212212: max3223140.54.5 2,0 Lzxxxxxxxx x2121212212:

25、 max3223140.54.5 3,0 Lzxxxxxxxx x 这样松弛问题这样松弛问题 L L0 0 变为了求解下述两个问变为了求解下述两个问题：题： L0 分解为分解为 L1 和和L2 ：L1 的最优解为：的最优解为：x1=3.5 , x2=2 , z=14.5L2 的最优解为：的最优解为：x1=2.5 , x2=3 , z=13.5 定界：定界：这时两个问题的最优值中较大的一个是这时两个问题的最优值中较大的一个是 14.5 14.5 ，比原来的上界要小，因此修改上界，比原来的上界要小，因此修改上界，令令 。 5 .14z又由于目前没有出现更好的整数界，所以下界仍然是又由于目前没有出现

26、更好的整数界，所以下界仍然是 0 0 。 分枝：分枝：选取最优值较大的子问题优先进行分枝，选取最优值较大的子问题优先进行分枝，将将L L1 1 分解为分解为 L L1111和和 L L1212 两个子问题。两个子问题。111212122112: max3223140.54.5 23,0 Lzxxxxxxxxx x121212122112: max3223140.54.5 24,0 Lzxxxxxxxxx x L L1111和和 L L1212 两个子问题的可行域为：两个子问题的可行域为： 继续分枝定界，最后剪枝求解得最优解（继续分枝定界，最后剪枝求解得最优解（4 , 4 , 1 1），最优解为

27、），最优解为1414。( (见见P93P93，图，图4.5)4.5)4 4割平面法割平面法 割平面法是求解整数规划问题最早提出割平面法是求解整数规划问题最早提出的一种方法，的一种方法，19581958年由高莫雷（年由高莫雷（GomoryGomory）提出。）提出。 基本思路是不断引进适当的线性约束条基本思路是不断引进适当的线性约束条件，使得可行域逐步缩小，但每次切割只是割去件，使得可行域逐步缩小，但每次切割只是割去问题的部分非整数解，直到使问题的目标值达到问题的部分非整数解，直到使问题的目标值达到最优的整数点成为缩小后可行域的一个顶点，这最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解

28、线性规划的方法找出这个最优解。样就可以用求解线性规划的方法找出这个最优解。 例例. . 用割平面法求解整数规划问题：用割平面法求解整数规划问题：12121212max322314 0.54.5,0 zxxxxxxx x取整数解解：（1 1）约束条件系数化整，忽略整数约束，）约束条件系数化整，忽略整数约束，用单纯形法求解对应的松弛问题用单纯形法求解对应的松弛问题012121212: max322314 29,0 Gzxxxxxxx xCj x1x2x3x4XBbCB0 1 1/2 -1/2 1 0 -1/4 3/43 2 0 0 5/2 13/4x2 x123cj - zj 00-1/4-5/4

29、得最终单纯形表：（2 2）找出非整数解变量中分数部分最大的基变量，）找出非整数解变量中分数部分最大的基变量，并写下这行约束并写下这行约束2342342434341111112(0)( 1)(2)22222211111112102222222xxxxxxxxxxxx 112123124345:max32231429 11122201,5 jGzxxxxxxxxxxxx , j ，（4 4）重复第一至第三步一直到找出问题的整数）重复第一至第三步一直到找出问题的整数最优解为止。（具体求解过程最优解为止。（具体求解过程P95P95）3451110222xxx（3）加入约束条件：在这个问题的求解过程中，

30、依次加入了两个在这个问题的求解过程中，依次加入了两个约束条件（割了两次平面），问题变为：约束条件（割了两次平面），问题变为：341212511102211222115022xxxxxxx21212312434556:max32231429111 222112201,6 jGzxxxxxxxxxxxxxx , j ，图示割平面图示割平面12122211(1)5(2)xxxx最优解为（最优解为（4 , 14 , 1）这时）这时 z z* *= 14= 14。(1)(1)(2)(2)步骤： 化标准形(隐枚举法)：1) 目标函数极小化 2) 约束条件化成 3) 使目标函数系数皆为非负, 若xj系数为负

31、值, 则令xj=1-xj 4) 使目标函数按变量系数由小大顺序排列，约束条件变 量排列的顺序要与之对应。 令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约 束条件，若满足，即为最优解；否则，分枝计算。 分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a) 对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b) zmin分枝，剪掉；(c) 能判断出为无可行解的分枝，剪掉；(d) 非上述情况，继续分枝。 5 5解解0-10-1规划问题的隐枚举法规划问题的

32、隐枚举法例：求解下述 0-1规划问题：Max z=8x1+2x2-4x3-7x4-5x5st. 3x1+3x2+x3+2x4+3x5 4 5x1+3x2- 2x3 - x4+ x5 4 xj=0或1 (j=1,2,3,4,5)1) 目标函数极小化:min z=-8x1-2x2+4x3+7x4+5x5 化标准形：2) 约束条件：-3x1-3x2-x3-2x4-3x5 -4 -5x1-3x2+ 2x3 + x4- x5 -4xj=0或1 (j=1,2,3,4,5)3) 使目标函数系数皆为正：令 x1=1-x1 ，x2=1-x2 min z=-8+8 x1 -2+2 x2 +4x3+7x4+5x5s

33、t. -3+3 x1 -3+3 x2 -x3-2x4-3x5 -4 -5+5 x1 -3+3 x2 + 2x3 + x4- x5 -4x1 , x2 ,xj=0或1 (j=3,4,5)4) 变量按顺序排列：min z= 2 x2 +4x3 +5x5 +7x4+8 x1 -10st. 3 x2 -x3 -3x5 -2x4 +3 x1 23 x2 + 2x3 - x5 + x4+5 x1 4x1 , x2 ,xj=0或1 (j=3,4,5)求解图示：1234567891011z=-10z =-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0 x3=1x3=0 x3=1x3=0 x5=1x5=0 x5=1x5=0z=-3min z= 2 x2 +4x3 +5x5 +7x4+8 x1 -10st. 3 x2 -x3 -3x5 -2x4 +3 x1 23 x2 + 2x3 - x5 + x4+5 x1 4x1 , x2 ,xj=0或1 (j=3,4,5)可编辑