匈牙利法中試指派的標(biāo)記法

徐玲，肖雙喜

匈牙利法中試指派的標(biāo)記法

徐玲，肖雙喜

介紹匈牙利法的數(shù)學(xué)模型及基本步驟，對匈牙利法中試指派現(xiàn)有的改進(jìn)方法進(jìn)行了探討，提出了新的改進(jìn)方法——標(biāo)記法。經(jīng)驗(yàn)證，標(biāo)記法是有效而簡單易用的方法。

指派問題；匈牙利法；標(biāo)記法

指派問題屬于0-1整數(shù)規(guī)劃問題，是一種特殊的線性規(guī)劃問題，可以用求解線性規(guī)劃的單純形法求解，但是因?yàn)槠渥兞窟^多，用單純形法求解就顯得非常復(fù)雜。庫恩（W.W.Kuhn）運(yùn)用匈牙利數(shù)學(xué)家康尼格(D.Konig)的一個(gè)定理“系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)與覆蓋所有0元素的最少直線數(shù)相等”，于1955年提出了匈牙利方法［1］。匈牙利方法是求解指派問題的經(jīng)典算法，但是其也存在一些不足，如計(jì)算過程比較復(fù)雜。國內(nèi)學(xué)者也運(yùn)用不同的思想給出了指派問題的一些解法，如葉微（2003）［2］、高興佑（2008）［3］、賈春玉（2004）［4］等運(yùn)用伏格爾法的基本思想提出了指派問題的伏格爾算法；高俊琦（2000）［5］提出了表上作業(yè)法；李蘇北（2000）［6］提出了動態(tài)規(guī)劃算法；孔繁利（2001）［7］提出了網(wǎng)絡(luò)圖算法，還有很多新的方法在不斷地被提出。這些算法各有不同的優(yōu)點(diǎn)，但也有其缺點(diǎn)，如有的算法比匈牙利法還要繁瑣，有的算法不一定能得到最終的最優(yōu)解。在這些求解指派問題的解法中，匈牙利方法仍然是大家推崇的最經(jīng)典的解法。本文對匈牙利法中試指派過程給出了改進(jìn)方法——標(biāo)記法。

一、匈牙利法的方法介紹

（一）匈牙利法數(shù)學(xué)模型

該問題的一般提法是某單位有n項(xiàng)工作需要完成，現(xiàn)恰好有n個(gè)人可以完成這n項(xiàng)工作，由于每個(gè)人的專業(yè)水平不同，各自完成各項(xiàng)工作的成本為cij，要求一人只能完成一項(xiàng)工作，一項(xiàng)工作只能安排一人完成，如何安排使總的效率最高（或者所需的總費(fèi)用最省）。這類最優(yōu)匹配問題被稱為指派問題。

(i=1,2,…,n,j=1,2,…,n)其數(shù)學(xué)模型如下：

（二）匈牙利法的計(jì)算步驟

匈牙利法的基本步驟分為四步：

第一步：對系數(shù)矩陣進(jìn)行行（列）變換，使各行各列中都出現(xiàn)0元素。

第二步：試指派?；静襟E為：在經(jīng)過行、列變換后的矩陣中尋找獨(dú)立0元素，若得到的獨(dú)立0元素的個(gè)數(shù)等于矩陣的階數(shù)n，則將解矩陣（xij）中獨(dú)立0元素對應(yīng)的元素定為1，其余元素定為0，即得到最優(yōu)解。當(dāng)n不大時(shí)，可以用觀察、試探等簡單方法準(zhǔn)確找出獨(dú)立0元素，但是當(dāng)n較大時(shí)，就無法用觀察、試探的方法找出獨(dú)立0元素了，而按以下步驟操作：

（1）給含有唯一0元素的行(列)的0元素加圈，記為◎，該元素就是獨(dú)立0元素；然后劃去◎同列(行)的其余所有0元素，記為?。

（2）給含有唯一0元素的列(行)的0元素加圈，記為◎；將◎所在行（列）的其余所有0元素劃去，記為?。

（3）重復(fù)進(jìn)行(1)、(2)步，直至無法進(jìn)行。

