primal network simplex

an implementation of the primal simplex algorithm for computing the minimum cost flow of the graph

Consider the digraph with N vertices and M arcs
N Vertices of the graph is expressed by the numbers 1,…,N.
Given the capacities of arcs, the demand functions of vertices and the cost functions of the arcs, then define the flow network of the given flow network.
This function computes the minimum cost flow for the given flow network.

input A , D , G
“A” is an N by N matrix whose entries a(i,j) denote the capacities of the arc ij.
Assume a(i,j) are nonnegative integers.
“D” is a N-dimensional vector whose integer entries d(i) denote the demand function of the vertex i: if d(i)>0 vertex i is called a demand vertex and if d(i)<0, it is called a supply vertex. Sum of the d(i) for all vertices 1,…,N is 0.
“G” is an N by N matrix whose entries g(i,j) denote the costs of the arc ij.
Assume g(i,j) are nonnegative integers.

output cost, minf
“cost” is the cost of the minimum cost flow
“minf” is a N by N matrix whose entries minf(i,j) gives the flow on the arc ij of the minimum cost flow of the given network.
If the function “simplex” returns the output minf=0, it means that there is no admissible flow on the given network.

The present implementation of the Network Simplex Algorithm refers to an earlier version provided by Naomichi Aoyama (2010).

Consider the following example of the flow network.
It is directed graph with three vertices and three arcs.

There are three arcs.
The first one is from vertex(1) to vertex(2) with the capacity 3, and the cost 1.
The second one is from vertex(1) to vertex(3) with the capacity 5, and the cost 4.
The third one is from vertex(2) to vertex(3) with the capacity 4, and the cost 2.

The demand functions of the three vertices 1,2,3 are given by
d(1)=-3
d(2)=-2
d(3)=5

In this case , input data a,d,g of the function “simplex” are given as follows:

A=[0 3 5;0 0 4;0 0 0]
D=[-3 -2 5]
G=[0 1 4;0 0 2;0 0 0]

Then, type

[ cost, minf ] = netSimplex( A, D, G )

then, you will get the minimum cost flow and minimum cost for the given flow network.