The Initial Basis
The Artificial Start
The primal simplex method requires an initial solution that is basic and feasible. A basic solution for the minimum cost flow network problem is identified by a graphical structure called a tree. A tree is a set of arcs that has no cycles. The initial tree consisting of artificial arcs is shown in the figure below.
After pressing the Iteration button on the worksheet, the initial flows are assigned to the artificial arcs as shown in the arc display. Remember that in first arc display all the artificial arcs were directed out of node 5. In this display arcs 9 and 10 have been reversed in direction to enter node 5. Here we see the purpose of the artificial arcs. They carry the fixed external flows at the nodes in the first iteration. We also see that arcs which formerly touched only one node in the network,, arcs 6, 7 and 8, now either originate or terminate at the slack node. The slack node has the ability to supply or absorb any amount of flow. For this pure problem (all gains 1), the slack node must supply +2 units of flow.
In the figure above, the costs for the artificial arcs are 1. When the simplex is applied with artificial arcs, the algorithm is applied in two phases. In phase 1, the artificial arcs have a cost of 1 and all the original arcs have a cost of zero. On the worksheet, these are in the column labeled Cost 1. As the algorithm progresses, if a feasible solution exists for the original problem, the minimum cost solution will have zero flow on the artificial arcs and all nonzero flows on the original arcs. This is the purpose of phase 1, that is to find some solution that is feasible to the original problem. The solution shown on the arc display is feasible when the artificial arcs are included, but not feasible otherwise. The total cost of this solution is 8.
If phase 1 ends with nonzero flows remaining on artificial arcs, there must be no feasible solution for the original problem. In this case the algorithm ends with a message that no feasible solution exists.
We use this display to explain the information shown on the worksheet. Note that most of the columns of the display are colored yellow. These columns contain formulas or are filled by the program. They are not to be changed by the user.
Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors