Transportation:
Minimization case: The following steps apply to a minimization problem of Transportation in which the objective is to reduce total cost of transporting goods from various sources to various destinations.
Preliminary Step:
Check if the given problem is balanced. Suppose given is a 3*3 cost matrix, Supply in Rows, Demand in Columns, Add the Supplys, Add the Demands. Check if the two Totals are same. If so, then the given problem is balanced. Go to step 1: If the Totals do not tally, it means the Total Demand is not equal to the Total Supply. Add a row (if Supply Total is less) or column (if Demand Total is less) with costs zero and write the required quantity of Supply/Demand correspondingly such that the given problem becomes balanced.
Step 1: Initial allocation:
Briefed here is Vogel’s approximation method or Penalty method. (There are two other methods available for this step viz – North-west corner rule, Least Cost/Inspection method. Here, we only discuss VAM for it is the best for this step)
- 1. Draw the original matrix. Write the costs at the top left corner of the cells. Leave the mid space of the cells empty to fill in with Allocations.
- 2. Start with the first row. Identify two consecutive least costs and write the difference as the Penalty on the R.H.S of the matrix. Repeat this for next two rows. Note: If there are 2 same least cost values, then Penalty is Zero.
- 3. Write the Penalty for the columns below.
- 4. Of all the Penaltys, Find the greatest.
- 5. In the corresponding Row/Column, find the Least Cost cell.
- 6. Do allocation. If the Demand is greater than the Supply for that cell, allocate all that is available. Then, strike off the Available Supply as there is no more. In adjustment to it, write the New Demand. It should have reduced obviously. (Apply the same concept if Supply is greater than the Demand)
- 7. Now, write the next level of Penaltys. To do this, strike of the entire Row if all if its Supply is consumed or strike of the entire Column if all its Demand is been fulfilled.
- 8. Consider only the remaining rows and columns to identify the new set of ‘successive least costs’ and write their difference as the Penalty.
- 9. Then, repeat from exercise 3 to 7 until all cells are allocated and there is no more supply or demand left remaining.
Note: put a circle around the allocations. This is like an indicator of the allocations and helps us differentiate other cells are occupied with other values.
Intermediate step:
- 1. Add the allocations in the first row. This should be equal to the total Supply for the first row. Add the allocations in the first column. This should be equal to the total Demand of the first column. Repeat this for all rows and columns. If the equality as said is attained then we did not do arithmetic mistakes.
- 2. Check if the number of allocations is equal to “number of rows + number of columns – 1”. If it is less, then the given case is a situation of Degeneracy.
Step 2: Checking for Optimality:
Briefed here is U-V method or Modified Mean (MODI) method. ( There is another method called stepping stone method but it is not the best application for this step. However, Stepping stone method will be briefed for step 3 as it is the only method available)
- 1. Rewrite the matrix with the costs and allocations anew. We need the space at the below and right to the matrix to write U and V values respectively.
- 2. First, assign Zero as the first V value on the right adjacent to the first row.
- 3. Start from the Zero, identify the cells in the first row where there is an allocation. Write the U value below the matrix and the corresponding column. This value is determined such that U+V gives the cost of that cell.
- 4. Proceed as this from the U values, identifying the cells with allocation in the corresponding columns and writing the V values by the same principle that U+V equals the cost in that cell (which will be actually the point of intersection when lines are drawn from the U and V value).
- 5. While proceeding as this, if you are not able to get a U or V value after considering all the rows and columns, then it means that there is no allocation available corresponding to the column if proceeded from U value to get V value or vice versa. This will be the situation when the problem is case of Degeneracy. To overcome this problem, assign a efsilon (the greek symbol). This is a dummy allocation. Do this to get the U or V value when it cannot be arrived by other means.
- 6. Once all U and V values are arrived, fill in with NE (net evaluation values). NE = C – U+V. Put braces around these values. Now, the cells with circled values will be called Stone cells and the cells with braced values will be called Water cells.
- 7. If all the NE i.e. water cells’ values are lesser or equal to zero, then the solution is optimal and we can go to the final step. If not, we go to the third step.
- Note: If found optimal and there is a ‘0’ value other than the basic variable (stone cell), it is an indication of an alternate optimal solution.
Step 3: Re-allocation (Stepping stone method)
- 1. Draw a loop. Start with the water cell with the least value. To form the loop, step on the Stone cells (only) by going Forward, taking Right or Left turns and end where started.
- Note: There can be only one possible loop formable for a water cell.
- In total, there will be even number of turnings only.
- 2. Assign ‘+’ and ‘-‘ signs alternatively at every cell where the loop turns from the starting cell and starting with the ‘+’ sign.
- 3. Identify the least value in the cells with ‘-‘ sign. Add this identified value to the values in the cells with ‘+’ signs and subtract it from the values in the cells with ‘-‘ signs.
- 4. The least value identified in the last step would now take the new position of water cell where the loop started. Now this along with the other altered values as by the last step will form the new set of allocations i.e we have re-allocated.
- 5. Repeat from step 2.
Note: If found optimal and there is a ‘0’ value other than the basic variable (stone cell), it is an indication of an alternate optimal solution.
Final Step:
- 1. Form a table of 5 number of columns and the number of rows equal to the order of matrix.
- 2. In first column, Write Source, second, Destination, third, No. of allocations, fourth, Unit Cost, fifth, the cost.
- 3. Sum up all the costs and this is the minimum cost arrived after optimum allocation. Thus, minimization objective attained.
