搜档网
当前位置:搜档网 › 指派问题的匈牙利解法

指派问题的匈牙利解法

指派问题的匈牙利解法
指派问题的匈牙利解法

指派问题的匈牙利解法

1、 把各行元素分别减去本行元素的最小值;然后在此基础上再把每列元素减去本列中的最小值。

???????? ??????????? ?

?0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 06 10 12 9 610 6 14 7 67 8 12 9 610

14 17 9 712 15 7 8 4 此时每行及每列中肯定都有0元素了。

2、 确定独立零元素,并作标记。

(1)、首先逐行判断是否有含有独立0元素的行,如果有,则按行继续处理;如没有,则要逐列判断是否有含有独立0元素的列,若有,则按列继续处理。若既没有含有独立0元素的行,也没有含有独立0元素的列,则仍然按行继续处理。

(2)在按行处理时,若某行有独立0元素,把该0元素标记为a ,把该0所在的列中的其余0元素标记为b ;否则,暂时越过本行,处理后面的行。把所有含有独立0元素的行处理完毕后,再回来处理含有2个以及2个以上的0元素的行:任选一个0做a 标记,再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b 。

(3)在按列处理时,若某列有独立0元素,把该0元素标记为a ,把该0所在的行中的其余0元素标记为b ;否则,暂时越过本列,处理后面的列。把所有含有独立0元素的列处理完毕后,再回来处理含有2个以及2个以上的0元素的列:任选一个0做a 标记,再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b 。

(4)、重复上述过程,即得到独立零元素(标记a 的“0”)

???????? ??a b b a b b a 0

4 3 2 04 0

5 0 01 2 3 2 03

7 7 1 08 11 0 3 0a b 3、 若独立零元素等于矩阵阶数,则已经得到最优解,若小于矩阵阶数,则继续以下步骤:

(1)、对没有标记a 的行作标记c

(2)、在已作标记c 的行中,对标记b 所在列作标记c

(3)、在已作标记c 的列中,对标记a 所在的行作标记c

(4)、对没有标记c 的行划线,对有标记c 的列划线

???????

? ??04320405001232037710

811030 / / / / / \/ \/

4、 在未被直线覆盖的所有元素中找出一个最小元素(Xmin ),未被直线覆盖的行(或列)中所有元素都减去这个数。(注:若未被直线覆盖部分是行数<列数,则是按行减,反之则按列)。

???????

? ??--04320405000121126601

811030 5、 这样必然出现负元素,所以对负元素所在列(或行)中各元素都加上这一最小元素(Xmin )以消除负数。这样,再返回步骤2,确定独立零元素个数。

重复上述操作,直到找出最优解。

特殊问题:

1、

若人数和工作数不等,则用“0”来补全空位 2、 若一个人可作几件事,则可化为相同的“几个人”来接受指派,费用系数相同。 ????????? ??0 4 3 2 14 0 5 0 1 0 1 2 102 6 6 0 08 11 0 3 0/ / /

指派问题的匈牙利解法

指派问题的匈牙利解法 1、 把各行元素分别减去本行元素的最小值;然后在此基础上再把每列元素减去本列中的最小值。 ???????? ??????????? ? ?0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 06 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 4 此时每行及每列中肯定都有0元素了。 2、 确定独立零元素,并作标记。 (1)、首先逐行判断是否有含有独立0元素的行,如果有,则按行继续处理;如没有,则要逐列判断是否有含有独立0元素的列,若有,则按列继续处理。若既没有含有独立0元素的行,也没有含有独立0元素的列,则仍然按行继续处理。 (2)在按行处理时,若某行有独立0元素,把该0元素标记为a ,把该0所在的列中的其余0元素标记为b ;否则,暂时越过本行,处理后面的行。把所有含有独立0元素的行处理完毕后,再回来处理含有2个以及2个以上的0元素的行:任选一个0做a 标记,再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b 。

