割り当て問題（assignment problem）

Presentation on theme: "割り当て問題（assignment problem）"— Presentation transcript:

1 割り当て問題（assignment problem）
2019/8/2 割り当て問題（assignment problem） 　 ｎ種類の資源（資材、人、設備など）を、 　 これと同数のｎ種類の用途（需要、仕事など）に一つずつ割り当て、 全体としての計画を最適化（最大化・最少化）する問題。 　　有効さ行列　・・・　ｎ×ｎの行列 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ

2 解法の基本 ハンガリー法 有効さ行列において、損失などを最少にする問題の固有の解法。
　　 有効さ行列において、損失などを最少にする問題の固有の解法。 　　 行列の各行、または各列に関して、任意の定数を引いても、各行、各列の値の関係は変わらず、適当な割り当て方も変わらない。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ

3 最小化問題の手順 ① 各行の最小値を各行のそれぞれの数値から引く。 ② 各列の最小値を各列のそれぞれの数値から引く。
　　　　　　　　　　→ 各行、各列に少なくとも１個の０が存在する。 ③ 出来る限り少ない本数の直線で全ての０を引く。 ④ 列（行）の数（ｎ）＝直線の本数ならば、最適割り当てを求める。 ⑤ 列（行）の数（ｎ）≠直線の本数ならば、修正行列をつくる。 　　直線の引かれていない数値の中の最小値（α）とすると、 　　・直線の引かれていない全ての値からαを引く。 　　・直線が交差している数値にはαを加える。 　　・その他の数値はそのまま。 ⑥ ③～⑤を、最適割り当てが見つかるまで繰り返す。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ

4 最大化問題の手順 最小化問題に直してから解く。 最大化問題 → 最小化問題 ① 有効さ行列の数値の中の最大値（β）を見つける。
　　① 有効さ行列の数値の中の最大値（β）を見つける。 　　② 有効さ行列の各数値をβから引く。 　　③ 最小化問題を解く。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ

5 ｍ×ｎの割り当て問題 ダミー（dummy）の行（あるいは列）を加えて、 ｎ×ｎの有効さ行列にする。
ダミー行（あるいは列）に割り当てがあった場合は、その割り当ては無視する。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ

6 最小化問題の例 ３人の作業員を３種類の仕事に就業させる。
　 ３人の作業員を３種類の仕事に就業させる。 　 作業員の各仕事に対する作業時間は表の通りである。総作業時間を最少にするような割り当てを考えよ。 仕事 Ⅰ Ⅱ Ⅲ 作業員 Ａ Ｘ１１ Ｘ１２ Ｘ１３ Ｂ Ｘ２１ Ｘ２２ Ｘ２３ Ｃ Ｘ３１ Ｘ３２ Ｘ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ

7 最大化問題の例 ３人の営業マンを３地域に営業に出す。
　 ３人の営業マンを３地域に営業に出す。 　 各営業マンの各地域に対する過去の成果は表の通りである。３人の成果合計を最大にするような割り当てを考えよ。 地域 Ⅰ Ⅱ Ⅲ 営業マン Ａ Ｘ１１ Ｘ１２ Ｘ１３ Ｂ Ｘ２１ Ｘ２２ Ｘ２３ Ｃ Ｘ３１ Ｘ３２ Ｘ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ

8 ＬＰの割り当て問題への適用 割り当て問題はＬＰで解くことも出来る。 ３×３の最小化問題の場合 Ａ ： ａ１１＋ａ１２＋ａ１３＝１
　　　　Ａ　 ：　ａ１１＋ａ１２＋ａ１３＝１ 　　　　Ｂ　 ：　ａ２１＋ａ２２＋ａ２３＝１ 　　　　Ｃ　 ：　ａ３１＋ａ３２＋ａ３３＝１ 　　　　Ⅰ　：　ａ１１＋ａ２１＋ａ３１＝１ 　　　　Ⅱ　：　ａ１２＋ａ２２＋ａ３２＝１ 　　　　Ⅲ　：　ａ１３＋ａ２３＋ａ３３＝１ 　　　 ａｉｊ は ０ ｏｒ １　（割り当てがあれば１、割り当てがなければ０） 　ａ１１Ｘ１１＋ａ１２Ｘ１２＋ａ１３Ｘ１３＋ａ２１Ｘ２１＋ａ２２Ｘ２２＋ａ２３Ｘ２３＋ａ３１Ｘ３１＋ａ３２Ｘ３２＋ａ３３Ｘ３３＝Ｚ 　Ｚを最少にするような ａｉｊ を求める。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