(i 1, ,4; j 1, ,4)
则该指派问题的数学模型为：
min z 2x11 15x12 13x13 4x14 L 11x43 9x44
4
xij
1
(i 1,L
, 4)
∑xij=1 (i=1,2,3,4) 表示第i人只能完成一项任务
j1
s.t.
4
xij
1
( j 1,L
, 4)
i1
xij=1 (j=1,2,3,4) 表示第0或1
(i，j 1,L
, 4)
满足约束条件的解称为可行解， 可写成矩阵形式，叫作解矩阵。
如本例的一个可行解矩阵（但不一定是最优解）
0 1 0 0
xij
0 1
0 0
1 0
0 0
0 0 0 1
指派问题的解矩阵应具有如下特点：
在实际中经常会遇到这样的问题，
有n 项不同的任务， 需要n 个人分别完成其中的一项，
但由于任务的性质和各人的专长不同， 因此各人去完成不同的任务的效率 （或花费的时间或费用）也就不同。 于是产生了一个问题: 应指派哪个人去完成哪项任务，
使完成 n 项任务的总效率最高（或所需时间最少），
这类问题称为指派问题或分派问题。
二 匈牙利算法
思路 算法原理 算法步骤
（一） 思路
匈牙利法基于这样一个明显的事实： 如果在m阶效率矩阵中，所有元素cij≥0， 而其中有m个位于不同行不同列的一组0元素， 则在解矩阵中，只要令对应于这些0元素位置的 xij＝1，其余的xij＝0，就得到最优解。 此时的最优解为０
•如效率矩阵为 •恰有4个不同行 不同列的0系数
2. 指派问题数学模型—一般形式
设[cij]表示指派问题的效率矩阵，令
1, 分配第i个人去完成第j项任务 xij 0, 不分配第i个人去完成第j项任务
(i 1, ,n; j 1, ,m)
则指派问题的数学模型一般形式为： xij 为第 i 个人指派去做
mm
min (或 max)z
cijxij
（1）解矩阵(xij)中各行各列的元素之和都是1； （2）可行解（最优解）中恰含有４个非零元，即4个1；
（3）可行解（最优解）矩阵中的1恰取于不同行不同列。
人 工作
甲
乙
丙
丁 人数
译成英文 2 10 9 7 1
译成日文 15 4 14 8 1
译成德文 13 14 16 11 1
译成俄文 4 15 13 9 1
甲 乙 丙 丁
E
J
G
R
2
15 13
4
10
4
14
15
9
14
16
13
7
8
11
9
❖ 这是一个标准型的指派问题
❖ 类似有：有n项加工任务，怎样指派到n台机床上分别完成；
有n条航线，怎样指定n艘船分别去航行….. 等。
❖ 对应每个指派问题，需有类似上表那样的数表，
表中数据称为效率矩阵或系数矩阵，
❖ 其元素cij>0(i,j=1,2,…n)， ❖ 表示指派第i人去完成第j 项任务时的效率（或时间、成本等）
一、指派问题的数学模型
（一）举例
例7： 有一份中文说明书， 要分别译成英、日、德、俄四种文字， 分别记作E 、 J 、 G 、 R ,交与甲、乙、丙、丁 四个人去完成. 因个人专长不同， 他们完成翻译不同语种的说明书所需的时间(h)如表所示. 应如何指派，使四个人分别完成这四项任务总时间为最小？
任务 人员
（二）算法的基本原理 匈牙利数学家狄·康尼格(D·Konig)证明的两个定理
c11 c12 … c1n
效率
C=(cij)n×n=
c21 c22 … c2n ……………… cn1 cn1 … cnn
矩阵
或
系数 矩阵
C=(cij )４×４=
2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9
求解题时通常需引入0-1变量：
1, 分配第i个人去完成第j项任务 xij 0, 不分配第i个人去完成第j项任务
如果一个指派模型满足以下三个条件： 1)目标要求为min 2)效率矩阵(cij)为m阶方阵 3)效率矩阵中所有元素cij≥0,且为常数
则称上面的数学模型为指派问题的标准形.
4. 指派模型的标准形的特点: 含有m×m个决策变量,均为0-1变量 m+m＝2m个约束方程
给定一个指派问题时，必须给出效率矩阵（系数矩阵） C=(cij)mxm,且cij0，因此必有最优解 。
0 14 9 3
9
20
0
23
23 0 3 8
0
12 14
0
令x11=1，x23=1，x32=1，x44=1，即可得最优解，
其解矩阵为
min Z=Z＊＝0
1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1
问题是如何找到位于不同行、不同列的m个0元素？
匈牙利算法基本思想： 对同一工作i来说， 所有人的效率都提高或降低同一常数， 不会影响最优分配； 同样，对同一人j来说, 做所有工作的效率都提高或降低同一常数， 也不会影响最优分配。
i1 j1
第 j 项任务； cij 为第 i 个人为完成第
m
xij 1 (i 1, ,n) j1
j 项任务时的工时消
耗，或称效率；
s.t.
n
xij 1
(j 1, ,m)
{cij} nm 为效率矩阵
i1
xij 0或1 (i 1, ,n；j 1, ,m)
3. 指派问题数学模型—标准形式
任务
1
1
1
1
可以看到指派问题既是0-1 规划问题，也是运输问题， 所以也可用整数规划，0-1 规划， 或运输问题的解法去求解。
（二）指派问题的数学模型 1. 指派问题的一般提法：
❖ 设m个人被指派去做m件工作， 规定每个人只做一件工作， 每件工作只有一个人去做。
❖ 已知第i个人去做第j 件工作的的效率（ 时间或费用） 为cij (i=1.2…m;j=1.2…m) ，并假设cij ≥0。 问应如何指派才能使总效率最高或总时间﹑ 总费用最低 ？
mm
MinZ
cijxij 0
i1 j1
指派问题有2m个约束条件，
但可行解（即解矩阵）中有且只有m个是非零值，
即m个值取为１，其余取为０, 是自然高度退化的。
指派问题是0-1 规划的特例， 也是运输问题的特例，所以可用整数规划，0-1 规划或运输问题的解法去求解， 但这就如同用单纯形法去求解运输问题一样， 是不合算的。 根据指派问题的特点可以有更简便的解法， 就是匈牙利算法， 其重要依据是： 系数矩阵中独立 0 元素的最多个数等于能覆盖 所有 0 元素的最少直线数。