Document

割当て問題
• 割当問題の記法・定式化
• 拡張
• 特殊ケース（マッチング）
• ３種類のものを割当てる問題
割当て問題とは
端的に言えば、制約条件を満たすように、人を仕事に割り
振る問題
割当て問題（基本のもの）
• それぞれの人は、できる仕事とできない仕事がある
• それぞれの人は、同時に受け持てる仕事の上下限がある
• それぞれの仕事は、受け持つ人の最低人数がある
担当者数
の上下限
担当仕事数
の上下限
受け持てない
割当て問題（基本のもの）
これらを満たす、人対仕事の割当を見つける問題
また、人 i が仕事 j を受け持つときに費用 aij がかかるとす
ると、総コストが最小な割り当て方を求める問題
割当て問題：記法
仕事をする人： 1,2,…,n
仕事：
1,2,…,m
人 i が仕事 j を受け持つときにかかる費用： aij
人 i が仕事 j をできる：
aij < +∞
人 i が仕事 j をできない： aij = +∞
人 i が受け持つ仕事数の上下限： ui, li
仕事 j を受け持つ人数の上下限： u'j, l'j
割当て問題：定式化
変数：
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整数計画問題になる
割当て問題：線形化
01制約を、線形緩和した線形計画を作る
目的関数：
制約条件：
Σ aij xij
li ≦ Σj=1,…,m xij ≦ ui
l‘j ≦ Σi=1,…,n xij ≦ u'j
0 ≦ xij ≦ 1
「単体法（シンプレックス法）で得られる最適解は、かならず
01解になっている」という良い性質がある
割当て問題：拡張
• 各人が、各仕事に何時間かの時間を割く、という問題を考える
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 ≦ 最長労働時間
• この問題も「単体法（シンプレックス法）で得られる最適解は、
（条件の係数が整数なら）必ず整数解になっている」
割当て問題：拡張 (2)
• 拡張した割当問題は、輸送問題の特殊ケース
－人
 工場
－仕事  小売店
という対応を考えると、
• 人 i が仕事 j を k 時間受け持つ
 工場 i から小売店 j へ製品を k 個輸送する
となり、そのまま輸送問題になる
 シンプレックス法で解いた場合、解の整数性が保障される
割当て問題：さらなる拡張
• 各個人に、それぞれの仕事の得意度のようなものがある場合
を考えよう。つまり
－人 i が仕事 j をするときの効率を fij とする
（つまり、単位時間働くと仕事が fij 進むということ）
－仕事 j は、合計で lj 以上 uj 以下の働きが必要
• 仕事に関する制約条件が
l’j ≦ Σi=1,…,n fij xij ≦ u’j
となる。相変わらず線形計画だが、整数最適解が得られるとは
限らない
• 最小費用流とは異なる問題となる
（一般化フロー問題、と呼ばれる問題と、等価）
最適マッチング
• グラフ G = (V,E) と、枝の重み w：E →R が与えられたとき、互
いに隣接しない枝集合で、枝重み和が最大（最小）なものを
求めよ
という問題が最適マッチング問題
• 最適マッチングは、O(|V||E|) 時間で求められる
• 最大マッチング（枝数が最も多いマッチング）は、
O(|V|1/2|E|) 時間で求められる
最適マッチング (2)
グラフが２部グラフのとき、マッチング問題は割当問題になる
• 人集合を頂点集合１に、仕事集合を頂点集合２に対応させる
• 人 i が受け持つ仕事数を 0,1 に
仕事 j を受け持つ人数を 0,1 に制限する
• グラフで枝がある組のコストを枝重み
枝がないところに +∞ のコストを与える
人
仕事
最適マッチングの求め方
交互パス・サイクル：
マッチングの枝とそうでない枝が交互になっているもの
• 交互パス・サイクルを入替ると、異なるマッチングが得られる
• ２つのマッチングの対称差は、交互パス･サイクルの集合になる
定理：枝集合が最大（重み）マッチング
 （本数・重みの）増加パス・サイクルがない
