当前位置：文档之家 › 匈牙利算法示例ppt

匈牙利算法示例ppt

  • 格式：ppt
  • 大小：145.50 KB
  • 文档页数：19

下载文档原格式

  / 19

合集下载

匈牙利算法

匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。

美国数学家哈罗德·库恩于1955年提出该算法。

此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。

匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

二分图：二分图又称作二部图，是图论中的一种特殊模型。

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

图一就是一个二分图。

匈牙利算法：匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。

匈牙利算法是基于Hall定理中充分性证明的思想，它是一种用增广路径求二分图最大匹配的算法。

Hall定理：二部图G中的两部分顶点组成的集合分别为X, Y; X={X1, X2, X3,X4, .........,Xm}, Y={y1, y2, y3, y4 , .........,yn}, G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻。

（1≤k≤m)匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

图一中红线为就是一组匹配。

未盖点：设Vi是图G的一个顶点，如果Vi 不与任意一条属于匹配M的边相关联，就称Vi 是一个未盖点。

如图一中的a 3、b1。

设P是图G的一条路，如果P的任意两条相邻的边一定是一条属于M而另一条不属于M，就称P是一条交错路。

匈牙利算法示例ppt

匈牙利算法示例ppt
(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划 去◎ 所在列(行)的其它0元素，记作Ø ；这表示这列所代表的任务已指派完， 不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎ 所在 行的0元素，记作Ø ． (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。
•
非标准型的指派问题：
匈牙利法的条件是：模型求最小值、效率cij≥0。 当遇到各种非标准形式的指派问题时，处理方法是先将 其转化为标准形式， 1、人数和事数不相等的指派问题：人少事情多，虚拟 “人”，做各事的费用系数为0；人多事情少，虚拟 “事”，各人做的费用系数为0。 2、对于求极大化的问题，只要系数矩阵变换为B＝（mcij）nn，仍可利用匈牙利算法进行求解。 3、一个人可以做几件事情的指派问题：可以将该人化 作相同的几个“人”来接受指派，费用一样。 4、某事一定不能由某人做的指派问题，费用系数为“ M” 然后用匈牙利法来求解。
2 0 2 4 5
-0 -0 -0 -0 -0
第二步：进行试指派，以寻求最优解。 在 (bij) 中找尽可能多的独立 0 元素，若能找出 n 个 独立 0元素，就以这 n个独立 0元素对应解矩阵 (xij)中的 元素为1，其余为0，这就得到最优解。找独立0元素， 常用的步骤为：
0 0 1 0 0
或
0 0 0 0 1
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0
解矩阵得到2个最优指派方案；（1）甲-B，乙-C， 丙--E，丁-D,戊-A；（2）甲-B，乙-D，丙-E,丁-C， 戊-A。所需时间为minz=7+6+9+6+4=32

指派问题的匈牙利法ppt

指派问题的匈牙利法ppt
判断就是否为最优解:圈起得零得个数就是否等 于n。
确定调整行与列
在没有圈起得零所在行上打“√”; 在打“√”行中所有零所在得列打“√”; 在打“√”列中含有圈起零得行上打“√”, 反复执行2)与3)两步,直到不能打“√”为止; 用直线划去打“√”得列与不打“√”得行,没有
划去得行构成调整得行,划去得列构成调整列。
调整可行解得方法
在调整行中寻找最小得元素,将它作为调整 量;
将调整行各元素减去调整量,对调整列中各 元素加上调整量。
再次执行“圈零”与“划零”得操作,并循 环以上得步骤,直到圈起得零数等于n为止。
匈牙利法解例3、3
时间矩阵
2 10 3 7
15
4
14
8
13 14 16 11
4
7
13
任务
人员
A
B
C
D
甲
6
7
11
2
乙
4
5
9
8
丙
3
1
10
4
丁
5
9
8
2
求解过程如下:
第一步,变换系数矩阵:
6 7 11 2 2
(cij
)
4 3
5 1
9 10
8 4 4 1
5 9 8 2 2
4 5 9 0 0 1 5 4 2 0 9 3 3 7 6 0
4 5 4 0 0 1 0 4 2 0 4 3 3 7 1 0
0元素,就以这n个独立0元素对应解矩阵(xij)中得元素为1, 其余为0,这就得到最优解。找独立0元素,常用得步骤为:
(1)从只有一个0元素得行(列)开始,给这个0元素加圈, 记作◎ 。然后划去◎ 所在列(行)得其它0元素,记作Ø ; 这表示这列所代表得任务已指派完,不必再考虑别人了。

