零元素行擴展路徑算法求解線性指派問題

遼寧省鞍山市新世紀實驗學校 何國旭

一、引言

給定一個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節的討論知：零元素行擴展路徑算法總可快速得到線性指派問題的一個最優解。