人員分派問題

定義

人員分派問題(personnel assignment prob - lem)亦稱第一類分派問題.一種特殊的運輸問 題.某公司準備分派、個工人二i，二2，…，二。做兒件 工作yyz,...,yn，已知這些工人中每個人都勝任一 件或幾件工作，試問能否把所有工人都分派做一件 他所能勝任的工作?這就是人員分派問題.構造一個 二部圖G=(X,Y,E>，其中X={二」, x1 , ...，二，} ,Y= {y. }yz,...,y}，並且{xy;}EE若且唯若二能勝任 y，工作.於是，人員分派問題轉化為求G的完美對 集問題(參見“對集”).它可用求二部圖最大對集的 匈牙利法得以解決.