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

Slides:



Advertisements
Similar presentations
Division of Process Control & Process Systems Engineering Department of Chemical Engineering, Kyoto University
Advertisements

問題解決のアプローチ 南山大学 数理情報学部 情報システム数理学科 稲川敬介. OUTLINE 問題解決のアプローチ  最適化手法と OR ( オペレーションズ・リサーチ ) OR の事例  悪魔の城へ  捕えられたネズミ  最適化 実践的な OR まとめ.
サプライ・チェイン最適化 ー収益管理を中心としてー 東京海洋大学 久保 幹雄
ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋
到着時刻と燃料消費量を同時に最適化する船速・航路計画
ロジスティクス工学 第6章 動的ロットサイズ決定モデル 東京商船大学 久保 幹雄
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
「基礎OR」/「OR演習」 第3回 宿題3.2 Red Brand Canners解説
© Yukiko Abe 2014 All rights reserved
実証分析の手順 経済データ解析 2011年度.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
Bassモデルにおける 最尤法を用いたパラメータ推定
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
サプライ・チェイン最適化の最新動向 久保 幹雄 東京商船大学 江東区越中島2ー1ー6 流通情報工学 流通管理工学講座 流通経営工学 助教授
ロジスティクス工学 第2章 経済発注量モデル サプライ・チェインの設計と管理 pp , 3.2.1節 経済的ロットサイズ・モデル
Natural Semantics 実行過程の、最初と最後の状態(state)の関係を考える。
経済・経営情報コース コース紹介.
クラスター変分法と確率的情報処理 --Belief Propagation と画像処理アルゴリズム--
1章前半.
最尤推定によるロジスティック回帰 対数尤度関数の最大化.
サプライ・チェインの設計と管理 第8章 製品設計とサプライ・チェイン設計の統合 pp
輪講用資料 5/24 森貴之.
情報経済システム論:第11回 担当教員 黒田敏史 2018/9/20 情報経済システム論.
計算量理論輪講 岩間研究室 照山順一.
サプライ・チェインの設計と管理 第11章 サプライ・チェイン・マネジメントのための 意思決定支援システム pp
© Yukiko Abe 2014 All rights reserved
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
© Yukiko Abe 2014 All rights reserved
第6章 連立方程式モデル ー 計量経済学 ー.
応用社会システム計画 (第10回) ここで、学習すること 学籍番号: 氏名: ■これまでの講義内容の整理 ■計画問題の設定と手法
小間田 春彦 高 雷 小林 磨生 小針 由香 小林 亮 毛塚 智彦
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
スペクトル法の一部の基礎の初歩への はじめの一歩
AMPLについて 2011年12月2日(金) 経営システム工学科 森戸 晋.
Online Decoding of Markov Models under Latency Constraints
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
第3回 アルゴリズムと計算量 2019/2/24.
Introduction to Soft Computing (第11回目)
25. Randomized Algorithms
First Course in Combinatorial Optimization
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
電機情報工学専門実験 6. 強化学習シミュレーション
ロジスティクス工学 第2章 経済発注量モデル サプライ・チェインの設計と管理 pp , 3.2.1節 経済的ロットサイズ・モデル
ベイズ・アプローチによる グラフィカル・テスト理論
ガウシアン確率伝搬法の 近似精度に対する理論解析
© Yukiko Abe 2015 All rights reserved
「経営システム工学総合実験」 モデリング&シミュレーション 第2回
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
ベイズ最適化 Bayesian Optimization BO
情報経済システム論:第13回 担当教員 黒田敏史 2019/5/7 情報経済システム論.
B03 量子論理回路の 最適化に関する研究 西野哲朗,垂井淳,太田和夫,國廣昇 電気通信大学 情報通信工学科.
データ解析 静岡大学工学部 安藤和敏
サプライ・チェイン最適化について 研究者・実務家が知っておくべきこと
第16章 動的計画法 アルゴリズムイントロダクション.
サプライ・チェイン最適化における モデリングについて
解析学 ー第9〜10回ー 2019/5/12.
ポッツスピン型隠れ変数による画像領域分割
ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
C:開放,L:短絡として回路方程式を解く
11.動的計画法と擬多項式時間アルゴリズム.
電気回路学Ⅱ 通信工学コース 5セメ 山田 博仁.
サプライ・チェイン 在庫最適化システム WebSCMのご紹介
経営システム工学総合実験 23班 研究企画 1G03H136 山本 亮 1G03H137 葉 寛明 1G03H138 横尾 英俊
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
混合ガウスモデル Gaussian Mixture Model GMM
Time Reversal E-Text: pp.80-83(PDF: pp.49-50) FM08002 太神 諭
Presentation transcript:

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

