第四章第四章 整数规划与分配问题整数规划与分配问题1 1整数规划的特点及作用整数规划的特点及作用 2分配问题与匈牙利法分配问题与匈牙利法 3分枝定界法分枝定界法 4割平面法割平面法 5解解0-1规划问题的隐枚举法规划问题的隐枚举法1 1整数规划的特点及应用整数规划的特点及应用 在实际问题中，全部或部分变量的取值必须是整数。在实际问题中，全部或部分变量的取值必须是整数。比如人或机器是不可分割的，选择建厂地点可以设置逻辑比如人或机器是不可分割的，选择建厂地点可以设置逻辑变量等。变量等。 在一个线性规划问题中要求全部变量取整数值的，称在一个线性规划问题中要求全部变量取整数值的，称纯整数线性规划或简称纯整数线性规划或简称纯整数规划纯整数规划；只要求一部分变量；只要求一部分变量取整数值的，称为取整数值的，称为混合整数规划混合整数规划。 对整数规划问题求解，有人认为可以不考虑对变量的对整数规划问题求解，有人认为可以不考虑对变量的整数约束，作为一般线性规划问题求解，当解为非整数时，整数约束，作为一般线性规划问题求解，当解为非整数时，用四舍五入或凑整方法寻找最优解，我们从下面的例子说用四舍五入或凑整方法寻找最优解，我们从下面的例子说明这样的方法是不合适的。明这样的方法是不合适的。 例例1. 求下述整数规划问题的最优解求下述整数规划问题的最优解 解解：如果不考虑整数约束（称为整数规划问题的：如果不考虑整数约束（称为整数规划问题的松弛松弛问题问题）用图解法得最优解为（）用图解法得最优解为（3.25 , 2.5） 考虑到整数约束，用凑整法求解考虑到整数约束，用凑整法求解时，比较四个点（时，比较四个点（4 , 3）,（4 , 2）,（3 , 3）（）（3 , 2），前三个都不是可行解，），前三个都不是可行解，第四个虽然是可行解，但第四个虽然是可行解，但 z=13 不是最不是最优。实际问题的最优解为（优。实际问题的最优解为（4 , 1）这）这时时 z*= 14。逻辑逻辑（0-1）变量在建立数学模型中的作用变量在建立数学模型中的作用1. m 个约束条件中只有个约束条件中只有 k 个起作用个起作用设设 m 个约束条件可以表示为：个约束条件可以表示为：定义逻辑变量定义逻辑变量又设又设 M 为任意大的正数，则约束条件可以改写为：为任意大的正数，则约束条件可以改写为：定义逻辑变量：定义逻辑变量：此时约束条件可以改写为：此时约束条件可以改写为： 2. 约束条件的右端项可能是约束条件的右端项可能是 r 个值中的某一个个值中的某一个即即 3. 两组条件满足其中一组两组条件满足其中一组 若若 x14，则，则 x21（第一组条件第一组条件）；否则当）；否则当 x1 4 时，时，x23（第二组条件第二组条件）. 定义逻辑变量：定义逻辑变量：又设又设 M 为任意大正数，则问题可表达为：为任意大正数，则问题可表达为：需注意，当约束需注意，当约束为大于时，右端为大于时，右端项中用减号。项中用减号。 4. 用以表示含固定费用的函数用以表示含固定费用的函数 用用 xj 代表产品代表产品 j 的生产数量，其生产费用函数表示为的生产数量，其生产费用函数表示为其中其中 Kj 是同产量无关的生产准备费用，问题的目标是使是同产量无关的生产准备费用，问题的目标是使所有产品的总生产费用为最小，即所有产品的总生产费用为最小，即定义逻辑变量（表示是否生产产品定义逻辑变量（表示是否生产产品 j ）又设又设 M 为任意大正数，为了表示上述定义，引入约束：为任意大正数，为了表示上述定义，引入约束：显然，当显然，当 xj 0 时，时，yj=1。将目标函数与约束条件合起来考虑有：将目标函数与约束条件合起来考虑有：由此看出，当由此看出，当 xj = 0 时，为使时，为使 z 极小化，应有极小化，应有 yj = 02 2分配问题与匈牙利法分配问题与匈牙利法 一、问题的提出与数学模型 分配问题分配问题也称也称指派问题指派问题（assignment problem），），是一种特殊的整数规划问题。假定有是一种特殊的整数规划问题。假定有 m 项任务分配给项任务分配给 m 个人去完成，并指定每人完成其中一项，每项只交给其中个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。一个人去完成，应如何分配使总的效率为最高。 如果完成任务的效率表现为资源消耗，考虑的是如何如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率表现为生分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。产效率的高低，则考虑的是如何分配使得目标函数极大化。 在分配问题中，利用不同资源完成不同计划活动的效在分配问题中，利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表，表格中数字组成率通常用表格形式表示为效率表，表格中数字组成效率效率矩阵矩阵。 例例2. 有一份说明书，要分别翻译成英、日、德、俄有一份说明书，要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，使这四个人分别完成四项任务总的时间为最小。效不同，使这四个人分别完成四项任务总的时间为最小。效率表如下：率表如下：效率矩阵用效率矩阵用aij 表示，为表示，为定义逻辑变量定义逻辑变量 则分配问题的数学模型写为：则分配问题的数学模型写为：二、匈牙利法 用表上作业法来求解分配问题时，单位运价表即效率用表上作业法来求解分配问题时，单位运价表即效率表，产销平衡表中产量和销量都设为表，产销平衡表中产量和销量都设为 1 即可。即可。 匈牙利数学家克尼格（匈牙利数学家克尼格（ Konig ）求解分配问题的计算）求解分配问题的计算方法被成为方法被成为匈牙利法匈牙利法，他证明了如下两个定理：，他证明了如下两个定理： 定理定理1 如果从分配问题效率矩阵如果从分配问题效率矩阵 aij 的每一行元素中的每一行元素中分别减去（或加上）一个常数分别减去（或加上）一个常数 ui (被称为该行的位势被称为该行的位势)，从，从每一列分别减去（或加上）一个常数每一列分别减去（或加上）一个常数 vj（被称为该列的位（被称为该列的位势），得到一个新的效率矩阵势），得到一个新的效率矩阵 bij，若其中，若其中 bij = aij-ui-vj，则则 bij 的最优解等价于的最优解等价于 aij 的最优解。的最优解。 定理定理2 若矩阵若矩阵 A 的元素可分成的元素可分成“ 0 ”与非与非“ 0 ”两部分，两部分，则覆盖则覆盖“ 0 ”元素的最少直线数等于位于不同行不同列的元素的最少直线数等于位于不同行不同列的“ 0 ”元素的最大个数。元素的最大个数。 结合例结合例2 说明说明匈牙利法的计算步骤匈牙利法的计算步骤 第一步：找出效率矩阵每行的最小元素，并分别第一步：找出效率矩阵每行的最小元素，并分别从每行中减去。从每行中减去。 第二步：找出矩阵每列的最小元素，分别从各列中减第二步：找出矩阵每列的最小元素，分别从各列中减去。去。 第三步：经过上述两步变换后，矩阵的每行每列至少第三步：经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。下面确定能否找出都有了一个零元素。下面确定能否找出 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 三、两点说明 1. 分配问题中人数和工作任务不相等时分配问题中人数和工作任务不相等时 当人数多于工作任务数时，可以添加假想任务使得人当人数多于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，因此完成数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，可添加假想这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方法类似。的人。这样的方法和运输问题中处理的方法类似。 2. 当问题目标变为求极大时当问题目标变为求极大时可改写为可改写为 此时效率矩阵中元素都变为了负值，可利用定理此时效率矩阵中元素都变为了负值，可利用定理1，使效率矩阵中全部元素都变为非负的，就可以利用匈牙利使效率矩阵中全部元素都变为非负的，就可以利用匈牙利法进行求解。法进行求解。3 3分枝定界法分枝定界法 记记待待解解的的整整数数规规划划问问题题为为 L ，相相应应的的线线性性规规划划问问题题(去去掉掉了了整整数数约约束束，即即松松弛弛问问题题)为为 L0 ，整整数数规规划划的的最最优优值值为为 z*。 分枝定界法的基本思想：分枝定界法的基本思想： （1）先不考虑整数条件，即先求解相应线性规划）先不考虑整数条件，即先求解相应线性规划 L0的最优解。若得到的是整数解，则问题得到解决的最优解。若得到的是整数解，则问题得到解决;否则，否则，这个非整数解必是原整数规划问题这个非整数解必是原整数规划问题 L 的最优解的最优解 z* 的上界，的上界，记为记为 ；而；而 L的任一整数解，可以看作一个下界，记为的任一整数解，可以看作一个下界，记为 。 （2）从得到的）从得到的 L0的最优解中，任选一个非整数的变的最优解中，任选一个非整数的变量量 xk ，在，在 L0中增加约束条件中增加约束条件 xk xk 构成一个新的线性构成一个新的线性规划问题规划问题 L1，它实际上是，它实际上是 L0 的一个分枝；在的一个分枝；在 L0中增加另中增加另一约束条件一约束条件 xk xk +1，又得到一个，又得到一个 L0 的分支，记为的分支，记为 L2；分别求出；分别求出 L1 和和 L2的最优解，判断这两个解是否是最优的最优解，判断这两个解是否是最优解，若是，问题得到解决；若不是，调整解，若是，问题得到解决；若不是，调整 和和 ，将它们，将它们再分枝，直到求出最优整数解为止。再分枝，直到求出最优整数解为止。 分枝定界法实质是将分枝定界法实质是将 L0 的可行域分成若干子区域的可行域分成若干子区域(称称为分枝为分枝)，逐渐减小，逐渐减小 和增大和增大 ，最终求出，最终求出 z*。 例例. 用分枝定界法求解整数规划问题：用分枝定界法求解整数规划问题： 解解：（1）求解对应的松弛问题）求解对应的松弛问题 L0其最优解为：其最优解为：最优值为：最优值为： 目前最优值为目前最优值为 z=14.75 ，令，令 =14.75； 现在还没有任何整数解，可以令（现在还没有任何整数解，可以令（0，0）作为初始整）作为初始整数解，因此有数解，因此有 =0 。 （2）定界）定界 （3）分枝）分枝 将线性规划问题将线性规划问题 L0分为两枝。分为两枝。 在在 L0的最优解中，任选一个非整数变量，如的最优解中，任选一个非整数变量，如 x2=2.5 ；因；因 x2 的最优整数解只可能是的最优整数解只可能是 x22 或或 x23 ，故在，故在 L0中中分别增加约束条件：分别增加约束条件： L0加上约束条件加上约束条件 x22 ，记为，记为 L1； L0加上约束条件加上约束条件 x23 ，记为，记为 L2 。这样，将分解成两个子问。这样，将分解成两个子问题题 L1 和和 L2（即两枝）。（即两枝）。 这样松弛问题这样松弛问题 L0 变为了求解下述两个问题：变为了求解下述两个问题： L0 分解为分解为 L1 和和L2 ：L1 的最优解为：的最优解为：x1=3.5 , x2=2 , z=14.5L2 的最优解为：的最优解为：x1=2.5 , x2=3 , z=13.5 定界：定界：这时两个问题的最优值中较大的一个是这时两个问题的最优值中较大的一个是 14.5 ，比原来的上界要小，因此修改上界，令，比原来的上界要小，因此修改上界，令 。 又由于目前没有出现更好的整数界，所以下界仍然是又由于目前没有出现更好的整数界，所以下界仍然是 0 。 分枝：分枝：选取最优值较大的子问题优先进行分枝，将选取最优值较大的子问题优先进行分枝，将L1 分解为分解为 L11和和 L12 两个子问题。两个子问题。 L11和和 L12 两个子问题的可行域为：两个子问题的可行域为： 继续分枝定界，最后剪枝求解得最优解（继续分枝定界，最后剪枝求解得最优解（4 , 1），最），最优解为优解为14。(见见P93，图，图4.5)4 4割平面法割平面法 割平面法是求解整数规划问题最早提出的一割平面法是求解整数规划问题最早提出的一种方法，种方法，1958年由高莫雷（年由高莫雷（Gomory）提出。）提出。 基本思路是不断引进适当的线性约束条件，基本思路是不断引进适当的线性约束条件，使得可行域逐步缩小，但每次切割只是割去问题使得可行域逐步缩小，但每次切割只是割去问题的部分非整数解，直到使问题的目标值达到最优的部分非整数解，直到使问题的目标值达到最优的整数点成为缩小后可行域的一个顶点，这样就的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划的方法找出这个最优解。可以用求解线性规划的方法找出这个最优解。 例例. 用割平面法求解整数规划问题：用割平面法求解整数规划问题：解解：（1）约束条件系数化整，忽略整数约束，）约束条件系数化整，忽略整数约束，用单纯形法求解对应的松弛问题用单纯形法求解对应的松弛问题Cj 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得最终单纯形表：（2）找出非整数解变量中分数部分最大的基变量，）找出非整数解变量中分数部分最大的基变量，并写下这行约束并写下这行约束（4）重复第一至第三步一直到找出问题的整数）重复第一至第三步一直到找出问题的整数最优解为止。（具体求解过程最优解为止。（具体求解过程P95）在这个问题的求解过程中，依次加入了两个在这个问题的求解过程中，依次加入了两个约束条件（割了两次平面），问题变为：约束条件（割了两次平面），问题变为：图示割平面图示割平面最优解为（最优解为（4 , 1）这时）这时 z*= 14。(1)(2)步骤： 化标准形(隐枚举法)：1) 目标函数极小化 2) 约束条件化成 3) 使目标函数系数皆为非负, 若xj系数为负值, 则令xj=1-xj 4) 使目标函数按变量系数由小大顺序排列，约束条件变 量排列的顺序要与之对应。 令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约 束条件，若满足，即为最优解；否则，分枝计算。 分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a) 对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b) zmin分枝，剪掉；(c) 能判断出为无可行解的分枝，剪掉；(d) 非上述情况，继续分枝。 5 5解解0-1规划问题的隐枚举法规划问题的隐枚举法例：求解下述 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+5x5st. -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=0x3=1x3=0x3=1x3=0x5=1x5=0x5=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)