動的計画法で最短路問題を解く  最適性原理に基づいて時間ごとの最適政策を求める方法を、動的計画法（Dynamic Programming； DP)という。  ベルマンの最適性原理とは、直観的に言えば全体の問題の最適解の部分解は部分問題の最適解に一致するということであるが、厳密には次の再帰方程式によって定式化される。ＤＰによる最短路解法 1 ベルマンの再帰方程式  目的関数をｆとする。有限期の場合、最終期Ｔとすると、１≦ｔ ≦Tに対して任意のｔ期以降の部分問題を考えることができる。第ｔ期の状態をｓ（ｔ）とし、以降の部分問題の目的関数の最適値をｆ［ｓ（ｔ）］と書く。  またｃ［ｓ‘（ｔ）、ｓ（ｔ）］をｓ（ｔ）から状態ｓ（ｔ＋１）＝ｓ’（ｔ）に移るための遷移費用とする。このとき最適政策は次のような再帰的条件によって表される。ｆ［ｓ（ｔ）］＝ Minｓ（ｋ＋１）（ｃ［ｓ（ｋ＋１），ｓ（ｋ）］＋ｆ［ｓ（ｋ＋１）］）、１ ≦ｋ≦Ｔ、ただしｃ［ｓ（Ｔ＋１），ｓ（Ｔ）］＝０とする。すなわち遷移費用と後継状態以降の最適政策が分かっていれば、ｔ期以降の最適政策が計算できる。全体のｆはｆ（ｓ（０））に等しい。ＤＰによる最短路解法 2 後方帰納  図の最短路問題のように有限期の場合は、後方帰納（Backwad Induction）と呼ばれる推論を使えば最適政策が求まる。  任意のノードｎから６までの最短ツアー距離をｆ（ｎ）とすると、以下の式がすべて成立つので、逐次代入して解いていけばよい。ＤＰによる最短路解法 3 例題１３９９０始点まで遡って解いて始めて最短路が完成する６＋５１７１９５ｆ（６）＝０、ｆ（６）＝０、ｆ（６）＝０ｆ（５）＝５＋０、ｆ（５）＝５＋０＝５ｆ（５）＝５＋ｆ（６）、 → ５ｆ（４）＝ｍｉｎ（９＋０、ｆ（４）＝ｍｉｎ（９＋ｆ（６）、６＋５）、６＋５）＝９６＋ｆ（５））、 →９ｆ（３）＝ｍｉｎ（１０＋ｆ（４）、１８＋ｆ（５））、ｆ（３）＝ｍｉｎ（１０＋９、１８＋５）＝１９ｆ（３）＝ｍｉｎ（１０＋ｆ（４）、１８＋ｆ（５））、 → ｆ（２）＝ｍｉｎ（１６＋ｆ（４）、ｆ（２）＝ｍｉｎ（１６＋９、ｆ（２）＝ｍｉｎ（１６＋ｆ（４）、８＋５、３＋１９）＝１３８＋ｆ（５）、３＋ｆ（３））、８＋ｆ（５）、３＋ｆ（３））、→ ｆ（１）＝ｍｉｎ（４＋ｆ（２）、ｆ（１）＝ｍｉｎ（４＋１３、ｆ（１）＝ｍｉｎ（４＋ｆ（２）、５＋１９）＝５＋ｆ（３））．５＋ｆ（３））．１７→ ＤＰによる最短路解法例題の出典：荒木勉(1999).経営科学.情報処理テキストシリーズ.実教出版. 4 経済的ロットサイズモデル  経済的ロットサイズ生産スケジュールないし経済的発注量は、生産と在庫についての数量的管理技法としてよく知られる。  例えば発注点法と呼ばれる方法では、毎回予め決まった発注点まで在庫水準が落ちると、自動的に予め決めておいた最適発注量（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 輸送1 輸送2 輸送3 在庫1 需要1 在庫2 需要2 需要3 5