《整数规划与分配问题1055》由会员分享，可在线阅读，更多相关《整数规划与分配问题1055（43页珍藏版）》请在金锄头文库上搜索。
1、第四章整数第四章整数规划与分配规划与分配问题问题第四章第四章 整数规划与分配问题整数规划与分配问题11整数规划的特点及作用整数规划的特点及作用 2 2分配问题与匈牙利法分配问题与匈牙利法 3 3分枝定界法分枝定界法 4 4割平面割平面法法 5 5应用举例应用举例引例：某厂利用集装箱托运甲、乙两种货物，引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量每箱体积重量 、可获利润及托运限制如下：、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413两种货物各托运多少箱使利润最大？两种货物各托运多少箱使利润最大？Max Z= 20x1 +10x25x1 +4x2242x1 +5x
2、213x1 , x20Max Z= 20x1 +10x25x1 +4x2242x1 +5x213x1 , x20x2x1Max Z= 20x1 +10x25x1 +4x2242x1 +5x213x1 , x20x2x1Max Z= 20x1 +10x25x1 +4x2242x1 +5x213x1 , x20x2x1(4.8, 0 ) AZ=96(4.8, 0 ) AZ=96Max Z= 20x1 +10x25x1 +4x2242x1 +5x213x1 , x20x2x1x1 , x2 为整数为整数Max Z= 20x1 +10x25x1 +4x2242x1 +5x213x1 , x20x1 ,
3、 x2 为整为整 数数x2x1(4.8, 0 ) AZ=96Max Z= 20x1 +10x25x1 +4x2242x1 +5x213x1 , x20x2x1(4.8, 0 ) AZ=96x1 , x2 为整数为整数(4,0) Z=80 (5,0) (4,1) max Z=901 整数规划的特点及作用 纯整数线性规划线性规划中要求全部变量取整数值。（混合整数线性规划） 求解方法：一般不能用线性规划的非整数解四舍五入（凑整）求得：工作量大或得不到最优解。 例1 求下述整数规划的最优解：（3.25，2.5）（3.25，2.5）的相邻整数点或不可行或不是最优解。最优解是（4，1）不是可行域顶点。用图
4、解法或单纯形法无法求出。 两个变量需讨论四个顶点，十个变量则需讨论 顶点 个， 工作量相当大。可能还得不出最优解。需研究解整数规划的特殊方法。 逻辑变量在建立数学模型中的作用1。m个约束条件中只有k个起作用设 m个约束条件可表为定义 假定第 i 个约束条件不起作用 假定第 i 个约束条件起作用 又M 为任意大的整数，则表明m个约束条件中有（m-k）个右端项为不起作用。 2。约束条件的右端项可能是 r 个值 中的某一个，即定义假定约束右端项为否则上述约束条件可表示为：3。两组条件中满足其中一组定义假定第 i 组条件不起作用假定第 i 组条件起作用又M 为任意大的整数，则问题可表达为： 4。用以表
5、示含固定费用的函数例 用 代表产品 的生产数量，其生产费用函数通常可表示为：式中 是同产量无关的生产准备费用。目标函数使所有产品的生产总费用为最小。即设置逻辑变量问题可表示为22分配问题与匈牙利法分配问题与匈牙利法 一、问题的提出与数学模型 分配问题也称指派问题（分配问题也称指派问题（assignment problem），是），是一种特殊的整数规划问题。假定有一种特殊的整数规划问题。假定有 m 项任务分配给项任务分配给 m 个个人去完成，并指定每人完成其中一项，每项只交给其中一人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。个人去完成，应如何分配使总
6、的效率为最高。 如果完成任务的效率表现为资源消耗，考虑的是如何如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率表现为生分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。产效率的高低，则考虑的是如何分配使得目标函数极大化。 在分配问题中，利用不同资源完成不同计划活动的效在分配问题中，利用不同资源完成不同计划活动的效率通常用表格形式表示为效率表，表格中数字组成效率矩率通常用表格形式表示为效率表，表格中数字组成效率矩阵。阵。 例例2. 有一份说明书，要分别翻译成英、日、德、俄有一份说明书，要分别翻译成英、日、
7、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，使这四个人分别完成四项任务总的时间为最小。效不同，使这四个人分别完成四项任务总的时间为最小。效率表如下：率表如下：效率矩阵用效率矩阵用aij 表示，为表示，为定义逻辑变量定义逻辑变量 则分配问题的数学模型写为：则分配问题的数学模型写为：二、匈牙利法 用表上作业法来求解分配问题时，单位运价表即效率用表上作业法来求解分配问题时，单位运价表即效率表，产销平衡表中产量和销量都设为表，产销平衡表中产量和销量都设为 1 即可。即可。 匈牙利数学家克尼格（匈牙利数学家克尼格（ Konig ）求解分
8、配问题的计算）求解分配问题的计算方法被称为匈牙利法，他证明了如下两个定理：方法被称为匈牙利法，他证明了如下两个定理： 定理定理1 如果从分配问题效率矩阵如果从分配问题效率矩阵 aij 的每一行元素的每一行元素中分别减去（或加上）一个常数中分别减去（或加上）一个常数 ui (被称为该行的位势被称为该行的位势)，从每一列分别减去（或加上）一个常数从每一列分别减去（或加上）一个常数 vj（被称为该列的（被称为该列的位势），得到一个新的效率矩阵位势），得到一个新的效率矩阵 bij，若其中，若其中 bij = aij-ui-vj，则，则 bij 的最优解等价于的最优解等价于 aij 的最优解。的最优解。
9、 定理定理2 若矩阵若矩阵 A 的元素可分成的元素可分成“ 0 ”与非与非“ 0 ”两部分，两部分，则覆盖则覆盖“ 0 ”元素的最少直线数等于位于不同行不同列的元素的最少直线数等于位于不同行不同列的“ 0 ”元素的最大个数。元素的最大个数。 结合例结合例2 说明匈牙利法的计算步骤说明匈牙利法的计算步骤 第一步：找出效率矩阵每行的最小元素，并分别第一步：找出效率矩阵每行的最小元素，并分别从每行中减去。从每行中减去。 第二步：找出矩阵每列的最小元素，分别从各列中减第二步：找出矩阵每列的最小元素，分别从各列中减去。去。 第三步：经过上述两步变换后，矩阵的每行每列至少第三步：经过上述两步变换后，矩阵的
10、每行每列至少都有了一个零元素。下面确定能否找出都有了一个零元素。下面确定能否找出 m 个位于不同行个位于不同行不同列的零元素的集合（该例中不同列的零元素的集合（该例中 m=4），也就是看要覆盖），也就是看要覆盖上面矩阵中的所有零元素，至少需要多少条直线。上面矩阵中的所有零元素，至少需要多少条直线。 1. 从第一行开始，若该行只有一个零元素，就对这从第一行开始，若该行只有一个零元素，就对这个零元素打上（个零元素打上（ ），对打括号的零元素所在的列画一条），对打括号的零元素所在的列画一条线，若该行没有零元素或者有两个以上零元素（已划去的线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），
11、则转下一行，依次进行到最后一行。不算在内），则转下一行，依次进行到最后一行。 2. 从第一列开始，若该列只有一个零元素，就对这个从第一列开始，若该列只有一个零元素，就对这个零元素打上（零元素打上（ ）（同样不考虑已划去的零元素），再对）（同样不考虑已划去的零元素），再对打括号的零元素所在行画一条直线。若该列没有零元素或打括号的零元素所在行画一条直线。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为有两个以上零元素，则转下一列，依次进行到最后一列为止。止。 3. 重复上述步骤重复上述步骤 1、2，可能出现三种情况：，可能出现三种情况： 效率矩阵每行都有打括号的零元素，只要对应
12、这些效率矩阵每行都有打括号的零元素，只要对应这些元素令元素令 xij= 1 就找到了最优解。就找到了最优解。 打括号的零元素个数少于打括号的零元素个数少于 m ，但未被划去的零元，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素打一个括号，然后对所有打括号的零元素所在行的零元素打一个括号，然后对所有打括号的零元素所在行（或列）画一条直线，同样得到最优解。（或列）画一条直线，同样得到最优解。 矩阵中所有零元素或被划去，或打上括号，但打括矩阵中所有零元素或被划去，或打上括号，但打括号的零元素少于号的零元素少于 m ，这时转
13、入第四步。，这时转入第四步。 第四步：按定理第四步：按定理 1 进行如下变换进行如下变换 1. 从矩阵未被直线覆盖的数字中找出一个最小的从矩阵未被直线覆盖的数字中找出一个最小的k ； 2. 对矩阵中的每行，当该行有直线覆盖时，令对矩阵中的每行，当该行有直线覆盖时，令 ui=0，无直线覆盖的，令，无直线覆盖的，令 ui= k ； 3. 对矩阵中有直线覆盖的列，令对矩阵中有直线覆盖的列，令 vj= -k，对无直线覆，对无直线覆盖的列，令盖的列，令 vj= 0 ； 4. 从原矩阵的每个元素从原矩阵的每个元素 aij中分别减去中分别减去 ui 和和 vj 。 第五步：回到第三步，反复进行，直到矩阵的每
14、一行第五步：回到第三步，反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方案。都有一个打括号的零元素为止，即找到最优分配方案。 由于调整后的矩阵中新出现了一个零，因此对打括号由于调整后的矩阵中新出现了一个零，因此对打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号元素所对应的决策变量取值为元素所对应的决策变量取值为1，就得到最优解。，就得到最优解。 该问题中，最优值为：该问题中，最优值为：4+4+9+11=28h习题习题 4.3 三、两点说明 1. 分配问题中人数和工作任务不相等时分配问题中人数和工作任务不相等时 当人
15、数多于工作任务数时，可以添加假想任务使得人当人数多于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，因此完成数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，可添加假想这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方法类似。的人。这样的方法和运输问题中处理的方法类似。 2. 当问题目标变为求极大时当问题目标变为求极大时可改写为可改写为 此时效率矩阵中元素都变为了负值，可利用定理此时效率矩阵中元素都变为了负值，可利用定理1，使效率矩阵中全部元素都变为非负的，就可以利用匈牙利使效率矩阵中全部
16、元素都变为非负的，就可以利用匈牙利法进行求解。法进行求解。作业作业 4.4 4.533分枝定界法分枝定界法 记记待待解解的的整整数数规规划划问问题题为为 A ，相相应应的的线线性性规规划划问问题题(去去掉掉了了整整数数约约束束，即即松松弛弛问问题题)为为 B ，整整数数规规划划的的最最优优解解为为 z*。 分枝定界法的基本思想：分枝定界法的基本思想： （1）先不考虑整数条件，即先求解相应线性规划）先不考虑整数条件，即先求解相应线性规划 B的最优解。若得到的是整数解，则问题得到解决的最优解。若得到的是整数解，则问题得到解决;否则，否则，这个非整数解必是原整数规划问题这个非整数解必是原整数规划问题
17、 A 的最优解的最优解 z* 的上界，的上界，记为记为 ；而；而 A 的任一整数解，可以看作的一个下界，记的任一整数解，可以看作的一个下界，记为为 。 （2）从得到的）从得到的 B 的最优解中，任选一个非整数的变的最优解中，任选一个非整数的变量量 xk ，在，在 B 中增加约束条件中增加约束条件 xk xk 构成一个新的线性规构成一个新的线性规划问题划问题 B1，它实际上是，它实际上是 B 的一个分枝；在的一个分枝；在 B 中增加另一中增加另一约束条件约束条件 xk xk +1，又得到一个，又得到一个 B 的分支，记为的分支，记为 B2；分；分别求出别求出 B1 和和 B2的最优解，判断这两个
18、解是否是最优解，的最优解，判断这两个解是否是最优解，若是，问题得到解决；若不是，调整若是，问题得到解决；若不是，调整 和和 ，将它们再分，将它们再分枝，直到求出最优整数解为止。枝，直到求出最优整数解为止。 分枝定界法实质是将分枝定界法实质是将 B 的可行域分成若干子区域的可行域分成若干子区域(称称为分枝为分枝)，逐渐减小，逐渐减小 和增大和增大 ，最终求出，最终求出 z*。 例例. 用分枝定界法求解整数规划问题：用分枝定界法求解整数规划问题： 解：（解：（1）求解对应的松弛问题）求解对应的松弛问题 B其最优解为：其最优解为：最优值为：最优值为： 目前最优值为目前最优值为 z=14.75 ，令，
19、令 =14.75； 现在还没有任何整数解，可以令（现在还没有任何整数解，可以令（0，0）作为初始整）作为初始整数解，因此有数解，因此有 =0 。 （2）定界）定界 （3）分枝）分枝 将线性规划问题将线性规划问题 B 分为两枝。分为两枝。 在在 B 的最优解中，任选一个非整数变量，如的最优解中，任选一个非整数变量，如 x2=2.5 ；因；因 x2 的最优整数解只可能是的最优整数解只可能是 x22 或或 x23 ，故在，故在 B 中中分别增加约束条件：分别增加约束条件：B 加上约束条件加上约束条件 x22 ，记为，记为 B1；B加上约束条件加上约束条件 x23 ，记为，记为 B2 。这样，将分解成
20、两个子问。这样，将分解成两个子问题题 B1 和和 B2（即两枝）。（即两枝）。 这样松弛问题这样松弛问题 B 变为了求解下述两个问题：变为了求解下述两个问题： B 分解为分解为 B1 和和 B2 ：B1 的最优解为：的最优解为：x1=3.5 , x2=2 , z=14.5B2 的最优解为：的最优解为：x1=2.5 , x2=3 , z=13.5 定界：定界：这时两个问题的最优值中较大的一个是这时两个问题的最优值中较大的一个是 14.5 ，比原来的上界要小，因此修改上界，令，比原来的上界要小，因此修改上界，令 。 又由于目前没有出现更好的整数界，所以下界仍然是又由于目前没有出现更好的整数界，所以
21、下界仍然是 0 。 分枝：选取最优值教大的子问题优先进行分枝，将分枝：选取最优值教大的子问题优先进行分枝，将B1 分解为分解为 B11和和 B12 两个子问题。两个子问题。 B11和和 B12 两个子问题的可行域为：两个子问题的可行域为： 继续分枝定界，求解得最优解（继续分枝定界，求解得最优解（4 , 1），最优解为），最优解为14。4割平面法割平面法一、基本思想一、基本思想 找到纯整数线性规划的松弛问题，不考找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉松弛问题的可行域切割一部分，但不切割掉
22、任何整数解，只切割掉包括松弛问题的最优任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。解在内的非整数解。二、割平面求解举例二、割平面求解举例Max Z=x1+x2-x1+x213x1+x2 4x1 , x20且为整数且为整数松弛问题松弛问题Max Z=x1+x2-x1+x213x1+x2 4x1 , x20-x1+x2+x3 =13x1+x2 +x4=4x1 , x20不考虑整数解约束，解松弛问题的最优单纯形表为：不考虑整数解约束，解松弛问题的最优单纯形表为：CBXBb1100x1x2x3x40x31-11100x44310111001x13/410-1/41/41x27/4013/4
23、1/4Z=5/200-1/2-1/2找 中真分数部分大的所对应的约束条件：将将 -3x3-x4+x5= -3（切割方程）（切割方程） 代入最优表代入最优表CBXBb11000x1x2x3x4x51x13/410-1/41/401x27/4013/41/400x5-300-3-11Z=5/200-1/2-1/201x111001/31/121x2101001/40x310011-1/3Z=2000-1/3-1/3MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20 且为整数且为整数MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20CB
24、XBb11000x1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70x431/700-3/7122/7Z=5/200-5/70-3/7x1+1/7x3 + 2/7x5=13/7x1+1/7x3 + 2/7x5=1+6/7x1- 1 = 6/7 -（1/7x3 + 2/7x5）6/7 -（1/7x3 + 2/7x5）0-1/7x3 - 2/7x5- 6/7 -1/7x3 - 2/7x5- 6/7-1/7x3 - 2/7x5+x6=- 6/7CBXBb110000x1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700x431/700-3/7122/700x6-6/700-1/70-2/71Z=5/200-5/70-3/70CBXBb110000x1x2x3x4x5x63x11100001-1x24/5010-1/40-5/40x35/2001-1/20-11/20x57/40001/41-3/4Z=5/200000-17/4-1/4x4 + 1/4x6-3/4余下略余下略
