the Network Simplex Algorithm (Scripts) 1.0

Average Rating
User Rating:
Visitors Rating:
My rating:

• Last update: 6 years ago
• Price: Free |
• Operating system: Linux, Mac OS X, Win All, BSD, Solaris
• Publisher: Naomichi Aoyama
See full specifications

the Network Simplex Algorithm (Scripts) Publisher's description

Consider the digraph with N vertices and M arcsN Vertices of the graph is expressed by the numbers 1,вЂ¦,N.

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.

System Requirements:

MATLAB 7.11 (2010b)
Program Release Status: Major Update
Program Install Support: Install and Uninstall

the Network Simplex Algorithm (Scripts) Tags:

Click on a tag to find related softwares

Most Popular

ASK, OOK, FSK, BPSK, QPSK, 8PSK modulation 1.1
ASK, OOK, FSK, BPSK, QPSK, 8PSK modulation contain several functions for digital modulation simulation