運用匈牙利法求解分配問題

于淑蘭

(泊頭職業(yè)學院 經(jīng)濟管理系，河北 泊頭 062150)

匈牙利法是求解極小型(優(yōu)化方向為極小)指派問題的一種方法，這種方法最初由w.w.kuhn提出，后經(jīng)改進而形成，解法基于匈牙利數(shù)學家D.K?nig給出的一個定理而得名.它的基本原理是:對任何一個求最小值的效率矩陣(cij)，將其某一行或某一列的各個元素減去或者加上同一個常數(shù)k，得到一個新的矩陣(bij)，則新矩陣與原矩陣有相同的最優(yōu)解.如果問題是求最大值的話，則需要把目標函數(shù)轉(zhuǎn)換成求最小值，再使用匈牙利法求解.當矩陣中獨立零元素的個數(shù)等于矩陣階數(shù)n時，獨立零元素對應的變量xij=1，其他元素對應的變量xij=0，這就是分派問題的最優(yōu)解矩陣，而很多情況下我們很難直接得到獨立零元素的個數(shù)等于矩陣階數(shù)這種結(jié)果，遇到這種情況需要進行調(diào)整，在《運籌學基礎及應用》這本教材中給出了調(diào)整的方法，在教學過程中發(fā)現(xiàn)書中針對此內(nèi)容寫的有些松散，方法不易學生接受，難度大.結(jié)合自己的教學經(jīng)驗，歸納整理了一個更為簡單可行的調(diào)整方法.下面將其應用到具體實例中加以說明.

例1 有一份說明書，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個人去完成.因個人專長不同，他們完成翻譯不同文字所需的時間(h)如表1所示，應如何分配，使這四人分別完成這四項任務總的時間為最小.

表1 翻譯不同文字所需的時間(h)

解題步驟如下:(1)先從效率矩陣的每行減去該行的最小元素，再從效率矩陣的每列減去該列的最小元素;(2)找出矩陣中獨立零元素.先找出每行中僅有一個“0”的元素，并劃去與該“0”同列的其他0元素，即φ；然后對矩陣的列作同樣的變換;(3)當矩陣中獨立零元素的個數(shù)等于矩陣的階數(shù)時，可以分派任務，否則需要調(diào)整矩陣，方法如下:①對沒有獨立的零所在的行打*;②在已打*的行中，對φ所在的列打*;③在已打*的列中，對有獨立零所在的行打*;簡記為:沒有零的行→φ的列→有獨立零的行;④重復以上三步直到不能做標記為止;⑤用直線劃去沒有標記的行，劃去有標記的列;⑥將保留下來的元素減去它們的最小元素，將僅被一條直線覆蓋的元素保持不變，將同時被兩條直線覆蓋的元素，分別加上“減去的最小元素”.

調(diào)整完畢后，再重新找出獨立的零元，滿足獨立零元的個數(shù)等于矩陣的階數(shù)，就停止，否則就按上述步驟繼續(xù)調(diào)整，直到得到分配方案為止.

解 (1)從矩陣的每行減去該行的最小元素，再從矩陣的每列減去該列的最小元素(目的是為了簡化數(shù)據(jù))；

(2)找出矩陣中獨立的零元素，記得要劃去對應列或者對應行的“0”；

(3)由于獨立零元素的個數(shù)為3個，小于矩陣的階數(shù)4，所以必須進行調(diào)整.

未被直線覆蓋的數(shù)字最小的是2，將“8、2、5、11、4、5”分別減去2，將同時被兩條直線覆蓋的數(shù)字“11、2”加上2，得到新的矩陣，并找出獨立的零元

即最優(yōu)方案為:甲將說明書譯成俄文，乙將說明書譯成日文，丙將說明書譯成英文，丁將說明書譯成德文，全部所需的時間為4+4+9+11=28h，這種方法，相對于教材要簡單明了，思路上更清晰，學生更容易接受.

有時我們會發(fā)現(xiàn)對矩陣進行調(diào)整后，各行各列都沒有獨立的零元素，對于這種情況就需要進行假設.

例2 假定有五位司機被分配完成五項任務，完成各項任務的時間(h)如表2:問應如何分配，使得這五位司機完成這五項任務時間最短.

表2 司機完成任務的時間

解 (1)從矩陣的每行減去該行的最小元素，再從矩陣的每列減去該列的最小元素，并找出獨立的零元素.

(2)調(diào)整矩陣

獨立零元的個數(shù)不等于矩陣的階數(shù)，仍需要調(diào)整.

(3)按照規(guī)則進行調(diào)整

矩陣中各行各列都沒有獨立的零.可以從第一行中任意一個“0”處進行假設，此例中第一行共有三個零，可以進行三種假設.

(4)①假設司機甲做任務A，找出獨立的零元，要注意的是，甲已經(jīng)做了任務A，就不能再做其他任務，所以第一行中余下的兩個“0”應劃去，同時劃去第一列的“0”；再從各行到各列找出獨立的零元.

獨立零元的個數(shù)等于矩陣的階數(shù)，得到分配方案1.

司機甲完成任務A，司機乙完成任務E，司機丙完成任務C，司機丁完成任務B，司機戊完成任務D.完成該方案總的時間為:7+9+4+3+5=28h.

5+7+6+6+4=28h.

5+7+6+6+4=28h.

經(jīng)過對比發(fā)現(xiàn)三個方案用時是一樣的，所以用哪個方案均可，如果問題中三個方案的時間不相同，我們應該取用時最短的那個方案.

參考文獻：

[1]王凱陽.物流運籌學[M].北京:北京大學出版社，2009.

[2]胡運權(quán)，等.運籌學基礎及應用[M].第五版，北京:高等教育出版社，2008.