(3)在按列处理时,若某列有独立0元素,把该0元素标记为a ,把该0所在的行中的其余0元素标记为b ;否则,暂时越过本列,处理后面的列。把所有含有独立0元素的列处理完毕后,再回来处理含有2个以及2个以上的0元素的列:任选一个0做a 标记,再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b 。 (4)、重复上述过程,即得到独立零元素(标记a 的“0”) ???????? ??a b b a b b a 0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 0a b 3、 若独立零元素等于矩阵阶数,则已经得到最优解,若小于矩阵阶数,则继续以下步骤: (1)、对没有标记a 的行作标记c (2)、在已作标记c 的行中,对标记b 所在列作标记c (3)、在已作标记c 的列中,对标记a 所在的行作标记c (4)、对没有标记c 的行划线,对有标记c 的列划线 ??????? ? ??04320405001232037710 811030 / / / / / \/ \/

运筹学指派问题的匈牙利法实验报告

运筹学 课 程 设 计 报 告 专业: 班级: 学号: : 2012年6月20日

目录 一、题目。 二、算法思想。 三、算法步骤。 四、算法源程序。 五、算例和结果。 六、结论与总结。

一、题目:匈牙利法求解指派问题。 二、算法思想。 匈牙利解法的指派问题最优解的以下性质: 设指派问题的系数矩阵为C=()c ij n n?,若将C的一行(或列)各元素分别减去一个常数k(如该行或列的最小元素),则得到一个新的矩阵C’=()'c ij n n?。那么,以C’位系数矩阵的指派问题和以C位系数矩阵的原指派问题有相同最优解。 由于系数矩阵的这种变化不影响约束方程组,只是使目标函数值减少了常 数k,所以,最优解并不改变。必须指出,虽然不比要求指派问题系数矩阵中无 负元素,但在匈牙利法求解指派问题时,为了从以变换后的系数矩阵中判别能否 得到最优指派方案,要求此时的系数矩阵中无负元素。因为只有这样,才能从总 费用为零这一特征判定此时的指派方案为最优指派方案。 三、算法步骤。 (1)变换系数矩阵,使各行和各列皆出现零元素。 各行及各列分别减去本行及本列最小元素,这样可保证每行及每列中都有 零元素,同时,也避免了出现负元素。 (2)做能覆盖所有零元素的最少数目的直线集合。

因此,若直线数等于n,则以可得出最优解。否则,转第(3)步。 对于系数矩阵非负的指派问题来说,总费用为零的指派方案一定是最优指派方案。在第(1)步的基础上,若能找到n个不同行、不同列的零元素,则对应的指派方案总费用为零,从而是最优的。当同一行(或列)上有几个零元素时,如选择其一,则其与的零元素就不能再被选择,从而成为多余的。因此,重要的是零元素能恰当地分布在不同行和不同列上,而并在与它们的多少。但第(1)步并不能保证这一要求。若覆盖所有零元素的最少数目的直线集合中的直线数目是n,则表明能做到这一点。 此时,可以从零元素的最少的行或列开始圈“0”,每圈一个“0”,同时把位于同行合同列的其他零元素划去(标记为),如此逐步进行,最终可得n个位于不同行、不同列的零元素,他们就对应了最优解;若覆盖所有零元素的最少数目的直线集合中的元素个数少于n,则表明无法实现这一点。需要对零元素的分布做适当调整,这就是第(3)步。 (3)变换系数矩阵,是未被直线覆盖的元素中出现零元素。回到第(2)步。 在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行(或列)中各元素都减去这一最小元素,这样,在未被直线覆盖的元素中势必会出现零元素,但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元素,只要对它们所在的列(或行)中个元素都加上这一最小元素(可以看作减去这一最小元素的相反数)即可。 四、算法源程序。

指派问题的解法

