零元素行扩展路径算法求解线性指派问题

辽宁省鞍山市新世纪实验学校 何国旭

一、引言

给定一个n阶消耗矩阵[cij]和一个二元变量xij，其中xij=1表示第i行指派给第j列，xij=0表示第i行不指派给第j列，则线性指派问题描述如下。

（1）约束条件：

（2）其中x=1ij或0

（3）利用两个关联变量ui和vj分别替换约束条件（2）（3），可得线性指派问题的对偶问题为：D(AP)

（4）约束条件：ui+ vj≤ cij(i, j = 1,2,…,n)

2问题的一个最优解。

线性指派问题是一个典型的组合优化问题，在运筹学、管理学等领域具有广泛的应用。

本章受到匈牙利算法和最短扩展路径算法基本思想的启发，得到了一种新的求解线性指派问题算法：零元素行扩展路径算法。

该方法的基本思想是首先对消耗矩阵作一个初步的简化，并根据简化的消耗矩阵得到一个预指派。然后对预指派中的每一个非零元素，依据该元素所在的行得到一条零元素行扩展路径。最后根据该路径对预指派作进一步的调整以增加指派中的零元素。重复上述步骤直到预指派中的所有元素都为零，即得到了一个最优解。

二、理论基础

本节中，c表示初步简化后的消耗矩阵；y表示预指派，其中y把每一行指派给不同的列。如果y把i行指派给j列，则称cij是一个被y选中的元素。

定义1：如果cij2=0且j2列被y指派给不同于i的i2行，则i2行是i行的一个行零元素行，i行是i2行的一个列零元素行。

定义2：根据下述步骤可得到一个行集SRZRi，则称该行集为第i行的零元素行集。1）初始化SRZRi为{i}。2）针对c中的每一行j，如果它不在SRZRi中且是SRZRi中某行的一个零元素行，则把j添加到SRZRi中。3）重复步骤2）直到没有新的行能添加到SRZRi中为止。

定义3：1）如果 il+1是il(l=1,2, …, k)的一个行零元素行和 i1行是i行的一个行零元素行，则路径i→i1→…→ik-1→ik是i行到 ik行的一个零元素行路径。 2）如果路径i→i1→…→ik-1→ik是i行到 ik行的一个零元素行路径，且 、 或 ，其中行i、ik分别指派给列j和jk，则该路径是i行到 ik行的一个零元素行扩展路径。

定理1：如果路径i→i1→…→ik-1→ik是i行到 ik行的一个零元素行扩展路径，假设il行(l=1, … , k-1, k)指派给jl列和i行指派给j列，如图1所示。则根据下面的变换后将使得被选零元素的数量至少增加一个: ik行指派给j列，il-1行指派给jl(l=k, k-1,…, 2)列和i行指派给 j1列。

定义4：假设SRZRi={ik, ik-1, …,i1, i0=i}，il指派给 jl(l=k, k-1,…, 1) 列和i行指派给j列。当j列和il(l= k, k-1, …, 1, 0)行上的所有元素都大于零时，假设miu 是il(l=k, k-1, …, 1, 0)行上值最小的元素但不是 jl(l=k, k-1, …, 1)列上值最小的元素，则称一次如下的变化为一次零元素行简化: 首先il(l= k,k-1, …, 1, 0)行上的所有元素减去miu，然后jl (l=k, k-1, …, 1)列上所有元素加上miu。

定理2：假设i 行指派给j列。对于一次零元素行简化，1）化简后c中所有元素仍然都非负；2）如果 j列和SRZRi中的行上没有等于miu的元素，则SRZRi中的行数至少增加1。

定理3：对于y选中的非零元素cij，如果不存在i行到SRZRi中行的零元素行扩展路径，同时y选中 k1 (＜n)个零元素，则最多进行(k1+1)次零元素化简，cij将变为零，或者SRZRi中至少存在一个ih行，使得i行到ih行的零元素行路径是一个零元素行扩展路径。

三、零元素行扩展路径算法

对于给定的n维消耗矩阵c，根据第2节的讨论，得到了求解线性指派问题的零元素行扩展路径算法，其基本步骤如下。

Step1. 首先消耗矩阵c中的每一行都减去该行中的最小元素。然后c中的每一列都减去该列中的最小元素，从而得到一个简化的消耗矩阵，仍记为c。

Step2. 据简化的消耗矩阵c得到一个预解y，然后令i=1。

Step3. 如果i＞n, 则结束计算，意味着y已是一个最优解。否则转step4。

Step4. 设cij 是y中的一个元素。那么如果cij=0，则令i=i+1, 然后转step3。否则转step5。

Step5. 根据定义2得到i行的零元素行集SRZRi。如果在SRZRi中存在一行ik, 使得ik到i行的零元素行路径是一条零元素行扩展路径，则据该零元素行扩展路径调整指派y，然后转step4。否则转step6.

Step6. 针对SRZRi进行一次零元素行简化，然后转step5。

根据第2节的讨论知：零元素行扩展路径算法总可快速得到线性指派问题的一个最优解。