～簡単なDPMによる実験編～
平賀 友浩
１．概要
２．モデル
３．アルゴリズム
４．計算
５．まとめ
単期間での解体問題を取り扱う
簡単な部品を考えて、適当な制約条件を付け
てHeuristicなアルゴリズムを動かしてみる
前回同様、a、b、c、dの４つの部品からなる
モデルを考える。
Bを取り外すためには、aとcを分離する必要
がある。
a/b/c/d
1
2
a/b/c
a/b
c/d
5
3
d
c
4
a
b
A
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
1
1
0
0
1
0
0
0
1
0
0
1
1
1
1
1
1
0
0
1
1
新品部品の取得コスト；
a/b/c a/b c/d a b c d
80
50 35 20 40 30 10
需要
a/b/c a/b c/d a
2
6 1 4
b
3
c d
7 4
解体するための原料調達費
30
各プランのOperationにかかる時間
プラン 1 2 3 4 5 6 7
時間
1 3 4 3 6 7 7
納涼区制約；25時間
解体費用
Operationにかかる時間×５
Step
1. DPMを作成。 Aij と、コストのパラメ
ータを設定。 Set t = 0 and k = 0, kは時 刻t
での反復回数(今回の場合はｔは固定)
Step 2. t = t + 1とし、 If t ≤ Tなら Step 3へ
、でなければStep 14へ（今回の場合T=1）
Step 3. 需要 Djt を初期化、在庫 Yjt. For all j,
もし Djt ≥ Yj(t-1), then set Djt = Djt - Yj(t-1) 、
Yjt = 0,でなければ, Yjt = Yj(t-1) - Djt and Djt =
0. (今回の場合在庫はなし)
Step
4. 時刻tにおける初期解をすべての需要
を新規取得によって充足したものとして設定
。TRCの初期値を計算.
Step 5. kをk = k + 1とし、 Fiをもとにプラン
iを策定.
Step 6. 最大のFiからi*をi*k = max {F1, F2,…,
Fi} のように決定。 Ai*j = 1 かつ Djt > 0 で、
プランiで最小 の需要を満たすようにzを決定
Zi*kt = min {D1t, D2t, …, Djt},
Step 7. MTkt を使用容量としMTkt = MT(k-1)t +
DTi∙Z i*kt, と更新する
Step 8. もし MTkt ≤ MCt,つまり使用した容量
がキャパシティの範囲内なら Step 9へ,そうで
なければStep 11へ
Step
9. TRCt、 Djt, Yjt を更新。
TRCt = TRCt - ∑COj∙Zi*kt+(CD∙DTi+CP)∙Zi*kt.
Ai*j = 1に対して、もし Djt > 0なら, Djt = Djt - Ai*j∙
Z i*kt, でなければ, Yjt = Yjt + Ai*j∙Z i*kt.
Step
10. もし、すべての需要が0ならば(∑Djt =
0), 残っている容量を RCt = MCt - MTktとし、
TRCt = TRCt + ∑Yjt∙Hjt,としてStep 2へ、そう
でなければStep 5へ
Step 11. Zi*kt = Zi*kt – 1とデクリメントし、も
し Zi*kt > 0ならStep 7へ,そうでなければ Fi* = 0
とする
Step 12. もし∑Fi > 0ならstep 6へ,そうでなけ
ればStep 13へ
Step
13.(今回の場合は単期間なのでないが)
t = 1 からt – 1まで RCt ≥ min{DTi} かつ ∑Fi > 0を検
索し、あれば Djt* = Djt, MCt* = RCt*, かつ t = t*, た
だし t*はtの最近傍としてStep 5へ。なければ RCt
= MCt – MTkt かつ MINCOSTt = MINCOSTt + ∑Yjt∙Hjt
としてStep 2へ。
Bfpi
解体時間 単価
取得費用 Fi
順位
p1
90
1
5
30
55
1
p2
90
3
5
30
45
3
p3
100
4
5
30
50
2
p4
85
3
5
30
40
4
5p
95
6
5
30
35
5
6p
90
7
5
30
25
6
7p
100
7
5
30
35
5
一回目では上のようなFiとなったので、パー
ツa/b/cの需要の２まで、プラン１を選択。
このとき使用した用量は２
次に、a/b/cの需要が０となったので、それ
を考慮してBfiを再計算し、Fiを出すと、
Fi
p1
p2
p3
p4
5p
6p
7p
-25
45
50
40
35
25
35
したがって、プラン３をdの残りの需要２ま
で採択。このとき使用した容量は８
Dの需要がなくなったので、Bfiを再計算し、
Fiを出すと
Fi
p1
p2
35
p3
40
p4
40
5p
35
6p
15
7p
25
したがって、プラン4をc/dの需要１まで採択
。これによって使用された用量は3
これによりc/dの需要がなくなったので、再
計算すると、
Fi
p1
p2
35
p3
0
p4
5
5p
0
6p
15
7p
25
したがって、プラン2をcの需要と容量制約を
考えて4まで採択。これによって使用された用
量は12
これで、容量が限界となったので、残りの需
要を購入により埋め合わせ、TRCを計算する
と、555となった。
実際に手で計算してみて、このアルゴリズム
がどのように動いているのか、実感できた。
バックワードのアルゴリズムは、複数の期間
になった場合に、あるtで要領不足の場合に、
それ以前で要領の空きがある場合に、そこで
解体し、それを在庫しておくために必要であ
ると考えた。それにより、在庫費用との比較
によって、どちらが最適か判断するためのも
のであると考えた。
© Copyright 2024 ExpyDoc
