ネットワークシンプレックス法における巡回を防ぐ方法

概要

論文の詳細を見る
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.
2013-04-00