動的計画法で最短路問題を解く 最適性原理に基づいて時間ごとの最適政策を求める方法を、動的計画法（Dynamic Programming； DP)という。 ベルマンの最適性原理とは、直観的に言えば全体の問題の最適解の部分解は部分問題の最適解に一致するということであるが、厳密には次の再帰方程式によって定式化される。

Presentation on theme: "動的計画法で最短路問題を解く 最適性原理に基づいて時間ごとの最適政策を求める方法を、動的計画法（Dynamic Programming； DP)という。 ベルマンの最適性原理とは、直観的に言えば全体の問題の最適解の部分解は部分問題の最適解に一致するということであるが、厳密には次の再帰方程式によって定式化される。"— Presentation transcript:

1 動的計画法で最短路問題を解く 最適性原理に基づいて時間ごとの最適政策を求める方法を、動的計画法（Dynamic Programming； DP)という。 ベルマンの最適性原理とは、直観的に言えば全体の問題の最適解の部分解は部分問題の最適解に一致するということであるが、厳密には次の再帰方程式によって定式化される。 作成： 20 Jun 2000 管理工学の補助教材として作成 改訂：20 Nov 2002 前後;1 Dec 在庫ネットワーク追加 ＤＰによる最短路解法

2 ベルマンの再帰方程式 目的関数を ｆ とする。有限期の場合、最終期Ｔとすると、１≦ｔ≦Tに対して任意の ｔ 期以降の部分問題を考えることができる。第 ｔ 期の状態をｓ（ｔ）とし、以降の部分問題の目的関数の最適値を ｆ［ｓ（ｔ） ］と書く。 またｃ［ｓ‘（ｔ）、ｓ（ｔ）］をｓ（ｔ）から状態ｓ（ｔ＋１）＝ｓ’（ｔ）に移るための遷移費用とする。このとき最適政策は次のような再帰的条件によって表される。 　ｆ［ｓ（ｔ） ］ 　　＝　Minｓ（ｋ＋１） （ｃ［ｓ（ｋ＋１），ｓ（ｋ）］＋ｆ［ｓ（ｋ＋１） ］）、１≦ｋ≦Ｔ、ただしｃ［ｓ（Ｔ＋１），ｓ（Ｔ）］＝０とする。 　すなわち遷移費用と後継状態以降の最適政策が分かっていれば、 ｔ期以降の最適政策が計算できる。全体のｆはｆ（ｓ（０））に等しい。 ＤＰによる最短路解法

3 後方帰納 図の最短路問題のように有限期の場合は、後方帰納（Backwad Induction）と呼ばれる推論を使えば最適政策が求まる。
任意のノードｎから６までの最短ツアー距離をｆ（ｎ）とすると、以下の式がすべて成立つので、逐次代入して解いていけばよい。 ＤＰによる最短路解法

4 始点まで遡って解いて始めて最短路が完成する
例題 １３ ９ ９ ０ 始点まで遡って解いて始めて最短路が完成する ６＋５ １７ １９ ５ ｆ（６）＝０、 ｆ（５）＝５＋０、　　　　→　５ ｆ（４）＝ｍｉｎ（９＋０、 ６＋５）、　　→９ ｆ（３）＝ｍｉｎ（１０＋ｆ（４）、１８＋ｆ（５））、　　→ ｆ（２）＝ｍｉｎ（１６＋ｆ（４）、 ８＋ｆ（５）、３＋ｆ（３））、　→ ｆ（１）＝ｍｉｎ（４＋ｆ（２）、 ５＋ｆ（３））．　→ ｆ（６）＝ ｆ（５）＝ ｆ（４）＝ ｆ（３）＝ ｆ（２）＝ ｆ（１）＝ ｆ（６）＝０ ｆ（５）＝５＋０＝５ ｆ（４）＝ｍｉｎ（９＋０、 ６＋５）＝９ ｆ（３）＝ｍｉｎ（１０＋９、１８＋５）＝１９ ｆ（２）＝ｍｉｎ（１６＋９、 ８＋５、３＋１９）＝１３ ｆ（１）＝ｍｉｎ（４＋１３、 ５＋１９）＝　１７ ０、 ５＋ｆ（６）、　　 ｍｉｎ（９＋ｆ（６）、 ６＋ｆ（５））、 ｍｉｎ（１０＋ｆ（４）、１８＋ｆ（５））、 ｍｉｎ（１６＋ｆ（４）、 ８＋ｆ（５）、３＋ｆ（３））、 ｍｉｎ（４＋ｆ（２）、 ５＋ｆ（３））． ＤＰによる最短路解法 例題の出典：荒木勉(1999).経営科学.情報処理テキストシリーズ.実教出版.