（4）若仍有0元素未被劃圈（或劃去），且與該0元素同行(列)的未被劃圈（或劃去）的0元素至少有兩個(gè)，則從含未被劃圈（劃去）的0元素最少的行(列)開始，比較其所在列（行）中未被劃圈（或劃去）的0元素的數(shù)目，選擇最少的加圈(表示選擇性多的各方要“禮讓”選擇性少的一方)，然后劃去與其同行同列的其他所有0元素。重復(fù)進(jìn)行操作，直至矩陣中所有的0元素都已劃圈（或劃去）。

（5）若劃圈的獨(dú)立0元素（記為◎）的數(shù)目m與矩陣的階數(shù)n相等，則已得最優(yōu)解。若m小于n，則要轉(zhuǎn)入下一步［1］。

第三步：劃覆蓋線，以最少的直線覆蓋所有的0元素來確定該矩陣中最多能找到多少個(gè)獨(dú)立的0元素。若此時(shí)覆蓋線的條數(shù)小于矩陣的階數(shù)，則要進(jìn)入第四步繼續(xù)進(jìn)行系數(shù)矩陣的變換；若此時(shí)覆蓋線的條數(shù)等于矩陣的階數(shù)，而第二步得出的獨(dú)立0元素的個(gè)數(shù)小于矩陣的階數(shù)，則說明第二步的試指派尋找獨(dú)立0元素有誤，要重新回到第二步進(jìn)行試指派。

第四步：繼續(xù)進(jìn)行系數(shù)矩陣的變換，得到新的系數(shù)矩陣，重新回第二步進(jìn)行試指派。

匈牙利法的最大不足就是計(jì)算過程比較繁瑣，特別是第二步進(jìn)行試指派的過程非常繁瑣，也容易出錯誤。部分學(xué)者對此進(jìn)行了一些改進(jìn)，但是很多改進(jìn)并不成功，如學(xué)者張聯(lián)朋提出了利用對角線法來快速尋找獨(dú)立0元素［8］。這種方法表面看非常合理，但是在尋找獨(dú)立0元素的時(shí)候，要將系數(shù)矩陣按照列向量進(jìn)行重新排列，如果第一次無法得到n個(gè)獨(dú)立0元素，則經(jīng)歷一輪調(diào)整后重新進(jìn)行試指派，又要對系數(shù)矩陣按列向量進(jìn)行重新排列，幾個(gè)回合下來，運(yùn)算者都不清楚哪一列對應(yīng)哪項(xiàng)工作，會變得更加繁瑣。學(xué)者袁遷（2007）［9］將最小元素法引入了試指派問題的求解，但是其自己在文中也提到，經(jīng)過1340次的試驗(yàn)分析，1267次運(yùn)算有效，73次無法優(yōu)化，說明此種方法也存在問題。本文繼續(xù)運(yùn)用匈牙利方法的原理，對試指派問題提出了簡潔而準(zhǔn)確的尋找獨(dú)立0元素的方法。

二、匈牙利法中試指派的改進(jìn)方法：標(biāo)記法

試指派是通過尋找獨(dú)立0元素來完成的。庫恩（W.W.Kuhn）在基本步驟中提到：選擇性多的要“禮讓”選擇性少的。實(shí)際的做法就是將各0元素所在行和列的0元素個(gè)數(shù)之和進(jìn)行比較，個(gè)數(shù)之和較大的要“禮讓”最小的，即個(gè)數(shù)之和最小的那個(gè)就做為獨(dú)立0元素。本文的方法就是將每個(gè)0元素所在行和列的0元素之和求出，并將數(shù)字寫在該0元素的右上角，以便于比較。這種試指派的方法命名為“標(biāo)記法”。具體過程如下：

（1）將所在行和列中一眼就可以看出是獨(dú)立0元素的0（如該行、該列只有一個(gè)0元素的0）找出，將其打圈，記作◎，將與其同行、同列的其余0元素劃去，記作?。

（2）將其余0元素進(jìn)行標(biāo)記：將各0元素所在行和列的0元素個(gè)數(shù)相加，寫在各0元素的右上角。

