论文部分内容阅读
一、引言
给定一个n阶消耗矩阵[cij]和一个二元变量xij，其中xij=1表示第i行指派给第j列，xij=0表示第i行不指派给第j列，则线性指派问题描述如下。
C（AP） ； （1）约束条件： ；（2）
； 其中 或0 （3）
利用两个关联变量ui和vj分别替换约束条件（2）（3），可得线性指派问题的对偶问题为：
D（AP） （4）约束条件： （5）
令 表示简化消耗矩阵，给定一组解x和（u，v）分别对应原始和对偶问题，则最优条件是 （6）
即如果在简化矩阵 中存在n个独立的零元素或一个关于（1， 2， …， n）的排列 使 ，则 是线性指派问题的一个最优解。
线性指派问题是一个典型的组合优化问题，在运筹学、管理学等领域具有广泛的应用。
本章受到匈牙利算法和最短扩展路径算法基本思想的启发，得到了一种新的求解线性指派问题算法：零元素行扩展路径算法。
该方法的基本思想是首先对消耗矩阵作一个初步的简化，并根据简化的消耗矩阵得到一个预指派。然后对预指派中的每一个非零元素，依据该元素所在的行得到一条零元素行扩展路径。最后根据该路径对预指派作进一步的调整以增加指派中的零元素。重复上述步骤直到预指派中的所有元素都为零，即得到了一个最优解。
二、理论基础
本节中，c表示初步简化后的消耗矩阵；y表示预指派，其中y把每一行指派给不同的列。如果y把i行指派給j列，则称cij是一个被y选中的元素。
定义1：如果 且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维消耗矩阵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节的讨论知：零元素行扩展路径算法总可快速得到线性指派问题的一个最优解。
给定一个n阶消耗矩阵[cij]和一个二元变量xij，其中xij=1表示第i行指派给第j列，xij=0表示第i行不指派给第j列，则线性指派问题描述如下。
C（AP） ； （1）约束条件： ；（2）
； 其中 或0 （3）
利用两个关联变量ui和vj分别替换约束条件（2）（3），可得线性指派问题的对偶问题为：
D（AP） （4）约束条件： （5）
令 表示简化消耗矩阵，给定一组解x和（u，v）分别对应原始和对偶问题，则最优条件是 （6）
即如果在简化矩阵 中存在n个独立的零元素或一个关于（1， 2， …， n）的排列 使 ，则 是线性指派问题的一个最优解。
线性指派问题是一个典型的组合优化问题，在运筹学、管理学等领域具有广泛的应用。
本章受到匈牙利算法和最短扩展路径算法基本思想的启发，得到了一种新的求解线性指派问题算法：零元素行扩展路径算法。
该方法的基本思想是首先对消耗矩阵作一个初步的简化，并根据简化的消耗矩阵得到一个预指派。然后对预指派中的每一个非零元素，依据该元素所在的行得到一条零元素行扩展路径。最后根据该路径对预指派作进一步的调整以增加指派中的零元素。重复上述步骤直到预指派中的所有元素都为零，即得到了一个最优解。
二、理论基础
本节中，c表示初步简化后的消耗矩阵；y表示预指派，其中y把每一行指派给不同的列。如果y把i行指派給j列，则称cij是一个被y选中的元素。
定义1：如果 且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维消耗矩阵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节的讨论知：零元素行扩展路径算法总可快速得到线性指派问题的一个最优解。