割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース（マッチング） • ３種類のものを割当てる問題.

Presentation on theme: "割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース（マッチング） • ３種類のものを割当てる問題."— Presentation transcript:

1 割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース（マッチング） • ３種類のものを割当てる問題

2 割当て問題とは 端的に言えば、制約条件を満たすように、人を仕事に割り振る問題

3 割当て問題（基本のもの） • それぞれの人は、できる仕事とできない仕事がある • それぞれの人は、同時に受け持てる仕事の上下限がある
• それぞれの仕事は、受け持つ人の最低人数がある 担当者数 の上下限 担当仕事数 の上下限 受け持てない

4 割当て問題（基本のもの） これらを満たす、人 対 仕事の割当を見つける問題
また、人 i が仕事 j を受け持つときに費用 aij がかかるとすると、総コストが最小な割り当て方を求める問題

5 割当て問題：記法 仕事をする人： 1,2,…,n 仕事： 1,2,…,m 人 i が仕事 j を受け持つときにかかる費用： aij
人 i が受け持つ仕事数の上下限： ui, li 仕事 j を受け持つ人数の上下限： u'j, l'j

6 割当て問題：定式化 変数： xij ：人 i が仕事 j を受け持つとき 1、そうでないとき 0 目的関数： Σ aij xij 制約条件：
　　li ≦ Σj=1,…,m xij ≦ ui 　　l‘j ≦ Σi=1,…,n xij ≦ u'j 　　xij ∈ { 0, 1 } 01整数計画問題になる

7 割当て問題：線形化 01制約を、線形緩和した線形計画を作る 目的関数： Σ aij xij 制約条件：
　　li ≦ Σj=1,…,m xij ≦ ui 　　l‘j ≦ Σi=1,…,n xij ≦ u'j 　　0 ≦ xij ≦ 1 「単体法（シンプレックス法）で得られる最適解は、かならず01解になっている」という良い性質がある

8 割当て問題：拡張 • 各人が、各仕事に何時間かの時間を割く、という問題を考える xij ：人 i が仕事 j に割く時間
人 i が仕事 j に割く時間の上下限： ui, li 仕事 j を必要な総時間数の上下限： u'j, l'j 目的関数：　　Σ aij xij 制約条件：　　li ≦ Σj=1,…,m xij ≦ ui 　　　　　　　　　l‘j ≦ Σi=1,…,n xij ≦ u'j 　　　　　　　　　0 ≦ xij ≦ 最長労働時間 • この問題も「単体法（シンプレックス法）で得られる最適解は、（条件の係数が整数なら）必ず整数解になっている」

9 割当て問題：拡張 (2) • 拡張した割当問題は、輸送問題の特殊ケース － 人  工場 － 仕事  小売店 という対応を考えると、
－ 人　　 　工場 － 仕事　　小売店 という対応を考えると、 • 人 i が仕事 j を k 時間受け持つ 　　 工場 i から小売店 j へ製品を k 個輸送する となり、そのまま輸送問題になる 　 シンプレックス法で解いた場合、解の整数性が保障される

10 割当て問題：さらなる拡張 • 各個人に、それぞれの仕事の得意度のようなものがある場合を考えよう。つまり
　　－ 人 i が仕事 j をするときの効率を fij とする 　　　　（つまり、単位時間働くと仕事が fij 進むということ） 　　－ 仕事 j は、合計で lj 以上 uj 以下の働きが必要 • 仕事に関する制約条件が 　　　　　　　　　l’j ≦ Σi=1,…,n fij xij ≦ u’j となる。相変わらず線形計画だが、整数最適解が得られるとは限らない • 最小費用流とは異なる問題となる （一般化フロー問題、と呼ばれる問題と、等価）

11 最適マッチング • グラフ G = (V,E) と、枝の重み w：E →R が与えられたとき、互いに隣接しない枝集合で、枝重み和が最大（最小）なものを求めよ という問題が最適マッチング問題 • 最適マッチングは、O(|V||E|) 時間で求められる • 最大マッチング（枝数が最も多いマッチング）は、 O(|V|1/2|E|) 時間で求められる

