分配问题指派问题与匈牙利法.ppt

第5讲 分配问题（指派问题）与匈牙利法,分配问题的提出,分配问题的提出,若干项工作或任务需要若干个人去完成。由于每人的知识、能力、经验的不同，故各人完成不同任务所需要的时间不同（或其他资源）。,问： 应指派哪个人完成何项工作，可使完成所有工作所消耗的总资源最少？,分配问题的提出,设某公司准备派 n 个工人x1，x2，xn ，去作 n 件工作 y1，y2，yn。已知工人xi完成工作 yj 所需时间为cij (i,j=1,2,n)。 现问：如何确定一个分派工人去工作的方案，使得工人们完成工作的总时间为最少。,还比如：,整体解题思路总结,例题：,单位：小时,标准形式的分配问题,标准形式的分配问题,分派方案满足下述两个条件： 任一个工人都不能去做两件或两件以上的工作 任一件工作都不能同时接受两个及以上的工人去做,设某公司准备派 n 个工人x1，x2，xn ，去作 n 件工作 y1，y2，yn。已知工人xi完成工作 yj 所需时间为cij (i,j=1,2,n)。 现问：如何确定一个分派工人去工作的方案，使得工人们完成工作的总时间为最少。,标准形式的分配问题,n个人 n件事,每件事必有且只有一个人去做,每个人必做且只做一件事,数学模型,n个人 n件事,cij：第i人做第j事的费用,总费用：,i，j1, ., n,j1,.,n,i1,.,n,每件事必有且只有一个人去做,每个人必做且只做一件事,时间、原料、金钱等资源,数学模型,线性规划问题,运输问题,0-1型整数规划问题,匈牙利法,1955年由美国数学家W.W.kuhn(库恩)提出，利用了匈牙利数学家D.Konig(康尼格)证明的2个定理。,系数矩阵 (效率矩阵),解矩阵 (决策变量矩阵),n个人 n件事,定义：在系数矩阵C中，处在不同行不同列的一组零元素，称为独立零元素组，其中每个元素称为独立零元素。,最优解,定理：若将分配问题系数矩阵的每一行及每一列分别减去各行及各列的最小元素，则新分配问题与原分配问题有相同的最优解，只有最优值差一常数。,相关定理,使每行每列 都出现零元素,步骤1：变换系数矩阵，使其每行每列都出现0元素 把各行元素分别减去本行元素的最小值，然后在此基础上再把每列元素减去本列中的最小值。,此时每行及每列中肯定都有0元素,步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。,（1）逐行检验,对只有一个未标记的零元素的行，用记号O将该零元素圈起，然后将被圈起的零元素所在列的其他未标记的零元素用记号/划去。,重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素为止。,表示此人只能做该事 （此事只能由该人做）,表示此事已不能由 其他人来做 （此人已不能做其他事）,圈0即独立零元素,步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。,（2）逐行检验,步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。,（2）逐列检验,与行检验类似：对只有一个未标记的零元素的列，用记号O将该零元素圈起，然后将被圈起的零元素所在行的其他未标记的零元素用记号/划去。,重复列检验，直到没有未被标记的零元素或至少有两个未被标记的零元素为止。,圈0即独立零元素,步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。,（2）逐列检验,可能出现三种情况,1.每一行均有圈0出现，圈0的个数恰好等于n 2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素，但圈0的个数n,（3）判断独立零元素的个数,可能出现三种情况,2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素，但圈0的个数n,（3）判断独立零元素的个数,圈0个数等于n=5,多重最优解,可能出现三种情况,3.不存在未被标记过的零元素，但圈0的个数n,（3）判断独立零元素的个数,圈0个数4 n=5,定理：系数矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少线数。,例：分别求下列矩阵中的独立零元素的最多个数。,独立零元素 的个数最多：,对不含圈0的行打；,在打的行中，对所有零元素所在列打；,在所有打的列中，对圈0所在行打；,重复2,3步，直到不能打为止。,对未打的每一行画一横线，对已打的每一列画一纵线，即得到覆盖当前0元素的最少直线集。,找未被直线覆盖的最小数字k；,对矩阵的每行：当该行有直线覆盖时，令ui=0； 当该行无直线覆盖时，令ui=k。,对矩阵的每列：当该列有直线覆盖时，令vj=-k； 当该列无直线覆盖时，令vj=0。,从原矩阵的每个元素aij 中分别减去ui和vj，得到新元素,再次寻找独立零元素,逐列检验,原题：,分配方案A=7+9+6+6+6=34,再次寻找独立零元素,逐列检验,分配方案B=7+9+7+6+6=35,对不含圈0的行打；,在打的行中，对所有零元素所在列打；,在所有打的列中，对圈0所在行打；,重复2,3步，直到不能打为止。,对未打的每一行画一横线，对已打的每一列画一纵线，即得到覆盖当前0元素的最少直线集。,圈0个数4 n=5,找未被直线覆盖的最小数字k；,对矩阵的每行：当该行有直线覆盖时，令ui=0； 当该行无直线覆盖时，令ui=k。,对矩阵的每列：当该列有直线覆盖时，令vj=-k； 当该列无直线覆盖时，令vj=0。,从原矩阵的每个元素aij 中分别减去ui和vj，得到新元素,再次寻找独立零元素,分配方案B,再次寻找独立零元素,分配方案B,整体解题思路总结,整体解题思路总结,例题：,单位：小时,整体解题思路总结,例题：,步骤1：变换系数矩阵，使其每行每列都出现0元素 把各行元素分别减去本行元素的最小值，然后在此基础上再把每列元素减去本列中的最小值。,此时每行及每列中肯定都有0元素,圈0即独立零元素,步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。,（2）逐行检验,可能出现三种情况,3.不存在未被标记过的零元素，但圈0的个数n,（3）判断独立零元素的个数,圈0个数4 n=5,对不含圈0的行打；,在打的行中，对所有零元素所在列打；,在所有打的列中，对圈0所在行打；,重复2,3步，直到不能打为止。,对未打的每一行画一横线，对已打的每一列画一纵线，即得到覆盖当前0元素的最少直线集。,找未被直线覆盖的最小数字k；,对矩阵的每行：当该行有直线覆盖时，令ui=0； 当该行无直线覆盖时，令ui=k。,