指派模型 宋海洲 一：指派问题 设有n个人被分配去做n件工作，规定每
个人只做一件工作，每件工作只由一个人做。已
知第i个人做第j件工作的效率（时间或费用)为 ，并假设 。 ?问：应
如何分配才能使总效率（总时间或总费用）最高？ 引进变量 设 建立模型 分
析 这是线性规划模型； 也是整数规划模型；0-1规划模型； 更是运输模型。 共
有n*n个变量，实际上只需找n个变量为1即可，因此这是高度退化的线性规划
模型。 例1 设有5个人被分配去做5件工作，规定每个人只做一件工作，每件
工作只由一个人做。已知第i个人做第j件工作的费用如下表所示。问：应
如何分配工作才能使总费用最省？ 二：匈牙利法 定义：指派问题的效益矩阵：
效益矩阵的性质 定理1：从效益矩阵C的第k行（或第k列）的每一个元素中
减去一个常数a得到的矩阵C’所表示的指派问题具有相同的最优解。（ C’称
缩减效益矩阵） 定义：如果这些0元素分布在效益矩阵的不同的行和不同的列
上，则称这些0元素为独立的0元素。 定理2：若方阵的一部分元素为0，一部
分元素不为0，则覆盖方阵内所有0元素的最少直线数，等于矩阵中独立的0元
素的最多个数（匈牙利：konig） 积和式 定义： 积和式的性质 按行展开性； 转
置不变性； 换行不变性； 倍法变换增倍性； 单行可加性； Laplace法则。 补
矩阵 定义： 匈牙利法解指派模型算法 第一步：将原指派问题的效益矩阵C进
行变换得矩阵CC，使得CC的各行各列均出现0元素，其方法是： （1）从效益
矩阵C的每行元素减去该行最小元素； （2）在从所得的效益矩阵的每列元素减
去该列最小元素。 第二步：计算CC的补矩阵D,计算D的积和式per(D)。 判断
per(D)是否不等于0，如果per(D)不等于0，转第五步； 如果per(D)等于0，
转第三步。 第三步： （1）在CC中找0元素最少的一排（行或列），选中其中
一个0，记为0，将该0所在的行及列划去。 （2）对上述划去一行及一列的矩
阵，重复（1）的做法。 „„. 一共得到m个0 。(m n) 记下这m个0 所在的
行号i1,i2,„,im及列号j1,j2,„,jm. (则CC所有的0或0必在i1,i2,„,im
行中或在j1,j2,„,jm中） (3)①：在 CC中找出不在i1,i2,„,im行的0，记
下他们的列号r1,r2,„;并将这些列划竖线； ②：在划去竖线的CC中找出不含
0的列的0，记下他们的行号s1,s2,„;并将这些列划横线； 重复① ②，则这
些直线构成覆盖方阵CC内所有零元素的最少直线。 第四步：调整CC ,使之增
加一些0，为此按如下方法进行： （1）在没有直线覆盖的元素中，找出最小元
素x; （2）在未划线的行减去最小元素x； （3）在划线的列加上最小元素x；
得到新的CC，返回第二步。 第五步： （1）在CC中找0元素最少的一排（行
或列），选中其中一个0，记为0，将该0所在的行及列划去。 （2）对上述划去
一行及一列的矩阵，重复（1）的做法。 „„. 一共得到n个0 。 （3）将n
个0 所在位置对应的变量赋“1”，其他变量赋“0”，得到最优解。 例2：用匈
牙利法求解例1 第一步：将原指派问题的效益矩阵C进行变换 第二步：计算
CC的补矩阵D,计算D的积和式per(D)。 第三步： （1）在CC中找0元素最
少的一排（行或列），选中其中一个0，记为0，将该0所在的行及列划去。 （2）
对上述划去一行及一列的矩阵，重复（1）的做法。 „„.。一共得到4个0 。
(4 n=5) 记下这4个0 所在的行号1，2，3，5。 （3）在 CC中找出不在1，
2，3，5行的0(不是0 ）的列号2，并将第2列划竖线，在CC划去竖线后剩下
的0划横线；则这些直线构成覆盖方阵CC内所有零元素的最少直线:（下一页）
第四步：调整CC ,使之增加一些0，为此按如下方法进行： （1）在没有直线覆
盖的元素中，找出最小元素x=1; （2）在未划线的行减去最小元素x； （3）在
划线的列加上最小元素x； 得到新的CC，返回第二步。 返回第二步：计算
CC的补矩阵D,计算D的积和式per(D)=0。再进行第三步得： 返回第四步：
调整CC ,使之增加一些0，为此按如下方法进行： （1）在没有直线覆盖的元素
中，找出最小元素x=1; （2）在未划线的行减去最小元素x； （3）在划线的列
加上最小元素x； 得到新的CC， 返回第二步，此时per(D)~=0,转第五步
得： 三：极大指派问题
模型： 令Cij’=maxCij-Cij,则模型等价为： 四：不平衡指派问题 令
令 模型转化为： * * 工作 人 a b c d e 甲 乙 丙 丁 戊
7 9 8 7 4 5 12 5 3 6 9 7 4 6 7 8 11 6 9 5 11 9 8 6 11