サプライ・チェインの設計と管理第2章ロジスティクス

ロジスティクス工学
第10章施設配置モデル
第11章ロジスティクス・ネットワーク
設計モデル
サプライ・チェインの設計と管理
第２章ロジスティクス・ネットワークの構成
コケコーラの事例を読んでおくこと！
副読本：組合せ最適化[短編集]
第10章施設配置問題
東京商船大学
久保幹雄
平面上の配置問題
Fermat（フェルマー）の古典問題
• 各点上に顧客がいるとして，顧客の歩く総距離が最小になる
点に施設を建てる．->Weber問題->施設配置問題
• 各点上にコンピュータがあるとして，総距離が最小になるよう
に繋ぐ．（ただしハブを使っても良い．）->Steiner木問題
Steiner（スタイナー）木問題
• 平面上に点が与えられたとき，総距離が最小に
なるように繋ごう！ただし中継点を使っても良い．
（中継点なしだと最小木問題になり簡単（どん欲
アルゴリズムで解ける！）
距離の2乗和を最小にする平面上の
施設配置問題
• n 人の顧客が平面上に分布しており，その座標
を (Xi,Yi), i=1,...,n とする．このとき，顧客からの
距離の２乗和を最小にするような施設は平面上
のどこに作れば良いか？
• f(X,Y)=Σi (Xi-X) 2+(Yi-Y)2 最小にする(X,Y)を
求める問題
（Xi,Yi)
（２，１），（９，１），（１２，３）
（５，８），（１１，７）
距離の2乗和を最小にする平面上の
施設配置問題の解法
• f(X,Y)=Σi (Xi-X) 2+(Yi-Y)2を最小にす
る！->微分する！
• ∂f(X,Y)/∂X =
• ∂2f(X,Y)/∂X2 =
So f(X,Y) is
X* =
.
Y* =
Weber（ウエーバー）問題
• n 人の顧客が平面上に分布しており，その座標
を (Xi,Yi), i=1,...,n とする．このとき，顧客からの
距離の和（2乗和でなはい！）を最小にするような
施設は平面上のどこに作れば良いか？
•
f(X,Y)=Σi {(Xi-X) 2+(Yi-Y)2 }1/2を最小にす
る(X,Y)を求める問題
（Xi,Yi)’s are:
（２，１），（９，１），（１２，３）
（５，８），（１１，７）
Weber問題の解法
• f(X,Y)=Σi {(Xi-X) 2+(Yi-Y)2 }1/2 を微分し
てみる．
• ∂f(X,Y)/∂X =
• ∂2f(X,Y)/∂X2=
So f(X,Y) is
X* =
.
Y* =
練習問題
• Find the optimal location of the facility of
Continuous Location and Weber examples.
k-メディアン問題
各点上にいる顧客 A,B,C,D,E （カッコ内の数字は人数を表す）は，
開設された最も近い施設を利用するものとする．このとき，顧客の
総走行距離を最小にするように，k個の施設を選択せよ．
(3)
(1)
距離
4
A
B
2
2
D
(3)
1
C
(2)
4
3
E
(1)
A
B
C
D
E
A
0
4
3
2
6
B
4
0
2
3
4
C
3
2
0
1
3
D
2
3
1
0
4
E
6
4
3
4
0
k-メディアン問題（定義）
•
•
•
•
無向グラフ G=(V,E)
距離関数 d: E→R+（非負の実数）
需要関数（点の重み） w: V →R+
重みつきの
施設の数 k （正数）
合計をとる
が与えられたとき，
総移動距離を
最小にするk個
の施設を選択

min  w j min d (i, j )
S k
jV
iS