指派问题的解法总结 问题引入:在工作的时候,常常需要对一些人进行工作安排,由于某些条件的限制, 每个人只能进行一种工作,怎么安排才能使得总工作时间最小。我们把这一类问题称 为指派问题。在这里,我只对人和工作刚好一对一的指派问题的解法进行总结,而对 于不是一对一的,则可以通过文献1中的一些方法进行变换。 目前问题解法的总结。 1:最广泛应用的解法:匈牙利算法。 算法简介:库恩(fW.W.Kuhn)于1955年提出了指派问题的解法.他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理:系数矩阵中独立0元素的最多个数等 于覆盖所有0元素的最少直线数。这个解法称为匈牙利解法。 匈牙利算法虽是运用最广泛的算法,但其操作过程却过于复杂。在划0的时候也不方 便记忆,对于初学者来说掌握不便。于是国内很多学者对指派问题给出了几个较简单,方便易记的算法。 2:指派问题新解法——目标值子矩阵法。 算法描述:任取变量矩阵X某一行中的最小元素,为该行元素目标值的最优解(但 不一定是系统目标函数的最优解),应该是系统目标函数满意解中的一个元素,记作 a11 划去a11 所在的行和列,取剩下的子矩阵中某一行的最小元素,记作a22。依次 类推,直到最后一个元素a nn.这些元素相加得系统目标函数的一个满意解,此为一 次运算.第二次运算取变量矩阵X中含a 以外的任一行,做与上面相同运算,又可以 得到系统的第二个满意解.相同地,对于n行做n次运算,共得到系统的n个满意解,系统的最优解即应该是这 n个满意解当中的最小值.若第i的最小元素在前面以被取 用过,则在进行第i的运算时,不选取该元素,取该行中未被选用过的元素中最小的一个进行运算。 算法分析:相对于匈牙利算法,此算法简单,方便操作。但不能给出所有最优解,得出的最优解唯一,若要给出全部最优解,则算法的次数将大大增加。 当矩阵维数较大的时候,可以对矩阵进行划分,以更快计算。 算法举例:对于变量矩阵x;

匈牙利法解决人数及任务数不等的指派问题

