@article{oai:doshisha.repo.nii.ac.jp:00022133,
 author = {米田, 彩香 and Yoneda, Sayaka and 渡辺, 扇之介 and Watanabe, Sennosuke and 渡邊, 芳英 and Watanabe, Yoshihide},
 issue = {1},
 journal = {同志社大学理工学研究報告, The Science and Engineering Review of Doshisha University},
 month = {Apr},
 note = {本論文では,フローネットワークにおける最適化問題の1つである,最小費用流問題に着目する.最小費用流問題とは,容量制約と需要条件を満たすフローの中で,そのコストが最小となるフローを求める問題で,実社会に広く応用されている問題である.この最小費用流問題を解くアルゴリズムとして,最も効率的であるのがネットワークシンプレックス法である.このアルゴリズムは木構造と呼ばれるものを更新し,最小費用流問題の最適解を求めるアルゴリズムであるが,更新が収束しない現象が頻繁に起こる.この現象は巡回と呼ばれ,巡回は強認容木構造をと呼ばれる特別な木構造を保つことで防ぐことができる.本論文では,この強認容木構造を保ちながら更新するための新しい方法について述べる.この新しい方法を第一閉鎖辺選択規則と呼ぶ.この方法はネットワークシンプレックス法における巡回の数学的構造をあきらかにする,重要な役割を果たす., In the present paper, we focus on the minimum cost flow problem which is one of the well-known optimization problems on flow-networks. The minimum cost flow problem is the problem for finding the minimum cost flow which satisfies the given capacity conditions and the demand conditions. It is known to have wide applications to real fields. The network simplex algorithm is known as the most efficient algorithm for solving the minimum cost flow problem. This algorithm gives an optimal solution to the minimal cost flow problem by updating the so called tree structure, but it does not necessarily terminate in a finite number of steps, even for small networks. This infinite iteration is caused by the cycling of tree structure. It is known that the cycling in the network simplex algorithm can be prevented by maintaining a special type of the tree structure, that is called a strongly admissible tree structure. In the present paper, we give a new rule for updating the tree structure, by which the strongly admissible tree structure is maintained. We call this new rule, rule of the first blocking edge. This will play a key role in clarifying the mathematical structure of the cycling in the network simplex algorithm., application/pdf},
 pages = {95--100},
 title = {ネットワークシンプレックス法における巡回を防ぐ方法},
 volume = {54},
 year = {2013},
 yomi = {ヨネダ, サヤカ and ワタナベ, センノスケ and ワタナベ, ヨシヒデ}
}