任務分配問題

維基百科,自由的百科全書

任務分配問題是在加權二分圖中尋找最大(或最小)加權匹配的問題。

詳述[編輯]

分為以下幾類:

  • 線性任務分配問題:二元組集合,其中分別是集合中的元素是某一函數,並滿足特定約束條件,例如:的每一個元素必須在中出現一次,或者的每一個元素必須在中出現一次,或者以上二者都必須滿足。線性任務分配問題的目標就是最大化或者最小化之和。

    該問題是線性的,因為代價函數只取決於特定的二元組,而與其它的二元組沒有任何關係。
  • 二次任務分配問題:給定家工廠和個庫房。每個庫房被分配給一家工廠。很顯然有種不同的分配組合。每家工廠和它的庫房間的代價函數被定義為二者間的距離和物流量的乘積。如何分配以使所有的代價總和最小?

這些問題都是組合優化的研究對象。

舉例[編輯]

有一些員工要完成一些任務。各個員工完成不同任務所花費的時間都不同。每個員工只分配一項任務。每項任務只被分配給一個員工。怎樣分配員工與任務以使所花費的時間最少?

婚配問題:有一些男人和一些女人,各位男人如果和某位女人結婚則其婚姻穩定程度具有不同的穩定數值。如何匹配可以使得所有配對的穩定值總和最大?也稱婚姻匹配問題。

算法[編輯]

匈牙利算法是眾多用於解決線性任務分配問題的算法之一,它可以在多項式時間內解決問題。 分配問題是運輸問題的特例,運輸問題最少成本流量問題的特例,而它們都是線性規劃的特例。因此,單純形法可以作為解決這些問題的通法。然而,針對每種特殊情形設計的專門算法可以提高解決問題的效率。如果問題的成本函數包含二次不等式,則稱之為二次分配問題。

任務分配問題一般可以在多項式時間內轉化成最大流量問題(Maximum Flow Problem)。

參看[編輯]