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
- 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
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
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.
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 of arcs.
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 basis.
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
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 step 2.
for a demonstration