ppt19 匈牙利算法与最优匹配算法

ppt19 匈牙利算法与最优匹配算法

y4
y5
(c) y2为M非饱和点，加上y2和边x3y2生长树H。此 时，置M=MΔE(P)=｛x1y1, x2y3, x3y2｝
x1 y2 x2 x3 x4 x5
x3
y1
y2
y3 G=(X, Y)
y4
y5 10
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
15
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
定义2 设G=(X, Y), 若对任意的x ∈X, y ∈Y,有：
l ( x ) l ( y ) w ( xy )
称 l 是赋权完全偶图G的可行顶点标号。 对于任意的赋权完全偶图G，均存在G的可行顶点标号。 事实上，设：
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
2) 若 T N (S ) 令y ∈N(S) – T, 则在树H中存在点x与y邻接。因为H的所有 点，除u外，均在M下配对。所以，或者x = u，或者x与H的某 xy M 一顶点配对，但无论哪种情况，都有
w ( M *)
eM *

w(e)
vV ( G )

l (v )
又设M是G的任一完美匹配，则：
w( M )
eM
w(e)
l (v )
vV ( G )
所以，w (M*)≥w (M)。即M*是G的最优匹配。
18
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
w ( xy ), 若 x X , l ( x ) max yY l ( y ) 0, 若 y Y .

指派问题与匈牙利算法

指派问题与匈牙利算法
5 11 8 6 3 9 6 14 4 2 10 3 17 5 1 5 11 8 6 3 9 6 14 4 2 10 3 17 5 1 0 0 0 0 0 0 0 0 0 0
当人数m小于工作数n时，加上n－m个人，例如
7 0 C ′＝ 8 4
0 19 2 8 17 0 7 11 0 0 10 2
0 9 2 8 7 0 7 1 0 0 0 2
1 1 最优解： 最优解： X＝ 1 1
即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项。 总分为： ＝ ＋ ＋ ＋ ＝ 总分为：Z＝92＋95＋90＋80＝357
§5.5 指派问题 Assignment Problem
Ch5 Integer Programming
2011年5月9日星期一 Page 6 of 12
用匈牙利法求解：
10 3 22 0 8 17 C ′＝ 13 12 16 9 5 15 7 0 C ′＝ 8 4
5 0 5 7
则 与
′ m w = ∑∑cij xij in
i j
m z = ∑∑cij xij ax
i j
的最优解相同。
§5.5 指派问题 Assignment Problem
Ch5 Integer Programming
2011年5月9日星期一 Page 5 of 12
【例】某人事部门拟招聘4人任职4项工作，对他们综合考评的 例 得分如下表（满分100分），如何安排工作使总分最多。
2011年5月9日星期一 Page 4 of 12
求最大值的指派问题 匈牙利法的条件是：模型求最小值、效率cij≥0 设C=(cij)m×m 对应的模型是求最大值 将其变换为求最小值 令

匈牙利算法示例

匈牙利算法示例

