OR-A**3

Report
「ORーA」 第14回
2012/01/20
• 宿題の定式化(略解)
–
–
–
–
–
–
ハブ&スポークネットワークの設計(宿題11.2)
本社機能の分散(宿題11.1)
格差最小の議員定数配分(宿題10.2)
3次元3目並べ(宿題10.1)
凹関数の凸多面体上での最小化(宿題13.1)
Wagner-Whitinモデル(宿題13.2)
• 双対単体法
1
ハブ&スポークネットワークの設計
2
ハブ&スポーク 定式化
所与のデータ
• hij = 点iと点j 間の輸送需要
• cij = ノンハブ点i からハブ点j にの間の単位
需要当たりの輸送費用
• α=ハブ間の輸送費用に対するディスカウント
ファクタ
ハブ間の単位需要当たりの輸送費用はα*cij
• p =ハブの数
3
ハブ&スポーク 定式化
変数
• zij=1 ノンハブ点i がハブ点j に接続して
いるとき(i ≠j の場合)
=0 そうでないとき
• zii=1 点i がハブであるとき
=0 そうでないとき
4
ハブ&スポーク 定式化
0-1二次計画問題
最小化 z =ΣiΣjΣ kΣm hij (cikzik +αckmzikzjm+ cjmzjm )
制約条件 Σj zij =1, ∀i
点iはハブかいずれかのハブに接続
Σi zii =p , ∀i ハブはp個
zij-zjj≦0 , ∀i,j
ノンハブには接続不可
zij ∈{0,1}, ∀i,j
接続不可制約の代替案 Σi zij-(n-p+1)zjj≦0 ,∀j
5
ハブ&スポーク 線形の定式化
変数の取り方
• zijkm=1 点i ,点j 間の輸送がハブ点kとハブ
点mを経由するとき
=0 そうでないとき
• xi =1 点i がハブであるとき
=0 そうでないとき
• この定式化では変数の個数がn4のオーダー
• 定数cijkm= cik +α ckm+ cmj を定義
6
ハブ&スポーク 定式化
(線形)整数計画問題
最小化 z =ΣiΣjΣ kΣm hij cijkmzijkm
制約条件 Σk Σm zijkm =1, ∀i,j
点iは点j間は、ハブkとハブmを経由
xi
Σi xi =p ,
∀i ハブはp個
zijkm-xk≦0 , ∀i,j,k,m
zijkm-xm≦0 , ∀i,j,k,m
ノンハブには接続不可
zijkm ∈{0,1}, ∀i,j,k,m
xi ∈{0,1},
∀i
7
本社機能分散 問題のデータ(1)
• 再配置による利益は以下の通り(単
位:1000万円/年〕
Pij=部門 i を都市 j に配置したときの
利益 A
B
C
D
E
X
Y
Z
0
10
10
0
15
20
0
10
15
0
20
15
0
5
15
8
本社機能分散 問題のデータ(2)
• Cikは部門iと部門kとの間の年間通信量
• Djl は都市jと都市lとの間の単位当たりの
通信費
• 部門i を都市j に配置し、部門kを都市l に
配置したときの通信費はCikDjl
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
9
本社機能分散 問題の定式化
• 変数:
δ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
10
本社機能分散問題に対する
整数2次計画問題
最小化 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}, ∀i,j
δij=1(0) 部門iを都市jに配置する(しない)
11
特殊な定式化の応用
宿題10.2 以下のシナリオを定式
化せよ
• ある議会の議員定員はM人である
• 議員はN(<M)個の選挙区から選挙され
る
• 選挙区jの人口(選挙権を持つ人の人口)
pjは既知である
• 人口1人当たりの議員数(逆に、議員1人
当たりの人口、でもよい)の最大値と最小
値の差を最小化する議員定数の配分(各
選挙区の議員定数)を決めたい
12
「格差最小」の議員定数配分
Min z = u ー v
s.t. xj/pj ≦ u,
j=1,...,N
xj/pj ≧ v,
j=1,...,N
∑ xj = M
xj ≧ 1 かつ 整数
xj = 選挙区jの定員
u = この問題を解くとxj/pjの最大値
v = この問題を解くとxj/pjの最小値
13
3次元3目並べ(配布資料p.16)
• 各マスに1から27まで番号をつける
• 各 マ ス j ( j = 1,…,27) に 白 な ら 0 、 黒 な ら 1 と い う
0-1変数xjを定義
• 「線」に番号をつける(「線」は何本あるか?)
• 同色の線の本数を数え,その本数を最小化する
14
3次元3目並べ
• 各マスに1から27まで番号をつける
• 各マスj(j=1,…,27)に白なら0、黒なら1という
0-1変数xjを定義
• 49本の「線」にも番号をつける
• i 番目の線に関わるマスの番号がi1,i2,i3とする
• i 番目の線が同色xi1+xi2+xi3=0 or 3 →δi=1
(対偶)
δi = 0→ i 番 目 の 線 が 同 色 で な い
δi=0→ xi1+xi2+xi3≧1 and xi1+xi2+xi3≦2
• 0-1変数xjの合計Σj=1,…,27 xj =14
15
• 目的関数はΣi=1,49δiの最小化
3次元3目並べ(続き)
• i 番目の線が同色xi1+xi2+xi3=0 or 3 →δi=1
(対偶)
δi = 0→ i 番 目 の 線 が 同 色 で な い
δi=0→ xi1+xi2+xi3≧1 and xi1+xi2+xi3≦2
• たとえば, δi=0 → xi1+xi2+xi3≦2
は,公式にしたがって,
xi1+xi2+xi3ー 2≦0
xi1+xi2+xi3ー 2≦ □δi
xi1+xi2+xi3ー 2≦ δi
∴ xi1+xi2+xi3ー δi≦2
□は左辺の上界=1
• 同様に, δi=0 → xi1+xi2+xi3≧1 を数式化
16
凹関数の凸多面体上での最小化
端点解に最適解あり(宿題13.1)
宿題13.1 凹関数を有界な凸多面体上で最小化するとき、
凸多面体の端点の中に最適解となるものがある
あるn点x1,...,xn の凸結合で表される x*= ∑i=1nλi xi , ∑i=1nλi
=1
を考える。このとき、f(x)が凹関数であるから、
f(x*)=f(∑i=1nλi xi )≧ ∑i=1nλi f(xi)
となる。Mini f(xi)= f(xk) とすると、
f(x*)=f(∑i=1nλi xi )≧ ∑i=1nλi f(xi) ≧ ∑i=1nλi f(xk) = f(xk)
となる。これより、
f(x*) ≧f(xk)
17
宿題13.2 Wagner-Whitinモデル
• ft= tー1期末在庫It-1が0のときに、 t期以降(T期末まで)を最適に計画した
ときのt期以降の最小費用
• ft=mink=t+1,…,T+1{ctk +fk } (DPの漸化式)
ただし、fT+1 = 0 (境界条件)
• f7= 0 (境界条件)
• f6= min{c67 +f7 }=100+0=100, k*=7(最適なkの値)
• f5= min{ c56 +f6 ,c57 +f7 }=min{100+100,170+0}
= min{200,170}=170, k*=7
• f4= min{ c45 +f5 , c46 +f6 ,c47 +f7 }
=min{100+170,160+100,300+0}
= min{270,260,300}=260, k*=6
• f3= min{ c34 +f4 , c35 +f5 , c36 +f6 ,c37 +f7 }
=min{100+260,140+170,260+100,470+0}
= min{360,310,360,470}=310, k*=5
• f2= min{ c23 +f3 , c24 +f4 , c25 +f5 , c26 +f6 ,c27 +f7 }
=min{ 100+310, 200+260,280+170,460+100,740+0}
= min{410,460,450,560,740}=410, k*=3
• f1= min{ c12 +f2 , c13 +f3 , c14 +f4 , c15 +f5 , c16 +f6 ,c17 +f7 }
=min{ 100+410,170+310, 370+260,490+170,730+100,1080+0}
= min{510,480,630,660,830,1080}=480, k*=3
18
宿題13.2 Wagner-Whitinモデル(続き)
• ft= tー1期末在庫It-1が0のときに、 t期以降(T期末まで)を最適に計画した
ときのt期以降の最小費用
• ft=mink=t+1,…,T+1{ctk +fk } (DPの漸化式)
ただし、fT+1 = 0 (境界条件)
• f7= 0 (境界条件)
• f6= min{c67 +f7 }=100+0=100, k*=7(最適なkの値)
• f5= min{ c56 +f6 ,c57 +f7 }=170, k*=7
• f4= min{ c45 +f5 , c46 +f6 ,c47 +f7 }=260, k*=6
• f3= min{ c34 +f4 , c35 +f5 , c36 +f6 ,c37 +f7 }=310, k*=5
• f2= min{ c23 +f3 , c24 +f4 , c25 +f5 , c26 +f6 ,c27 +f7 }=410, k*=3
• f1= min{ c12 +f2 , c13 +f3 , c14 +f4 , c15 +f5 , c16 +f6 ,c17 +f7 }
=min{ 100+410,170+310, 370+260,490+170,730+100,1080+0}
= min{510,480,630,660,830,1080}=480, k*=3
• 以上から,最小費用は480. 最小費用を達成する最適生産計画は,
1期に(f1を達成するk*=3だから),1期と2期分の需要量75を作る
3期に(f3を達成するk*=5だから),3期と4期分の需要量70を作る
5期に(f5を達成するk*=7だから),5期と6期分の需要量65を作る
19
双対単体法
20
例題を双対単体法で解く
min w = 14 y1 + 8 y2 + 18 y3
s.t.
y1 + y2 + 3 y3 ≧ 2
2 y1 + y2 + y3 ≧ 3
y1≧0, y2≧0, y3≧0
(P=) min w = 14 y1 + 8 y2 + 18 y3
s.t.
y1 + y2 + 3 y3 - y4
=2
2 y1 +
y2 + y3
- y5 = 3
y1≧0, y2≧0, y3≧0, y4≧0, y5≧0
(P=)’ min w = 14 y1 + 8 y2 + 18 y3
s.t.
ー y1 ー y2 ー 3 y3 + y4
=ー 2
ー2 y1 ー y2 ー y3
+y5 =ー3
y1≧0, y2≧0, y3≧0, y4≧0, y5≧0
(P)
問題(P=)’を双対単体法で解く
目的関数行は最小化に
関して最適を示している
元問題を双対単体法で解く
w
1
0
0
w
1
0
0
w
1
0
0
y1
-14
-1
-2
y2
-8
-1
-1
y3
-18
-3
-1
↓
y1
y2
y3
0
-1 -11
0 -1/2 -5/2
1 1/2 1/2
y1
0
0
1
y2
0
1
0
y3
-6
5
-2
y4
0
1
0
y5
0
0
1
右辺 基底 No.0
定数 変数
0
w
-2
y4
-3
y5
解は実行可能解でない
1)軸の行の決定: 基
底変数の値が負の行
y4
y5
0
-7
1 -1/2
0 -1/2
右辺 基底 No.1
定数 変数
21
w
-1/2 y4 ←
3/2 y1
2)軸の列の決定: 「比
の計算」(ただし、軸の行の
y4
-2
-2
1
右辺 基底 No.2
定数 変数
22
w
1
y2
1
y1
3)軸演算(今までと同
じ)
終了判定:ステップ1で
負の値をとる基底変数
が見つからないとき
y5
-6
1
-1
要素の値が負の列だけが対
象)
問題(P)の双対問題(D)
min w = 14 y1 + 8 y2 + 18 y3
s.t.
y1 + y2 + 3 y3 ≧ 2
2 y1 + y2 +
y3 ≧ 3
y1≧0, y2≧0, y3≧0
(D)
max z = 2 x1 + 3 x2
s.t.
x1 + 2 x2 ≦ 14
x1 +
x2 ≦ 8
3 x1 +
x2 ≦ 18
x1≧0, x2≧0
(D=) max z = 2 x1 + 3 x2
s.t.
x1 + 2 x2 + x3
= 14
x1 +
x2
+x4
= 8
3 x1 +
x2
+x5 = 18
x1≧0, x2≧0, x3≧0, x4≧0, x5≧0
(P)
元問題を双対単体法で解く
w
1
0
0
w
1
0
0
w
1
0
0
↓
y1
-14
-1
(-2)
y2
-8
-1
-1
y1
0
0
1
↓
y2
-1
(-1/2)
1/2
y1
0
0
1
y2
0
1
0
y3
-18
-3
-1
y3
-11
-5/2
1/2
y3
-6
5
-2
y4
0
1
0
双対問題を主単体法で解く
y5
0
0
1
y4
y5
0
-7
1 -1/2
0 -1/2
y4
-2
-2
1
y5
-6
1
-1
右辺 基底
定数 変数
0
w
-2
y4
-3
y5 ←
z
1
0
0
0
右辺 基底
定数 変数
z
21
w
1
-1/2 y4 ← 0
3/2 y1
0
0
右辺 基底
定数 変数
22
w
1
y2
1
y1
z
1
0
0
0
x1
-2
1
1
3
↓
x1
-1/2
1/2
(1/2)
5/2
x1
0
0
1
0
↓
x2
-3
(2)
1
1
x3
0
1
0
0
x2
x3
0 3/2
1 1/2
0 -1/2
0 -1/2
x2
0
1
0
0
x3
1
1
-1
2
x4
0
0
1
0
x4
0
0
1
0
x4
1
-1
2
-5
x5
0
0
1
0
右辺 基底
定数 変数
0
z
14
x3 ←
8
x4
18
x5
x5
0
0
0
1
右辺 基底
定数 変数
21
z
7
x2
1
x4 ←
11
x5
x5
0
0
0
1
右辺 基底
定数 変数
22
z
6
x2
2
x1
6
x5
(Bを基底とする)基底形式表現
min z = cx
s.t.
Ax=b
x ≧0
(P2) min z= cBxB+cNxN
s.t.
BxB+NxN = b
xB≧0,xN≧0
基底B(基底変数xB)によって定まる基底形式
z
-(cN-cBB-1N )xN = cBB-1b
xB+
B-1NxN = B-1b
(P1)
双対可能基底(dual feasible basis)
(主問題は最小化を想定)
基底B(基底変数xB)によって定まる基底形式(単体表)
z
-(cN-cBB-1N )xN = cBB-1b
xB +
B-1NxN = B-1b
xB = B-1b ≧0である基底 →(主)可能基底
xB = B -1 b ≧0、かつ、 cN - cB B -1 N ≧0である基底
→(主)最適基底
cN - cB B - 1 N ≧0 で あ る 基 底 → 双 対 可 能 基 底
(最小化問題なら「最適」を示す)
(最小化問題に対して)
B -1 ≧0である基底を
c N- c B
N
なぜ双対可能基底と呼ぶか
(P2)の双対問題(D2):
(D2) max w= yb
s.t.
yB ≦cB
yN ≦cN
①
②
y=π=cBB-1は双対問題(D2)の実行可能解!
∵①はcB≦cBで常時成立; ②は双対可能基底だから
元問題を双対単体法で解く
w
1
0
0
w
1
0
0
w
1
0
0
↓
y1
-14
-1
(-2)
y2
-8
-1
-1
y1
0
0
1
↓
y2
-1
(-1/2)
1/2
y1
0
0
1
y2
0
1
0
y3
-18
-3
-1
y3
-11
-5/2
1/2
y3
-6
5
-2
y4
0
1
0
双対問題を主単体法で解く
y5
0
0
1
右辺 基底
定数 変数
0
w
-2
y4
-3
y5 ←
y4
y5
0
-7
1 -1/2
0 -1/2
右辺 基底
定数 変数
21
w
-1/2 y4 ←
3/2 y1
y4
-2
-2
1
右辺 基底
定数 変数
22
w
1
y2
1
y1
y5
-6
1
-1
z
1
0
0
0
x1
-2
1
1
3
z
1
0
0
0
↓
x1
-1/2
1/2
(1/2)
5/2
z
1
0
0
0
x1
0
0
1
0
↓
x2
-3
(2)
1
1
x3
0
1
0
0
x2
x3
0 3/2
1 1/2
0 -1/2
0 -1/2
x2
0
1
0
0
x3
1
1
-1
2
x4
0
0
1
0
x4
0
0
1
0
x4
1
-1
2
-5
x5
0
0
1
0
右辺 基底
定数 変数
0
z
14
x3 ←
8
x4
18
x5
x5
0
0
0
1
右辺 基底
定数 変数
21
z
7
x2
1
x4 ←
11
x5
x5
0
0
0
1
右辺 基底
定数 変数
22
z
6
x2
2
x1
6
x5

similar documents