Chapter 6.5 指派问题3.ppt

◎ ? ? ◎ ? ? ◎ ? ◎ ? ◎ ◎ ? ? ◎ ? ? ◎ ? ◎ ? ◎ 用匈牙利法求解下列指派问题，已知效率矩阵分别如下： 指派 问题（Assignment Problem , AP）是一种特殊的线性规划问题，也属于 0-1 整数规划问题 . 5.5 指派问题 问题描述：在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。 x3 x1 x2 y2 y1 y3 x4 x5 y4 y5 该问题也可用矩阵表示 如果 xi 会做 yj 否则 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 在矩阵中寻找什么？ 寻找最多的不同行不 同列的 1 元素. 指派问题的数学模型 设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j 件工作的的效率（ 时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij ≥0。问应如何分配才能使总效率（ 时间或费用）最高？ 任务 人员 E J G R A 2 15 13 4 B 10 4 14 15 C 9 14 16 13 D 7 8 11 9 Example 有一份中文说 明书需要译成英、日、德、 俄四种语言，分别记为 E、 J、G、R . 现有 A、B、C、 D 四人，他们将中文翻译 成不同语言所需时间如表, 问应分配何人去完成何任务（一人完成一项任务），使所需总时间最少？ 设决策变量 1 分配第i 个人去做第j 件工作 xij = 0 相反 ( i,j=1.2. …n ) 其数学模型为： 显然，这是一个 0-1 规划问题， 也是一个 特殊的运输问题 任务 人员 E J G R ai A 2 15 13 4 1 B 10 4 14 15 1 C 9 14 16 13 1 D 7 8 11 9 1 bj 1 1 1 1 所以,分配问题可用解IP 问题方法（如：分 支定界法), 或解运输问题的表上作业法. 由于算法引用了匈牙利数学家 K?nig 的结论,所以，该算法也称为匈牙利算法 . Theorem 如果从效益矩阵 (cij) 的第 i 行中每个元素减去 a 和第 j 列中每个元素加上 b ，得到一个新的效益矩阵(cij)*.则以(cij)*为新的目标函数与原目标函数的指派问题最优解相同 . 匈牙利算法： Step 1 使效益矩阵各行各列出现零元素； 具体：从效益矩阵的每行各元素减去该行最小元素； 再从所得矩阵的每列各元素减去该列最小元素 . 第二步：画最少0元素的覆盖线，求维数r,检验是否能找到最优解； 当维数r =矩阵阶数时，则已能找到最优解，转第四步； 当维数r 矩阵阶数时，则还不能找到最优解，转第三步； =28 每行每列有零元素，能保证有 n 个独立零元素吗？ R=4=n,则已得到最优解； Zmin= 第三步：调整0元素的分布后，重复第二步。 调整0元素分布的步骤： （1）在未被直线覆盖的元素中找出最小数，记a;（2）将未被直线覆盖的元素减去a; （3）仅被一条直线覆盖的元素不变； （4）同时被两条直线覆盖的元素加上a. 第四步：找出n个独立的0元素，确定最优解。 要强调的是匈牙利法要求人数与任务数相等，且目标函数必须极小化。当人数与任务数不等，目标函数为极大化时，必须进行适当处理后才能用匈牙利法求解。 ? 任务 人员 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 例6.11 有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如表所示。问指派哪个工人去完成哪项工作，可使总的消耗时间最小？ 求解过程如下： 第一步，变换系数矩阵： 第三步，作最少的直线覆盖所有0元素： 独立零元素的个数m等于最少直线数l，即l＝m=3n=4； 第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1, 得到3个独立零元素，再调整 线的条数4=阶数4，因此能找到最优解： 总时间=15+22+16+