0 0 0 1 1 0 0 0
15
3 ◎ 2 2
3 ◎ Ø 5 1 ◎ 4 4 6 ◎ Ø 4
得到4个独 立零元素， 所以最优解 矩阵为：
练习：
费 工作 用 人员
A
7
B
5
C
9
D
8
E
11
甲
乙
丙 丁 戊
9
8 7 4
12
5 3 6
7
4 6 7
11
6 9 5
0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2
4 2
0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0
Ø 0 0 13 7 ◎ 6 0 6 9 ◎ ◎ 0 5 3 2 ◎ Ø 0 0 1 0 Ø
0 0 1 0
0 0 1 1 0 0 0 0 0 0 1 0
例二、 有一份中文说明书，需译成英、日、德、俄四种 文字，分别记作A、B、C、D。现有甲、乙、丙、丁四 人，他们将中文说明书译成不同语种的说明书所需时 间如下表所示，问如何分派任务，可使总时间最少？
任务
人员
例一：
任务
人员
A 2
10 9 7
B 15
4 14 8
C 13
14 16 11
D 4
15 13 9
甲
乙 丙 丁
2 10 9 7
15 13 4 4 14 15 14 16 13 8 11 9
2 4
9
7
0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2
2 2 4 4 ◎ 0

二分图匹配(匈牙利算法)


KM算法
对于任意的G和M,可行顶标都是存在的: l(x) = maxw(x,y) l(y) = 0 欲求完全二分图的最佳匹配,只要用匈牙利算法求 其相等子图的完备匹配;问题是当标号之后的Gl无 完备匹配时怎么办?1957年(居然比匈牙利算法 早???),Kuhn和Munkras给出了一个解决该问 题的有效算法,用逐次修改可行顶标l(v)的办法使对 应的相等子图之最大匹配逐次增广,最后出现完备 匹配.
例题3 打猎 猎人要在n*n的格子里打鸟,他可以在某一行 中打一枪,这样此行中的所有鸟都被打掉, 也可以在某一列中打,这样此列中的所有鸟 都打掉.问至少打几枪,才能打光所有的鸟? 建图:二分图的X部为每一行,Y部为每一列, 如果(i,j)有一只鸟,那么连接X部的i与Y部的j. 该二分图的最大匹配数则是最少要打的枪数.
1 2 3 4 5
1 2 5 3 4
1
2
3
4
由于每条边表示一个空地,有冲 突的空地之间必有公共顶点,所 以问题转化为二部图的最大匹配 问题.
1 2Leabharlann 34例题1 Place the Robots(ZOJ) 小结
比较前面的两个模型:模型一过于简单,没有给问 题的求解带来任何便利;模型二则充分抓住了问题的内 在联系,巧妙地建立了二部图模型.为什么会产生这种 截然不同的结果呢?其一是由于对问题分析的角度不同: 模型一以空地为点,模型二以空地为边;其二是由于对 原型中要素的选取有差异:模型一对要素的选取不充分, 模型二则保留了原型中"棋盘"这个重要的性质.由此 可见,对要素的选取,是图论建模中至关重要的一步.
例题4 最小路径覆盖 一个不含圈的有向图G中,G的一个路径覆盖 是一个其结点不相交的路径集合P,图中的每 一个结点仅包含于P中的某一条路径.路径可 以从任意结点开始和结束,且长度也为任意 值,包括0.请你求任意一个不含圈的有向图 G的最小路径覆盖数. 理清一个关系:最小路径覆盖数=G的定点 数-最小路径覆盖中的边数

匈牙利算法详解

大意：已知两个图和两个图中的点和边的连接情况，求两个图中最多能连接的边的数目。

（每个点最多只能连接一条边）分析：算法总体可以采用类似于探索的方法，例如下面的这个图。

CADBE如这个有向图，共有5个结点A、B、C、D、E，A、B作为第一张图，C、D、E作为第二张图。

第一次DFS时先看A连接的点（顺序查找）是否已经有爹了，发现没有，那么爹变成了A，同时A的匹配找到了。

再找B的匹配，发现C已经有爹了即A，那么就试探A的下一个连接点发现没有爹且能与B相连，那么B的匹配也找到了，依次类推直到推到最后。