ベルマンの再帰方程式 目的関数を f とする。有限期の場合、最終期Tとすると、1≦t≦Tに対して任意の t 期以降の部分問題を考えることができる。第 t 期の状態をs(t)とし、以降の部分問題の目的関数の最適値を f[s(t) ]と書く。 またc[s‘(t)、s(t)]をs(t)から状態s(t+1)=s’(t)に移るための遷移費用とする。このとき最適政策は次のような再帰的条件によって表される。  f[s(t) ]   = Mins(k+1) (c[s(k+1),s(k)]+f[s(k+1) ])、1≦k≦T、ただしc[s(T+1),s(T)]=0とする。  すなわち遷移費用と後継状態以降の最適政策が分かっていれば、 t期以降の最適政策が計算できる。全体のfはf(s(0))に等しい。 DPによる最短路解法

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

始点まで遡って解いて始めて最短路が完成する 例題 13 9 9 0 始点まで遡って解いて始めて最短路が完成する 6+5 17 19 5 f(6)=0、 f(5)=5+0、    → 5 f(4)=min(9+0、 6+5)、  →9 f(3)=min(10+f(4)、18+f(5))、  → f(2)=min(16+f(4)、 8+f(5)、3+f(3))、 → f(1)=min(4+f(2)、 5+f(3)). → f(6)= f(5)= f(4)= f(3)= f(2)= f(1)= f(6)=0 f(5)=5+0=5 f(4)=min(9+0、 6+5)=9 f(3)=min(10+9、18+5)=19 f(2)=min(16+9、 8+5、3+19)=13 f(1)=min(4+13、 5+19)= 17 0、 5+f(6)、   min(9+f(6)、 6+f(5))、 min(10+f(4)、18+f(5))、 min(16+f(4)、 8+f(5)、3+f(3))、 min(4+f(2)、 5+f(3)). DPによる最短路解法 例題の出典:荒木勉(1999).経営科学.情報処理テキストシリーズ.実教出版.

経済的ロットサイズモデル 経済的ロットサイズ生産スケジュールないし経済的発注量は、生産と在庫についての数量的管理技法としてよく知られる。 例えば発注点法と呼ばれる方法では、毎回予め決まった発注点まで在庫水準が落ちると、自動的に予め決めておいた最適発注量(EOQ)が発注される[*1]。 EOQを求めるにはWilsonの公式が用いられた。繰越在庫のある場合や多段階生産販売の場合[*2]は、動的計画法を用いてネットワーク最短路問題に翻訳できる。(満足解を見つけるアルゴリズムの研究や、近年のSCMへの応用も注目される分野である。) 需要1 +需要2 +需要3 需要1+需要2+需要3 =輸送1 +輸送2 +輸送3 需要1=輸送1 +在庫0 -在庫1 需要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). 『ロジスティック工学』経営科学のニューフロンティア8, 朝倉書店, とくに第6章と第2章. Harris, F. (1915). Operations and costs (Factory Management Series). A.W.Shaw Co., pp.48-52. Wagner, H.M. and T.M. Whitin (1958). Dynamic version of the economic lot size model. Management Science 5: 89-96. 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): 506-527. 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): 268-277. Roundy, R. (1985). 98% effective integer-ratio lot-sizing for one warehouse multi-retailer systems. Management Science 31: 1416-1430 Chen, F., A. Federgruen and Y-.S. Zheng (2001). Coordnation mechanisms for distribution system with one supplier and multiple retailers. Management Science 47(5): 693-708. Milgrom, P. and J. Roberts (1990). The economics of modern manufacturing: Technology, strategy, and Organization. American Economic Review 80(3): 511-528. 輸送1 在庫1 在庫2 需要1 需要2 需要3 DPによる最短路解法