The Primal Simplex Method for the Pure Minimum Cost Flow Problem

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.

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 ­ 1.

a. If node i has bi > 0, construct an artificial arc from node i to the slack node. Set the arc flow and the arc capacity to bi.

b. If node i has bi < 0, construct an artificial arc from the slack node to node i. Set the arc flow and the arc capacity to -bi.

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.

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 algo-rithm.

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 basis, nB, and the sets n0 and n1, corresponding to nonbasic arcs at their lower and upper bounds respectively, that is feasible for the primal problem. Compute the primal and dual basic solutions for the initial basis.

2. Compute the reduced costs, dk, for all nonbasic arcs.3. If for each nonbasic arc one of the conditions below holds then stop with the optimum solution.

Conditions for Optimality:

If xk = 0, then dk > 0.

If xk = uk , then dk < 0.

Otherwise, select some nonbasic arc that violates the optimality condition and call it the entering arc.

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

Return to Exercises Home Page

return to tour start