《运筹学10-11整数规划与分配问题》由会员分享，可在线阅读，更多相关《运筹学10-11整数规划与分配问题（43页珍藏版）》请在金锄头文库上搜索。
1、运筹学演示课件 第 四 章 第四章 整数规划与分配问题 1整数规划的特点及作用 2分配问题与匈牙利法 3分枝定界法 4割平面法 5应用举例 引例：某厂利用集装箱托运甲、乙两种货物， 每箱体积重量 、可获利润及托运限制如下： 体积重量利润 甲5220 乙4510 托运限制2413 两种货物各托运多少箱使利润最大？ Max Z= 20 x1 +10 x2 5x1 +4x224 2x1 +5x213 x1 , x20 Max Z= 20 x1 +10 x2 5x1 +4x224 2x1 +5x213 x1 , x20 x2 x1 Max Z= 20 x1 +10 x2 5x1 +4x224 2x1
2、+5x213 x1 , x20 x2 x1 Max Z= 20 x1 +10 x2 5x1 +4x224 2x1 +5x213 x1 , x20 x2 x1 (4.8, 0 ) A Z=96 (4.8, 0 ) A Z=96 Max Z= 20 x1 +10 x2 5x1 +4x224 2x1 +5x213 x1 , x20 x2 x1 x1 , x2 为整数 Max Z= 20 x1 +10 x2 5x1 +4x224 2x1 +5x213 x1 , x20 x1 , x2 为整 数 x2 x1 (4.8, 0 ) A Z=96 Max Z= 20 x1 +10 x2 5x1 +4x224
3、2x1 +5x213 x1 , x20 x2 x1 (4.8, 0 ) A Z=96 x1 , x2 为整数 (4,0) Z=80 (5,0) (4,1) max Z=90 1 整数规划的特点及作用 纯整数线性规划线性规划中要求全部变量取 整数值。（混合整数线性规划） 求解方法：一般不能用线性规划的非整数解四 舍五入（凑整）求得：工作量大或得不到最优 解。 例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、函数 通常可表示为： 式中 是同产量无关的生产准备费用。 目标函数使所有产品的生产总费用为最小。即 设置逻辑变量 问题可表示为 2分配问题与匈牙利法 一、问题的提出与数学模型 分配问题也称指派问题（assignment problem）， 是一种特殊的整数规划问题。假定有 m 项任务分配给 m 个人去完成，并指定每人完成其中一项，每项只交给其中 一个人去完成，应如何分配使总的效率为最高。 如果完成任务的效率表现为资源消耗，考虑的是如何 分配任务使得目标极小化；如果完成任务的效率表现为生 产效率的高低，则考虑的是如何分配使得目标函数极大化 。 在分配问题中，利用不同资源完成不同计划活动的效 率通
6、常用表格形式表示为效率表，表格中数字组成效率 矩阵。 例2. 有一份说明书，要分别翻译成英、日、德、俄 四种文字，交甲、乙、丙、丁四个人去完成。因各人专长 不同，使这四个人分别完成四项任务总的时间为最小。效 率表如下： 效率矩阵用aij 表示，为 定义逻辑变量 则分配问题的数学模型写为： 二、匈牙利法 用表上作业法来求解分配问题时，单位运价表即效率 表，产销平衡表中产量和销量都设为 1 即可。 匈牙利数学家克尼格（ Konig ）求解分配问题的计算 方法被称为匈牙利法，他证明了如下两个定理： 定理1 如果从分配问题效率矩阵 aij 的每一行元素中 分别减去（或加上）一个常数 ui (被称为该行
7、的位势)，从 每一列分别减去（或加上）一个常数 vj（被称为该列的位 势），得到一个新的效率矩阵 bij，若其中 bij = aij-ui-vj， 则 bij 的最优解等价于 aij 的最优解。 定理2 若矩阵 A 的元素可分成“ 0 ”与非“ 0 ”两部分， 则覆盖“ 0 ”元素的最少直线数等于位于不同行不同列的“ 0 ”元素的最大个数。 结合例2 说明匈牙利法的计算步骤 第一步：找出效率矩阵每行的最小元素，并分别 从每行中减去。 第二步：找出矩阵每列的最小元素，分别从各列中减 去。 第三步：经过上述两步变换后，矩阵的每行每列至少 都有了一个零元素。下面确定能否找出 m 个位于不同行 不同列
8、的零元素的集合（该例中 m=4），也就是看要覆盖 上面矩阵中的所有零元素，至少需要多少条直线。 1. 从第一行开始，若该行只有一个零元素，就对这 个零元素打上（ ），对打括号的零元素所在的列画一条 线，若该行没有零元素或者有两个以上零元素（已划去的 不算在内），则转下一行，依次进行到最后一行。 2. 从第一列开始，若该列只有一个零元素，就对这个 零元素打上（ ）（同样不考虑已划去的零元素），再对 打括号的零元素所在行画一条直线。若该列没有零元素或 有两个以上零元素，则转下一列，依次进行到最后一列为 止。 3. 重复上述步骤 1、2，可能出现三种情况： 效率矩阵每行都有打括号的零元素，只要对应这
9、些 元素令 xij= 1 就找到了最优解。 打括号的零元素个数少于 m ，但未被划去的零元 素之间存在闭回路，这时顺着闭回路的走向，对每个间隔 的零元素打一个括号，然后对所有打括号的零元素所在行 （或列）画一条直线，同样得到最优解。 矩阵中所有零元素或被划去，或打上括号，但打括 号的零元素少于 m ，这时转入第四步。 第四步：按定理 1 进行如下变换 1. 从矩阵未被直线覆盖的数字中找出一个最小的k ； 2. 对矩阵中的每行，当该行有直线覆盖时，令 ui=0， 无直线覆盖的，令 ui= k ； 3. 对矩阵中有直线覆盖的列，令 vj= -k，对无直线覆 盖的列，令 vj= 0 ； 4. 从原矩
10、阵的每个元素 aij中分别减去 ui 和 vj 。 第五步：回到第三步，反复进行，直到矩阵的每一行 都有一个打括号的零元素为止，即找到最优分配方案。 由于调整后的矩阵中新出现了一个零，因此对打括号 的元素重新进行调整，得到如下矩阵，这时只要把打括号 元素所对应的决策变量取值为1，就得到最优解。 该问题中，最优值为：4+4+9+11=28h 习题 4.3 三、两点说明 1. 分配问题中人数和工作任务不相等时 当人数多于工作任务数时，可以添加假想任务使得人 数与工作任务数相同，因为工作任务是假想的，因此完成 这些任务的时间是零。当任务数多于人数时，可添加假想 的人。这样的方法和运输问题中处理的方法
11、类似。 2. 当问题目标变为求极大时 可改写为 此时效率矩阵中元素都变为了负值，可利用定理1， 使效率矩阵中全部元素都变为非负的，就可以利用匈牙利 法进行求解。 作业 4.4 4.5 3分枝定界法 记待解的整数规划问题为 A ，相应的线性规划问题( 去掉了整数约束，即松弛问题)为 B ，整数规划的最优解 为 z*。 分枝定界法的基本思想： （1）先不考虑整数条件，即先求解相应线性规划 B 的最优解。若得到的是整数解，则问题得到解决;否则， 这个非整数解必是原整数规划问题 A 的最优解 z* 的上界 ，记为 ；而 A 的任一整数解，可以看作的一个下界， 记为 。 （2）从得到的 B 的最优解中，
12、任选一个非整数的变 量 xk ，在 B 中增加约束条件 xk xk 构成一个新的线性 规划问题 B1，它实际上是 B 的一个分枝；在 B 中增加另 一约束条件 xk xk +1，又得到一个 B 的分支，记为 B2； 分别求出 B1 和 B2的最优解，判断这两个解是否是最优解 ，若是，问题得到解决；若不是，调整 和 ，将它们再 分枝，直到求出最优整数解为止。 分枝定界法实质是将 B 的可行域分成若干子区域(称 为分枝)，逐渐减小 和增大 ，最终求出 z*。 例. 用分枝定界法求解整数规划问题： 解：（1）求解对应的松弛问题 B 其最优解为： 最优值为： 目前最优值为 z=14.75 ，令 =14
13、.75； 现在还没有任何整数解，可以令（0，0）作为初始整 数解，因此有 =0 。 （2）定界 （3）分枝 将线性规划问题 B 分为两枝。 在 B 的最优解中，任选一个非整数变量，如 x2=2.5 ；因 x2 的最优整数解只可能是 x22 或 x23 ，故在 B 中 分别增加约束条件：B 加上约束条件 x22 ，记为 B1；B 加上约束条件 x23 ，记为 B2 。这样，将分解成两个子问 题 B1 和 B2（即两枝）。 这样松弛问题 B 变为了求解下述两个问题： B 分解为 B1 和 B2 ： B1 的最优解为： x1=3.5 , x2=2 , z=14.5 B2 的最优解为： x1=2.5
14、, x2=3 , z=13.5 定界：这时两个问题的最优值中较大的一个是 14.5 ，比原来的上界要小，因此修改上界，令 。 又由于目前没有出现更好的整数界，所以下界仍然是 0 。 分枝：选取最优值教大的子问题优先进行分枝，将B1 分解为 B11和 B12 两个子问题。 B11和 B12 两个子问题的可行域为： 继续分枝定界，求解得最优解（4 , 1），最优解为14 。 44割平面法割平面法 一、基本思想 找到纯整数线性规划的松弛问题，不考 虑整数约束条件，但增加线性约束条件，将 松弛问题的可行域切割一部分，但不切割掉 任何整数解，只切割掉包括松弛问题的最优 解在内的非整数解。 二、割平面求解举例 Max Z=x1+x2 -x1+x21 3x1+x2 4 x1 , x20且为整数 松弛问题 Max Z=x1+x2 -x1+x21 3x1+x2 4 x1 , x20 -x1+x2+x3 =1 3x1+x2 +x4=4 x1 , x20 不考虑整数解约束，解松弛问题的最优单纯形表为 ： CBXBb 1100 x1x2x3x4 0 x31-1110 0 x4