12 最適マッチング (2) グラフが２部グラフのとき、マッチング問題は割当問題になる • 人集合を頂点集合１に、仕事集合を頂点集合２に対応させる
• 人 i が受け持つ仕事数を 0,1 に 　 仕事 j を受け持つ人数を 0,1 に制限する • グラフで枝がある組のコストを枝重み 　 枝がないところに +∞ のコストを与える 人 仕事

13 最適マッチングの求め方 交互パス・サイクル： マッチングの枝とそうでない枝が交互になっているもの
　マッチングの枝とそうでない枝が交互になっているもの • 交互パス・サイクルを入替ると、異なるマッチングが得られる • ２つのマッチングの対称差は、交互パス･サイクルの集合になる 定理： 枝集合が最大（重み）マッチング  （本数・重みの）増加パス・サイクルがない 証明

14 最適マッチングの求め方 (2) １． 空集合のマッチングからスタート ２．重みの増加する交互パス・サイクルを見つけては入替える
（グラフ探索で O(|E|+|V|) 時間で見つけられる） • 毎回、枝の本数が増える交互パスの中で、最も重みが増加するものを見つけるようにすると、極大になったところで最適になる （最大 |V| 回、O(|V||E|) 時間で見つけられる） • 最大マッチングの場合は、毎回、見つけられる だけ増加交互パスを見つけるようにすると、 最大 √|V| 回、O(√|V| |E|) 時間になる

15 交互パス・サイクルを見つける • マッチングの枝に頂点集合１から頂点集合２への向きを、そうで各枝には反対の向きをつける 頂点集合１

16 交互パス・サイクルを見つける (2) • マッチングの枝に頂点集合１から頂点集合２への向きを、そうでない枝には反対の向きをつける
 有向グラフができる 頂点集合１ 頂点集合２ • 交互○○と、有向グラフの有向○○の間に対応ができる － 交互サイクル  有向サイクル － 交互パス  有向パス － 増加パス  （端点がマッチング枝に接続しない）有向パス

17 交互パス・サイクルを見つける (3) • 交互サイクルを見つける  有向サイクルを見つければよい
• 交互サイクルを見つける  有向サイクルを見つければよい • 交互パスを見つける  有向パスを見つける ただし、交互パスは入れ替えてマッチングにならないものもある （パスの端点が、パスに含まれないマッチングの枝に接続してると） 有効な交互パスを 見つけるために、 頂点 s,t と／枝を追加 t s

18 交互パス・サイクルを見つける (4) • s から t への有向パスで、 －茶色の枝に始まり、茶色の枝で終わるもの  増加交互パス
－茶色の枝に始まり、茶色の枝で終わるもの  増加交互パス －橙の枝に始まり、橙の枝で終わるもの  減少交互パス －始まりの枝と終りの枝の色が異なるもの  増減無し交互パス t どのタイプの交互パスも、グラフ探索で線形時間で 見つけられる s

19 ３種類のものを割当る • 「人と仕事」だけでなく、「人と仕事と道具」といった、3種類以上のものを割り当てる問題を考える
人 i が仕事 j を道具 k を使って行うとき 1 となる変数 xijk 使って定式化する 目的関数：　　 Σ aijk xijk 制約条件： 　　li ≦ Σj,k xijk ≦ ui 　　l‘j ≦ Σi,k xijk ≦ u'j 　　l''k ≦ Σi,j xijk ≦ u''k 　　xijk ∈ { 0, 1 }

20 残念ながら • xijk が0,1 でなくて良い状況なら（例えば人 i が仕事 j のために道具 k を使って xijk 時間働く、というような場合）線形計画になる 　　目的関数：　　 Σ aijk xijk 　　制約条件： 　　　　li ≦ Σj,k xijk ≦ ui 　　　　l‘j ≦ Σi,k xijk ≦ u'j 　　　　l''k ≦ Σi,j xijk ≦ u''k 　　 　　0 ≦ xijk ≦ 1 残念ながら、必ず整数最適解がある、というわけにはいかない しかし、いろいろな使い道がある

