文献

J-GLOBAL ID：201102207643101789   整理番号：11A1323996

最短路問題を用いたネットワークシンプレックス法のMATLABへの実装

Implementation of the Network Simplex Algorithm to MATLAB by way of the shortest path problem

著者 (3件)： 青山直路 (Doshisha Univ., Kyoto) ,  渡邊芳英 (Doshisha Univ., Kyoto) ,  伊藤利明 (Doshisha Univ., Kyoto)
資料名： 同志社大学理工学研究報告  (Science and Engineering Review of Doshisha University)
巻： 52  号： 2  ページ： 99-106  発行年： 2011年07月31日 
JST資料番号： F0617A  ISSN： 0036-8172  CODEN： DDRKA  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフとは数学的に,頂点集合と,頂点の間を結ぶ辺の集合から構成されるものであり,グラフ上の各辺に数値が与えられているとき,それをネットワークと呼ぶ。それらの数値は,長さやコストや通信容量などを表す。このようなグラフ上のネットワークにおける最適化問題のなかで最も基本的な問題が最短路問題であり,各辺の長さが与えられている時,任意の2頂点間の最短路を求める問題である。本論文の主題は,最小費用流問題であり,その解法アルゴリズムであるネットワークシンプレックス法をMATLABに実装することである。最小費用流問題とは,与えられた各辺に対する容量条件と,頂点に関する需要供給条件を満足する流れのなかで,コストが最小となるものを求める問題である。最小費用流問題の代表的な解法アルゴリズムがネットワークシンプレックス法である。このネットワークシンプレックス法は様々なグラフ理論のアルゴリズムの集合体のようなもので,実装に際しては各計算ステップをどのようなグラフ理論の問題と捉え,どのような手法で解くかという自由度が非常に高いアルゴリズムである。本論文ではこの実装に際して効率よりも,分かり易さを重視し,様々なところで最短路問題を用いて実装を行った。その結果,比較的簡便な300ステップ程度のネットワークシンプレックス法の実装が可能となった。まだ残された課題は多いが,今回グラフ上のネットワーク理論に関する様々な予備知識を必要とせず,この複雑なアルゴリズムであるネットワークシンプレックス法を実際に動かすことができたことは有意義なことであると考えている。

シソーラス用語： *シンプレックス法 ,  *プログラムパッケージ ,  *ネットワーク ,  最短路問題 ,  *最小費用流問題 ,  アルゴリズム ,  実装 ,  グラフ理論 ,  有向グラフ
準シソーラス用語： *MATLAB ,  *ネットワークシンプレックス法

分類 (2件)： 数値計算  (JE02000J) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (4件)： 最短路問題 ,  シンプレックス法 ,  MATLAB ,  実装