割当問題#

読み: わりあてもんだい
英名: Assignment Problem

代表的な組合せ最適化問題の一つである．ある集合の各要素について別の集合のどの要素に割り当てると様々な制約条件を満たしつつ最も良い割り当てを行なうことができるのかを決定する問題のことである．割当問題の例としては，各社員にどの作業を割り当てると最もコストが少なくなる（もしくは最も利益を上げることができる）のかを求める問題がある．