2009年度 第5回輪講 ～簡単なDPMによる実験編～ 平賀 友浩.

Presentation on theme: "2009年度 第5回輪講 ～簡単なDPMによる実験編～ 平賀 友浩."— Presentation transcript:

1 2009年度 第5回輪講 ～簡単なDPMによる実験編～ 平賀 友浩

2 目次 １．概要 ２．モデル ３．アルゴリズム ４．計算 ５．まとめ

3 概要 単期間での解体問題を取り扱う 簡単な部品を考えて、適当な制約条件を付けて Heuristicなアルゴリズムを動かしてみる

4 モデル 前回同様、a、b、c、dの４つの部品からなるモデ ルを考える。 Bを取り外すためには、aとcを分離する必要があ る。

5 a/b/c/d 1 a/b/c 3 c d 2 a/b 4 a b c/d 5

6 DPM

7 各種制約および条件設定 新品部品の取得コスト； 需要 a/b/c a/b c/d a b c d 80 50 35 20 40 30 10
需要

8 各プランのOperationにかかる時間
解体するための原料調達費 30 各プランのOperationにかかる時間 プラン　 時間　　 納涼区制約；25時間 解体費用 Operationにかかる時間×５

9 アルゴリズム 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. ( 今回の場合在庫はなし)

10 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へ

11 Step 12. もし∑Fi > 0ならstep 6へ,そうでなければ Step 13へ
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へ

12 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へ。

13 計算 Bfpi 解体時間 単価 取得費用 Fi 順位 p1 90 1 5 30 55 p2 3 45 p3 100 4 50 2 p4 85
40 5p 95 6 35 6p 7 25 7p

14 一回目では上のようなFiとなったので、パーツ a/b/cの需要の２まで、プラン１を選択。このとき 使用した用量は２
次に、a/b/cの需要が０となったので、それを考 慮してBfiを再計算し、Fiを出すと、 Fi p1 -25 p2 45 p3 50 p4 40 5p 35 6p 25 7p

15 したがって、プラン３をdの残りの需要２まで採択 。このとき使用した容量は８
Dの需要がなくなったので、Bfiを再計算し、Fiを出 すと Fi p1 p2 35 p3 40 p4 5p 6p 15 7p 25

16 したがって、プラン4をc/dの需要１まで採択。これ によって使用された用量は3
Fi p1 p2 35 p3 p4 5 5p 6p 15 7p 25

17 したがって、プラン2をcの需要と容量制約を考え て4まで採択。これによって使用された用量は12
これで、容量が限界となったので、残りの需要を 購入により埋め合わせ、TRCを計算すると、555と なった。

18 まとめ 実際に手で計算してみて、このアルゴリズムがど のように動いているのか、実感できた。
バックワードのアルゴリズムは、複数の期間にな った場合に、あるtで要領不足の場合に、それ以 前で要領の空きがある場合に、そこで解体し、そ れを在庫しておくために必要であると考えた。そ れにより、在庫費用との比較によって、どちらが 最適か判断するためのものであると考えた。