標籤: 暫無標籤

  匈牙利解法(Hungarian method)

  匈牙利法是求解及小型(優化方向為極小)指派問題的一種方法,這種方法最初由w.w.kuhn提出,后經改進而形成,解法基於匈牙利數學家D.König給出的一個定理而得名。

1 匈牙利法 -匈牙利法的理論基礎

  (1)若從效率矩陣(cij)的行(或列)的各元素中分別減去該行(或列)的最小元素后得到一個新矩陣(bij),則以(bij)為效率矩陣的指派問題與原問題有相同的最優解。

  經過上述變換后,(bij)中的每行和每列都至少含有一個0元素,稱位於不同行不同列的0元素為獨立的0元素。

  (2)若(bij)有n個獨立的0元素,由此可得一個解矩陣,方法為在X中令對應於(bij)的0元素位置的元素為1,其它位置的元素為0,則X為指派問題的最優解。

  (3)D.König定理:矩陣中獨立0元素的最多個數等於能覆蓋所有0元素的最少直線數。

  根據上面的原理,匈牙利法可分為如下的四個步驟:

  1.對效率矩陣(cij)做變換得(bij),使(bij)中每行每列均有0元素,實現的方法是:

  (1)從(cij)的每行元素中減去該行的最小元素;

  (2)再從所得矩陣的每列元素中減去該列的最小元素,得(bij).

  2.求(bij)的獨立0元素。行列相間地對0元素給出兩種標記「*」和「△」,它們分別表示該元素「是」或「不是」獨立0元素,在所有的0元素全局有標記時,若獨立0元素(即標有*的0元素)的個數為n時,已得最優解,否則轉第3步,

  標記的方法是:搜索含有未被標記的0元素且個數最少的行(或列),等概率地從中隨機選擇一個0元素給以標記*,並對該元素所在的行和列中其它未被標記的0元素給以標記△。

  顯然標記過程可在有限步完成,從經濟意義上看,當給位置為(i,j) 的0元素標記*時,就意味著將第j項工作分配給第i個人員,此時完成任務的效率最高,同時對人員i和工作j的指派已經完成,需將對第i行和第j列的未被標記的0元素標記△,以示以後不再考慮它們的指派,應當說明:在按行(或列)進行標記時,若有多個未被標記的0元素時,上述方法只保證這種指派的局部最優性,在全局上是否最優依賴於獨立0元素的個數是否等於n .

  3.確定矩陣(bij)中獨立0元素的最多個數m,當m<n時,轉第4步;否則,去掉已有標記,轉第2步。

  確定m的方法是: 據(bij)中未被刪除的部分搜索不含標記*的0元素所在的行,給該行以標號「√」,若該行有標記為△的0元素,刪去該元素所在的列,在不具有滿足上述條件的行時,過程終止。設被標記的行數為k,刪去的列數為l。則m=n-k+l.

  這一步的依據是D.K&ouml;nig定理,這是因為對被刪除的每一列和未被標記的每一行做直線,這些直線式覆蓋所有0元素所需要的最少的直線,從而直線條數為(bij)中獨立0元素最多的個數,在m=n時,表示在第2步中某一次指派僅為局部最優,但不為全局最優,演算法要求退回第2步,重新進行指派,第2步中關於等概率地隨機選取標記為*的0元素可使新指派得以實現。在m<n時,說明如果僅按將工作指派給效率最高的人員去完全(即第2步),是無法實現,需要將一些工作指派給效率次高的人員。在數學上體現為矩陣(bij)中的0元素還不足夠的多。下一步的目的是對(bij)再做變換以得到更多的0元素,從經濟上講,就是如何選擇一些工作由效率次高的人員去完成。

  4.對(bij)再做變換以增加獨立0元素的個數。

  方法為:求出所有已標記「√」的行中且未被刪除部分包含元素的最小值,然後,所有已標記的行中的每一個元素(含已刪除部分)加上這一最小值,而它刪除的列中的每一個元素減去該值,得到一個新矩陣,仍記為(bij),去掉所有的標記,轉第2步。

  在人員數和任務n不是很大時,匈牙利法是求解指派問題的有效方法,且易於編製成軟體,。

  在實際問題中還可能遇到極大型的指派問題,我們可以將之轉化為極小型問題,然後應用匈牙利法求解,具體地,

  令

  C』ij=M-Cij, i,j=1,2,3,…,n

  其中M為一個足夠大的正數以保證c』ij非負,例如可取M 為矩陣C中的最大元素,這樣可生成一個以(c』ij)為矩陣的極小型指派問題,由於

  ,

  nM為固定的常數,兩個指派問題有最同的最優解。

  在實際的任務分配中,還可能出現人員(或設備)數與任務數不相等的情況,而且要求每個人員只先完成一件任務(在人員數少於任務數時),或者有些人員可暫不安排任務(在人員數多餘任務數時),可稱這樣的問題為不平衡的指派問題,此時,可通過虛擬人員或虛擬任務使之轉化為一般(平衡)的指派問題,即在原矩陣中增加一些行或者列,使之成為方陣,在極小型問題中所增加的元素應充分的大,如為原矩陣中最大的元素的值,而在極大型問題中增加的元素應足夠的小。如可取零值。

相關評論

同義詞:暫無同義詞