WEKO3
アイテム
最大流問題とその双対問題
https://doi.org/10.14988/pa.2017.0000012832
https://doi.org/10.14988/pa.2017.0000012832bfcb02b9-7c3c-460a-88b5-f53516126c52
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
023053020007.pdf (3.2 MB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-08-28 | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | 最大流問題とその双対問題 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | サイダイリュウ モンダイ ト ソノ ソウツイ モンダイ | |||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | The maximum flow problem and its dual | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | jpn | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 主題 | 最大流問題, 線形計画問題, 双対問題, 最大フロー・最小カットセット定理 maximum flow problem, linear programming problem, dual problem, max-flow min-cutset theorem |
|||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | departmental bulletin paper | |||||||||||||||||
| ID登録 | ||||||||||||||||||
| ID登録 | 10.14988/pa.2017.0000012832 | |||||||||||||||||
| ID登録タイプ | JaLC | |||||||||||||||||
| アクセス権 | ||||||||||||||||||
| アクセス権 | open access | |||||||||||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||||||||
| 著者 |
米田, 彩香
× 米田, 彩香× 渡辺, 扇之介
WEKO
2484
× 渡邊, 芳英
WEKO
15621
|
|||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 米田, 彩香 / Graduate School of Science and Engineering, Doshisha University | |||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 渡辺, 扇之介 / Graduate School of Science and Engineering, Doshisha University | |||||||||||||||||
| 著者所属 | ||||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 値 | 渡邊, 芳英 / 同志社大学理工学部数理システム学科教授 | |||||||||||||||||
| 著者所属（英） | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 値 | Doshisha University | |||||||||||||||||
| 所属機関識別子種別 | ||||||||||||||||||
| 値 | kakenhi | |||||||||||||||||
| 所属機関識別子 | ||||||||||||||||||
| 値 | 34310 | |||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | 本論文では,フローネットワーク最適化問題の1つとして有名な最大流問題に注目する.最大流問題とは,ネットワークにおいて2つの制約,容量制約と流量保存則のもとでフローの値が最大となるフローを見つける問題である.多くの組み合わせ最適化問題は線形計画問題(LP問題)として定式化され,最大流問題についてもLPへの定式化の方法は知られている.一方で,組み合わせ最適化問題において有名な定理,最大フロー・最小カットセット定理はネットワークにおけるフローとカットセットの双対性を表したものだと知られている.我々の研究の目的は,フローとカットセットの双対性をLP問題を通して明らかにすることである.本論文では知られている定式化とは違う新しい最大流問題の定式化を行った.実験結果によると,新しい定式化の双対問題は解として0-1ベクトルが現れ,これは最小カットセットを与えていた.この結果よりこの定式化は我々の意図するものだといえる.しかし,LP問題の双対問題を作ったのにもかかわらず,0-1ベクトルが解として現れた理由についてはまだ分かっておらず,これを今後の課題とする. | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | In the present paper, we focus on the maximum flow problem which is one of the well-known optimization problems on flow-networks. The maximum flow problem is the problem for finding the flow such that the flow value is maximal among the flows subject to the capacity restriction and the flow conservation laws. Many of the combinatorial optimization problems can be formulated as linear programming (LP) problems, and it is known that the maximum flow problem can be formulated as an LP problem. On the other hand, the max-flow min-cutset theorem which is one of the famous results in combinatorial optimization, suggests the duality between flows and cutsets in networks. The purpose of our study is to clarify the duality between flows and cutsets in the maximum flow problem through the LP problem. In the present paper, we give a new formulation of the maximum flow problem as an LP problem which is slightly different from the one in the references. Computational experiments show that the dual of the LP problem computes a binary vector as the optimal solution, which presents the min-cutset. This implies that our formulation in the present paper is adequate for our purpose. However, we cannot make clear the reason why the optimal solution of the dual problem of the maximum flow problem becomes the binary vector, though the dual problem is an LP problem. This remains as a future subject of study. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 書誌情報 |
ja : 同志社大学理工学研究報告 en : The Science and Engineering Review of Doshisha University 巻 53, 号 2, p. 99-103, 発行日 2012-07-31 |
|||||||||||||||||
| 出版者 | ||||||||||||||||||
| 出版者 | 同志社大学理工学研究所 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 出版者（英） | ||||||||||||||||||
| 出版者 | Science and Engineering Research Institute of Doshisha University | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||
| 収録物識別子 | 00368172 | |||||||||||||||||
| 書誌レコードID | ||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||
| 収録物識別子 | AN00165868 | |||||||||||||||||
| 権利者情報 | ||||||||||||||||||
| 権利者識別子Scheme | AID | |||||||||||||||||
| 権利者識別子URI | https://ci.nii.ac.jp/author/DA03974933 | |||||||||||||||||
| 権利者識別子 | 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 | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | VoR | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||||||
| 日本十進分類法 | ||||||||||||||||||
| 主題Scheme | NDC | |||||||||||||||||
| 主題 | 417 | |||||||||||||||||
