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

分配问题指派问题与匈牙利法分配问题指派问题与匈牙利法分配问题的提出分配问题的提出若干项工作或任务需要若干个人去完成 由于每人的知识、能力、经验的不同，故各人完成不同任务所需要的时间不同（或其他资源） 问：应指派哪个人完成何项工作，可使完成所有工作所消耗的总资源最少？分配问题的提出设某公司准备派n个工人x1，x2，，xn，去作n件工作y1，y2，，yn 已知工人xi完成工作yj所需时间为cij(i,j=1,2,,n) 现问：如何确定一个分派工人去工作的方案，使得工人们完成工作的总时间为最少 台机床加工项任务；条航线有艘船去航行等 nnnn还比如：整体解题思路总结例题：工1工2工3工4工5工作14871512工作279171410工作3691287工作46714610工作56912106单位：小时标准形式的分配问题标准形式的分配问题分派方案满足下述两个条件：1.任一个工人都不能去做两件或两件以上的工作2.任一件工作都不能同时接受两个及以上的工人去做设某公司准备派n个工人x1，x2，，xn，去作n件工作y1，y2，，yn 已知工人xi完成工作yj所需时间为cij(i,j=1,2,,n)。

现问：如何确定一个分派工人去工作的方案，使得工人们完成工作的总时间为最少 标准形式的分配问题n个人n件事每件事必有且只有一个人去做每个人必做且只做一件事数学模型n个人n件事cij：第i人做第j事的费用xij1若指派第i人做第j事0若指派第i人不做第j事总费用：11nnijijijcxi，j1,.,nj1,.,ni1,.,nniijx11njijx11每件事必有且只有一个人去做每个人必做且只做一件事时间、原料、金钱等资源数学模型ninjijijxcz11minniijx11njijx11j1,.,ni1,.,n,...,n,i,jxij2110或s.t.线性规划问题运输问题0-1型整数规划问题匈牙利法1955年由美国数学家W.W.kuhn(库恩)提出，利用了匈牙利数学家D.Konig(康尼格)证明的2个定理 nnnnnncccccccccC....112222111211nnnnnnxxxxxxxxxX..................112222111211系数矩阵(效率矩阵)解矩阵(决策变量矩阵)n个人n件事定义：在系数矩阵C中，处在不同行不同列的一组零元素，称为独立零元素组，其中每个元素称为独立零元素。

0084765000320205C4431321243312412,,cccccccc44313241,cccc0100000110000010Xninjijijxcz11min最优解014丙085乙210甲CBA时工作间人员0丙7乙0甲时间458丙4129乙987甲CBA时工作间人员定理：若将分配问题系数矩阵的每一行及每一列分别减去各行及各列的最小元素，则新分配问题与原分配问题有相同的最优解，只有最优值差一常数 相关定理使每行每列都出现零元素步骤1：变换系数矩阵，使其每行每列都出现0元素把各行元素分别减去本行元素的最小值，然后在此基础上再把每列元素减去本列中的最小值 61012961061476781296101417971217840432040500123203771081103004630408101263037012081134066674min00310min此时每行及每列中肯定都有0元素步骤2：进行试分配，判断是否存在n个独立零元素尝试对所有零元素做标记，确定独立零元素 （1）逐行检验对只有一个未标记的零元素的行，用记号O将该零元素圈起，然后将被圈起的零元素所在列的其他未标记的零元素用记号/划去。

01370606905320100重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素为止 表示此人只能做该事（此事只能由该人做）表示此事已不能由其他人来做（此人已不能做其他事）04320405001232037710811030圈0即独立零元素步骤2：进行试分配，判断是否存在n个独立零元素尝试对所有零元素做标记，确定独立零元素 （2）逐行检验步骤2：进行试分配，判断是否存在n个独立零元素尝试对所有零元素做标记，确定独立零元素 （2）逐列检验与行检验类似：对只有一个未标记的零元素的列，用记号O将该零元素圈起，然后将被圈起的零元素所在行的其他未标记的零元素用记号/划去 重复列检验，直到没有未被标记的零元素或至少有两个未被标记的零元素为止 0137060690532010004320405001232037710811030圈0即独立零元素步骤2：进行试分配，判断是否存在n个独立零元素尝试对所有零元素做标记，确定独立零元素 （2）逐列检验可能出现三种情况1.每一行均有圈0出现，圈0的个数恰好等于n2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。