匈牙利法解决人数与任务数不等的指派问题 于凯 重庆科技学院经济管理学院物流专业重庆沙坪坝区 摘要:本文将讨论运筹学中的指派问题,而且属于非标准指派问题,即人数与任务数不相等的指派问题,应当视为一个多目标决策问题,首先要求指派给个人任务数目两两之间相差不能超过1,其次要求所需总时间最少,并且给出了该类问题的求解方法。 关键词:运筹学指派问题匈牙利算法系数矩阵解矩阵 引言:在日常的生产生活中常遇到这样的问题:有n项任务,有n个人员可以去承担这n 项任务,但由于每位人员的特点与专长不同,各对象完成各项任务所用的时间费用或效益不同;有因任务性质要求和管理上需要等原因,每项任务只能由一个人员承担来完成,这就涉及到应该指派哪个人员去完成哪项任务,才能使完成n项任务花费总时间最短,总费用最少,产生的总效益最佳。我们把这类最优匹配问题称为指派问题或分配问题。 1.指派问题的解法——匈牙利法 早在1955年库恩(,该方法是以匈牙利数学家康尼格(koning)提出的一个关于矩阵中0元素的定理为基础,因此得名匈牙利法(The Hungonrian Method of Assignment) 1.1匈牙利解法的基本原理和解题思路 直观的讲,求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。 而指派问题的最优解又有这样的性质:若从系数矩阵C(ij)的一行(列)各元素都减去该行(列)的最小元素,得到新矩阵CB(ij),那么以CB(ij)为系数矩阵求得的最优解和原系数矩阵C(ij)求得的最优解相同。 由于经过初等变换得到的新矩阵CB(ij)中每行(列)的最小元素均为“○”,因此求原指派问题C(ij)的最优方案就等于在新矩阵CB(ij)中找出n个分布于不同行不同列的“○”元素(简称为“独立○元素”),这些独立○元素就是CB(ij)的最优解,同时与其对应的原系数矩阵的最优解。 1.2匈牙利法的具体步骤 第一步:使指派问题的系数矩阵经过变换在各行各列中都出现○元素。 (1)先将系数矩阵的每行中的每个元素减去本行中的最小元素。 (2)再从系数矩阵的每列中的每个元素减去本列的最小元素。 第二步:进行试指派,以寻求最优解。 (1)从含有○元素个数最少的行(列)开始,给某个○元素加圈,记作◎,然后划去与◎所在同行(列)杂其他○元素,记作?。(注:从含元素 少的开始标记◎的原则) (2)重复进行(1)的操作,直到所有○元素都记作◎或?,称作“礼让原则”。 (3)按以上方法操作后,若◎元素数目m’等于矩阵阶数n,那么指派问题最优解已得到。若m﹤n,则转入下一步。 第三步:做最少的直线覆盖所有的○元素,以确定该系数矩阵中能找到最多的独立○元素。 (1)对没有◎的行打√号; (2)对已打√号的行中含有?元素所在的列打√号; (3)对已打√号的列中含有◎元素所在的行打√号; (4)重复(2)、(3)直到得不到新√号的行和列为止; (5)对没有√号的行画一横线,有√号的列画一竖线。如此便可以覆盖所有

匈牙利解法的步骤

指派问题的匈牙利法求解步骤: 1) 变换指派问题的系数矩阵(c ij)为(b ij),使在(b ij)的各行各列中都出现0元素,即 从(cij)的每行元素都减去该行的最小元素; 再从所得新系数矩阵的每列元素中减去该列的最小元素。 2) 进行试指派,以寻求最优解。 在(bij)中找尽可能多的独立0元素,若能找出n个独立0元素,就以这n个独立0 元素对应解矩阵(xij)中的元素为1,其余为0,这就得到最优解。 找独立0元素,常用的步骤为: 从只有一个0元素的行开始,给该行中的0元素加圈,记作◎。然后划去◎所 在列的其它0元素,记作?;这表示该列所代表的任务已指派完,不必再考虑别人了。依次进行到最后一行。 从只有一个0元素的列开始(画?的不计在内),给该列中的0元素加圈,记作◎; 然后划去◎所在行的0元素,记作?,表示此人已有任务,不再为其指派其他任务了。依次进行到最后一列。 若仍有没有划圈的0元素,且同行(列)的0元素至少有两个,比较这行各0元素所 在列中0元素的数目,选择0元素少这个0元素加圈(表示选择性多的要“礼让” 选择性少的)。然后划掉同行同列的其它0元素。可反复进行,直到所有0元素都已圈出和划掉为止。 若◎元素的数目m 等于矩阵的阶数n(即:m=n),那么这指派问题的最优解已 得到。若m < n, 则转入下一步。 3) 用最少的直线通过所有0元素。其方法: 对没有◎的行打“√”; 对已打“√”的行中所有含?元素的列打“√”; 再对打有“√”的列中含◎元素的行打“√”; 重复①、②直到得不出新的打√号的行、列为止; 对没有打√号的行画横线,有打√号的列画纵线,这就得到覆盖所有0元素的最 少直线数l 。 注:l 应等于m,若不相等,说明试指派过程有误,回到第2步,另行试指派;若 l=m < n,表示还不能确定最优指派方案,须再变换当前的系数矩阵,以找到n 个独立的0元素,为此转第4步。 4) 变换矩阵(b ij)以增加0元素 在没有被直线通过的所有元素中找出最小值,没有被直线通过的所有元素减去这 个最小元素;直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。

指派问题的算法

指派问题的算法分析与实现 摘要 在企业、公司的运营与管理中,管理者总是希望把人员最佳分派以发挥其最大工作效率,从而降低成本、提高效益。然而,如果没有科学的方法是很难实现优化管理的,由此我们引入了指派问题。指派问题多是求项目的工时最少,而很多情况下人们并不关心项目总工时的多少,而只关心项目能否在最短的时间内完成,即历时最少的指派问题。这类问题研究的是n个人执行n项任务,执行每项任务的人数以及总的指派人项数均有限制,要求最优指派。在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解,但指派问题也可以归结为一个0-1整数规划问题,本文先对指派问题进行陈述,引出对实际问题的求解。在指派问题的背景、描述中充分理解该问题,先运用匈牙利算法实现指派问题,然后再建立一个0-1整数规划模型,并运用matlab和lingo编译程序对问题进行编译,运用软件解决模型问题,最终实现指派问题在实际问题中的运用。通过运用匈牙利算法和0-1整数规划同时对指派问题求解,我们发现用0-1整数规划的方法来求解可以更简单,也更方便程序的阅读和理解。与此同时,我们还对0-1整数规划问题由整数数据深入研究到小数数据。最后通过实例来说明运用matlab,lingo编译程序来解决整数规划问题的简便和有效性。 关键词:指派问题;匈牙利算法;0-1整数规划;matlab模型;lingo模型1. 问题陈述 指派问题又称分配问题,其用途非常广泛,比如某公司指派n个人去做n 件事,各人做不同的事,如何安排人员使得总费用最少?若考虑每个职工对工作效率(如熟练程度等),怎样安排会使总销量达到最大?这些都是一个企业经营

