指派问题详解

第一章 绪 论

1、指派问题的背景及意义

指派问题又称分配问题，其用途非常广泛，比如某公司指派n个人去做n件事，各人做不同的一件事，如何安排人员使得总费用最少？若考虑每个职工对工作的效率（如熟练程度等），怎样安排会使总效率达到最大？这些都是一个企业经营管理者必须考虑的问题，所以该问题有重要的应用价值.

虽然指派问题可以用0-1规划问题来解，设X(I,J)是0-1变量, 用X(I,J)=1表示第I个人做第J件事, X(I,J)=0表示第I个人不做第J件事. 设非负矩阵C（I，J）表示第I个人做第J件事的费用， 则问题可以写成LINGO程序

SETS: PERSON/1..N/; WORK/1..N/;

WEIGHT(PERSON, WORK): C, X ; ENDSETS DATA: W=… ENDDATA

MIN=@ SUM(WEIGHT: C*X);

@FOR(PERSON(I): @SUM(WORK(J):X(I,J))=1); @FOR(WORK(J): @SUM(PERSONM(I):X(I,J))=1); @FOR(WEIGHT: @BIN(X));

其中2*N个约束条件是线性相关的, 可以去掉任意一个而得到线性无关条件.

但是由于有N^2个0-1变量, 当N很大时，用完全枚举法解题几乎是不可能

的. 而已有的0-1规划都是用隐枚举法做的，计算量较大. 对于指派问题这种特殊的0-1规划，有一个有效的方法——匈牙利算法，是1955年W. W. Kuhn利用匈牙利数学家D.K?nig的二部图G的最大匹配的大小等于G的最小顶点覆盖的大小的定理提出的一种算法，这种算法是多项式算法，计算量为O(N3).

匈牙利算法的基本原理是基于以下两个定理.

定理1 设C=(Cij)n×n是指派问题的效益矩阵，若将C中的任一行（或任一列）减去该行（或该列）中的最小元素，得到新的效率矩阵C’，则C’对应的新的指派问题与原指派问题有相同的最优解.

证明：设X’是最优解, 即@SUM(WEIGHT: C*X’)<= @SUM(WEIGHT: C*X), 则当C中任一行或任一列减去该行或该列的最小数m时,得到的阵C’还是非负矩阵, 且 @SUM(WEIGHT: C’*X’)<=

@SUM(WEIGHT: C*X)-m=

@SUM(WEIGHT: C’*X)

定理2 效率矩阵C中独立的0元素的最多个数等于覆盖所有0元素的最少直线数. 当独立零元素的个数等于矩阵的阶数时就得到最优解.

1

3、理论基础

定义: 图G的一个匹配M是图G中不相交的边的集合. 属于匹配M中的边的所有端点称为被该匹配M饱和, 其他的顶点称为M-未饱和的. 如果一个匹配M饱和了图G的所有顶点，则称该匹配M是一个完全匹配. 可见顶点数是奇数的图没有完全匹配. 一个匹配M称为是极大匹配, 如果它不能再扩张成更大的一个匹配. 一个匹配称为是最大匹配, 如果不存在比它更大的匹配.

定义: 对于一个匹配M, 图G的一个M-交替路是图G中的边交替地在M中及不在M中的边组成. 从M-未饱和点出发到M-为饱和点结束的M-交替路称为一条M-增广路. 把M-增广路中不是M中的边改成新的匹配M’中的边, 把M-增广路中M中的边不作为M’中的边, 在M-增广路以外的M中的边仍作为M’中的边, 则M’的大小比M大1. 故名M-增广路. 因此最大匹配M不存在M-增广路.

定义: 若图G和图H有相同的顶点集V, 我们称G和H的对称差,记为G?H,是一个以V为顶点集的图, 但其边集是G和H的边集的对称差: E(G?H)=E(G) ?E(H)=E(G)?E(H)-(E(G)?E(H))=(E(G)-E(H)) ? (E(H)-E(G))

定理: (Berge, 1957) 图G的一个匹配M是最大匹配,当且仅当G中没有M-增广路.

证明: 我们只要证明, G中没有M-增广路时, M是最大匹配. 用反证法, 若有一个比M大的匹配M’. 令G的一个子图F, E(F)=M?M’, 因M和M’都是匹配, F的顶点的最大度数至多是2, 从而F由不相交的路和环组成, 它们的边交替地来自M和M’, 于是F中的环的长度是偶数. 由于M’比M大, F中存在一个连通分支,其中M’ 中的边数大于M中的边数. 这个分支只能是起始和终止的边都在M’中. 而这就是一条G中的M-增广路. 与假设矛盾. 证毕.

定理(Hall, 1935) 设G是一个二部图, X和Y是其二分集, 则存在匹配M饱和X当且仅当对于X中的任意子集S, Y 中与S中的点相邻的点组成的集合N(S)中元素的个数大于等于集合S中元素的个数.

