指派问题(经典运筹学)

3 40 1整数规划 一 决策问题与0 1变量 1 0 做第i件事 不做第i件事 n件事中必须做k件并只做k件事 n件事中最多做k件事 n件事中至少做k件事 做第i件事的充要条件是做第j件事 做第i件事的充要条件是不做第j件事 只在做了第i件事前提下才考虑是否做第j件事 该公司只有600万资金可用于投资 由于技术上的原因 投资受到以下约束 1 在项目1 2和3中必须有一项被选中2 项目3和4只能选中一项3 项目5被选中的前提是项目1被选中 如何在满足上述条件下选择一个最好的投资方案 使投资收益最大 例1 投资问题 华美公司有5个项目被列入投资计划 每个项目的投资额和期望的投资收益见下表 1 0 投资第i个项目 不投资第i个项目 Z表示投资效益 投资项目模型 例2 布点问题 某城市共有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次 三 指派问题与匈牙利法 设有n个工作 要由n个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的费用 求总费用最低的指派方案 费用 12 j n 12 i n 指派问题模型 i 1 2 n j 1 2 n 第i个人做第j人件事 Z表示总费用 i 1 2 n j 1 2 n 第i个人不做第j人件事 1 指派问题的数学模型 i 1 2 n j 1 2 n 当n 4时 有16变量 8个约束方程 例 现有4份工作 4个人应聘 由于各人技术专长不同 他们承担各项工作所需费用如下表所示 且规定每人只能做一项工作 每一项工作只能由一人承担 试求使总费用最小的分派方案 工作 人 费用 1234 1234 3545 6768 89810 1010911 1 0 第i人做第j件事 Z表示总费用 i 1 2 3 4 j 1 2 3 4 第i人不做第j件事 2 费用矩阵 设有n个工作 要由n个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的费用 求总费用最低的指派方案 费用 12 j n 12 i n cij表示第i个人做第j件事的费用 费用矩阵 例 现有4份工作 4个人应聘 由于个人的技术专长不同 他们承担各项工作所需费用如下表所示 且规定每人只能做一项工作 每一项工作只能由一个人承担 试求使总费用最小的分派方案 工作 人 收费用 1234 1234 3545 6768 89810 1010911 费用矩阵 对应一个5个人5个工作的指派问题 第2个人做第4个工作的费用 5 第4个人做第2个工作的费用 0 定理 在费用矩阵C cij 的任一行 列 中减去一个常数或加上一个常数不改变本问题的最优解 n个人n个工作的指派问题1 b 3 匈牙利法 n个人n个工作的指派问题2 i 1 2 n j 1 2 n i 1 2 n j 1 2 n b b i 1 2 n j 1 2 n i 1 2 n j 1 2 n 任务 对C的行和列减去某个常数 将C化的尽可能简单 简单到可一眼看出该问题的最优解 b 3 40 1整数规划 三 指派问题与匈牙利法 费用 12 j n 12 i n 指派问题模型 i 1 2 n j 1 2 n 第i个人做第j人件事 Z表示总费用 i 1 2 n j 1 2 n 第i个人不做第j人件事 1 指派问题的数学模型 设有n个工作 要由n个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的费用 求总费用最低的指派方案 2 费用矩阵 设有n个工作 要由n个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的费用 求总费用最低的指派方案 费用 12 j n 12 i n cij表示第i个人做第j件事的费用 费用矩阵 定理 在费用矩阵C cij 的任一行 列 中减去一个常数或加上一个常数不改变本问题的最优解 b 3 匈牙利法 指派问题的最优解 若C中有n个位于不同行不同列的零元素 则令这些零元素对应的变量取1 其余变量取零 既得指派问题的最优解 i 1 2 3 4 j 1 2 3 4 可行解 最优解 匈牙利法的基本思路 对费用矩阵C的行和列减去某个常数 将C化成有n个位于不同行不同列的零元素 令这些零元素对应的变量取1 其余变量取零 既得指派问题的最优解 例 有一份说明书要分别译成英 日 德 俄四种文字 现交给甲 乙丙 丁四个人去完成 每人完成一种 由于个人的专长不同 翻译成不同文字所需的时间 小时数 如右表 问应派哪个人去完成哪个任务 可使总花费时间最少 工作 人 时间 英日德俄 甲乙丙丁 215134 1041415 9141613 78119 2 4 9 7 最优方案 甲翻译俄文 乙翻译日文 丙翻译英文 丁翻译德文 总费用 28小时 4 2 2 4 9 7 4 2 最优解的取法 从含0元素最少的行或列开始 圈出一个0元素 用 表示 然后划去该 所在的行和列中的其余0元素 用 表示 依次类推 若能得到n个 则得最优解X0 例 求费用矩阵为右表的指派问题的最优解 工作 人 费用 ABCDE 甲乙丙丁戊 127979 89666 717121412 15146610 4107106 7 6 7 6 4 得4个 且不存在没打 的0 修改方法 对n阶费用矩阵C 若C有n个位于不同行不同列的零元素 即可得最优解X0 否则 对C进行调整 2 2 2 最优指派方案 甲做B工作 乙做C工作 丙做A工作 丁做D工作 戊做E工作 当C没有n个位于不同行不同列的零元素时 对C进行调整 第一步 做能复盖所有0元素的最小直线集合 1 对没有 的行打 号 2 对打 号的行上所有0元素的列打 号 3 再对打 号的列上所有 的行打 号 4 重复以上步骤直到得不出新的打 号为止 5 对没有打 号的行画横线 所有打 号的列画纵线 所得到的直线既是复盖所有0元素的最小直线集合 具体步骤 第二步 在没有被直线复盖的元素中找出最小元素 让打 号的列加上这个元素 打 号的行减去这个元素 第三步 对所得到的矩阵画 若能得到n个 则得最优解 否则重复以上步骤 直至得到n个 2 2 2 例 求费用矩阵为下表的指派问题的最优解 工作 人 费用 ABCDE 甲乙丙丁戊 127979 89666 717121412 15146610 4107106 7 6 7 6 4 2 2 2 最优指派方案 甲做B工作 乙做C工作 丙做A工作 丁做D工作 戊做E工作 32 匈牙利法的具体步骤 第一步 变换指派问题的费用矩阵 使其在各行各列都出现0元素 方法 首先每行元素减去该行的最小元素 然后每列减去该列的最小元素 第二步 进行试指派 画 方法 从含0元素最少的行或列开始 圈出一个0元素 用 表示 然后划去该 所在的行和列中的其余0元素 用 表示 依次类推 若矩阵中的 的个数等于n 则得最优解 若矩阵中的 的个数 n 则进行第三步 第三步 做能复盖所有0元素的最小直线集合 1 对没有 的行打 号 2 对打 号的行上所有0元素的列打 号 3 再对打 号的列上所有 的行打 号 4 重复以上步骤直到得不出新的打 号为止 5 对没有打 号的行画横线 所有打 号的列画纵线 所得到的直线既是复盖所有0元素的最小直线集合 第四步 在没有被直线复盖的元素中找出最小元素 让打 号的列加上这个元素 打 号的行减去这个元素 转第一步 例 现有4份工作 4个人应聘 由于个人的技术专长不同 他们承担各项工作所需费用如下表所示 且规定每人只能做一项工作 每一项工作只能由一个人承担 试求使总费用最小的分派方案 工作 人 收费用 1234 1234 15182124 19232218 26171619 19212317 最优方案 第一个人做第一件事 第二个人做第四件事 第三个人做第三件事 第四个人做第二件事 总费用 70 4 一般的指派问题 1 求maxZ的指派问题 2 人数与工作数不等的指派问题 3 一个人可做几件事的指派问题 4 某事一定由 不能由 某人做的指派问题 收益 12 j n 12 i n 指派问题模型 i 1 2 n j 1 2 n 第i个人做第j人件事 Z表示总收益 i 1 2 n j 1 2 n 第i个人不做第j人件事 设有n个工作 要由n个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的收益 求总收益最大的指派方案 1 求maxZ的指派问题 工作 人 收益 12 j n 12 i n 指派问题最大化的数学模型 i 1 2 n j 1 2 n 指派问题最小化的数学模型 i 1 2 n j 1 2 n 用匈牙利法 i 1 2 n j 1 2 n i 1 2 n j 1 2 n 对maxZ的指派问题 工作 人 收益 12 j n 12 i n 用匈牙利法求C 例 现有4份工作 4个人应聘 由于个人的技术专长不同 他们承担各项工作的效益如下表所示 且规定每人只能做一项工作 每一项工作只能由一个人承担 试求使总效益最大的分派方案 工作 人 收益 1234 12797 7171214 151466 410710 1234 分派方案 第1个人第3项工作 第2个人第2项工作 第3个人第1项工作 第4个人第4项工作 总效益 9 17 15 10 51 2 人数与工作数不等的指派问题 设有n个工作 要由m个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的费用 求总费用最低的指派方案 a m n 工作 人 费用 12 j n 12 i m n 1n 2 m 用匈牙利法求解 例 现有4份工作 6个人应聘 由于个人的技术专长不同 他们承担各项工作所需时间如下表所示 且规定每人只能做一项工作 每一项工作只能由一个人承担 试求使总时间最少的分派方案 工作 人 时间 1234 123456 56 000000 000000 12797 7171214 151466 410710 6558 4576 分派方案 第3个人第4项工作 第4个人第1项工作 第5个人第3项工作 第6个人第2项工作 第1 2个人没工作 总时间 6 4 5 5 20 工作 人 费用 12 j n 12 i m m 1m 2 n b m n 用匈牙利法求解 3 一个人可做几件事的指派问题 设n个人中的第k个人可同时做t件事 把第k个人视为t个人 这t个人做同一件事的费用系数都一样 问题化为人数为n 1 t个人的指派问题 4 某人一定不能做某事的指派问题 如在minZ问题中 第k个人一定不能做第t件事 如在maxZ问题中 第k个人一定不能做第t件事 例 某商业公司计划开办五家新商店 为了尽早建成营业 商业公司决定由3家建筑公司分别承建 已知第Ai i 1 2 3 个建筑公司对第Bj j 1 2 3 4 5 家新商店的建造费用的报价如下表 为保证工程进度 每家建筑公司最多只能承建两个商店 且由于某种原因 第B3家商店不能由第A1个建筑公司承办 求使总费用最少的指派方案 商店 建筑公司 报价 B1B2B3B4B5 A1A2A3 4871512 79171410 691287 B1B2B3B4B5 A11A12A21A22A31A32 每家公司最多可承建两家商店 人数 工作数 B1B2B3B4B5B6 A11A12A21A22A31A32 B3不能由A1承办 50 50 B1B2B3B4B5B6 A11A12A21A22A31A32 由A1承建B1 B2 指派方案 由A2承建B5 由A3承建B3 B4 总费用 42 作业 6个人应聘4份工作 由于个人的技术专长不同 他们承担各项工作所获得的收益如下表 且规定每人只能做一项工作 每一项工作只能由一个人承担 试求使总收益最大的指派方案 工作 人 收益 1234 123456 3545 6768 89810 1010911 12111012 13121113 分派方案 第3个人第2项工作 第4个人第3项工作 第5个人第1项工作 第6个人第4项工作 第1 2个人没工作 第一步 变换费用矩阵 使其在各行各列都出现0元素 方法 每行减去该行的最小元素 然后每列减去该列的最小元素 第二步 进行试指派 画 方法 从含0元素最少的行或列开始 圈出一个0元素 用 表示 然后划去该 所在的行和列