Methods - Operations Research Models and Methods

Models Section

Methods

Teach Transportation

The Model

Initial Tableau

Primal Simplex

Iterations

	Teach Transportation Add-in
	-The Primal Simplex

The Algorithm
	The linear programming simplex algorithm is adapted for the transportation problem. On the following pages we illustrate the steps of the algorithm using the Teaching Transportation add-in. Step 1. Construct the initial tableau. Step 2. Compute the dual variables and reduced costs for the current basis. Step 3. Find the cell to enter the basis by selecting a cell with a negative reduced cost. If there are no cells that are candidates to enter the basis, the solution is optimum. The algorthmi terminates. Step 4. Find the cell to leave the basis by finding the cycle of basic cells and the entering the cell on which the flow may change. Change the flow on the cycle by an amount that causes one of the cell flows to go zero. That cell will leave the basis. Step 5. Change the basic solution and return to step 2.
	We start with the basic solution defined by the Northwest Corner Rule
Find the Entering Cell
	The primal simplex method first tries to find some cell that has a negative reduced cost. If there are none the solution is optimal. To search for the entering variable click on the red button. The dialog at the upper left is displayed. The entering variable is chosen by specifying a cell by its row and column number. Initially, these two fields are blank. With the Instruction option there is a Hint button. Clicking on the hint button once, causes the cells with negative reduced costs to be colored orange. Clicking on it twice selects the cell with the most negative reduced cost. Clicking it further will cause the selection to be cycled through all the cells with negative reduced cost. Any of these can be chosen by clicking on the OK button in the dialog. The operating options effect what information is shown at each iteration. In the demonstration option, the student is not asked to choose the entering cell. The program selects the most negative and displays a dialog with that information. In the Self option, no hints are provided and it is possible to choose any cell to enter. In the Run option, no dialogs are presented, but the program quickly runs through iterations, pausing for the delay entered in the original problem definition dialog. The option buttons appear in each dialog, so the student can switch between options. Once a cell is chosen to enter the basis, the next step is to find a cell to leave the basis.
Finding the Leaving Cell
	The entering cell always determines a cycle that consists of the entering cell and basic cells in the current solution. We find that cycle by starting at the entering cell and moving from one cell to another in horizontal or vertical moves. For small problems, students can usually identify the cycle by observation. Once the cycle is found, we identify with positive (+) signs and negative (-) signs the cells in which flow is changing and the direction of change for each cell. The entering cell has a positive sign because flow is increasing in that cell. The next cell in the cycle has a negative sign because flow is decreasing. The cells in the cycle are thus labeled with alternating positive and negative signs. The cell that must leave the basis is a cell taken from the set with negative signs. It is the cell from the set with the smallest flow. If there is more than one cell holding the smallest flow any one can be chosen. The add-in presents the dialog below with fields for the row and column of the cell that will leave the basis. The instruction option provides hints concerning the leaving cell. This image shows the dialog after two clicks of the hint button. The cell labeled with a negative that has the smallest flow is selected. The cycle is shown on the graphic with alternating positive and negative signs. Clicking the OK button presents the next step of the algorithm. Clicking the hint button again will show any other cells that are candidates to leave the basis. With the Self option, the student must choose a basic cell to leave. If the wrong cell is chosen, the solution may become infeasible.
Changing the Basis
	The next step in the process is to change the basis. This is accomplished by clicking OK button on the dialog. The tableau displays the iteration number and the current cost, as well as the entering and leaving variable for the previous iteration. The basis is changed by marking the entering cell with a B and marking the leaving cell with an N. The cell flows, dual variables and reduced costs are recomputed and shown on the image. It is should be noted that the reduced costs are determined by formulas in the worksheet cells. These formulas must not be disturbed. Clicking the red button initiates the second iteration. The next page shows the complete sequence of basic solutions for the example.

Return to Top

Operations Research Models and Methods
Internet
by Paul A. Jensen
Copyright 2004 - All rights reserved