5 経済的ロットサイズモデル 経済的ロットサイズ生産スケジュールないし経済的発注量は、生産と在庫についての数量的管理技法としてよく知られる。
例えば発注点法と呼ばれる方法では、毎回予め決まった発注点まで在庫水準が落ちると、自動的に予め決めておいた最適発注量（EOQ)が発注される[*1]。 EOQを求めるにはWilsonの公式が用いられた。繰越在庫のある場合や多段階生産販売の場合[*2]は、動的計画法を用いてネットワーク最短路問題に翻訳できる。（満足解を見つけるアルゴリズムの研究や、近年のSCMへの応用も注目される分野である。） 需要1 +需要2 +需要3 需要1+需要2+需要3 =輸送1 +輸送2 +輸送3 需要1=輸送1 +在庫0 －在庫１ 需要2=輸送2 +在庫1 －在庫2 需要3=輸送3 +在庫2 －在庫3 在庫0 =在庫3=0 輸送3 輸送2 [*1] EOQはロット生産方式にもそのまま応用できるが、この場合は経済的ロットサイズモデルと呼ばれる。なおロジスティックスの分野に応用されるこの Wilsonの経済的発注量（EOQ)公式は、Wagner and Whitin(1958)によると文献的には Harris(1915)に遡れる。 [*2] 動的経済的ロットサイズモデルすなわちW-Wモデルは、 Wagner-Whitin(1958)、Zangwill(1969), Eppenら(1969)によって改良された。Roundy(1985)は発注サイクルを意思決定変数とする新しいモデルが提案したが、実務の経験とも一致するとしてこの分野が再び注目されるきっかけになった(久保, 2001)。Roundyのそれを代表とする近年のロットサイズモデルでは、厳密解からの乖離が小さく抑えられることが厳密に証明できるという意味での満足解を効率的に見出すヒューリスティックス（確定的あるいは確率的にギャップ上界が証明されているならアルゴリズムと呼んでかまわないだろう）を提案しているのが特徴といえる。一方、Topkisによる束論的モデル上での抽象化を経て、Milgromらによって製造企業の経済学的モデル分析へと応用された。いうまでもなく、これらEOQの拡張は、近年言われるSCM（サプライチェーン経営）のモデル分析のための基礎と考えうる（例えばChen ら(2001)）。 久保幹雄(2001). 『ロジスティック工学』経営科学のニューフロンティア８, 朝倉書店, とくに第６章と第２章. Harris, F. (1915). Operations and costs (Factory Management Series). A.W.Shaw Co., pp Wagner, H.M. and T.M. Whitin (1958). Dynamic version of the economic lot size model. Management Science 5: Zangwill, W.I. (1969). A backlogging model and a multi-echelon model of a dynamic economic lot size production system: A network approach. Management Science 15(9): Eppen, G.D., F.J. Gould and B.P. Pashigian (1969). Extensions of the planning horizon theorem in the dynamic lot size model. Management Science 15(5): Roundy, R. (1985). 98% effective integer-ratio lot-sizing for one warehouse multi-retailer systems. Management Science 31: Chen, F., A. Federgruen and Y-.S. Zheng (2001). Coordnation mechanisms for distribution system with one supplier and multiple retailers. Management Science 47(5): Milgrom, P. and J. Roberts (1990). The economics of modern manufacturing: Technology, strategy, and Organization. American Economic Review 80(3): 輸送1 在庫1 在庫2 需要1 需要2 需要3 ＤＰによる最短路解法