@article{oai:doshisha.repo.nii.ac.jp:00021797,
 author = {米田, 彩香 and Yoneda, Sayaka and 渡辺, 扇之介 and Watanabe, Sennosuke and 渡邊, 芳英 and Watanabe, Yoshihide},
 issue = {2},
 journal = {同志社大学理工学研究報告, The Science and Engineering Review of Doshisha University},
 month = {Jul},
 note = {本論文では,フローネットワーク最適化問題の1つとして有名な最大流問題に注目する.最大流問題とは,ネットワークにおいて2つの制約,容量制約と流量保存則のもとでフローの値が最大となるフローを見つける問題である.多くの組み合わせ最適化問題は線形計画問題(LP問題)として定式化され,最大流問題についてもLPへの定式化の方法は知られている.一方で,組み合わせ最適化問題において有名な定理,最大フロー・最小カットセット定理はネットワークにおけるフローとカットセットの双対性を表したものだと知られている.我々の研究の目的は,フローとカットセットの双対性をLP問題を通して明らかにすることである.本論文では知られている定式化とは違う新しい最大流問題の定式化を行った.実験結果によると,新しい定式化の双対問題は解として0-1ベクトルが現れ,これは最小カットセットを与えていた.この結果よりこの定式化は我々の意図するものだといえる.しかし,LP問題の双対問題を作ったのにもかかわらず,0-1ベクトルが解として現れた理由についてはまだ分かっておらず,これを今後の課題とする., 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., application/pdf},
 pages = {99--103},
 title = {最大流問題とその双対問題},
 volume = {53},
 year = {2012},
 yomi = {ヨネダ, サヤカ and ワタナベ, センノスケ and ワタナベ, ヨシヒデ}
}