（3）將右上角標(biāo)記數(shù)字最小的0元素找出，若同時(shí)有幾個(gè)最小數(shù)，則可以選其中任意一個(gè)，將其打圈，記作◎。將該元素所在行和列的其余0元素劃去，記作?。表示該人只完成一項(xiàng)工作，該工作只有一人完成?；氐降冢?）步，重復(fù)進(jìn)行，直到所有的0元素都已圈出或者劃去為止。

三、算例

例：求以下效率矩陣的最優(yōu)解（極小值）［1］

第二步：進(jìn)行試指派。

（1）將所在行和列中一眼就可以看出是獨(dú)立0元素的0（如該行、該列只有一個(gè)0元素的0）找出，將其打圈，記作◎。上面矩陣中沒有這樣的0元素，所以進(jìn)入第（2）步；

（2）將其余0元素進(jìn)行標(biāo)記：將各0元素所在行和列的0元素個(gè)數(shù)相加，寫在各0元素的右上角。此問題進(jìn)行標(biāo)記如下：

（3）將右上角標(biāo)記數(shù)字最小的0元素找出，若同時(shí)有幾個(gè)最小數(shù)，則可以選其中任意一個(gè)，將其打圈，記作◎。將該元素所在行和列的其余0元素劃去，記作?。本例中有3個(gè)0元素的標(biāo)記最小，均為2，則可將這三個(gè)0元素中的任意一個(gè)打圈，記作◎，將其同行（同列）的其他0元素劃去，記作?，結(jié)果如下：

（4）回到第（1）步，因?yàn)槭Ｏ碌?中不含所在行和列只有一個(gè)0元素的0，且剛才被圈出的兩個(gè)0不對其他各0的標(biāo)記產(chǎn)生影響，所以剩下各0的標(biāo)記不變，直接進(jìn)入第（3）步，得：

因此步被圈出（或劃去）的0元素影響了其他未被圈出（或劃去）的0元素，則將他們的標(biāo)記修改為：

（5）將右上角數(shù)字最小的0元素找出，將其打圈，記作◎。將該元素所在行和列的其余0元素劃去，記作?。本例中有3個(gè)0元素的標(biāo)記最小，均為3，則可將這三個(gè)0元素中的任意一個(gè)打圈，記作◎，將其同行（同列）的其他0元素劃去，記作?，結(jié)果如下：

最后還剩下兩個(gè)未被圈出（或劃去）的0元素，則可以將其標(biāo)號抹去，直接將這兩個(gè)中的任意一個(gè)圈出，而將另一個(gè)劃去，結(jié)果如下：

此時(shí)，獨(dú)立0元素的個(gè)數(shù)為4個(gè)，少于矩陣的階數(shù)，進(jìn)入第三步。

第三步：劃覆蓋線，以最少的直線覆蓋所有的0元素，結(jié)果如下：

第四步：將打√行的各元素-2，打√列的各元素+2，得新的矩陣如下：

第五步：重新進(jìn)行試指派如下：

（1）將所在行和列只有一個(gè)0元素的0找出，將其打圈，記作◎。上面矩陣中沒有這樣的0元素，所以進(jìn)入第（2）步；

（2）將其余0元素進(jìn)行標(biāo)記：將各0元素所在行和列的0元素個(gè)數(shù)相加，寫在各0元素的右上角。此問題進(jìn)行標(biāo)記如下：

（3）將右上角標(biāo)記數(shù)字最小的0元素找出，若同時(shí)有幾個(gè)最小數(shù)，則可以選其中任意一個(gè)，將其打圈，記作◎。將該元素所在行和列的其余0元素劃去，記作?。本例中有2個(gè)0元素的標(biāo)記最小，均為2，則可將這2個(gè)0元素中的任意一個(gè)打圈，記作◎，將其同行（同列）的其他0元素劃去，記作?，結(jié)果如下：

此時(shí)第一列的一個(gè)0元素被圈出，另一個(gè)0元素被劃出，被劃去的0元素影響了其同行的0元素的標(biāo)記，則將此0的標(biāo)記由3改為2，其余0元素的標(biāo)記不受這二個(gè)0元素的影響，則繼續(xù)找標(biāo)記最小的0元素，仍有2個(gè)標(biāo)記最小的0元素，標(biāo)記為2，則將其任意一個(gè)圈出，結(jié)果如下：

