指派问题与运筹4-27 .ppt

匈牙利法的步骤 4.继续变换系数矩阵 1 3 0 11 8 0 0 6 6 2 0 1 2 1 0 1 0 5 0 4 1 2 3 4 0 （1）未被覆盖的元素中减去最小元素，出现新的0元素 （2）打√列中各元素都加上最小元素。 匈牙利法的步骤 5.重新寻找独立0元素 1 3 0 11 8 0 0 6 6 2 0 1 2 1 0 1 0 5 0 4 1 2 3 4 0 匈牙利法的步骤 5.重新寻找独立0元素 1 3 ◎ 11 8 φ◎ 6 6 2 ◎ 1 2 1 φ 1 φ 5 ◎ 4 1 2 3 4 ◎ X=(xij )n×n= 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 恰有N个人完成N个任务，每人完成一项 匈牙利算法给出了这种寻找的方法，下面先给出匈牙利算法基本思想 新的效率矩阵下的目标函数值 新的效率矩阵下的目标函数值 按不同的方式找，可能对不同行不同列的0元素有不同的答案，取其最大值 按不同的方式找，可能对覆盖0元素的直线数也有不同的答案，取其最小值 实际上，就是只要表中含有不同行一不同列的0元素，都可以通过线覆盖的方式来找到它们 这样必得到各行都有0元素的矩阵了，但它们是否还分列于不同列，对于大型矩阵显然不能通过观察得到结论，这就需要一个统一的算法，即定理2 对应７９ 无线减，双线加，单线不减也不加 对应２６ 行有多个０时不能选，因为最小直线数 ◎ ? ◎ ? ◎ ? ◎ ? √ √ √ √ √ √ √ ◎ ? ◎ ? ◎ ? ◎ ? √ √ √ √ √ √ √ -1 +1 +1 +1 -1 -1 -1 ◎ ? ? ◎ ? ? ◎ ? ◎ ? ◎ 此问题有多个最优解 ◎ ? ? ◎ ? ? ◎ ? ◎ ? ◎ ◎ ? ? ◎ ? ? ◎ ? ◎ ? ◎ 练习2:　有一份中文说明书，需译成英、日、德、 俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ 任务 人员 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 求解过程如下： 第一步，变换系数矩阵： －5 第二步，试指派： ◎ ◎ ◎ ? ? 找到 3 个独立零元素 但 m = 3 n = 4 第三步，作最少的直线覆盖所有0元素： ◎ ◎ ◎ ? ? √ √ √ 独立零元素的个数m等于最少直线数l，即l＝m=3n=4； 第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派： 得到4个独立零元素， 所以最优解矩阵为： ◎ ◎ ◎ ? ? √ √ √ ◎ ◎ ◎ ? ? 15 ◎ ◎ ◎ ? ? ◎ 在实际应用中，经常遇到非标准形式的指派问题。处理方法： 化标准，再按匈牙利算法求解。 三、非标准形指派问题 1. 最大化指派问题 目标函数变为： a)上述目标函数等价于： b)应用定理一，将之化为标准形：设最大化分配问题效率矩阵A=[aij],其中最大元素为m。令B= [bij]=[m+(-aij)] =[m-aij], 则以B为系数矩阵的最小化指派问题和以A为系数矩阵的原最大化指派问题有相同最优解。 最大化指派问题 例: 有4种机械要分别安装在4个工地，它们在4个工地工作效率（见下表）不同。问应如何指派安排，才能使4台机械发挥总的效率最大？ 工地 机器 甲 乙 丙 丁 Ⅰ Ⅱ Ⅲ Ⅳ 30 25 40 32 32 35 30 36 35 40 34 27 28 43 32 38 解：设最大化的指派问题系数阵