最短路問題を用いたネットワークシンプレックス法のMATLABへの実装

概要

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