遼寧省鞍山市新世紀(jì)實(shí)驗(yàn)學(xué)校 何國旭

一、引言

給定一個(gè)n階消耗矩陣[cij]和一個(gè)二元變量xij，其中xij=1表示第i行指派給第j列，xij=0表示第i行不指派給第j列，則線性指派問題描述如下。

（1）約束條件：

（2）其中x=1ij或0

（3）利用兩個(gè)關(guān)聯(lián)變量ui和vj分別替換約束條件（2）（3），可得線性指派問題的對偶問題為：D(AP)

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

2問題的一個(gè)最優(yōu)解。

線性指派問題是一個(gè)典型的組合優(yōu)化問題，在運(yùn)籌學(xué)、管理學(xué)等領(lǐng)域具有廣泛的應(yīng)用。

本章受到匈牙利算法和最短擴(kuò)展路徑算法基本思想的啟發(fā)，得到了一種新的求解線性指派問題算法：零元素行擴(kuò)展路徑算法。

該方法的基本思想是首先對消耗矩陣作一個(gè)初步的簡化，并根據(jù)簡化的消耗矩陣得到一個(gè)預(yù)指派。然后對預(yù)指派中的每一個(gè)非零元素，依據(jù)該元素所在的行得到一條零元素行擴(kuò)展路徑。最后根據(jù)該路徑對預(yù)指派作進(jìn)一步的調(diào)整以增加指派中的零元素。重復(fù)上述步驟直到預(yù)指派中的所有元素都為零，即得到了一個(gè)最優(yōu)解。

二、理論基礎(chǔ)

本節(jié)中，c表示初步簡化后的消耗矩陣；y表示預(yù)指派，其中y把每一行指派給不同的列。如果y把i行指派給j列，則稱cij是一個(gè)被y選中的元素。

定義1：如果cij2=0且j2列被y指派給不同于i的i2行，則i2行是i行的一個(gè)行零元素行，i行是i2行的一個(gè)列零元素行。

定義2：根據(jù)下述步驟可得到一個(gè)行集SRZRi，則稱該行集為第i行的零元素行集。1）初始化SRZRi為{i}。2）針對c中的每一行j，如果它不在SRZRi中且是SRZRi中某行的一個(gè)零元素行，則把j添加到SRZRi中。3）重復(fù)步驟2）直到?jīng)]有新的行能添加到SRZRi中為止。

定義3：1）如果 il+1是il(l=1,2, …, k)的一個(gè)行零元素行和 i1行是i行的一個(gè)行零元素行，則路徑i→i1→…→ik-1→ik是i行到 ik行的一個(gè)零元素行路徑。 2）如果路徑i→i1→…→ik-1→ik是i行到 ik行的一個(gè)零元素行路徑，且 、 或 ，其中行i、ik分別指派給列j和jk，則該路徑是i行到 ik行的一個(gè)零元素行擴(kuò)展路徑。

定理1：如果路徑i→i1→…→ik-1→ik是i行到 ik行的一個(gè)零元素行擴(kuò)展路徑，假設(shè)il行(l=1, … , k-1, k)指派給jl列和i行指派給j列，如圖1所示。則根據(jù)下面的變換后將使得被選零元素的數(shù)量至少增加一個(gè): ik行指派給j列，il-1行指派給jl(l=k, k-1,…, 2)列和i行指派給 j1列。

定義4：假設(shè)SRZRi={ik, ik-1, …,i1, i0=i}，il指派給 jl(l=k, k-1,…, 1) 列和i行指派給j列。當(dāng)j列和il(l= k, k-1, …, 1, 0)行上的所有元素都大于零時(shí)，假設(shè)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：假設(shè)i 行指派給j列。對于一次零元素行簡化，1）化簡后c中所有元素仍然都非負(fù)；2）如果 j列和SRZRi中的行上沒有等于miu的元素，則SRZRi中的行數(shù)至少增加1。

定理3：對于y選中的非零元素cij，如果不存在i行到SRZRi中行的零元素行擴(kuò)展路徑，同時(shí)y選中 k1 (＜n)個(gè)零元素，則最多進(jìn)行(k1+1)次零元素化簡，cij將變?yōu)榱?，或者SRZRi中至少存在一個(gè)ih行，使得i行到ih行的零元素行路徑是一個(gè)零元素行擴(kuò)展路徑。

三、零元素行擴(kuò)展路徑算法

對于給定的n維消耗矩陣c，根據(jù)第2節(jié)的討論，得到了求解線性指派問題的零元素行擴(kuò)展路徑算法，其基本步驟如下。

Step1. 首先消耗矩陣c中的每一行都減去該行中的最小元素。然后c中的每一列都減去該列中的最小元素，從而得到一個(gè)簡化的消耗矩陣，仍記為c。

Step2. 據(jù)簡化的消耗矩陣c得到一個(gè)預(yù)解y，然后令i=1。

Step3. 如果i＞n, 則結(jié)束計(jì)算，意味著y已是一個(gè)最優(yōu)解。否則轉(zhuǎn)step4。

Step4. 設(shè)cij 是y中的一個(gè)元素。那么如果cij=0，則令i=i+1, 然后轉(zhuǎn)step3。否則轉(zhuǎn)step5。

Step5. 根據(jù)定義2得到i行的零元素行集SRZRi。如果在SRZRi中存在一行ik, 使得ik到i行的零元素行路徑是一條零元素行擴(kuò)展路徑，則據(jù)該零元素行擴(kuò)展路徑調(diào)整指派y，然后轉(zhuǎn)step4。否則轉(zhuǎn)step6.

Step6. 針對SRZRi進(jìn)行一次零元素行簡化，然后轉(zhuǎn)step5。

根據(jù)第2節(jié)的討論知：零元素行擴(kuò)展路徑算法總可快速得到線性指派問題的一個(gè)最優(yōu)解。