第五章 匈牙利法与最佳指派问题
- 格式：ppt
- 大小：798.00 KB
- 文档页数：49
下载文档原格式
合集下载
指派问题的匈牙利算法
摘要在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。
然而，如果没有科学的方法是很难实现优化管理的，由此我们引入了指派问题。
指派问题多是求项目的工时最少，而很多情况下人们并不关心项目总工时的多少，而只关心项目能否在最短的时间内完成，即历时最少的指派问题。
这类问题研究的是n个人执行n项任务，执行每项任务的人数以及总的指派人项数均有限制，要求最优指派。
在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解，但指派问题也可以归结为一个0-1整数规划问题，本文先对指派问题进行陈述，引出对实际问题的求解。
在指派问题的背景、描述中充分理解该问题，先运用匈牙利算法实现指派问题，然后再建立一个0-1整数规划模型，并运用matlab和lingo编译程序对问题进行编译，运用软件解决模型问题，最终实现指派问题在实际问题中的运用。
通过运用匈牙利算法和0-1整数规划同时对指派问题求解，我们发现用0-1整数规划的方法来求解可以更简单，也更方便程序的阅读和理解。
与此同时，我们还对0-1整数规划问题由整数数据深入研究到小数数据。
最后通过实例来说明运用matlab，lingo编译程序来解决整数规划问题的简便和有效性。
关键词：指派问题；匈牙利算法；0-1整数规划；matlab模型；lingo模型AbstractIn business, the company's operations and management, managers always want the best distribution of the staff to maximize their efficiency, reduce costs and improve efficiency. However, if there is no scientific method is difficult to achieve optimal management, which we introduced the assignment problem. Multi-assignment problem is to get the project working hours at least, and in many cases people do not care about how much the total project work, but only care about whether the project can be completed within the shortest possible time, that lasted for at least the assignment problem. Such problems is the n individual execution of tasks n, the number of people to perform each task and assign the total number of items are restricted to two people, requiring the optimal assignment. Integer programming in operations research for solving the assignment problem is usually solved by Hungarian algorithm, but the assignment problem can be reduced to a 0-1 integer programming problem, this paper first to make a statement on the assignment problem, leads to the solution of practical problems. Assignment problem in the background to fully understand the problem description, the first assignment problem using Hungarian algorithm, and then a 0-1 integer programming model and compiler using matlab and the lingo of the problem to be compiled using the software solution model problem Ultimately in the assignment of the application in practical problems. By using the Hungarian algorithm and the 0-1 integer programming to solve assignment problems simultaneously, we found that 0-1 integer programming method to solve a more simple and easier to read and understand the program. At the same time, we also 0-1 integer programming problem in-depth study by the integer data to a decimal data. Finally, an example to illustrate the use of matlab, lingo compiler to solve the integer programming problem is simple and effective.Keywords:assignment problem; Hungarian algorithm; 0-1 integer programming;matlab model; lingo model目录1. 问题陈述 (1)2. 指派问题的背景 (1)3. 指派问题的描述 (1)3.1 指派问题的一般形式 (1)3.2 问题的数学模型一般形式 (2)3.3 目标函数极大化的指派问题 (2)4．指派问题实现 (3)4.1 匈牙利算法 (3)4.1.1 匈牙利算法的理论基础 (3)4.1.2 匈牙利算法的实现步骤 (3)4.1.3 匈牙利算法实现指派问题 (4)4.2 0-1整数规划 (5)4.2.1 模型假设 (6)4.2.2 模型建立 (6)4.2.3 模型求解 (7)5. 问题的深入（0-1整数规划） (10)5.1 模型建立 (10)5.2 模型求解 (11)5.2.1 用matlab求解问题 (11)5.2.2 用lingo求解问题 (12)6. 结论 (14)6.1 总结概论 (14)6.2 具体分工.................................. 错误！未定义书签。
匈牙利法求解指派问题
然后划去所在的列的其他0 元素，记作Ø。
Ø 13 7 0 6 6 9 5 3 2 Ø1 0 0
➢给只有一个0元素的列的0 元素加圈，记。
Ø 13 7 0 6 6 9 5 3 2 Ø 1 0
然后划去所在的行的其他0元 素，记作Ø
Ø 13 7 0 6 6 9 5 3 2 Ø 1 Ø
➢给最后一个0元素加圈， 记。
Ø 13 7 6 6 9 5 3 2 Ø 1 Ø
可见m=n=4,得到最优解。
0001 0100 1000 0010
即甲译俄文、乙译日文、丙 译英文、丁译德文所需时间 最少。Z=28小时
例6 分配问题效率矩阵
任务 A B C D E 人员
甲 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
12 7 9 7 9 7 89666 6 7 17 12 14 9 7 15 14 6 6 10 6 4 10 7 10 9 4
50202 23000 0 10 5 7 2 98004 06365
➢从只有一个0元素的行开始，给 这个0元素加圈，记
50202 23000
10 5 7 2
98004 06365
然后划去所在的列的其他0元素，记 作Ø。
70202 4 3 000 Ø 8350 11 8 0 0 4 4 1 4 3
➢从只有一个0元素的行开始，给这个0 元素加圈，记
70202 4 3 000 Ø 8 3 5 11 8 0 0 4 4 1 4 3
然后划去所在的列的其他0元素，记 作Ø。
70202 4 3 00Ø Ø 8 3 5 11 8 0 0 4 4 1 4 3
求解指派问题的匈牙利算法.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 解：先作等价变换如下∨∨∨⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡→⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡----- 2636040*08957510*00*0032202*056107104106614151214121776669897971246767 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但5=n ，最优指派还无法看出。
指派问题的匈牙利法讲课稿
√√
√
l =m=4 < n=5
1 ◎0 3 1 3 √ 0 0 3 0 3
2
6
◎0
3
Ø0
√
1
6
0
2
0
4 2 Ø0 1 3 √ 3 2 0 0 3
3
Ø0 2
4
◎0
√
2
0
2
3
0
◎0 3 3 Ø0 5 0 4 4 0 6
√√
√
0 0 3 0 3
1
6
0
2
0
3 2 0 0 3
1
6
0Ø 2
◎0
3 2 0◎ 0Ø 3
2
◎0
2
3
Ø0
0◎ 4 4 0Ø 6
用匈牙利法求解下列指派问题，已知效率矩 阵分别如下：
7 9 10 12
1
3
12
16
1
7
15 16 14 15
1 1 1 2 1 5 1 6
3 8 2 10 3
8
7
2
9
7
6 4 2 7 5
8 4 2 3 5
2
60ຫໍສະໝຸດ 3026
◎0
3
Ø0
√
4 2 0 1 3 4 2 Ø0 1 3 √
3
0
2
4
0
3
Ø0
2
4
◎0
√
0 3 3 0 5 ◎0 3 3 Ø0 5
√√
√
1 ◎0 3 1 3 √
2
6
◎0
3
Ø0
√
4 2 Ø0 1 3 √
3
Ø0
匈牙利法的指派问题-33页文档资料
C
c11 c21
ci1
b
c12 c22
ci2 b
cn1
cn2
c1n c2n
cin b
cnn
minZ Z b
minZ Zb
若X0是minZ的最优， 解则 X0也是 minZ的最优解
指派问题的最优解：
若C中有n 个位于不同行不同列的零元素，
则令这些零元素对应的变量取1，其余变量
例：有一份说明书要分别译成英、 工作
日、德、俄四种文字，现交给甲、人
英日德 俄
乙丙、丁四个人去完成，每人完 甲 2 15 13 4
成一种。由于个人的专长不同，
乙 丙
10 4 14 15 9 14 16 13
翻译成不同文字所需的时间（小 丁 7 8 11 9
时数）如右表，问应派哪个人去
完成哪个任务，可使总花费时间
2
C
10
9 7
15 4 14 8
13 14 16 11
4 -2
15 -4
13 9
-9 -7
0
6 0 0
13 0 5 1
11 10 7 4
2 0 13
11
4 2
6
0 0
0 5 1
7 6 3 0
0
9
2
0
-4 -2
最优解的取法：
从含0元素最少的行或列开始，圈出一个0元 素，用 ○表示，然后划去该○所在的行和列 中的其余0元素，用×表示，依次类推，若能 得到n个○，则得最优解X0
最 优
取x14 1，x22 1, x31 1, x43 1 ,其余 xij 0
解
总费用 Z c14 x14 c22x22c31x31c43x43 0
第五节 指派问题
第二步：进行试指派，以寻求最优解 经过第一步后,矩阵的每行每列都有了0 元素， 但我们希望找出n个位于不同行不同列的0 元素， 如果能找到，我们就以把这些元素写成1， 令其余的元素写成0 ，即得问题的最优解．
0 13 7 6 0 6 LL 0 5 3 0 1 0 0 9 2 0
13
14 16 11
10 9 7
15 13 9
目标函数：
min S 2 x11 15 x12 13 x13 14 x14
10 x21 4 x22 14 x23 15 x24
9 x31 14 x32 16 x33 13 x34
7 x41 8 x42 11 x43 9 x44
0 7 15 13 2 0 10 4 14 15 min 1 6 14 16 13 8 0 9 0 7
0 1 0 0
0 0 0 1
1 0 0 0
（2）出现死循环时灵活处理
例5.7 求解指派问题，系数矩阵为
n
目标函数的系数可以写成矩阵的形式，称 为系数矩阵或收益矩阵.
如例1的收益矩阵为
2 15 13 4 10 4 14 15 C 9 14 16 13 8 11 9 7
满足约束条件的可行解也可以写成矩阵形 式，称为解矩阵.
如例1的解矩阵有
( x )ij 0 0 0 1 0 1 0 0 或 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 或 1 0 0 1 0 0 0 1 1 0 0 0
指派问题与匈牙利算法
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 对应的模型是求最大值 将其变换为求最小值 令
当人数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 对应的模型是求最大值 将其变换为求最小值 令
第五讲分配问题指派问题与匈牙利法
i1 j 1
相关定理
使每行每列 都出现零元素
定理：若将分配问题系数矩阵的每一行及每一列分别 减去各行及各列的最小元素，则新分配问题与原分配 问题有相同的最优解，只有最优值差一常数。
时 工作
时 工作
间
A
B
间C
A
B
C
人员
人员
甲
7 8
甲9
0 10
2
乙
9
12
乙4 5
87
0
丙
8
5
丙4 4
10 0
步骤1：变换系数矩阵，使其每行每列都出现0元素
cn1
cn1
...
cnn
x11 x12 ... x1n
X
x21
x22
...
x2
n
... ... ... ...
xn1
xn1
...
xnn
系数矩阵
(效率矩阵)
n个人 n件事
解矩阵
(决策变量矩 阵)
定义：在系数矩阵C中，处在不同行不同列的一
组零元素，称为独立零元素组，其中每个元素
称为独立零元素。
圈0个数等于n=55 0 2 0 9
2 3 0 0 8
0 10 5 7 5 9 8 0 0 4
0 6 3 6 0
0 1 0 0 0
0 0 1 0 0
1 0 0 0 0 0 0 0 1多重0最优解
0 0 0 0 1
5 0 2 0 9
2 3 0 0 8
0 10 5 7 5 9 8 0 0 4
0 6 3 6 0
一纵线，即得到覆盖当前0元素的最少直线集。
0 3 0 11 8
0 1 7 7 3
指派问题
Step 4、改进 1 、改进C
8 2 5√ 0 5 4 3 0 0 √ 1列中加上 ； 在已打√号的列中加上 在已打 号的列中加上θ； 13 C2 = 得到一个新矩阵 C2。 4 -2 用 C2 代替 C1，返回步骤 2. 0
8 2 5 0 5 4 3 0 0 11 4 5
0 11 C = 上述步骤可能出现三种情况 1 2 情况一： 情况一：矩阵每行都有一个打圈的 0
0 元素。此时得到问题的最优解 元素。此时得到问题的最优解.
8 2 5 0 5 4 3 0 0 11 4 5
2 15 C= 13 4
10 9 7 4 14 8 14 16 11 15 13 9
2 4 11 4
0 11 B= 2 0
8 7 5 0 10 4 3 5 0 11 9 5
Step 2、确定 1中线性独立的 元素 元素. 、确定C 中线性独立的0元素 从第一行开始，若该行只有一个 元素 就对这个0 元素， 从第一行开始，若该行只有一个0元素，就对这个 元素加圈，然后划去其所在列的其它0元素 元素;若该行 元素加圈，然后划去其所在列的其它 元素 若该行 没有其它0元素或有两个以上 元素（ 元素或有两个以上0元素 没有其它 元素或有两个以上 元素（已划去的不 ），转下一行 直到最后一行为止。 转下一行； 计），转下一行；直到最后一行为止。 然后,从第一列开始 若该列只 然后 从第一列开始,若该列只 从第一列开始 0 有一个0元素 就对这个0元素 元素,就对这个 有一个 元素 就对这个 元素 11 加圈（同样不考虑已划的） 加圈（同样不考虑已划的）, 再划去其所在行的其它0元素 元素; 1 再划去其所在行的其它 元素 C = 2 若该列没有0元素或有两个以 若该列没有 元素或有两个以 元素， 上0元素，则转下列直到最后 元素 0 一列为止。 一列为止。 重复上述步骤. 重复上述步骤
指派问题匈牙利算法最大值
指派问题匈牙利算法最大值
匈牙利算法(匈牙利算法,也被称为“插入-删除算法”或“排序算法”)是一种整数排序算法,在指派问题中可以将一个整数数组按照一定规则排序,使得所有指派中最大的元素出现的位置都不相同。
以下是匈牙利算法在解决指派问题的最大值问题的步骤:
1. 将数组分为两个部分,左半部分尽可能地小,右半部分尽可能地大。
2. 从右半部分开始,将一个元素与它的指派对象的最大值进行
比较。
如果两个元素之间的指派关系不符合要求,就将它们交换位置。
3. 接下来,从左边半部分开始,将一个元素与它的指派对象的最大值进行比较。
如果两个元素之间的指派关系不符合要求,就将它们交换位置。
4. 重复步骤2和步骤3,直到左半部分的最大值与右半部分的最大值相等。
5. 在最右半部分找到最大的元素,将它与左半部分的最大值交换。
6. 重复步骤1到步骤5,直到数组中的所有元素都被排序。
匈牙利算法的时间复杂度为O(nlogn),其中n为数组的长度。
在实际应用中,该算法通常用于小规模数据的排序,对于大规模数据的
排序则需要使用更高效的算法。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
7 2 2
4
3
8 3 5 3
11 8
4
4 1 4
情况一出现，即得到了最优解，其相应的解矩阵为：
0 1 0 0 0
0 0 1 0 0
xij
1
0
0
0
0
0 0 0 1 0
0 0 0 0 1
由此得知最优指派方案为甲完成任务B，乙完成任务
C，丙完成任务A，丁完成任务D，戊完成任务E，最少时
间为
min z 7 6 7 6 6 32
而总的最少时间为32天．
当然，由于方法中的第二步4中的情况二的出现，造成 指派问题的最优解常常是不唯一的，但不同最优解的 最优值总是相同的．
第三节 非标准指派问题
前一节的匈牙利法只适用于目标函数为极小、价值 系数矩阵为方阵且价值系数矩阵中元素均为非负的情况。 当指派问题不满足上述三个条件时，就应先化成标准的 指派问题，然后再用匈牙利法求解．
解：
ABC DEF
甲 16 10 12 15 0 0 8 2
甲 16 10 12 15 0 0
8
2
乙 11 12 10 18 0 0 3 2 3
乙
11
12
10
18
0
0
3
2
3
丙 8 17 13 16 0 0 7 3 1
丙
8
17 13 16
0
0
7
3
1
8 10 10 15
本例经过反复的行、列检验后得到如下矩阵：
5 2 2
2
3
10 5 7 5
9
8
4
6 3 6 2
情况三出现，亦即未得到完全分配方案，求解过程 按以下步骤继续进行。
第三步：作最少的直线覆盖当前所有0元素（包括标 记上△和 的）
1．对所有不含△的行的右侧打√号； 2．对已打√号的行中含有 元素的列的下侧打√号 3．对已打√号的列中含有△的行的右侧打√号； 4、重复上述步骤“第三步2”“第三步3”，直到不 能进一步打√为止； 5、对没打√号的每一行画一横线，而对于已打√号 的每列画一纵线，即得到覆盖当前所有0元素的最少直线。
3
6
1
0
3
cij
5 5
4 4
3 2 2 2 3 2 1 0 0
7
2
5
5
0
9 12
7 10
8 2 3 4 5 3 11 1 0 7 8
1
0 6 8 5 2 6 8 5 2
3
5
1
0
3
3
5
1
3
3 1 1 0 0 3 1 1
0
8 12 7 10
8 12
第五章 匈牙利法与 最佳指派问题
什么是最佳指派问题？
最佳指派（或分配）问题是经济计划工作中经常遇到
的一个问题．比如，当某一个部门或某一个企业的生产任 务已经确定，如何分配给它们所属的单位，使得完成这些 任务所需费用最小（或效益最大）．分配问题是较简单的 线性规划问题，也是运输问题的一个特例，当然可以用线 性规划的单纯形法加以求解．然而，使用本章介绍的方法 ——匈牙利法去求解，效果会更好，该方法的得名是因为
此模型称为指派问题的标准形式。
第二节 标准指派问题的匈牙利法
匈牙利法的基本原理 匈牙利法的求解步骤
一、匈牙利法的基本原理
1、指派问题最优解的性质
假设
cij
nn
是指派问题的价值系数矩阵，现将它的某
一行（或某一列）的各个元素都减去一个常数 k（k可为
正，也可为负），得到矩阵
bij nn．那么以
bij
情况二：存在未标记的0元素，但它们所在行和列中 ，未标记的0元素均至少有2个．
情况三：不存在未标记的0元素，但△的个数m<n.
4、如果情况一出现，则得一完整的最优分配方案， 可停止计算；如果情况二出现，可标记△到任何一个0元 素上，再将其同行、同列的其它0元素上标记，然后返回 步骤“第二步1”；如果情况三出现，则转到“第三步”。
一般地，当指派n个人去完成n项任务时，其数学模
型如下：
nn
min z
cij xij
i1 j1
n
xij 1
(i 1,2, ,n)
j1
s.t.
n
xij 1
( j 1,2, ,n)
i1
xij 0或1
（5.1.1）
其中 cij为第 i个人完成第项任务所消耗的资源（一般指时
间或费用等），称之为价值系数．
非标准指派问题：
目标函数为求极大值的问题 价值系数矩阵中存在负元素 价值系数矩阵不是方阵
一、目标函数为求极大值的问题
当目标函数为：
nn
max z
cij xij
i1 j1
时，记 M max 1i, jn
cij
bij M cij i, j 1,2, , n
得到一新矩阵
bij
nn
．由最优解的性质知，以
2 0
3 10
0 5
0 7
0 5
9 8 0 0 4
0 6 3 6 2
第二步：进行试指派，以寻求最优解 1．进行行检验 从第一行开始逐行检查，当遇到只含有一个未标记 的0元素的一行时，就在该0元素上标记符号△，这表示 分配△所在行的那个人担任△所在列的那个任务．然后 在该0元素所在列的其它0元素上标记 ，以免对此任务 再进行分配． 重复上述行检验，直到每一行都没有未标记的0元素 或至少有两个未标记的0元素时为止．
7
10
11 0 0 7 8 11 7 8
0 4 6 3 0 4 6 3 4 6 3
5
5
1
0 3
5
5
1
3
5
5
1
3
5 1 1 0 0 5 1 1 5 1 1
0
6 10
5 8
6 10 5
8
6 10
5
8
13 0 0 7 8 13 7 8 13 7 8
第 j 项工作由第 i 人完成 第 j 项工作不由第 i 人完成
此时 xij 称为0-1变量．
由于每个人只能完成一项工作，因而有：
x1 1 x21
x1 2 x22
x1 3 x23
1 1
x31 x32 x33 1
又由于每项工作只能由一个人完成，因而又有：
xx1121
x21 x22
x3 1 x3 2
素，即可使价值系数矩阵 cij nn满足非负条件，然后可以用
匈牙利法求解．
例1 求价值系数矩阵为如下所示的指派问题的最小 解．
3 4 5 2 1
4
cij
5
7 4
5 4
2
1
4
3 2 2
7
2
5
8 2 3 4 5
解：
3 4 5 2 1 3 0 7 8 5 2
4
7
2
1
4
1
本例题中，给第2步所得矩阵的第5行打√号，再给 第1列打√号，然后给第3行打√号．分别对该矩阵的第1、 2、4行画一横线，而对第1列画一纵线．即得到覆盖当前 所有0元素的最少直线．此矩阵如下：
第四步：对上步所得矩阵进行变换，以增加其0元 素．
从没被任何直线覆盖的各元素中找出最小元素，逐 个将打√号的行的各元素都减去这个最小元素，而打√ 号的列的各元素都加上这个元素，以保证打√号的行中 的0元素不变为负值而仍为0元素．
变量取值为0，就可以得到原指派问题的最优解．
2、关于矩阵中0元素的定理
系数矩阵中独立0元素的最多个数等于能覆盖所有0 元素的最少直线数．
二、匈牙利法的求解步骤
例1 有5个人去完成5项任务．每个人只能完成1项任 务，每项任务也只能由1个人完成，价值系数矩阵如下表 所示（单位：天）．问如何分配才能使完成任务的总时 间最少？
工作．因各人对不同文字的熟悉程度不一样，所需工作 时间（单位：天）也不同（见下表）．问应指派哪一个 人去完成哪一项工作才能使花费的总时间最短？
解：对于某个人来讲，要么做某项工作，比如“译 英”要么不做，二者必居其一，换句话说，每个人与每 项工作之间只有两种状态：“做”或“不做”为此我们 设变量：
1 , xij 0 ,
nn
为价值系
数矩阵的新的指派问题的最优解与原指派问题的最优解
相同，但其最优值比原来减小 k．
利用上述性质，可使原价值系数矩阵变为含有很多0
元素的新系数矩阵，而其最优解保持不变，在系数矩阵
bij
nn
中，我们关心位于不同行不同列的0元素，以下简称
为独立0元素，若能在系数矩阵中得到n个独立的0元素，
则令解矩阵中对应这n个独立0元素的变量取值为1，其它
匈牙利数学家狄·考尼格（D·Konig）为发展这个方法证
明了主要定理．
本章主要内容
第一节 最佳指派问题的线性规划模型 第二节 标准指派问题的匈牙利法 第三节 非标准指派问题
第一节 最佳指派问题的LP模型
例1 有一份资料需从汉语译成英、日、俄三种文字
，现有A、B、C三人，每人需完成且只完成其中的一种
11 8 0 0 4
0 4 1 4 0
返回“第二步”对矩阵进行行、列检验．得到如下 矩阵．
7 2 2
4
3
0
0
8 3 5 3
11 8 0
0
4
4 1 4
情况二出现．此时可以在四个0元素中任取一个，比 如第2行第3列的元素进行标记，然后将其所在行、列的 其它0元素上标记，再重新进行检验给第4行第4列的0元素 标记△．于是得到：
将矩阵中标记的△、还原为0，去掉√及直线，返 回“第二步”对矩阵进行行、列检验．