指派问题详解VIP专享

第一章 绪 论 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 很大时，用完全枚举法解题几乎是不可能 1 的. 而已有的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 元素的最少直线数. 当独立零元素的个数等于矩阵的阶数时就得到最优解. 2 3 、理论基础 定义: 图G 的一个匹配M 是图G 中不相交的边的集合. 属于匹配M 中的边的所有端点称为被该匹配M 饱和, 其他的顶点称为M-未饱和的. 如果一个匹配M饱和了图G 的所有顶点，则称该匹配M 是一个完全匹配....