スライド 1 - Morito Lab. 森戸研究室

1
「OR-A」第10回
定型的定式化
森戸晋
WWモデルの定式化
最小化 z＝Σt=1,…,T（ at yt＋htIt）
制約 It-1＋xtーdt ＝ It ， ∀t （流量保存）
xt≦M yt
It≧0（品切れ不許可）， xt≧0， ∀t
I0＝0， IT＝0； Mは十分に大きい数
2
シナリオ20：遊園地の遊び順
3
A男君はB子さんを誘って、年増園に遊びにいき、いま入場したと
ころです。年増園には広大な敷地に n 個のアトラクションがあり、
場所が広いだけに移動に時間がかかります。アトラクション iから
アトラクションjへの移動時間Tijはわかっています。また、各アトラ
クションに要する時間は待ち時間を含めてTiであることが（確定的
に）分かっています。A男君は前もって、B子さんの好きなアトラク
ションを調べており、B子さんがアトラクションｉに乗ったときの満足
度ｓ i が分かっています。B子さんは飽きやすい性格のため、同じ
アトラクションに複数回のることを拒みます。いまから年増園が閉
じてしまうまでに残された時間は Tであり、T以内に退場しなけれ
ばなりません。A男君は、B子さんを最大限満足させるために、ど
のようにアトラクションを回ったらよいでしょうか。（2001年度「OR
－A」、厨健太郎君レポート）
「遊園地の遊び順」の定式化
• 変数：ｘij＝「枝」ｉｊを「通る」とき１、さもなくば０
ｙi＝「点」ｉを「訪れる」とき１、さもなくば０
• 目的関数（恋人の満足最大）：
最大化ｚ＝ Σi ｓｉｙi
• 制約条件（選んだ乗り物を1回ずつ訪問）：
制約 ΣiΣｊ Tｉｊｘij ＋ Σｊ Tｉｙｉ ≦ T
Σｊｘｉｊ＝ｙｉ ∀ｉ（または、ｉ＝1,2,…,n）
Σｉｘｉｊ＝ｙj ∀ｊ（または、ｊ＝1,2,…,n）
Σｉ∈ＳΣｊ∈Ｖ＼Ｓｘｉｊ ≧ ｙh，
h∈V＼1，∀Ｓ⊂Ｖ： 1∈Ｓ， h∈V＼Ｓ
（選ばれた点はすべて1（出発点）につながっている）
4
施設配置問題の定式化
• 定数：ｄi ＝倉庫ｉの経費（固定費）
ｃij ＝倉庫ｉからｊへの輸送単価
ai ＝倉庫ｉの能力
• 変数：ｙi ＝倉庫ｉを借りるとき１、さもなくば０
ｘij ＝倉庫ｉからｊへの輸送量（ｘij≧０）
• 目的関数（総費用最小）：
最小化ｚ＝ Σi ｄiｙi ＋ ΣiΣj ｃijｘij
制約
需要を満足しなければならない
倉庫を借りないならば、送り出してはいけない
倉庫の能力を超えてはならない
5
施設配置問題の定式化
最小化
制約
ｚ＝ Σi ｄiｙi ＋ ΣiΣj ｃijｘij
Σi ｘij≧ｂj
ｊ＝1,2,…,n
Σj ｘij≦ａｉｙi
ｉ＝1,2,…,m
ｘij≧０，ｙi ＝０ or １
6
シナリオ１９（本社機能の分散）
２次割当問題
7
• ある企業では、一部本社機能の、現在地Xからの移
転を検討中（安い土地代、賃借料、政府の補助、
採用の容易さ等のメリット；部門間の通信費が高くな
るというデメリット）
• 年間総通信費を最小にするには、各部門をどこに配
置したら良いか?
• 当該企業は5部門（A、B、C、D、E）からなる
• 再配置の候補は、候補地Yと候補地Z；現在地Xにと
どまることも可
• 1都市当たり最大3部門のみしか配置できない
• 特定の部門の複数都市への分散配置は不許可
本社機能分散問題のデータ(1)
• 再配置による利益は以下の通り(単位:1000
万円／年〕
Pij＝部門 i を都市 j に配置したときの利益
X
Y
Z
A
0
10
10
B
0
15
20
C
0
10
15
D
0
20
15
E
0
5
15
8
本社機能分散問題のデータ(2)
9
• Cikは部門iと部門kとの間の年間通信量
• Djl は都市jと都市lとの間の単位当たりの通
信費
• 部門i を都市j に配置し、部門kを都市l に配
置したときの通信費はCikDｊl
A
B
C
D
通信量　C ik （単位：1000万円）
A
B
C
D
0.0
1.0
1.5
1.4
1.2
0.0
E
0.0
0.0
2.0
0.7
Y
Z
X
単位通信費　D jl (単位：万円）
Y
Z
X
5
14
13
5
9
10
本社機能分散問題の定式化
10
• 変数：
δij＝1 部門i を都市j に配置するとき
（ただし、i ＝A,B,C,D,E； j ＝X,Y,Z）
δij＝0 部門i を都市j に配置しないとき
• 制約条件：
Σjδij＝1，
Σiδij≦3，
i＝A,B,C,D,E（各部門は1都市に配置）
j ＝X,Y,Z（特定の都市には高々3部門）
• 目的関数（＝総費用＝総通信費－利益）：
Σij kl; i < k Cik DjlδijδklーΣij Pij δij
本社機能分散問題に対する
整数2次計画問題
11
最小化 z ＝Σij kl; i < k Cik Djlδijδkl－Σij Bij δij
制約条件 Σjδij＝1，
i＝A,B,C,D,E
（各部門は1都市に配置）
Σiδij≦3，
j ＝X,Y,Z
（特定の都市には高々3部門）
δij∈{0,1}, ∀ｉ，ｊ
δij＝1(0) 部門iを都市jに配置する（しない）
最短路問題：主問題
• 辺上の数字は辺の長さ
1
10
0
1
3
5
12
4
6
2
2
3
2
min 10 x01  5 x02  2 x12  x14  3 x21  2 x23  6 x34
s.t. - x01 - x02
 -1
- x12 - x14  x21
0
x01
- x21 - x23
0
x02  x12
x23 - x34  0
 x34  1
x14
xij  0, (i, j )  A
最短路問題（Shortest Path
Problem)
• ネットワーク上の点s（始点；ソース）から点t
（終点；シンク）までの最短路
min  c x
( i , j ) A
ij
subject t o
ij
x
ki
x
ki
kV  ( i )
kV ( i )
x
kV  ( i )
ki

x
kV  ( i )


ik
x
kV ( i )
x
kV  ( i )
ik
ik
 1, i  s
 0, i  V \ {s, t}
 1, i  t
最適解はxij∈{0,1}
A

)
j
,
i
(

,
0 xij
13
最短路問題の双対問題
 
 
max t 
subject t o
s
j
i
 cij , (i, j )  A
•任意のaについてπiをπi+a と置き換えても実行
可能⇒ 始点でπs=0と定める
•πiとは？⇒始点sから点iへの最短距離の下界
•πiをsからiへの最短距離と定めると双対問題
の実行可能解なので、双対問題を解いてもsか
らtへの最短距離が求められることがわかる
14
最短路問題：双対問題
 
s.t .   
   5
   2
   1
   3
   2
   6
max
4
1
2
0
2
1
4
1
1
2
3
2
4
3
• πj-πi≦cij
0
0
 10
• 点j までの最短路の距離
≦
（点iまでの最短路の距離
＋(i, j) 間の距離）
15
最大流問題（Max Flow Problem)16
• 始点（ソース）sから終点（シンク）tへのフロー
vの最大化
• 辺(i,j)の容量hij
max
v
subject t o
x
kV ( i )
x
kV ( i )
x
kV ( i )
ki
ki
ki

x
kV ( i )


x
kV ( i )
x
kV ( i )
0 x  h
ij
ij
ik
ik
ik
 v, i  s
 0, i  V \ {s, t}
 v, i  t
, (i, j )  A
最大流問題の双対問題
min
17
h w
( i , j ) A
ij
ij
subject t ou i  u j  wij  0, (i, j )  A
u  u  1,
w  0, u は符号制約無し
s
ij
t
j
•始点sを含む点集合X, 終点tを含む点集合X－に対して
•ui=1, i∈X
•uj=0, j∈X－
•wij=1, i∈X, j∈X－それ以外wij= 0
•上のように定めると双対問題の実行可能解が得られる
•全てのケースで実行可能性が確認できる
•{i ∈X, j ∈X}, {i ∈X, j ∈X－}, {i ∈X －, j ∈X},{i ∈X－, j ∈X－}
•双対問題における上の実行可能解に対する目的関数値
⇒カット容量と一致する
（双対問題の最適値の上界）
 hij wij   hij
( i , j )A
iX , jX

Download Report