S内の最も近い
施設に行く
となるような点集合Sを求める問題．
ただし，d(i,j) は2点i,jの最短距離を表す．
施設を点の上に配置したと仮定しても
最適性が失われないことの証明(1)
k=1の場合で証明
枝p,qの間のxに配置するのが最適と仮定
P: p経由の方が近い点集合
Q: q経由の方が近い点集合
x
p
q
d(x,p) d(x,q)=d(p,q)-d(x,p)
P
Q
Pの方が顧客が多いと仮定(w.l.g.:without loss of generality)
w  w
jP
j
jQ
j
施設を点の上に配置したと仮定しても
最適性が失われないことの証明(2)
d(x,q)=d(p,q)-d(x,p)
 w d ( x, j)   w d ( x, p)  d ( p, j)   w d ( x, q)  d (q, j)
jV
j
j
jP
jQ
  w j d ( x, p)  d ( p, j )    w j d ( p, q)  d ( x, p)  d (q, j ) 
jP
jP
jQ


 d ( x, p)  w j   w j    w j d ( p, j )   w j d ( p, q)  d (q, j ) 
jQ
jQ
 jP
 jP
w  w
j
j
jQ
０以上
d(p,j)≦d(p,q)+d(q,j)
点pからjへ行くには，
Q経由より直接の方が近い！
j
 w d ( x, j)   w d ( p, j)  w d ( p, j)  w d ( p, j)
jV
j
jP
j
jQ
j
jV
j
途中の点xの施設より点pの方が良い！
k-メディアン問題のExcelによる表現（median.xls)
A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
B
C
D
E
F
G
Open
0
4
3
2
6
99999
4
99999
2
99999
2
3
6
4
0
2
3
4
99999
0
99999
3
99999
0
1
0
3
2
0
0
3
99999
2
99999
0
99999
0
2
0
=IF(G2=1,A2,99999)
2
3
1
1
4
6
4
3
4
0
0
1
0
1
0
=MIN(A8:A12)
99999
3
99999
1
99999
1
3
3
99999
=SUM(A15:E15)
4
99999
4
99999
4 Min Dsitance
1 Demand
4
13 Total
=A13*A14
もし G2のセルに１が入っていたら，A2の値，それ以外なら大きな数
貪欲解法
• 貪欲解法（greedy algorithm）
k=1の場合の最適な施設（1-メディアン）を
求め，それを固定した上で，次の施設を順
に（施設数がkになるまで）選択していく．
１つの施設を建てる場合-> 点Dが最適！
２つの施設を配置する場合：貪欲解法のとき点D と点[ ]
最適解
点[ ]と点[ ]
貪欲解法（逆順）
（組合せ最適化短編集第10章の第１話参照）
• 貪欲解法とは逆に，すべての施設が配置されて
いる場合からはじめて，1つの施設を除いたとき
の費用の増加が最も少ないもを削除．これを施
設数がkになるまで繰り返す．(medan2.xls)
顧客1
施設A
施設B
施設C
施設D
顧客2
110
640
670
450
顧客3
585
65
590
115
顧客4
165
200
125
840
595
580
115
100
練習問題 (k-メディアン問題)
(3)
A
距離
4
(1)
B
2
2
(3)
D
1
3
4
(2)
C
(1)
3
2
F (0)
(4)
G
H (1)
E
各点上にいる顧客 A-H
（カッコ内の数字は人数を
表す）は，開設された最も
近い施設を利用するもの
とする．
このとき，顧客の
総走行距離を最小にする
ように，1個の施設を選択
せよ．
また，2個選択する場合は
どうか?
Excelによる試行錯誤と貪
欲解法，貪欲解法（逆順）
で解け．
k-センター問題
各点上にいる顧客 A,B,C,D,E は，開設された最も近い施設から
サービスを受けるものとする．このとき，施設から最も遠い顧客
への距離を最小にするように，k個の施設を選択せよ．
（消防署などの緊急を要する施設の配置で利用）
距離
4
A
B
2
1
2
D
C
1
E
A
B
C
D
E
A
0
4
3
1
2
B
4
0
2
4
5
C
3
2
0
2
3
D
1
4
2
0
1
E
2
5
3
1
0
k-センター問題（定義）
• 無向グラフ G=(V,E)
• 距離関数 d: E→R+（非負の実数）
最も遠い（不
• 施設の数 k （正数）
利な）顧客を
が与えられたとき，
選択
最大距離を
最小にするk個
の施設を選択