証明
最適マッチングの求め方 (2)
１．空集合のマッチングからスタート
２．重みの増加する交互パス・サイクルを見つけては入替える
（グラフ探索で O(|E|+|V|) 時間で見つけられる）
• 毎回、枝の本数が増える交互パスの中で、最も重みが増加する
ものを見つけるようにすると、極大になったところで最適になる
（最大 |V| 回、O(|V||E|) 時間で見つけられる）
• 最大マッチングの場合は、毎回、見つけられる
だけ増加交互パスを見つけるようにすると、
最大 √|V| 回、O(√|V| |E|) 時間になる
交互パス・サイクルを見つける
• マッチングの枝に頂点集合１から頂点集合２への向きを、そうで
各枝には反対の向きをつける
頂点集合１
頂点集合２
交互パス・サイクルを見つける (2)
• マッチングの枝に頂点集合１から頂点集合２への向きを、そうで
ない枝には反対の向きをつける
 有向グラフができる
頂点集合１
頂点集合２
• 交互○○と、有向グラフの有向○○の間に対応ができる
－交互サイクル  有向サイクル
－交互パス  有向パス
－増加パス  （端点がマッチング枝に接続しない）有向パス
交互パス・サイクルを見つける (3)
• 交互サイクルを見つける  有向サイクルを見つければよい
• 交互パスを見つける  有向パスを見つける
ただし、交互パスは入れ替えてマッチングにならないものもある
（パスの端点が、パスに含まれないマッチングの枝に接続してると）
t
有効な交互パスを
見つけるために、
頂点 s,t と／枝を追加
s
交互パス・サイクルを見つける (4)
• s から t への有向パスで、
－茶色の枝に始まり、茶色の枝で終わるもの  増加交互パス
－橙の枝に始まり、橙の枝で終わるもの  減少交互パス
－始まりの枝と終りの枝の色が異なるもの  増減無し交互パス
t
s
どのタイプの交互
パスも、グラフ探
索で線形時間で
見つけられる
３種類のものを割当る
• 「人と仕事」だけでなく、「人と仕事と道具」といった、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 }
残念ながら
• 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
残念ながら、必ず整数最適解がある、というわけにはいかない
しかし、いろいろな使い道がある
予備校の時間割作成
• 予備校の授業時間割を作りたい
月曜1時限中1国語田村中2英語山本．．．
月曜2時限中1英語鈴木中3英語田中．．．
火曜1時限中2数学加藤中3国語山田．．．
３種類の割当て
• 教師と科目と時間の割当てが時間割である
教師
科目
時間
中1国語
月曜1時限
中1英語
月曜2時限
中2数学
火曜1時限
・・・
・・・
予備校時間割の定式化
• 教師 i が授業 j を k 時限目に行うとき 1 となる変数 xijk
（全部並べて、月曜の最初1時限、金曜の最後 n 時限、とする）
制約
• 教師は、行う授業の数に上下限がある
• どの授業も、必ず、ちょうど 1 回（あるいは複数回）行われる
• 同時に行える授業は h 個
• 教師は、同時に２つ以上の授業を行わない
予備校時間割の制約条件
• 教師 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
≦ 1 for ∀i,k
学校の時間割
• 教師（科目）とクラスと時間の割当てが時間割である
教師（科目）
クラス
時間
1年A組
月曜1時限
1年B組
月曜2時限
2年A組
火曜1時限
・・・
・・・
学校の時間割定式化
教師 i の授業を、クラス j が k 時限目に行うとき 1 となる変数 xijk
（全部並べて、月曜の最初1時限、金曜の最後 n 時限、とする）
制約
• 教師は同時に2つの授業はできない
• 各クラスはそれぞれの授業をちょうど何回かする
• 各クラスは同時に2つの授業を受けない
予備校バージョンと同じように制約式が作れる
基本的な制約
教師 i の授業を、クラス j が k 時限目に行うとき 1 となる変数 xijk
• 教師は同時に2つの授業はできない
0 ≦ Σj xijk ≦ 1 for ∀i,k
• 各クラスは各科目のどれかの先生の授業をちょうど何回か受ける
Σk,i∈C xijk = ci
for ∀j
• 各クラスは同時に2つの授業を受けない
0 ≦ Σj xijk ≦ 1 for ∀j,k
その他の制約
• 1時間目、午後にしない授業
• 連続で行う授業の制約
• 同じ科目は、なるべく離して配置
• 同じ年度のクラスは連続して行いたい授業
などなど
•以上、数理的な条件として表せるので、数理計画として解ける。
まとめ
• 基本的な割り当て問題、各人が仕事に割く時間を考えた割り当
て問題は、線形計画で整数解が得られる
• 仕事の能率の要素を入れても線形計画で解けるが、整数解が
得られるとは限らない
• 割り当て問題の特殊ケースであるマッチング問題は簡単に解
ける
• 授業の時間割作成問題は3つのものを割り当てる問題になる

Download Report