Start in the top left corner (the north west corner) & fill in the maximum number of units that can move along this route by considering the row (supply) and column (demand) totals
Repeat for each cell in the top row until the supply is exhausted
Repeat steps 1 & 2 for all rows until all supply and demand are exhausted
Calculate initial costs by adding the costs from ONLY the occupied cells together
REMEMBER TO CHECK THE TOTAL SUPPLY EQUALS THE TOTAL DEMAND BEFORE STARTING. IF THE TWO AREN'T EQUAL, ADD A DUMMY ROW OR COLUMN!
1 of 5
Shadow Costs
Check that the number of occupied cells is one less than the total number of rows and columns
Let R1=0, find what to add to R1 to get the initial cost. Continue doing this until all unoccupied cells have been checked & shadow costs found.
2 of 5
Improvement Indices
In unoccupied cells only, take the shadow costs of each cell (across and above or below) away from the initial cost
This gives improvement indices.
Iij= Cij- Ri- Kj
where Iij is the improvement index for row i, column j
Cij is the cost for row i, column j
Ri is the improvement index for row i
Kj is the improvement index for column j
3 of 5
Stepping Stone Method
Start at the entering cell (the cell with the largest improvement index) and replace it with θ
Go through the occupied cells & modify them by adding or subtracting θ so the row & column totals remain the same
The exiting cell is the one where θ can have the lowest value whilst all other values remain positive
Repeat the shadow costs and improvement indices
If all improvement indices are positive, the solution is optimal and no further itterations are required.
4 of 5
Formulation as a Linear Program
For each row & column, add the cost for each cell multiplied by a variable (usually x) together, to total the supply (rows) or demand (columns)
Do the same for the tableaux as a whole, adding each cell with a variable to total another variable, Z
Comments
No comments have yet been made