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

于淑蘭

(泊頭職業學院 經濟管理系，河北 泊頭 062150)

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

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

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

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

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

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

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

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

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

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

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

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

表2 司機完成任務的時間

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

(2)調整矩陣

獨立零元的個數不等于矩陣的階數，仍需要調整.

(3)按照規則進行調整

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

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

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

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

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

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

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

參考文獻：

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

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