The problem is solved using the primal simplex in two phases.
The first phase starts with artificial arcs for each node. Phase
1 drives the artificial arcs out of the basis. If a feasible
basic solution is found in Phase 1, Phase 2 starts with this
solution and continues to the optimum solution.
For the following define the notation.
- m: the number of nodes in the network
the external flow at node i
the dual value for node i
the reduced cost for arc k
the flow on arc k
The Initial Solution
The initial solution consists of artificial arcs going to and
from the slack node. An arc is included for each node in the
network. These arcs comprise the initial basis.
For each node i = 1 to m.
a. If node i has
> 0, construct an artificial arc from node i to
the slack node. Set the arc flow and the arc capacity to .
b. If node i has
< 0, construct an artificial arc from the slack node to
node i. Set the arc flow and the arc capacity to -.
c. For Phase 1, set the cost on the artificial arcs to 1.
Set all other arc costs to 0.
Two Phase Method
1. Assign the arc cost of +1 to each of the artificial arcs
and a cost of 0 to each of the original arcs.
2. Using the artificial arcs as the initial basis, solve
the network problem with the primal simplex algorithm. If
the total cost at optimality is greater than zero, an artificial
arc has nonzero flow, and there is no feasible solution to
the original problem. Stop and indicate that there is no feasible
If the total cost at optimality is zero, all the artificial
arcs have zero flow and a feasible solution has been found.
Proceed with phase 2. The figure below shows the basis at
the end of phase 1.
3. Assign the original arc costs to the original arcs. Assign
0 cost and 0 capacity to each artificial arc. Starting with
the basic solution found in phase 1, solve the network problem
with the primal simplex algorithm. The optimum solution for
the example is below.
The Primal Simplex Algorithm
The primal simplex algorithm for the minimum cost network flow
programming problem is accomplished by the following steps.
1. Start with a basic solution. It is defined by three sets
The set of arcs in the basis.
The set of nonbasic arcs with flows at the lower bounds.
The set of nonbasic arcs with flows at the upper bounds.
Compute the primal and dual basic solutions for the initial
2. Compute the reduced costs for all nonbasic arcs. For the
general arc k that passes from node i to node
j the reduced cost is:
3. If for each nonbasic arc one of the conditions below holds
then stop with the optimum solution.
Conditions for Optimality:
If some nonbasic arc violates the optimality condition choose
it to enter the basis. If more than one violates the condition,
any one can enter the basis.
4. Find the increase or decrease in the entering arc that
will either drive it to its opposite bound or drive some basic
arc to one of its bounds. If the entering arc is driven to
its bound go to step 3. If a basic arc is driven to one of
its bounds, let this be the leaving arc.
5. Change the basis by removing the leaving arc from the
basis and adding the entering arc. Compute the primal and
dual basic solutions associated with the new basis. Go to
Click below for a demonstration
Primal Simplex Algorithm