代码：function dfs(x:longint):boolean;vari:longint;beginif use[x] then exit(false);{如果出现某个点访问过返回false。

}use[x]:=true;{同时标记为已访问过。

}for i:=1 to m dobeginif (b[x,i]) and ((link[i]=0) or (dfs(link[i]))) then{如果要连的点还没爹可以连，或者是它的爹的所连的点还有剩余就可以继续（前提是必须可以相连）。

}beginlink[i]:=x;{修改爹。

}exit(true);end;end;exit(false);end;procedure XYL;vari:longint;beginfor i:=1 to n do{先进行查找。

}beginfillchar(use,sizeof(use),false);{初始化每个点都未访问过以便遍历图。

}if dfs(i) then inc(ans);{返回true说明可以匹配。

}end;writeln(ans);end;。

匈牙利算法（二分图）

匈⽛利算法（⼆分图）---------------------------------------------------------------------题材⼤多来⾃⽹络，本篇由神犇整理基本概念—⼆分图⼆分图：是图论中的⼀种特殊模型。

若能将⽆向图G=(V,E)的顶点V划分为两个交集为空的顶点集，并且任意边的两个端点都分属于两个集合，则称图G为⼀个为⼆分图。

匹配：⼀个匹配即⼀个包含若⼲条边的集合，且其中任意两条边没有公共端点。

如下图，图3的红边即为图2的⼀个匹配。

1 最⼤匹配在G的⼀个⼦图M中，M的边集中的任意两条边都不依附于同⼀个顶点，则称M是⼀个匹配。

选择这样的边数最⼤的⼦集称为图的最⼤匹配问题,最⼤匹配的边数称为最⼤匹配数.如果⼀个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

如果在左右两边加上源汇点后，图G等价于⼀个⽹络流，最⼤匹配问题可以转为最⼤流的问题。

解决此问的匈⽛利算法的本质就是寻找最⼤流的增⼴路径。

上图中的最⼤匹配如下图红边所⽰：2 最优匹配最优匹配⼜称为带权最⼤匹配，是指在带有权值边的⼆分图中，求⼀个匹配使得匹配边上的权值和最⼤。

⼀般X和Y集合顶点个数相同，最优匹配也是⼀个完备匹配，即每个顶点都被匹配。

如果个数不相等，可以通过补点加0边实现转化。

⼀般使⽤KM算法解决该问题。

3 最⼩覆盖⼆分图的最⼩覆盖分为最⼩顶点覆盖和最⼩路径覆盖：①最⼩顶点覆盖是指最少的顶点数使得⼆分图G中的每条边都⾄少与其中⼀个点相关联，⼆分图的最⼩顶点覆盖数=⼆分图的最⼤匹配数；②最⼩路径覆盖也称为最⼩边覆盖，是指⽤尽量少的不相交简单路径覆盖⼆分图中的所有顶点。

⼆分图的最⼩路径覆盖数=|V|-⼆分图的最⼤匹配数；4 最⼤独⽴集最⼤独⽴集是指寻找⼀个点集，使得其中任意两点在图中⽆对应边。

对于⼀般图来说，最⼤独⽴集是⼀个NP完全问题，对于⼆分图来说最⼤独⽴集=|V|-⼆分图的最⼤匹配数。

匈牙利算法示例ppt


0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0
解矩阵得到2个最优指派方案；（1）甲-B，乙-C， 丙--E，丁-D,戊-A；（2）甲-B，乙-D，丙-E,丁-C， 戊-A。所需时间为minz=7+6+9+6+4=32
3 匈牙利法的改进
实际上很多效率矩阵用上述匈牙利法进行求解时必 须经要经历第（3）和第（4），但在这些效率矩阵 中有很大部分用改进后的匈牙利法就不需要经历第 （3）和第（4）步即可求解。
12 7 9 7 9
8
9
6
6
6
7 17 12 14 9
15 14 6 6 10
4 10 7 10 9
Min
4
7
66
6
从上面可以看到列中最小个数之和为7，而行中最小个数之 和为9,。即应该先从系数矩阵的每列元素中减去该列的最小 元素。
8 0 3 1 3 0
4
2
0 0 0 0
3 10 6 8 3 3 11 7 0 0 0 0
或
4
Ø
2 7
◎
3
Ø
5
◎Ø
◎ 11
7 3
Ø ◎ Ø
1 4 3
它具有n个独立0元素，这就得到了最优解，相应的解矩阵为
0 1 0 0 0
0 1 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 1 0 0 1 0 0
或
0 0 0 0 1 0 0 0 1 0
1 0 0 0 0
1 0 0 0 0
7 ◎ 2 Ø 2
7 ◎ 2 Ø 24ຫໍສະໝຸດ Ø3 8◎
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