此時(shí)第一行的一個(gè)0元素被圈出，另一個(gè)0元素被劃去，被劃去的0元素影響了其同列的0元素的標(biāo)記，則將其同列的0元素標(biāo)記各減1，即第四列下面兩個(gè)0的標(biāo)記分別由5變?yōu)?和由4變?yōu)?，繼續(xù)對上面矩陣找標(biāo)記最小的0元素，即有標(biāo)記為2的0元素，將其圈出，結(jié)果如下：

此時(shí)第四列的一個(gè)0元素被圈出，成為獨(dú)立0元素，另一個(gè)0元素被劃去，被劃去的0元素影響了其同行的0元素的標(biāo)記，故將其同行的0元素的標(biāo)記各減1，均變?yōu)?。，此時(shí)還剩4個(gè)為被圈出（或劃去）的0元素，其標(biāo)號相同，且四個(gè)0分別位于對角線位置，則將其中處于對角線的任意兩個(gè)圈出，另外兩個(gè)劃去即可。結(jié)果如下：

此時(shí)找出5個(gè)位于不同行不同列的獨(dú)立0元素，且獨(dú)立0元素的個(gè)數(shù)m等于矩陣的階數(shù)n，則得最優(yōu)解，相應(yīng)的解矩陣為：

該問題的最優(yōu)值為：7＋6＋9＋6＋4＝32。 結(jié)果完全正確。

四、結(jié)論

1.計(jì)算結(jié)果與庫恩（W.W.Kuhn）的匈牙利法計(jì)算結(jié)果完全相同。標(biāo)記法試指派的思想來源于原匈牙利算法，也表明了這種方法的正確性。

2.標(biāo)記法采取將矩陣中每個(gè)0元素標(biāo)記的方法來確定獨(dú)立0元素，使初學(xué)者容易理解且容易操作。

3.當(dāng)遇到標(biāo)號最小的0元素多于一個(gè)時(shí)，可以選取其中的任意一個(gè)進(jìn)行標(biāo)號，此時(shí)說明該問題有多重解。

[1]運(yùn)籌學(xué)教材編寫組.運(yùn)籌學(xué)[M].北京:清華大學(xué)出版社,2005.

[2]葉微,申卯興,高歆,程智峰.求解指派問題的伏格爾方法[J].陜西師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2003(2)．

[3]高興佑,張向輝.一種基于伏格爾法的指派問題新算法[J].曲靖師范學(xué)院學(xué)報(bào),2008(3)．

[4]賈春玉,溫良.元素差額法在指派問題中的應(yīng)用[J].長春大學(xué)學(xué)報(bào),2004(2)．

[5]高俊琦.指派問題的表上作業(yè)法[J].運(yùn)籌與管理,2000(1)．

[6]李蘇北.一類最優(yōu)指派問題的動態(tài)規(guī)劃解法[J].運(yùn)籌與管理,2000(1)．

[7]孔繁利,林閩.指派問題的一種網(wǎng)絡(luò)解法[J].內(nèi)蒙古民族大學(xué)學(xué)報(bào),2001(2)．

[8]張聯(lián)朋.對指派問題匈牙利解法的兩點(diǎn)改進(jìn)[J].西安航空技術(shù)高等?？茖W(xué)校學(xué)報(bào),2007（1）.

[9]袁遷,劉舒燕.關(guān)于匈牙利法的優(yōu)化[J].武漢理工大學(xué)學(xué)報(bào),2007(3).

D221.1

A

1673-1999（2012）06-0101-03

徐玲（1975-），女，安徽潛山縣人，碩士，安徽建筑工業(yè)學(xué)院(安徽合肥 230601)管理學(xué)院講師；肖雙喜（1974-），男，安徽省宣城人，博士，安徽農(nóng)業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院副教授。

2012-01-10

國家人文社科基金青年項(xiàng)目“我國棉花產(chǎn)業(yè)面臨的外部沖擊及其縱向傳導(dǎo)跟蹤調(diào)查研究”（10CGL047)。