整数规划模型

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