0-1整数规划模型ppt课件

一 决策问题与0 1变量 1 0 做第i件事 不做第i件事 n件事中必须做k件并只做k件事 n件事中最多做k件事 n件事中至少做k件事 做第i件事的充要条件是做第j件事 做第i件事的充要条件是不做第j件事 只在做了第i件事前提下才考虑是否做第j件事 1 例1 布点问题 某城市共有6个区 每个区都可以建消防站 市政府希望设置的消防站最少 但必须满足在城市任何地区发生火火警时 消防车要在15分钟内赶到现场 据实地测定 各区之间消防车行驶的时间见右表 请为该市制定一个最节省的计划 在第i个地区建站 Z表示全区消防站总数 不在第i个地区建站 i 1 2 6 布点问题模型 最优解x2 1 x4 1 最优值Z 2 2 二 过滤隐枚举法 适合于变量个数较少的0 1规划 000 001 010 100 101 110 011 111 0 Z 0 枚举法 检验可行解 32次运算 2 5 Z 5 3 1 8 3 6 运算次数 21 计算目标函数值 8次 3 例有一份说明书 需译成英 日 德 俄四种文字 现有甲 乙 丙 丁四个人 他们将说明书译成不同文字所需的时间如下表 问应指派哪个人完成哪项工作 使所需的总时间最少 二 指派问题 4 指派问题的求解 最简便易行的方法是匈牙利法 可见指派问题是0 1型整数规划的特例 不难发现 指派问题也是运输问题的特例 其产地和销地数都为n 各产地的产量和各销地的销量都为1 5 匈牙利法基于这样一个明显的事实 如果系数矩阵的所有元素满足cij 0 而其中有n个位于不同行不同列的一组0元素 则只要令对应于这些0元素位置的xij 1 其余的xij 0 就得到最优解 匈牙利法求解指派问题的步骤如下 6 第一步 变换系数矩阵 使每行每列都出现0元素 1 系数矩阵的各行分别减去各行中的最小元素 2 所得系数矩阵的各列再分别减去各列中的最小元素 第二步 试求最优解 1 给只有一个0元素 不含划去的0 的行中的 0 画 划去与 同列的其它 0 2 给只有一个0元素 不含划去的0 的列中的 0 画 划去与 同行的其它 0 3 重复 1 2 直到无新的 画出 若系数矩阵中已无未画 也未划去的 0 则已得到最多的 转 5 否则 便出现了0元素的闭回路 转 4 4 从0元素的闭回路上任选一个 0 画 划去其同行同列的其它 0 转 1 5 显然 按上述步骤得到的 是位于不同行不同列的 若 已达n个 则指派问题的最优解已得到 结束计算 否则 转第三步 7 第三步 用最少的直线覆盖所有0元素 1 给无 的行打 2 给打 行中含有0元素的列打 3 给打 列中含有 元素的行打 4 重复 2 3 直到无新的 打出 5 给没有打 的行画横线 给打 的列画纵线 第四步 变换系数矩阵 增加0元素 在未被画线覆盖的其它元素中找出最小元素 各打 行减去最小元素 各打 列加上最小元素 转第二步 8 指派问题的数学模型为 9 克尼格定理 如果从分配问题效率矩阵 aij 的每一行元素中分别减去 或加上 一个常数ui 从每一列中分别减去 或加上 一个常数vj 得到一个新的效率矩阵 bij 则以 bij 为效率矩阵的分配问题与以 aij 为效率矩阵的分配问题具有相同的最优解 10 指派问题的求解步骤 1 变换指派问题的系数矩阵 cij 为 bij 使在 bij 的各行各列中都出现0元素 即从 cij 的每行元素都减去该行的最小元素 再从所得新系数矩阵的每列元素中减去该列的最小元素 2 进行试指派 以寻求最优解 在 bij 中找尽可能多的独立0元素 若能找出n个独立0元素 就以这n个独立0元素对应解矩阵 xij 中的元素为1 其余为0 这就得到最优解 11 找独立0元素 常用的步骤为 从只有一个0元素的行开始 给该行中的0元素加圈 记作 然后划去 所在列的其它0元素 记作 这表示该列所代表的任务已指派完 不必再考虑别人了 依次进行到最后一行 从只有一个0元素的列开始 画 的不计在内 给该列中的0元素加圈 记作 然后划去 所在行的0元素 记作 表示此人已有任务 不再为其指派其他任务了 依次进行到最后一列 若仍有没有划圈的0元素 且同行 列 的0元素至少有两个 比较这行各0元素所在列中0元素的数目 选择0元素少这个0元素加圈 表示选择性多的要 礼让 选择性少的 然后划掉同行同列的其它0元素 可反复进行 直到所有0元素都已圈出和划掉为止 12 若 元素的数目m等于矩阵的阶数n 即 m n 那么这指派问题的最优解已得到 若m n 则转入下一步 3 用最少的直线通过所有0元素 其方法 对没有 的行打 对已打 的行中所有含 元素的列打 再对打有 的列中含 元素的行打 重复 直到得不出新的打 号的行 列为止 对没有打 号的行画横线 有打 号的列画纵线 这就得到覆盖所有0元素的最少直线数l 注 l应等于m 若不相等 说明试指派过程有误 回到第2步 另行试指派 若l m n 表示还不能确定最优指派方案 须再变换当前的系数矩阵 以找到n个独立的0元素 为此转第4步 4 变换矩阵 bij 以增加0元素在没有被直线通过的所有元素中找出最小值 没有被直线通过的所有元素减去这个最小元素 直线交点处的元素加上这个最小值 新系数矩阵的最优解和原问题仍相同 转回第2步 14 例4 6有一份中文说明书 需译成英 日 德 俄四种文字 分别记作A B C D 现有甲 乙 丙 丁四人 他们将中文说明书译成不同语种的说明书所需时间如下表所示 问如何分派任务 可使总时间最少 15 解 1 变换系数矩阵 增加0元素 5 2 试指派 找独立0元素 找到3个独立零元素但m 3 n 4 16 3 作最少的直线覆盖所有0元素 独立零元素的个数m等于最少直线数l 即l m 3 n 4 4 没有被直线通过的元素中选择最小值为1 变换系数矩阵 将没有被直线通过的所有元素减去这个最小元素 直线交点处的元素加上这个最小值 得到新的矩阵 重复2 步进行试指派 17 试指派 得到4个独立零元素 所以最优解矩阵为 即完成4个任务的总时间最少为 2 4 1 8 15 18 例4 7已知四人分别完成四项工作所需时间如下表 求最优分配方案 19 解 1 变换系数矩阵 增加0元素 2 试指派 找独立0元素 独立0元素的个数为4 指派问题的最优指派方案即为甲负责D工作 乙负责B工作 丙负责A工作 丁负责C工作 这样安排能使总的工作时间最少 为4 4 9 11 28 20 例4 8已知五人分别完成五项工作耗费如下表 求最优分配方案 21 1 2 解 1 变换系数矩阵 增加0元素 22 2 试指派 找独立0元素 独立0元素的个数l 4 5 故画直线调整矩阵 23 选择直线外的最小元素为1 直线外元素减1 直线交点元素加1 其他保持不变 24 l m 4 n 5 选择直线外最小元素为1 直线外元素减1 直线交点元素加1 其他保持不变 得到新的系数矩阵 25 总费用为 5 7 6 6 4 28 注 此问题有多个最优解 26 总费用为 7 9 4 3 5 28 27 总费用为 8 9 4 3 4 28 28 课堂练习 用匈牙利法求解下列指派问题 练习1 练习2 29 分配问题与匈牙利法 48 21 答案 30