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

DOI 機関リポジトリ Web Site オープンアクセス

書誌事項

タイトル別名
  • Implementation of the network simplex algorithm to MATLAB by way of the shortest path problem
  • サイタンロ モンダイ オ モチイタ ネットワーク シンプレックスホウ ノ MATLAB エノ ジッソウ
  • 最短経路問題を用いたネットワークシンプレックス法のMATLABへの実装

この論文をさがす

説明

本論文の主題は,最少費用粒問題の解法アルゴリズムであるネットワークシンプレックス法をMATLABへ実装することである.最小費用流問題とは,与えられた需要条件と容量条件の下で,コストが最少であるフローをみつける問題である.この問題は実社会の問題に広く応用がある問題であるにも関わらず,知られている解法アルゴリズムは少ない.ネットワークシンプレックス法はもっとも効率的なものであるが,多くの部分アルゴリズムから構成されており,きわめて複雑なアルゴリズムである.従って,実装は容易ではなく,部分アルゴリズムの組み合わせにおいて多様性がある.本論文においては,最短経路問題の解法アルゴリズムであるダイクストラ法やフロイド・ワーシャル法を部分アルゴリズムとして効率的に用いたネットワークシンプレックス法の実装を提案する.本実装は,非常に効率的であるとは言い難いが,グラフ理論における様々なアルゴリズムに対する知識を少ししか必要としない理解しやすい実装となっている.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