Initial basic feasible solution of a transportation problem

Initial basic feasible solution of a transportation problem can be obtained by any of the following methods:

1. North–west corner rule

The major advantage of the north–west corner rule method is that it is very simple and easy to apply. Its major disadvantage, however, is that it is not sensitive to costs and consequently yields poor initial solutions. The steps involved in determining an initial solution using north–west corner rule are as follows:

Step1. Write the given transportation problem in tabular form (if not given).

Step2. Go over to the north-west corner of the table. Suppose it is the (i, j)th cell.

Step3. Allocate min (ai, bj) to this cell. If the min (ai , bj) = ai, then the availability of the ith origin is exhausted and demand at the jth destination remains as bj-ai and the ith row is deleted from the table. Again if min (ai, bj) = bj, then demand at the jth destination is fulfilled and the availability at the ith origin remains to be ai-bj and the jth column is deleted from the table.

Step4. Repeat steps 2, 3 until all origins are exhausted and all demands are fulfilled.

Note. If at any point before the end, a row’s supply and column’s demand are both satisfied simultaneously, then only one (either one) may be crossed out and the next variable to be added to the basic solution will necessary be at the zero level. Such a situation is known as degeneracy.

2. Row minima method

Step1. Write the given transportation problem in tabular form (if not given).

Step2. Choose the cell with minimum cost in the first row. If it is not unique, anyone of the cell in the Ist row, with minimum cost can be chosen. Suppose it is the (i, j)th cell.

Step3. Allocate min (ai, bj) to this cell. If the min (ai , bj) = ai, then the availability of the ith origin is exhausted and demand at the jth destination remains as bj-ai and the ith row is deleted from the table. Again if min (ai, bj) = bj, then demand at the jth destination is fulfilled and the availability at the ith origin remains to be ai-bj and the jth column is deleted from the table.

Step4. Repeat steps 2, 3 until first row is deleted.

Step5. Then choose the cell with minimum cost in the second row and continue step III until the 2nd row is deleted. Likewise consecutive rows get deleted repeating step3 continuously and we stop when all the rows have been deleted.

3. Column minima method

Step1. Write the given transportation problem in tabular form (if not given).

Step2. Choose the cell with minimum cost in the first column. If it is not unique, anyone of the cell in the Ist column, with minimum cost can be chosen. Suppose it is the (i, j)th cell.

Step3. Allocate min (ai, bj) to this cell. If the min (ai , bj) = ai, then the availability of the ith origin is exhausted and demand at the jth destination remains as bj-ai and the ith row is deleted from the table. Again if min (ai, bj) = bj, then demand at the jth destination is fulfilled and the availability at the ith origin remains to be ai-bj and the jth column is deleted from the table.

Step4. Repeat steps 2, 3 until first column is deleted.

Step5. Then choose the cell with minimum cost in the second column and continue step III until the 2nd column is deleted. Likewise consecutive columns get deleted repeating step3 continuously and we stop when all the columns have been deleted.

4. Matrix minima method (Lowest cost entry method)

In this method, allocations are made on the basis of economic desirability. The steps involved in determining an initial solution using least-cost method are as follows:

Step1. Write the given transportation problem in tabular form (if not given).

Step2. Choose the cell with minimum cost. If it is not unique, anyone can be chosen. Suppose it is the (i, j)th cell.

Step3. Allocate min (ai, bj) to this cell. If the min (ai , bj) = ai, then the availability of the ith origin is exhausted and demand at the jth destination remains as bj-ai and the ith row is deleted from the table. Again if min (ai, bj) = bj, then demand at the jth destination is fulfilled and the availability at the ith origin remains to be ai-bj and the jth column is deleted from the table.

Step4. Repeat steps 2, 3 until all origins are exhausted and all demands are fulfilled. The process must end as .

5. Vogel’s approximation method (unit cost penalty method) (VAM)

VAM is an improved version of the least-cost method that generally, but not always, produces better starting solutions. VAM is based upon the concept of minimizing opportunity (or penalty) costs. The opportunity cost for a given supply row or demand column is defined as the difference between the lowest cost and the next lowest cost alternative. This method is preferred over the methods discussed above because it generally yields, an optimum, or close to optimum, starting solutions. Consequently, if we use the initial solution obtained by VAM and proceed to solve for the optimum solution, the amount of time required to arrive at the optimum solution is greatly reduced. The steps involved in determining an initial solution using VAM are as follows:

Step1. Write the given transportation problem in tabular form (if not given).

Step2. Compute the difference between the minimum cost and the next minimum cost corresponding to each row and each column which is known as penalty cost.

Step3. Choose the maximum difference or highest penalty cost. Suppose it corresponds to the ith row. Choose the cell with minimum cost in the ith row. Again if the maximum corresponds to a column, choose the cell with the minimum cost in this column.

Step4. Suppose it is the (i, j)th cell. Allocate min (ai, bj) to this cell. If the min (ai , bj) = ai, then the availability of the ith origin is exhausted and demand at the jth destination remains as bj-ai and the ith row is deleted from the table. Again if min (ai, bj) = bj, then demand at the jth destination is fulfilled and the availability at the ith origin remains to be ai-bj and the jth column is deleted from the table.

Step5. Repeat steps 2, 3, 4 with the remaining table until all origins are exhausted and all demands are fulfilled.

Note.

  • In order to reduce large number of steps required to obtain the optimal solution, it is advisable to proceed with the initial feasible solution which is close to the optimal solution. Vogel’s method often gives the better initial feasible solution to start with. Although Vogel’s method takes more time as compared to other two methods, but it reaches the time in reaching the optimal solution.
  • There is no way that we can predict that a transportation problem will have degenerate solution, just by looking at it.
  • In VAM the cost difference indicate the penalties for not using the respective least cost routes.

Bookmark the permalink.