the Network Simplex Algorithm

the Network Simplex Algorithm

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 minf
“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 function “simplex” does not compute the cost of the minimum cost flow
If you want to get the minimum cost. The function “value” is available which computes the minimum cost for the minimum flow computed by the function “simplex”.

The present implementation of the Network Simplex Algorithm is based on the description in Chap. 11 of the Text book
Dieter Jungnickel “Graphs, Networks and Algorithms” second ed. Springer, 2005

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

minf=simplex(a,d,g)
value(minf,g)

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