21 予備校の時間割作成 • 予備校の授業時間割を作りたい 月曜1時限 田村 山本 ．．． 月曜2時限 鈴木 田中 ．．．
月曜1時限　　　　　　　　田村　　　　　　　　山本　．．． 月曜2時限　　　　　　　　鈴木　　　　　　　　田中　．．． 火曜1時限　　　　　　　　加藤　　　　　　　　山田　．．． 中1国語 中2英語 中1英語 中3英語 中2数学 中3国語

22 ３種類の割当て • 教師と科目と時間の割当てが時間割である 教師 科目 時間 中1国語 月曜1時限 中1英語 月曜2時限 火曜1時限
教師　　　　　　　　　　科目　　　　　　　　　　　時間 中1国語 月曜1時限 中1英語 月曜2時限 火曜1時限 中2数学 ・・・ ・・・

23 予備校時間割の定式化 • 教師 i が授業 j を k 時限目に行うとき 1 となる変数 xijk
（全部並べて、月曜の最初1時限、金曜の最後 n 時限、とする） 制約 • 教師は、行う授業の数に上下限がある • どの授業も、必ず、ちょうど 1 回（あるいは複数回）行われる • 同時に行える授業は h 個 • 教師は、同時に２つ以上の授業を行わない

24 予備校時間割の制約条件 • 教師 i の行う授業数 ＝ 各 j,k について xijk を足す
　　　l ≦ Σjk xijk ≦ u for ∀i • 授業 j が行われる回数　＝ 各 i,k について xijk を足す 　　Σik xijk ＝ c for ∀j • k 時限目の授業数　＝ 各 i,j について xijk を足す 　　Σij xijk ≦ h for ∀k • k 時限目に教師 i の行う授業数　＝ 各 j について xijk を足す 　　　Σj xijk ≦ for ∀i,k

25 学校の時間割 • 教師（科目）とクラスと時間の割当てが時間割である 教師（科目） クラス 時間 1年A組 月曜1時限 1年B組 月曜2時限
教師（科目）　　　　　　　　　クラス　　　　　　　　　　　　時間 1年A組 月曜1時限 1年B組 月曜2時限 火曜1時限 2年A組 ・・・ ・・・

26 学校の時間割定式化 教師 i の授業を、クラス j が k 時限目に行うとき 1 となる変数 xijk
（全部並べて、月曜の最初1時限、金曜の最後 n 時限、とする） 制約 • 教師は同時に2つの授業はできない • 各クラスはそれぞれの授業をちょうど何回かする • 各クラスは同時に2つの授業を受けない 予備校バージョンと同じように制約式が作れる

27 基本的な制約 教師 i の授業を、クラス j が k 時限目に行うとき 1 となる変数 xijk • 教師は同時に2つの授業はできない
　　　 0 ≦ Σj xijk ≦ for ∀i,k • 各クラスは各科目のどれかの先生の授業をちょうど何回か受ける 　　　 Σk,i∈C xijk = ci for ∀j • 各クラスは同時に2つの授業を受けない 　　　 0 ≦ Σj xijk ≦ for ∀j,k

28 その他の制約 などなど • 1時間目、午後にしない授業 • 連続で行う授業の制約 • 同じ科目は、なるべく離して配置
• 同じ年度のクラスは連続して行いたい授業 などなど •以上、数理的な条件として表せるので、数理計画として解ける。

29 まとめ • 基本的な割り当て問題、各人が仕事に割く時間を考えた割り当て問題は、線形計画で整数解が得られる
• 仕事の能率の要素を入れても線形計画で解けるが、整数解が得られるとは限らない • 割り当て問題の特殊ケースであるマッチング問題は簡単に解ける • 授業の時間割作成問題は3つのものを割り当てる問題になる