To Index To Models
Operations Research Models and Methods / Methods / Network Methods / Teach Network Add-in

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.

Arc Display with Artifical Arcs

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.

Node Display with Artifical Arcs

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.

  • Fixed: This range holds the fixed external flows of the original network. The fixed flow of the slack node has been assigned the value of 2 to balance the external flows of the other nodes.
  • Balance: This range holds a formula that computes the net flow at each node. For a solution that obeys the conservation of flow requirement, the range should have all zeros.
  • Adj. Ext.: The abbreviation stands for Adjusted External Flows. When some of the nonbasic arcs have flows equal to the upper bounds, the fixed external flows must be adjusted at the nodes to reflect these nonbasic flows. This range holds the adjusted flows.
  • Basis: This range holds the indices of the basic arcs. In the first iteration the indices are the artificial arcs. Note that some of the indices are negative. We always arrange the basic arcs so that the arcs form a directed tree rooted at the slack node. To do this some arcs must be used in the reverse direction, as arcs 9 and 10 for the example. These are called mirror arcs. Arcs that are not reversed, such as 11 and 12, are forward arcs.
  • Origin: This range holds the origin nodes of the basic arcs.
  • Term.: The abbreviation means Terminal. The range holds the terminal nodes of the basic arcs.
  • Lower: These are the lower bounds for flow on the basic arcs. The number is 0 for forward arcs and the negative of the upper bound for mirror arcs.
  • Upper: These are the upper bounds for flow on the basic arcs. The number is given in the upper bound data on the arc display for forward arcs and 0 for mirror arcs.
  • Cost: This range holds the unit costs for the basic arcs. In phase 1, the artificial arcs all have a cost of 1 and the original costs have a cost of 0. The cost on a mirror arc is the negative of the corresponding cost on the forward arc.
  • Dual: This range holds the dual variables for the nodes. The dual value of the slack node is zero, and the dual values for all the other nodes are determined by the complementary slackness equation.
  • Flow: This range holds the flow variables for the basic variables. These are the flows required to obtain conservation of flow at the nodes. Note that the flow in the mirror arcs is the negative of the flow in the corresponding forward arc.
  • Delta and Ratio: These columns are used to determine the arc that is to leave the basis in the simplex procedure. We discuss them on the next page where we consider the basis change activity.

Next


To Index To Models TOC

Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors