WEKO3
アイテム
最短路問題を用いたネットワークシンプレックス法のMATLABへの実装
https://doi.org/10.14988/pa.2017.0000012465
https://doi.org/10.14988/pa.2017.000001246526985916-ca27-4626-aeea-0f6bebf97b66
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
023052020002.pdf (4.6 MB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-08-22 | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | 最短路問題を用いたネットワークシンプレックス法のMATLABへの実装 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | サイタンロ モンダイ オ モチイタ ネットワーク シンプレックスホウ ノ MATLAB エノ ジッソウ | |||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | Implementation of the network simplex algorithm to MATLAB by way of the shortest path problem | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | jpn | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | 有向グラフ | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | ネットワーク | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | 最短経路問題 | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | 最少費用流問題 | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | ネットワーク・シンプレックス法 | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | digraph | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | network | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | shortest path problem | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | minimum cost flow | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | network simplex algorithm | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | departmental bulletin paper | |||||||||||||||||
| ID登録 | ||||||||||||||||||
| ID登録 | 10.14988/pa.2017.0000012465 | |||||||||||||||||
| ID登録タイプ | JaLC | |||||||||||||||||
| アクセス権 | ||||||||||||||||||
| アクセス権 | open access | |||||||||||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||||||||
| その他（別言語等）のタイトル | ||||||||||||||||||
| その他のタイトル | 最短経路問題を用いたネットワークシンプレックス法のMATLABへの実装 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| その他（別言語等）のタイトル | ||||||||||||||||||
| その他のタイトル | サイタン ケイロ モンダイ オ モチイタ ネットワーク シンプレックスホウ ノ マトラブ エノ ジッソウ | |||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||
| 著者 |
青山, 直路
× 青山, 直路× 渡邊, 芳英
WEKO
15621
× 伊藤, 利明
WEKO
17744
|
|||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 青山, 直路 / Graduate School of Life and Medical Sciences, Doshisha University | |||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 渡邊, 芳英 / 同志社大学理工学部数理システム学科教授 | |||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 伊藤, 利明 / 同志社大学生命医科学部医工学科教授 | |||||||||||||||||
| 著者所属（英） | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 値 | Dosihsha University | |||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | 本論文の主題は,最少費用粒問題の解法アルゴリズムであるネットワークシンプレックス法をMATLABへ実装することである.最小費用流問題とは,与えられた需要条件と容量条件の下で,コストが最少であるフローをみつける問題である.この問題は実社会の問題に広く応用がある問題であるにも関わらず,知られている解法アルゴリズムは少ない.ネットワークシンプレックス法はもっとも効率的なものであるが,多くの部分アルゴリズムから構成されており,きわめて複雑なアルゴリズムである.従って,実装は容易ではなく,部分アルゴリズムの組み合わせにおいて多様性がある.本論文においては,最短経路問題の解法アルゴリズムであるダイクストラ法やフロイド・ワーシャル法を部分アルゴリズムとして効率的に用いたネットワークシンプレックス法の実装を提案する.本実装は,非常に効率的であるとは言い難いが,グラフ理論における様々なアルゴリズムに対する知識を少ししか必要としない理解しやすい実装となっている. | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | The main theme of the present paper is an implementation of the Network Simplex Algorithm for solving the minimum cost flow problem to MATLAB. The minimum cost flow problem is the problem for finding the minimum cost flow which satisfies the given capacity conditions and the demand and supply conditions. Although it is known to have a wide application to real fields, there have been known a few algorithms for solving the minimum cost flow problem. The Network Simplex Algorithm is known as the most efficient one, but it is a very complicated algorithm consisting of lots of sub-algorithms. So the implementation of the algorithm is not easy and it has varieties of combinations of sub-algorithms. In the present paper, we provide an implementation of the Network Simplex Algorithm using algorithms for the shortest path problems such as the Dijkstra algorithm or the Floyd-Warshall algorithm efficiently as sub-algorithms. We cannot say that the present implementation is quite efficient but it is easy to understand and requires a little knowledge about algorithms on graph theory. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 書誌情報 |
ja : 同志社大学理工学研究報告 en : The Science and Engineering Review of Doshisha University 巻 52, 号 2, p. 99-106, 発行日 2011-07-31 |
|||||||||||||||||
| 出版者 | ||||||||||||||||||
| 出版者 | 同志社大学理工学研究所 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 出版者（英） | ||||||||||||||||||
| 出版者 | Science and Engineering Research Institute of Doshisha University | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||
| 収録物識別子 | 00368172 | |||||||||||||||||
| 書誌レコードID | ||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||
| 収録物識別子 | AN00165868 | |||||||||||||||||
| 権利者情報 | ||||||||||||||||||
| 権利者識別子Scheme | AID | |||||||||||||||||
| 権利者識別子 | DA03974933 | |||||||||||||||||
| 権利者名 | 同志社大学理工学研究所 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 権利者名 | Science and Engineering Research Institute of Doshisha University | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 関連サイト | ||||||||||||||||||
| 関連タイプ | isFormatOf | |||||||||||||||||
| 識別子タイプ | URI | |||||||||||||||||
| 関連識別子 | https://doors.doshisha.ac.jp/opac/opac_link/bibid/SB00960326/?lang=0 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 関連名称 | 掲載刊行物所蔵情報へのリンク ／ Link to Contents | |||||||||||||||||
| フォーマット | ||||||||||||||||||
| 内容記述タイプ | Other | |||||||||||||||||
| 内容記述 | application/pdf | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | VoR | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||||||
| 日本十進分類法 | ||||||||||||||||||
| 主題Scheme | NDC | |||||||||||||||||
| 主題 | 417 | |||||||||||||||||
