最適化セミナーのご案内

2.13.1 割当問題とは

 割当問題とは,集合Aの要素を集合Bの要素のどれに割り当てるかを決定する問題です.

 また,割当問題はマス目を埋める問題に置き換えることができます.上記の図を,マス目を埋めるイメージで表すと以下の図のようになります.

  a1 a2 a3    
b1        
b2        
b3          
b4        
           
           

 

 割当問題はマスの埋め方のルールを制約条件として与えることによって,個々の問題に対応する定式化を行うことができます.割当問題の応用例として,例えば以下のものがあります.

  • 人員配置問題
  • シフトスケジューリング問題
  • 配車計画問題
  • 訪問スケジューリング決定問題
  • マーケットテリトリー決定問題

 

 

上に戻る