8 0 3 1 4 2 0 0 3 10 6 8 11 7 0 0 0 3 1 4
3 0 3 0 3
0 0
3 0 0
8 4 0 11 0
0 3 1 3 2 0 0 0 7 3 5 0 7 0 0 0 3 1 4 3
5 0 2 0 2 3 0 0 0 10 5 7 9 8 0 0 0 6 3 6
2 0 2 4 5
5 2 ◎ 9 Ø
◎
3 10 8 6
2 Ø Ø ◎ 5 7 2 ◎ Ø 4 3 6 5 2
Ø
第三步；作最少的直线覆盖所有0元素，以确 定该系数矩阵中能找到最多的独立元素数。 （1）对没有◎的行打√ （2）在已经打√的行中所含有的0元素打√号（3） √ 在已经打√号的列中含◎元素的行打√；（4）重复 （2）（3）直到得不出打√的行列为止（5）对没有 打√的行画一横线，有打√的列画一纵线，这就覆盖 所有0元素的最少直线数。令这一直线数为l。若 l<n,说明必须再换当前的系数矩阵，才能找到n个 独立的0元素，为此转到第四步；若l=n，而m<n， 应回到（2）（4）另行试探。
再从得到系数矩阵的每行元素中减 去该行的最小元素。
根据匈牙利法第二步，很容易得到下面的矩 阵
8 4 Ø 11
◎3
◎
1 3 2 Ø Ø 7 3 5 7 ØØ 3 1 4 3
◎ ◎ 或 ◎
8 4 Ø 11
◎
◎ 3 1 3 2 ◎Ø Ø 7 3 5 ◎ 7 Ø ◎Ø
（1）；查看每行的最小元素的个数总和r和每列的最小元素 的个数总和c。并比较r和c的大小。 （2）使指派问题的系数矩阵经变换，在各行各列中都出现0元 素。当r≥c，则先从系数矩阵的每列减去该列的最小元素，再从 所得系数矩阵的每行元素中减去该行的最小元素。反之如果当 r≤c，则先从系数矩阵的每行中减去该行的最小元素，再从所得 系数矩阵的每行元素中减去该列的最小元素。其他步奏同匈牙利 法。
bij
12 8 (cij ) 7 15 4
7 9 17 14 10
9 7 9 6 6 6 12 14 9 6 6 10 7 10 9
5 0 2 0 2 3 0 0 0 10 5 7 9 8 0 0 0 6 3 6
2 0 2 4 5
由解矩阵得到2个最优指派方案；（1）甲-B， 乙-D，丙-E，丁-C，戊-A；(2)甲-B，乙-C，丙E，丁-C，戊-A。所需总时间 Minz=7+6+9+6+4=32
4 结论
• a 改进后的匈牙利法比原来的匈牙利法大大 减少了计算量，并节省了一些很累赘的步 骤，在实际工作中可以为决策者与决策团 队节约宝贵的时间以及信息的时效性。 • b 2种方法计算结果完全一致，说明改进的 匈牙利法可以达到与原匈牙利法一样的效 果。 • c即使遇上了少数改进的匈牙利法无法改进 的系数矩阵时，也可按原匈牙利法的步骤 进行解析，不影响结果的正确性。
解矩阵得到2个最优指派方案；（1）甲-B，乙-C， 丙--E，丁-D,戊-A；（2）甲-B，乙-D，丙-E,丁-C， 戊-A。所需时间为minz=7+6+9+6+4=32
3 匈牙利法的改进
实际上很多效率矩阵用上述匈牙利法进行求解时必 须经要经历第（3）和第（4），但在这些效率矩阵 中有很大部分用改进后的匈牙利法就不需要经历第 （3）和第（4）步即可求解。
要求每人做一项工作，约束条件为
x
j 1
n
ij
1
(i 1, 2, , n)
要求每项工作只能安排一人，约束条件为
x
i 1
n
ij
1
( j 1, 2, , n)
变量约束为
xij 0或1
(i, j 1, 2,3, 4)
下表所示效率矩阵的指派问题
时间 任务 人员
A
12 8 7
上面矩阵有5个独立0元素，这就得到相应的最优解。
0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0
或
0 0 0 0 1
1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
11
7 x12 9 x13 7 x14 9 x15 8 x21 9 x22
6 x23 6 x24 6 x25 7 x31 17 x32 12 x33 14 x34 9 x35 15 x41 14 x42 6 x43 6 x44 10 x45 4 x51 10 x 52 7 x53 10 x54 9 x55
3 1 4 3
它具有n个独立0元素，这就得到了最优解，相应的解矩阵为
0 0 0 0 1
1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
或
0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0
第二步：进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个 独立0元素，就以这n个独立0元素对应解矩阵(xij)中的 元素为1，其余为0，这就得到最优解。找独立0元素， 常用的步骤为： (1)从只有一个0元素的行(列)开始，给这个0元素 加圈，记作◎ 。然后划去◎ 所在列(行)的其它0元素， 记作Ø ；这表示这列所代表的任务已指派完，不必再 考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记 作◎；然后划去◎ 所在行的0元素，记作Ø ． (3)反复进行(1)，(2)两步，直到尽可能多的0元素 都被圈出和划掉为止。
12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 9
Min 4 7 6 6 6
从上面可以看到列中最小个数之和为7，而行中最小个数之 和为9,。即应该先从系数矩阵的每列元素中减去该列的最小 元素。
B
7 9 17
C
9 6 12
D
7 6 14
E
9 6 9
甲 乙 丙
丁
戊
15
414ຫໍສະໝຸດ 10676
10
10
9
（二）、匈牙利法的解题步骤：


