問題解決の数理
放送大学教養学部 主任講師：大西 仁
第3章・第3回 ネットワーク最適化法
- 概要
-
ネットワーク最適化問題は、点と点が線で結ばれたネットワーク上で、特定の目的に関する最適解を求める問題で、カーナビゲーションシステムにおける最短経路の発見など幅広く応用されている。ネットワーク最適化問題とその解法について応用例を交え解説する。
【キーワード】
グラフ，ネットワーク，最短路問題，最大流問題
- 放送授業パタン，台本（字幕代りにどうぞ）
-
- メッセージ
-
この授業で重要視しているのは定式化であり，
ダイクストラ法やフロー増加法のアルゴリズムを暗記する必要はない．
ダイクストラ法のアルゴリズム自体は簡単であるが，なぜあのアルゴリズムで最短路問題が解けるのかは必ずしも直観的ではない．
納得するには，数学的な証明を読んだり（もちろん自分で証明できれば素晴らしい），問題に適用して解く過程を確認（トレース）するというのが有効と思う．
- Excelソルバーによるネットワーク最適化法
- 最短路問題 (0-1整数最適化法)
- 最短路問題 (線形最適化法)
- 最大流問題
- 演習問題 3.5 (最小費用流問題)
- R (lpSolveパッケージ)によるネットワーク最適化法
- 最短路問題 (0-1整数最適化法，線形最適化法)
- 最短路問題 (ダイクストラ法)
- 最大流問題 (線形最適化法)
- 最大流問題 (フロー増加法)
- 演習問題 3.5 (最小費用流問題)
- GLPKによるネットワーク最適化法
- 最短路問題 (0-1整数最適化法 モデル・データ非分離)
- 最短路問題 (線形最適化法 モデル・データ非分離)
- 最短路問題 (0-1整数最適化法 モデル)
- 最短路問題 (データ)
> glpsol -m SPIP.mod.txt -d SPIP.dat.txt -o SPIP.out.txt
- 最大流問題 (モデル)
- 最大流問題 (データ)
- 演習問題 3.5 (最小費用流問題) (モデル)
- 演習問題 3.5 (最小費用流問題) (データ)
- 演習問題 3.5 (最小費用流問題) (モデル別表現)
- 演習問題 3.5 (最小費用流問題) (別表現用データ)