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

Phase 1

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 solution.

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.

Phase 2

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 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 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 step 2.

Click below for a demonstration
Primal Simplex Algorithm