Network Simplex alg. for a simplyfied problem

[Alpar Juttner]

A simpler (but in fact equivalent) form of the Network Flow Problems when we have on upper limit on the arcs. We can also assume that the lower limit is 0 everywhere.

In this case Network Simplex algorithms becomes much easier:

• A basis is just a tree, and it's trivial to obtaine both the primal and the dual solutions from it.
• A starting dual feasible solution is just a feasible potential w.r.t. the cost, so it can be computed by a shortest path algorithm.