第一步：变换指派问题的系数矩阵（cij）为 (bij)，使在(bij)的各行各列中都出现0元素，即 (1) 从（cij）的每行元素都减去该行的最小 元素； (2) 再从所得新系数矩阵的每列元素中减去 该列的最小元素。
匈牙利算的优化
例
指派问题及其解法
有甲、乙、丙、丁、戊五位工人被指派去 完成A、B 、 C 、 D 、 E五项任务，每个 人完成任务所需的工时各不相同，见下表。 求应如何指派人员才能使得所用工时最少？
解
1, xij 0，
分配第i个人做j工作时 不分配第i个人做j工作时
目标函数为
12 x
7 ◎ 2 Ø 2 4 3 ◎ Ø Ø Ø 8 3 5 ◎ 11 8 Ø ◎ 4 ◎ 4 1 4 3
或
7 ◎ 2 Ø 2 4 3 Ø◎ Ø Ø 8 3 5 ◎ 11 8 ◎ Ø 4 4 1 4 3 ◎
0 5 ◎ 2 2 3 0 Ø 0 10 5 ◎ 9 8 ◎ 0 Ø 6 3 0 ×
0 Ø 2 0 0 Ø◎
√
7 2 √ -2 0 Ø 4 6 5 -2 √
+2
第四步；在没有被直线覆盖的部分中找出 最小元素。然后在行打√行每个元素减去这 一最小元素，而在打√列的每个元素都加上 这一最小元素，以保证原来0元素不变。这 样得到新系数矩阵。若得到n个独立的0元素， 则已得到最优解，否则回到第3）。