证明：必要性是显然的. 对于充分性, 假设 |N(S)|?|S|, ?S?X, 考虑G的一个最大匹配M, 我们用反证法，若M没有饱和X, 我们来找一个集合S不满足假设即可. 设u?X是一个M-未饱和顶点, 令S?X和T?Y分别是从u出发的M-交替路上相应的点.

2

我们来证明M中的一些边是T到S-u上的一个匹配. 因为不存在M-增广路，T中的每个点是M-饱和的. 这意味着T中的点通过M中的边到达S中的一个顶点. 另外, S-u中的每个顶点是从T中的一个顶点通过M中的一条边到达的. 因此M中的这些边建立了T与S-u的一个双射, 即|T|=|S-u|. 这就证明了M中的这些边是T到S-u上的一个匹配，从而意味着T?N(S), 实际上, 我们可证明T=N(S). 这是因为连接S和Y-T中的点y的边是不属于M的, 因为不然的话, 就有一条到达y的M-增广路, 与y?T矛盾. 故|N(S)|=|T|=|S-u|=|S|-1<|S|, 与假设矛盾.

当X与Y的集合的大小相同时的Hall定理称为婚姻问题,是由Frobenius(1917)证明的.

推论: k-正则的二部图（X的每一点和Y的每一点相关联的二部图）(k>0)存在完全匹配.

证明: 设二分集是X,Y. 分别计算端点在X和端点在Y的边的个数, 得k|X|=k|Y|, 即|X|=|Y|.因此只要证明Hall的条件成立即可. 使X饱和的匹配就是完全匹配. 考虑?S?X, 设连接S与N(S)有m条边, 由G的正则性, m=k|S|. 因这m条边是与N(S)相关联的, m?k|N(S)|, 即

k|S|? k|N(S)|, 即|N(S)|?|S|. 这就是Hall的条件.

用求M-增广路的方法来得到最大匹配是很费时的. 我们来给出一个对偶最优化问题.

定义: 图G的一个顶点覆盖是集合S?V(G), 使得G的每条边至少有一个端点在S中. 我们称S中的一个顶点覆盖一些边, 若这个顶点是这些边的公共端点.

因为匹配的任意两条边不能被同一个顶点覆盖, 所以顶点覆盖的大小不小于匹配的大小: |S|?|M|. 所以当|S|=|M| 时就同时得到了最大的匹配和最小的顶点覆盖.

定理(K?nig [1931],Egerváry[1931])二部图G的最大匹配的大小等于G的最小顶点覆盖的大小.

证明: 设M是G的任一个匹配, 对应的二分集是X,Y. 设U是一个最小的顶点覆盖, 则|U|?|M|, 我们只要由顶点覆盖U来构造一个大小等于|U|的匹配即完成证明. 令R=U?X, T=U?Y, 令H, H’ 分别是由顶点集R?(Y-T)及T?(X-R)

3

诱导的G的子图. 我们应用Hall的定理来证明H有一个R到Y-T中的完全匹配， H’有一个从T到X-R中的完全匹配. 再因这两个子图是不相交的, 这两个匹配合起来就是G中的一个大小为|U|的匹配.

因为R?T是G的一个覆盖, Y-T与X-R之间没有边相联接. 假设S?R, 考虑在H中S的邻接顶点集N(S), N(S) ?Y-T. 如果|N(S)|<|S|, 因为N(S)覆盖了不被T覆盖的与S相关联所有边, 我们可以把N(S) 代替S作为U中的顶点覆盖而得到一个更小的顶点覆盖. U的最小性意味着H中Hall条件成立. 对H'作类似的讨论得到余下的匹配. 证毕.

最大匹配的增广路算法

输入: 一个二分集为X，Y的二部图G，一个G中的匹配M， X中的M-未饱和顶点的集合U.

思路: 从U出发探求M-交替路， 令S?X，T?Y为这些路到达过的顶点集. 标记S中不能再扩张的顶点. 对于每个x?(S?T)-U, 记录在M-增广路上位于x前的点.

初始化: S=U,T=?.

叠代: 若S中没有未标记过的顶点, 结束并报告T?(X-S)是最小顶点覆盖而M是最大匹配.

不然, 选取S中未标记的点x, 考虑每个y?N(x)且xy?M, 若y是M-未饱和的, 则得到一个更大的匹配，它是把xy加入原来的匹配M得到的,将x从S中去除. 不然, y是由M中的一条边wy相连接的, w?X, 把y加入T(也有可能y本来就在T中), 把w加入S. w未标记, 记录w前的点是y. 对所有关联到x的边进行这样的探索后, 标记x. 再次叠代.

定理: 增广路算法可以得到一个相同大小的匹配和顶点覆盖. 证明: 考虑这个算法终止的情况, 即标记了S中所有的点. 我们要证明R=T?(X-S)是大小为|M|的一个顶点覆盖.

从U出发的M-交替路只能通过M中的边进入X中的顶点, 所以S-U中的每个顶点通过M与T中的顶点匹配, 并且没有M中的边连接S和Y-T. 一旦一条M-交替路到达x?S, 可以继续沿着任何未饱和的边进入T, 由于算法是对于x的所

4

本文来源：https://www.bwwdw.com/article/726f.html