Implementation of the network simplex algorithm to MATLAB by way of the shortest path problem

DOI IR Web Site Open Access

Bibliographic Information

Other Title
  • 最短路問題を用いたネットワークシンプレックス法のMATLABへの実装
  • サイタンロ モンダイ オ モチイタ ネットワーク シンプレックスホウ ノ MATLAB エノ ジッソウ
  • 最短経路問題を用いたネットワークシンプレックス法のMATLABへの実装

Search this article

Description

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.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top