割り当て問題（assignment problem） 2019/8/2 割り当て問題（assignment problem） ｎ種類の資源（資材、人、設備など）を、 これと同数のｎ種類の用途（需要、仕事など）に一つずつ割り当て、 全体としての計画を最適化（最大化・最少化）する問題。 有効さ行列 ・・・ ｎ×ｎの行列 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
解法の基本 ハンガリー法 有効さ行列において、損失などを最少にする問題の固有の解法。 有効さ行列において、損失などを最少にする問題の固有の解法。 行列の各行、または各列に関して、任意の定数を引いても、各行、各列の値の関係は変わらず、適当な割り当て方も変わらない。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
最小化問題の手順 ① 各行の最小値を各行のそれぞれの数値から引く。 ② 各列の最小値を各列のそれぞれの数値から引く。 → 各行、各列に少なくとも１個の０が存在する。 ③ 出来る限り少ない本数の直線で全ての０を引く。 ④ 列（行）の数（ｎ）＝直線の本数ならば、最適割り当てを求める。 ⑤ 列（行）の数（ｎ）≠直線の本数ならば、修正行列をつくる。 直線の引かれていない数値の中の最小値（α）とすると、 ・直線の引かれていない全ての値からαを引く。 ・直線が交差している数値にはαを加える。 ・その他の数値はそのまま。 ⑥ ③～⑤を、最適割り当てが見つかるまで繰り返す。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
最大化問題の手順 最小化問題に直してから解く。 最大化問題 → 最小化問題 ① 有効さ行列の数値の中の最大値（β）を見つける。 ① 有効さ行列の数値の中の最大値（β）を見つける。 ② 有効さ行列の各数値をβから引く。 ③ 最小化問題を解く。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
ｍ×ｎの割り当て問題 ダミー（dummy）の行（あるいは列）を加えて、 ｎ×ｎの有効さ行列にする。 ダミー行（あるいは列）に割り当てがあった場合は、その割り当ては無視する。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
最小化問題の例 ３人の作業員を３種類の仕事に就業させる。 ３人の作業員を３種類の仕事に就業させる。 作業員の各仕事に対する作業時間は表の通りである。総作業時間を最少にするような割り当てを考えよ。 仕事 Ⅰ Ⅱ Ⅲ 作業員 Ａ Ｘ１１ Ｘ１２ Ｘ１３ Ｂ Ｘ２１ Ｘ２２ Ｘ２３ Ｃ Ｘ３１ Ｘ３２ Ｘ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
最大化問題の例 ３人の営業マンを３地域に営業に出す。 ３人の営業マンを３地域に営業に出す。 各営業マンの各地域に対する過去の成果は表の通りである。３人の成果合計を最大にするような割り当てを考えよ。 地域 Ⅰ Ⅱ Ⅲ 営業マン Ａ Ｘ１１ Ｘ１２ Ｘ１３ Ｂ Ｘ２１ Ｘ２２ Ｘ２３ Ｃ Ｘ３１ Ｘ３２ Ｘ３３ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
ＬＰの割り当て問題への適用 割り当て問題はＬＰで解くことも出来る。 ３×３の最小化問題の場合 Ａ ： ａ１１＋ａ１２＋ａ１３＝１ Ａ ： ａ１１＋ａ１２＋ａ１３＝１ Ｂ ： ａ２１＋ａ２２＋ａ２３＝１ Ｃ ： ａ３１＋ａ３２＋ａ３３＝１ Ⅰ ： ａ１１＋ａ２１＋ａ３１＝１ Ⅱ ： ａ１２＋ａ２２＋ａ３２＝１ Ⅲ ： ａ１３＋ａ２３＋ａ３３＝１ ａｉｊ は ０ ｏｒ １ （割り当てがあれば１、割り当てがなければ０） ａ１１Ｘ１１＋ａ１２Ｘ１２＋ａ１３Ｘ１３＋ａ２１Ｘ２１＋ａ２２Ｘ２２＋ａ２３Ｘ２３＋ａ３１Ｘ３１＋ａ３２Ｘ３２＋ａ３３Ｘ３３＝Ｚ Ｚを最少にするような ａｉｊ を求める。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