3.不存在未被标记过的零元素，但圈0的个数n可进行分配：令圈0位置的决策变量取值为1，其他为0（3）判断独立零元素的个数013706069053201000001010010000010可能出现三种情况2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个 3.不存在未被标记过的零元素，但圈0的个数n从某行（列）的两个未被标记过的零元素中任选一个加上圈，然后给同列、同行的其他未被标记的零元素都加/，然后再进行行、列检验，可能出现情况1或3 （3）判断独立零元素的个数502092300801057598004063600100000100100000001000001圈0个数等于n=5多重最优解502092300801057598004063605020923008010575980040636050209230080105759800406360可能出现三种情况3.不存在未被标记过的零元素，但圈0的个数n（3）判断独立零元素的个数圈0个数4n=5作最少直线覆盖当前所有零元素，便于下步增加独立零元素的个数 04320405001232037710811030定理：系数矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少线数。

由匈牙利数学家D.Konig(康尼格)所证明502023000567480050202230000105729800406365例：分别求下列矩阵中的独立零元素的最多个数 44独立零元素的个数最多：对不含圈0的行打；在打的行中，对所有零元素所在列打；在所有打的列中，对圈0所在行打；重复2,3步，直到不能打为止 对未打的每一行画一横线，对已打的每一列画一纵线，即得到覆盖当前0元素的最少直线集 04320405001232037710811030找未被直线覆盖的最小数字k；对矩阵的每行：当该行有直线覆盖时，令ui=0；当该行无直线覆盖时，令ui=k 04320405001232037710811030ui01100对矩阵的每列：当该列有直线覆盖时，令vj=-k；当该列无直线覆盖时，令vj=0 vj-1000004320405001232037710811030ui01100vj-1000004320405000121026600811030从原矩阵的每个元素aij中分别减去ui和vj，得到新元素再次寻找独立零元素04320405000121026600811030逐列检验100000100000001000100010061012961061476781296101417971215784原题：分配方案A=7+9+6+6+6=34再次寻找独立零元素04320405000121026600811030逐列检验000010100010000000100010061012961061476781296101417971215784分配方案B=7+9+7+6+6=35对不含圈0的行打；在打的行中，对所有零元素所在列打；在所有打的列中，对圈0所在行打；重复2,3步，直到不能打为止。

对未打的每一行画一横线，对已打的每一列画一纵线，即得到覆盖当前0元素的最少直线集 5020223000010572980040636550202230000105729800406365圈0个数4n=5找未被直线覆盖的最小数字k；对矩阵的每行：当该行有直线覆盖时，令ui=0；当该行无直线覆盖时，令ui=k ui00202对矩阵的每列：当该列有直线覆盖时，令vj=-k；当该列无直线覆盖时，令vj=0 vj-20000502022300001057298004063653414040089053800003220225从原矩阵的每个元素aij中分别减去ui和vj，得到新元素ui00202vj-20000502022300001057298004063653414040089053800003220225再次寻找独立零元素分配方案B00001001001000001000000103414040089053800003220225再次寻找独立零元素分配方案B0000101000100000010000010整体解题思路总结整体解题思路总结例题：人1人2人3人4人5工作14871512工作279171410工作3691287工作46714610工作56912106单位：小时整体解题思路总结61012961061476781296101417971215784例题：步骤1：变换系数矩阵，使其每行每列都出现0元素把各行元素分别减去本行元素的最小值，然后在此基础上再把每列元素减去本列中的最小值。

610129610614767812961014179712157840432040500123203771081103004630408101263037012081134066674min00310min此时每行及每列中肯定都有0元素04320405001232037710811030圈0即独立零元素步骤2：进行试分配，判断是否存在n个独立零元素尝试对所有零元素做标记，确定独立零元素 （2）逐行检验可能出现三种情况3.不存在未被标记过的零元素，但圈0的个数n（3）判断独立零元素的个数圈0个数4n=5作最少直线覆盖当前所有零元素，便于下步增加独立零元素的个数 04320405001232037710811030对不含圈0的行打；在打的行中，对所有零元素所在列打；在所有打的列中，对圈0所在行打；重复2,3步，直到不能打为止 对未打的每一行画一横线，对已打的每一列画一纵线，即得到覆盖当前0元素的最少直线集 04320405001232037710811030找未被直线覆盖的最小数字k；对矩阵的每行：当该行有直线覆盖时，令ui=0；当该行无直线覆盖时，令ui=k。

04320405001232037710811030ui01100对矩阵的每列：当该列有直线覆盖时，令vj=-k；当该列无直线覆盖时，令vj=0 vj-1000004320405001232037710811030ui01100vj-1000004320405000121026600811030从原矩阵的每个元素aij中分别减去ui和vj，得到新元素再次寻找独立零元素04320405000121026600811030逐列检验1000001000000010001000100610129610614767。