S内の最も近い
施設から行く
min max min d (i, j )
S k
jV
iS

となるような点集合Sを求める問題．
ただし，d(i,j) は2点i,jの最短距離を表す．
1-センター問題の最適解
必ずしも点の上とは限らない！
消防署の最適配置！
点の上だとすると．．．
行ごとの最大値を計算．
それが最小になる点[ ]
が最適！
A
B
C
D
E
A
0
4
3
1
2
B
4
0
2
4
5
C
3
2
0
2
3
D
1
4
2
0
1
E
2
5
3
1
0
max
4
5
3
4
5
1-センター問題(枝上への最適配
置）
枝(A,B)上（Aからの距離がxの地点）に配置する場合
d(x,C) d(x,E)
d(x,B)
min max d (i, j )
S k
jV
5
(4)
A
(5)
B
4
x
2
1
2
D
(4)
C (3)
1
4
3
d(x,A)
2
1
A
E (5)
d(x,D)
B
1-センター問題(枝上への配置の下界の導出）
p
Mq=max{d(p,j)}
q
x
Mp=max{d(p,j)}
Mp-x
x+Mq-d(p,q)
Mp  Mq  d ( p, q )
2
最も小さい場合
Mp-x=x+Mq-d(p,q)
p
x=0
q
x=d(p,q)
1-センター問題(最適解）
Mp  Mq  d ( p, q )
2
>3（C上に配置）なら，枝pq上は調べなくて良い！
AB上 ->(4+5-4)/2=2.5＜３
(4)
A
4
x
(5)
B
2
1
2
D
(4)
1
AD上 ->(4+4-1)/2=3.5＞３
BC上 ->
CD上 ->
DE上 ->
C (3)
よってCD上のみ調べれば良い！
練習問題：枝 CD上の最適配置をグラフ
を用いて求めよ．
E (5)
容量制約なし施設配置問題
A
B
C
D
E
7 8 9
7
6
A
0
4
3
2
6
D
2
3
1
0
4
E
6
4
3
4
0
B
4
0
2
3
4
C
3
2
0
1
3
各点の需要量は１
= fj
施設開設の
固定費用
=cij
輸送費用
容量制約なし施設配置問題（定式化）
I: 需要地点(顧客）の集合
J: 施設の配置可能地点の集合
xij =顧客iの需要が施設jによって満たされる割合
yi = 1 施設が点j上に配置されるとき
0 それ以外のとき
十分に大きな数
（＝顧客の数）
（使わない方がよい！）
x
iI
ij
最小化　 f j y j   cij xij
jJ
iI jJ
条件　 xij  1　i  I
（式の本数は多いが
下界が）強い定式化
jJ
 I yij （下界が）弱い定式化
xij  y j i  I , j  J
xij  0　i  I , j  J
y j  {0,1}　j  J
練習問題
• k-センター問題，容量制約なし施設配置問
題を試行錯誤で解くためのExcelモデルを
作成せよ．
• Excelを用いた試行錯誤（What If分析）を
用いて k-メディアン, k-センター問題，容量
制約なし施設配置問題を解け．（k-メディ
アン, k-センター問題の場合には，kを色々
変えてみよ．）
Lagrange乗数
（任意の実数）
Lagrange緩和


最小化　 f j y j   cij xij   1   xij ui
jJ
iI jJ
iI 
jJ

条件　 xij  1　i  I
jJ
xij  y j i  I , j  J
xij  0　i  I , j  J
y j  {0,1}　j  J
条件　xij  y j 1　  xij  0　０
jJ
最初の式の緩和->最適値は等しいか小さい
->下界!
i  I , j  J
xij  0　i  I , j  J
y j {0,1}　j  J
Lagrange緩和（子問題への分解）
最小化　 f j y j   cij  ui xij   ui
jJ
iI jJ
条件　xij  y j i  I , j  J
xij  0　i  I , j  J
y j {0,1}　j  J
->各j（施設）ごとに分解できる！
最小化　f j y j   cij  ui xij
条件　xij  y j iI i  I
xij  0　i  I
y j  {0,1}　iI
各顧客がちょうど１つの
施設に行く条件を緩和
そのかわりに顧客iが
ui の「ご褒美」を施設に
与える！
を各jについて解いて
 ui を加える->下界
iI
Lagrange緩和（Excelモデル）flp-lag1.xls
[cij]
0
4
3
2
6
4
0
2
3
4
3
2
0
1
3
2
3
1
0
4
-3
0
0
-1
0
-4
7
0
0
99999
99999
99999
2
99999
2
0
-3
-1
0
0
-4
8
0
0
99999
99999
99999
3
99999
3
0
-1
-3
-2
-1
-7
9
0
0
99999
99999
99999
1
99999
1
-1
0
-2
-3
0
-6
7
0
0
99999
99999
99999
0
99999
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
4
3
4
0
[cij-ui]-
[ui] Lagrange乗数施設名
3A
3B
3C
3D
4E
16 Σui
Open
0
0
0
1
0
固定費用
7
8
9
7
6
0
0
0
0
-4
-4 Σ (cij-ui)6 固定費用
0
0
16 下界
0 yj
17 上界
99999
99999
99999
4
99999
4
10
開設している施設への最小輸送費用の和
0
0
0
7
0
7 固定費用の
ここを変えると下界が変化
（劣勾配はここに出てくる）
[xii]
0
0
0
0
0
1
1
1
1
1
劣勾配[si]
ここを変えると
上界が変化
Lagrange緩和（Excelモデル）flp-lag1.xls
[cij]
0
4
3
2
6
4
0
2
3
4
3
2
0
1
3
2
3
1
0
4
-3
0
0
-1
0
-4
7
0
0
99999
99999
99999
2
99999
2
0
-3
-1
0
0
-4
8
0
0
99999
99999
99999
3
99999
3
0
-1
-3
-2
-1
-7
9
0
0
99999
99999
99999
1
99999
1
-1
0
-2
-3
0
-6
7
0
0
99999
99999
99999
0
99999
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
4
3
4
0
[cij-ui]-
[ui] Lagrange乗数施設名
3A
3B
3C
3D
4E
16 Σui
Open
0
0
0
1
0
固定費用
7
8
9
7
6
0
0
0
0
-4
-4 Σ (cij-ui)6 固定費用
0
0
16 下界
0 yj
17 上界
99999
99999
99999
4
99999
4
10
開設している施設への最小輸送費用の和
0
0
0
7
0
7
[A8]=MIN(A2-$F2,0)
[A15]=MIN(A13+A14,0)
[A16]=IF(A15<0,1,0)
[A17]=IF($H2=1,A2,99999)
[xii]
0
0
0
0
0
1
1
1
1
1
劣勾配[si]
[A25]=IF(A8<=0,A$16,0)
双対上昇法
（主・双対ヒューリスティクス）
• Lagrange乗数を下界が単調に増加するように設
定する簡便法
– 各顧客（需要地点）が支払う「ご褒美」を０に設
定して，すべての顧客が施設に行けるように
なるまで以下を繰り返す．
• 各顧客に対して，順繰りに，次に近い施設への輸
送費用まで「ご褒美」を増やす．
• （ご褒美－輸送費用）が０以上なら，余剰のご褒美
を施設に与える．
• 施設がもらったご褒美の合計が，施設の固定費用
と一致したら，施設を開設する．このとき，その施
設に行くことにした顧客はご褒美を値上げするのを
やめる．
双対問題の導出（Lagrange緩和を経由）（１）


最小化　 f j y j   cij xij   1   xij ui   ( xij  y j )vij
jJ
iI jJ
iI 
jJ
iI jJ

0
Lagrange乗数 ui
（任意の実数）
条件　 xij  1　i  I
jJ
xij  y j i  I , j  J
xij  0　i  I , j  J
y j  0　j  J
0以下
Lagrange乗数 vij
（非負の実数）
1　  xij  0　jJ
xij  y j  0　整数条件を
（1以下の条件も）外す
（注意：テキストでは１以下を
残している！）
双対問題の導出（Lagrange緩和を経由）（２）


最小化　 ui    f j   vij  y j   (cij  ui  vij ) xij
iI
jJ 
iI
iI jJ

条件　xij  0　i  I , j  J
y j  0　j  J
項別に整理
目的関数にのせた式を緩和
0以下の項を加えて，さらに式を緩和したので下界!
下界が－∞にならないためには．．．これらの項が0以上！
より良い（＝大きい）下界を得るためには．．．ここを最大化．
最大化　 ui
iI
条件　ui  vij  cij i  I , j  J
v
iI
ij
 f j j  J
vij  0　i  I , j  J
双対問題
双対上昇法（主・双対ヒューリスティクス）
最大化　 ui
iI
条件　ui  vij  cij i  I , j  J
v
iI
ij
 f j j  J
vij  0　i  I , j  J
uiを大きくしていき，
cijを超えた分をvij
ui  cij  vij ui  cij なら，需要地点iは
施設jの近所とよぶ！
これが等号で成立したら施設j
を開設し，その施設の近所の
需要地点iのuiを大きくするの
をやめる．
1.
2.
uiを各需要地点ごとに次に近い施設までの移動費用まで増やす．
近所の施設が開設していない需要地点に対して，一様に増やす．
例題（ヒューリスティクスがうまくいかない例）
顧客１
倉庫１
工場１
50,000
3
0
需要量
4
5
顧客２
5
4
需要量
100,000
2
1
工場２
2
倉庫２
≦60,000
4
顧客３
需要量
50,000
最も近い倉庫から補充した場合
倉庫１
工場１
顧客１
足りない分は
工場１から運ぶ
50,000
2×50,000
顧客２
5×140,000
100,000
工場２
1×100,000
2×60,000
倉庫２
≦60,000
工場・倉庫間
700,000
120,000
小計 820,000
4×50,000
倉庫・顧客間
100,000
100,000
200,000
小計 400,000
顧客３
50,000
合計 122億円
最も安い経路（工場-倉庫-顧客）を選択した場合
顧客１
倉庫１
3×50,000
50,000
工場１
0×100,000
Min{0+3,4+3,
5+2,2+2}
工場２
5×40,000
5×50,000
顧客２
100,000
2×60,000
倉庫２
1×100,000
50,000
≦60,000
工場・倉庫間
200,000
120,000
小計 320,000
顧客３
倉庫・顧客間
150,000
250,000
100,000
小計 500,000
合計 82億円
最も安い経路（工場-倉庫-顧客）を選択した場合
ー倉庫２から顧客３への輸送費用が半額のときー
顧客１
倉庫１
3×50,000
50,000
工場１
0×50,000
5×90,000
4万->2万
顧客２
100,000
工場２
2×60,000
≦60,000
工場・倉庫間
450,000
120,000
小計 570,000
1×100,000
顧客３
倉庫２
2×50,000
倉庫・顧客間
150,000
100,000
100,000
小計 350,000
50,000
増えている！
合計 92億円
最も安い経路（工場-倉庫-顧客）を選択した場合
ーさらに倉庫２から顧客１への輸送費用を5000円にしたと
きー
顧客１
倉庫１
2万->0.5万
50,000
工場１
0.5×50,000
顧客２
5×140,000
100,000
工場２
2×60,000
≦60,000
工場・倉庫間
700,000
120,000
小計 820,000
1×100,000
顧客３
倉庫２
2×50,000
倉庫・顧客間
25,000
100,000
100,000
小計 225,000
50,000
さらに増えている！
合計 104.5億円
Excelソルバーによる求解 Table2-5.xls
変化させるセル
輸送費
w1
w2
輸送量
w1
w2
供給|需要量
費用計算用
4
2
3
2
4
1
0
60000
60000
60000
c1
50000
0
50000
50000
c2
90000
10000
100000
100000
0
120000
150000
0
360000
10000
0
5
p1
140000
0
140000
200000
0
0
c3
c2
c1
p2
p1
p2
5
2
c3
0
50000
50000
50000
0 510000
100000 230000
目的関数 740000
入量-出量
0
0
Excelソルバーの設定（１）
目的関数のセルを指定
$H$7=0
倉庫の入量=出量
工場の供給量上限
需要は必ず満たす
Excelソルバーの設定（２）
線形モデル，
非負数を仮定を
チェックする！
非線形モデルで使用
注意：初期値によっては収束しない可能性あり！
感度レポートの解釈
双対変数の最適値のこと
制約条件
セル
$B$8
$C$8
$D$8
$E$8
$F$8
$H$6
$H$7
名前
p1
p2
c1
c2
c3
w1 入量-出量
w2 入量-出量
計算
潜在制約条件許容範囲内許容範囲内
値
価格
右辺
増加
減少
140000
0
200000
1E+30
60000
60000
-1
60000
90000
10000
50000
3
50000
60000
50000
100000
4
100000
60000
90000
50000
5
50000
10000
50000
0
0
0
60000
140000
0
3
0
10000
90000
工場p2の生産量上限60000を１単位増やすと総費用が1減る
制約を90000まで増やすか，10000まで減らすと解が変わる
例題の最適解
倉庫１
顧客１
3×50,000
50,000
工場１
0×140,000
4×40,000
顧客２
5×50,000
100,000
工場２
2×60,000
倉庫２
1×60,000
50,000
≦60,000
工場・倉庫間
120,000
小計 120,000
顧客３
倉庫・顧客間
150,000
160,000
250,000
60,000
小計 620,000
合計 74億円
AMPLとは？
•
•
A Modeling Programming Languageの略
で，数理計画のモデリングをエレガントに
行うための言語
問題を解くための手法（ソルバー）は別売
•
•
線形計画：単体法など
（混合）整数計画：分枝限定法など
非線形計画：内点法など
WEB経由で無料で使える！
Excelのソルバーよりは本格的（プロ向き）
AMPLによるモデル化(1)
輸送費
w1
w2
p1
p2
0
5
工場 p1,p2
c1
4
2
倉庫 w1,w2
c2
3
2
c3
4
1
顧客 c1,c2,c3
変数 xij：工場 piから倉庫wjへの輸送量
変数 Xij: 倉庫wiから顧客cjへの輸送量
var x11 >=0; var x12 >=0; var x21>=0; var x22>=0; var X11>=0;
var X12>=0; var X13 >=0; var X21>=0; var X22>=0; var X23>=0;
minimize cost: 0*x11 +5*x12 +4*x21 +2*x22 +
3*X11 +4*X12 +5*X13 +2*X21 +1*X22 +2*X23;
5
2
AMPLによるモデル化(２)
工場２は最大で60000しか生産できない
subject to PlantCapacity: x21+x22 <=60000;
倉庫１に入る量と出る量が一致する
subject to Warehouse1: x11+x21=X11+X12+X13;
倉庫２に入る量と出る量が一致する
subject to Warehouse2: x12+x22=X21+X22+X23;
AMPLによるモデル化(３)
顧客１の需要 50000 は必ず満たす
subject to Customer1: X11+X21=50000;
顧客２の需要 100000 は必ず満たす
subject to Customer2: X12+X22=100000;
顧客３の需要 50000 は必ず満たす
subject to Customer3: X13+X23=50000;
AMPLのメイル経由での利用
NEOS サーバー：http://www-neos.mcs.anl.gov/neos/
• 以下の情報を電子メイル [email protected] に出
す．
BEGIN.COM
TYPE MINCO
SOLVER MINLP-AMPL
BEGIN.MOD
ここにモデルを書く．
END.MOD
BEGIN.DAT
ここにデータを（必要なら）書く．
END.DAT
AMPLコマンド：以下の2行は解を
得るためのおまじない．
solve;
display _varname, _var;
END.COM
BEGIN.COMMENT
ここにコメントを（必要なら）書く．
END.COMMENT
END-SERVER-INPUT
AMPLモデル Table2-5.mod
BEGIN.MOD
#の右はコメント文（書かなくても大丈夫！）：
#変数の宣言
var x11 >=0; var x12 >=0; var x21>=0; var x22>=0;
var X11>=0; var X12>=0; var X13 >=0; var X21>=0; var X22>=0; var X23>=0;
#目的関数
minimize cost: 0*x11 +5*x12 +4*x21 +2*x22 +3*X11 +4*X12 +5*X13 +2*X21
+1*X22 +2*X23;
#制約条件
subject to PlantCapacity: x21+x22 <=60000;
subject to Warehouse1: x11+x21=X11+X12+X13;
subject to Warehouse2: x12+x22=X21+X22+X23;
subject to Customer1: X11+X21=50000;
subject to Customer2: X12+X22=100000;
subject to Customer3: X13+X23=500000;
END.MOD
結果（メイルのリプライ）
10 variables, all linear
6 constraints, all linear; 18 nonzeros
1 linear objective; 9 nonzeros.
MINLP-B&B (20010722): MINLP-B&B (20010722): Optimal solution found
1 subproblem, objective = 740000
Evals: obj = 14, constr = 15, grad = 15, Hes = 14
: _varname _var :=
1 x11 140000
2 x12
0
3 x21
0
4 x22
60000
5 X11
50000
6 X12
65000
7 X13
25000
8 X21
0
9 X22
35000
10 X23
25000
;
AMPL
結果の解釈（１）
OBJECTIVES: 最適な目的関数の値
cost = 740000
VARIABLES: 最適な変数（輸送量）の値
x11 = 140000 x12 = 0 x21 = 0 x22 = 60000
X11 = 50000 X12 = 40000
X13 = 50000 X21 = 0 X22 = 60000 X23 = 0
より良いモデリング（データとモデルの分離）
４つの異なる問題を解きたい！今のままだと．．．
モデル１
モデル２
モデル３
モデル４
モデルとデータを分離しておくと．．．
モデルファイル
データ１
データ２
データ３
モデルは共通なので
書き直す必要なし！
データ４
AMPLモデル Table2-5-new.mod （１）
集合，パラメータ，変数の宣言
＃集合はsetで宣言
#工場の集合（中身はデータファイルで記述）
set Plant;
set Warehouse;
#倉庫の集合
set Customer;
#顧客の集合
#パラメータは paramで宣言：需要量｛顧客の集合｝ -> 集合は{}
param Demand{Customer};
param Supply{Plant};
#供給量 {工場の集合}
param cost{Plant,Warehouse};
＃工場・倉庫間の輸送費用
param Cost{Warehouse,Customer}; #倉庫・工場間の輸送費用
＃変数はvarで宣言工場・倉庫間の輸送量（０以上の指示）
var x{Plant,Warehouse} >=0;
var X{Warehouse,Customer} >=0; #倉庫・工場間の輸送量
AMPLモデル Table2-5-new.mod （２）
目的関数
最小化

iPlant , jWarehouse
costij xij 
 Cost
ij
iWarehouse , jCustomer
式には適当な名前を付ける！
minimize total_cost:
sum {i in Plant, j in Warehouse} cost[i,j]*x[i,j]+
sum {i in Warehouse, j in Customer} Cost[i,j]*X[i,j];
sum はΣを表し，合計は集合 {} で記述
添え字は[]で記述
X ij
AMPLモデル Table2-5-new.mod （３）
需要を満たすための制約
顧客ｊへ入ってくる輸送量の合計=顧客ｊの需要量
条件
X
iWarehouse
ij
 Demandj j  Customer
制約条件を記述するためのAMPLコマンド
subject to CustomerDemand{j in Customer}:
sum {i in Warehouse} X[i,j] =Demand[j];
各顧客に対する制約であることを示す．
式には適当な名前を付けておく（求解後に双対変数の
情報を得るときに用いる．）
AMPLモデル Table2-5-new.mod （４）
倉庫でのフロー整合条件
倉庫iに入っている量＝倉庫iから出ていく量
条件

jPlant
x ji  　X
jCustomer
ij
i Warehouse
subject to WarehouseFlow{i in Warehouse}:
sum{j in Plant} x[j,i] = sum{j in Customer} X[i,j];
AMPLモデル Table2-5-new.mod （３）
供給量の上限制約
工場iのから出ていく量≦工場iの供給量
(上限なしの場合には Supplyi に大きな数を入れておく．）
条件
X
ij
jWarehouse
 Supplyi i  Plant
subject to PlantSupply{i in Plant}:
sum{j in Warehouse} x[i,j] <=Supply[i];
AMPデータ Table2-5.dat とAMPLコマンド
BEGIN DATA
set Plant := p1 p2;
set Warehouse :=w1 w2;
set Customer :=c1 c2 c3;
param cost:=
p1 w1 0
p1 w2 4
p2 w1 5
p2 w2 2;
param Cost:=
w1 c1 3
w1 c2 4
w1 c3 5
w2 c1 2
w2 c2 1
w2 c3 2;
param Demand :=
c1 50000
c2 100000
c3 50000;
param Supply :=
p1 999999
p2 60000;
END.DAT
BEGIN.COM
solve; #（求解）
#変数の出力（display コマンド）
display x, X;
#制約（需要と供給）の情報の出力
display CustomerDemand,PlantSupply;
END.COM
AMPL
結果の解釈（２）
CONSTRAINTS (Dual Values): 最適な双対変数
CustomerDemand
c1 = 3 顧客１の需要が１単位増えると３ドル増える
c2 = 4 顧客２の需要が１単位増えると４ドル増える
c3 = 5 顧客３の需要が１単位増えると５ドル増える
PlantSupply
P1 0
P2 -1 工場２の生産量上限が１単位増えると輸送費用が１ドル減る
練習問題
• k-メディアン問題，容量制約なし施設配置
問題をAMPLを用いてモデリングせよ．
• （点の上に施設を配置する場合に限定し
た） k-センター問題をAMPLを用いてモデ
ル化せよ．（最大値を最小化するためには，
オデル化の工夫が必要！）
• 上で作成したモデルをNEOSサーバーを用
いて求解せよ．
遺伝的アルゴリズム
• メタヒューリスティックスのひとつ
• 進化論にアナロジーをもつ
遺伝子（＝解：Open施設）
表現
費用
１０１０１０１０
1357
１０
１０００１１１０
1567
２０
１０１１１０００
1345
３０
１０１０００１１
1378
４０
ルーレット選択
10
5
3.333333
2.5
費用
１０
２０
３０
４０
１００／費用に比例した面積の円グラフ
1
2
3
4
交叉（Crossover）
遺伝子（＝解：Open施設）
表現
費用
１０１０１０１０
1357
１０
１０００１１１０
1567
２０
１０１００１１０
1367
1557
交叉
(Crossover）
致死遺伝子！
自然淘汰(Natural Selection）
遺伝子（＝解：Open施設）
表現費用
１０１０１０１０
1357
１０
１０００１１１０
1567
２０
１０１１１０００
1345
３０
１０１０００１１
1378
４０
１０１００１１０
1367 １５
淘汰！

Download Report