管理者必须考虑的问题,所以该问题有重要的应用价值。 假设有n 件工作分派给n 个人来做,每项工作只能由一人来做,每个人只能做一项工作。若给出各人对各项工作所具有的工作效率。问应该如何安排人选,及发挥个人特长又能使总的效率最大。为此用0-1整数规划来实现指派问题即如何安排人选。 2.背景 在现实生活中,有各种性质的指派问题(Assignment Problem )。例如,在生产管理中,总希望把人员进行最佳分配,以发挥最大的工作效率;某部门有n 项任务要完成,而该部门正好有n 个人可以分别去完成其中任何一项,但由于任务性质和个人的专长不同,因此各人完成各项不同任务的效益(所费时间或所花费用)也有差别,如果分配每个人完成一项任务且仅为一项任务,则把每项任务分配给哪个人去完成,使完成所有n 项任务的总效益为最高(总时间、总费用为最小或创造的价值最大)?这是典型的分配问题或指派问题。又如有n 项加工任务,怎样指定n 台机器分别去完成,以使总的加工时间最少或总收入最大;有n 条航线,怎样指定n 艘船分别航行,使总收入最大,等等,都属于指派问题。 3. 指派问题的描述 3.1 指派问题的一般形式 指派问题的标准形式(以人和事为例)如下。有n 个人和n 项任务,已知第i 个人做第j 件事的费用为 ij c ,要求确定人和事之间的一一对应的指派方案,使 完成这n 项任务的费用最少。 一般把目标函数的系数写为矩阵形式,称矩阵 ? ? ? ? ?? ? ? ? ? ??????????==?nn n n n n n n ij c c c c c c c c c c C ..................)(212222111211 为系数矩阵(Coefficient Matrix ),也称为效益矩阵或价值矩阵。矩阵的元

浅析指派问题的匈牙利解法成稿讲解

浅析指派问题的匈牙利解法 胡小芹 数学科学学院数学与应用数学学号:040414057 指导教师:苏孟龙 摘要:对于指派问题,可以利用许多理论进行建模并加以解决,但匈牙利解法是解决指派问题的一种非常简单有效的方法,并且可以解决多种形式的指派问题,但匈牙利算法本身存在着一些问题,本文主要介绍了匈牙利算法的基本思想,基本步骤,以及它的改进方法.在匈牙利算法的基础上,本文还介绍了两种更简便实用的寻找独立零元素的方法——最小零元素消耗法和对角线法. 关键词:指派问题;匈牙利解法;最小零元素消耗法;对角线法 0 引言 在现实生活中经常会遇到把几个任务分派给几个不同的对象去完成,由于每个对象的条件不同,完成任务的效率和效益亦不同.指派问题的目标就是如何分派使所消耗的总资源最少(或总效益最优),如给工人分派工作,给车辆分配道路,给工人分配机床等等,同时许多网络问题(如旅行问题,任务分配问题,运输问题等),都可以演化成指派问题来解决.在现实生活中,指派问题是十分常见的问题,而匈牙利解法是解决指派问题的一种非常简单有效的方法.本文主要介绍匈牙利解法的基本原理及思想,解题步骤,不足与改进,以使匈牙利法更能有效地解决指派问题. 1 指派问题及其数学模型 指派问题是指由m项任务,需要n个人来承担,每人只能承担一项任务,且每项

任务只能有一人来承担,由于各人的专长不同,各人完成的任务不同,导致其效率也各不相同.因此,就产生怎样科学地指派任务,才能使完成各项任务所消耗的总资源最少(或总成本最低等),由于n m ,不同,指派问题可分为以下三种情况: 第一、当n m =时,即为每人指派一项任务. 第二、当n m >时,即任务数〉人数,这时可虚设)(n m -个人构成m m ?的 效率矩阵,并且这)(n m -个人在执行这m 项任务时的效率应该是效率最高. 第三、当n m <时,即配置人数〉任务数,这时应虚设)(m n -项任务,并且这n 个人在执行这)(m n -项任务时的成本最低. 通过虚设任务或人,指派问题的效率矩阵都可以转化成方阵.匈牙利解法要求指派问题最小化,其数学模型为 设用0ij c >(,1,2, ,)i j n =表示指派第i 个人去完成第j 项任务时所用的时间, 定义决策变量 10ij i j x i j ?=??表示第个人完成第项任务, 表示不指派第个人完成第项任务. 则问题可转化为0-1线性规划问题: ∑∑===n j ij n i c Z 11min t s ? 1 1 1,1,2,,, 1,1,2,,,01,i,j 1,2,,n n ij i n ij j ij x j n x i n x ==?==???==???==?? ∑∑或. 如果指派问题要求的是最大化问题如F max ,则可以转化为最小化问题,一般方法是:取max (,1,2 ),ij M c i j n ==令(,1,2,)ij ij b M c i j n =-=,则11 min ,n n ij i j f b ===∑∑,max F nM f F =-有从而求. 2 指派问题的解法——匈牙利解法

匈牙利算法在企业员工指派问题的应用(最终版)

闽江学院 本科毕业论文 题目匈牙利算法在企业员工指派问题的应用学生姓名张雯 学号120080901139 系别数学系 年级2008级 专业数学与应用数学 指导教师林耿 职称讲师 完成日期2012年4月10日

闽江学院毕业论文诚信声明书 本人郑重声明: 兹提交的毕业论文(设计)《匈牙利算法在企业员工指派问题的应用》,是本人在指导老师林耿的指导下独立研究、撰写的成果;论文(设计)未剽窃、抄袭他人的学术观点、思想和成果,未篡改研究数据,论文(设计)中所引用的文字、研究成果均已在论文(设计)中以明确的方式标明;在毕业论文(设计)工作过程中,本人恪守学术规范,遵守学校有关规定,依法享有和承担由此论文(设计)产生的权利和责任. 声明人(签名): 2012年4月10日

摘要 在当今社会,竞争无处不在,企业的竞争也是如此.而员工指派问题又是企业不得不面对的问题.因此,企业员工指派问题就显得非常重要了,谁能够在这方面做的好,谁就能在竞争中多一分胜算.企业员工指派问题是指企业安排若干人员去完成若干项任务(任务和人数不一定相等),并且要求完成的效率最高.对于这一问题,匈牙利算法就是一个很好的解法.本文首先给出企业员工指派问题的数学模型,它分为两大类,一类是标准指派问题(即企业指派员工数与任务数相等),另一类是非标准指派问题(即企业指派员工数与任务数不相等),其次,在对匈牙利算法及其原理深入理解的基础上,利用匈牙利算法对企业员工指派问题的数学模型进行求解.其中,用标准的匈牙利算法求解标准的指派问题,对于非标准的指派问题,先把它进行适当的变换,然后用标准的匈牙利算法求解.再次,讲述了匈牙利算法的一些缺点及其改进,把匈牙利算法用C语言表示出来,并把它运用到实际的企业员工指派问题当中.最后,讲述了匈牙利算法的应用推广. 关键词:匈牙利算法;员工指派问题;运筹学;效益矩阵

求解指派问题的匈牙利算法.doc

3.2 求解指派问题的匈牙利算法 由于指派问题的特殊性,又存在着由匈牙利数学家D.Konig 提出的更为简便的解法—匈牙利算法。算法主要依据以下事实:如果系数矩阵)(ij c C =一行(或一列)中每一元素都加上或减去同一个数,得到一个新矩阵)(ij b B = ,则以C 或B 为系数矩阵的指派问题具有相同的最优指派。 利用上述性质,可将原系数阵C 变换为含零元素较多的新系数阵B ,而最优解不变。若能在B 中找出n 个位于不同行不同列的零元素,令解矩阵中相应位置的元素取值为1,其它元素取值为零,则所得该解是以B 为系数阵的指派问题的最优解,从而也是原问题的最优解。 由C 到B 的转换可通过先让矩阵C 的每行元素均减去其所在行的最小元素得矩阵D ,D 的每列元素再减去其所在列的最小元素得以实现。 下面通过一例子来说明该算法。 例7 求解指派问题,其系数矩阵为 ????? ???????=16221917171822241819211722191516C 解 将第一行元素减去此行中的最小元素15,同样,第二行元素减去17,第三行元素减去17,最后一行的元素减去16,得 ????? ???????=06310157124074011B 再将第3列元素各减去1,得 ????? ???????=****20531005711407301B 以2B 为系数矩阵的指派问题有最优指派 ??? ? ??43124321 由等价性,它也是例7的最优指派。 有时问题会稍复杂一些。 例8 求解系数矩阵C 的指派问题

??????? ?????????=61071041066141512141217766698979712C 解:先作等价变换如下 ∨∨ ∨????????????????→????????????????----- 26360 40*089 57510*00*0032202*056107104106614151214121776669897971246767 容易看出,从变换后的矩阵中只能选出四个位于不同行不同列的零元素,但5=n ,最优指派还无法看出。此时等价变换还可进行下去。步骤如下: (1) 对未选出0元素的行打∨; (2) 对∨行中0元素所在列打∨; (3) 对∨列中选中的0元素所在行打∨; 重复(2)、(3)直到无法再打∨为止。 可以证明,若用直线划没有打∨的行与打∨的列,就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合,找出未覆盖的元素中的最小者,令∨行元素减去此数,∨列元素加上此数,则原先选中的0元素不变,而未覆盖元素中至少有一个已转变为0,且新矩阵的指派问题与原问题也等价。上述过程可反复采用,直到能选取出足够的0元素为止。例如,对例5变换后的矩阵再变换,第三行、第五行元素减去2,第一列元素加上2,得 ??????? ?????????0414******* 353800003420207 现在已可看出,最优指派为???? ??5314254321。

关于几种不平衡指派问题的修正匈牙利解法

龙源期刊网 https://www.sodocs.net/doc/0011649747.html, 关于几种不平衡指派问题的修正匈牙利解法作者:杜金玲;周杰 来源:《价值工程》2010年第13期 摘要:本文利用实例验证了在用匈牙利算法求解指派问题时,不平衡的指派问题转化为平衡指派问题的必要性;总结对于几种不平衡的指派问题转化为平衡指派问题的方法,从理论上作出解释,并给出了相应的例题,特别对于任务数多于人数的指派问题,本文提出了新的更有针对性的转化方法,如“一人化成p人法”、“加边补小法”、“加边补零(M)法”等。 Abstract: In this paper, the necessity of the transformation of the unbalanced assignment problem to the balanced assignment problem is tested with examples. The methods of transformation are summarized and explained from theory; and gived an example of the problem, especially, the methods of the transformation are brought up. For example, the method of "one to p persons", the method of "the adding rows with zero or M",the method of "the adding rows with min" and so on. 关键词:指派问题;匈牙利算法;一人化成p人法;加边补小法;加边补零(M)法 Key words: assignment problem;the Hungaryalgorithm;the method of "one to p persons";the method of "the adding rows with min";the method of “the adding rows with zero or M” 中图分类号:TP301.6文献标识码:A文章编号:1006-4311(2010)13-0120-03 0引言 在实际生活和生产安排中,经常遇到要指派不同的工作人员去完成不同的工作。由于每个 人的专长不同,不同的人去完成各项任务的效率(或所花时间或成本等)一般地也不同。这样,就 产生了指派何人去完成何任务,使总效率最高(或所花时间最少或成本最低等)的问题。这类问题称为指派问题(Assignment Problem),又称为分配问题。 1平衡指派问题的数学模型 对于有n项任务且恰好有n个人去完成的指派问题(称为平衡指派问题),规定每人只完成一项任务,且每项任务只能由一个人去完成。已知aij表示第i个人完成第j项任务时的效率(所用时间或成本等),[aij]称为效率矩阵。设决策变量: xij=1,第i个人完成第j项任务0,否则(i,j=1,2,…,n),于是指派问题的数学模型为: min z=aijxij

相关主题