Finding an initial feasible solution
There are number of methods available for generating an initial feasible solution for a transportation problem.
An initial basis feasible solution can be constructed by selecting the (m+n-1) basic variable (allocations) xij one at a time. After each selection we assign a value to that variable so as a to satisfy a linear constraint thus after (m+n-1) selections an entire basic feasible solution has been constructed in such a way that all the rim requirements are satisfied. We shall discuss here only the following three methods:
1. The north-west corner rule
2. Lowest cost entry method
3. Vogel's approximation method
1. North West Corner Method (NWCM). The simplest of the procedures used to generate an initial feasible solution is NWCM. It is called because we begin with the north west or upper left corner cell of our transportation table. Various steps of this method can be summarized as under.
Step 1. Select the north west (upper left-hand) other cell of the transportation table and allocate as many units as possible equal to the minimum between available supply and demand requirement i.e., min (s1, d1) .
Step 2. Adjust the supply and demand numbers in the respective rows and columns allocation.
Step 3. (a) if the supply for the first row is exhausted then move down to the first cell in the second row and first column and go to step2.
(b) if the demand for the first column is satisfied then move to the next cell in the second column and first rows and go to step2
Step 4. If for any cell supply equals demand then the next allocation can be made in cell either in the next row or column.
Step 5. Continue the procedure until the total available quantity is fully allocated to the cells assrequired.
Remarks 1. The quantities so allocated are circled to indicate the value of the corresponding variable.
2. Empty cells indicate the value the corresponding variable as zero i.e., no unit is shipped to this cell.
Advantages - simple and reliable method
- Easy to compute understand and interpret.
Drawbacks. This method of assignment does not take into consideration the shipping cost consequently the initial solution obtained by this method usually requires several iterations before optimum solution is obtained.
Area of application
(i) It is used in case of transportation within the campus of an organization as costs are not significant.
(ii) It is used for transportation to satisty such obligations where cost is not the criteria.
Least Cost Method (L.C.M). The allocation according to this method is very useful as it takes into consideration the lowest cost and therefore, reduces the computation as well as the amount of time necessary to arrive at the optimum solution. various steps of this method can be summarised as under:
Step 1. (a) Select the cell with the lowest transportation cost among all the rows or columns of the transportation table.
(b) If the minimum cost is not unique, then select arbitrarily any cell with this minimum cost.
Step 2. Allocate as many units as possible to the cell determined in step 1 and eliminate that row (column) in which either supply is exhausted or demand is satisfied.
Step 3. Repeat steps 1 and 2 for the reduced table until the entire supply at different factories is exhausted to satisfy the demand at different warehouses.
3. Vegel's Approximation Method (VAM). This method is preferred over the order two methods because the initial basic feasible solution obtained is either optimum or very close to the optimum solution. Therefore the amount of time required to arrive at the optimum solution is greatly reduced. Various steps of this method are summarised as under:
Step 1. Compute a penalty for each row and column in the transportation table. The penalty for a given row and column is merely the difference between the smallest cost and the next smallest cost in that particular row or column.
Step 2. Identify the row or column with the largest penalty. In this identified now or column. Choose the cell which has the smallest cost and allocate the maximum possible quantity to the lowest cost in that row or column so as to exhaust either the supply at a particular source or satisfy demand at a warehouse.
If a tie occurs in the penalties select that row/column which has minimum cost. If there is a tie in the minimum cost also select that row/column which will have maximum possible assignments. It will considerably reduce computational work.
Step 3. Reduce the row supply or the column demand by the amount assigned to the cell.
Step 4. If the row supply is now zero, eliminate the row, if the column demand is now zero, eliminate the column if both the row supply and the column demand are zero. Eliminate both the row and column.
Step 5. Recompute the row and column difference for the reduced transportation table, omitting rows or columns crossed out in the preceding step.
Step 6. Repeat the above procedure until the entire supply at factories are exhausted to satisfy demand at different warehouses.
Remark. Though the vogel's approximation method has the disadvantage of more computational work before the initial solution is reached, if usually results with an assignment which has less transportation cost associated with it than the cost associated with a solution obtained by other method. This ultimately helps in obtaining the optimum solution to the given problem in less iteration.