North-West Corner Method
- 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!
- 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.
- 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
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.
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
- DON'T FORGET the non-negativity constraints