USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Finding Initial Basic Feasible Solution

In this section three methods are to be discussed to find initial BFS of a T.P. In advance, it can be noted that the above three methods may give different initial BFS to the same T.P. Also allocation = minimum (supply, demand).

 

(a) North-West Corner Rule (NWC)

(i)              Select the n01th west comer cell of the transportation table.

(ii)            Allocate the mm (supply, demand) in that cell as the value of the variable.

 

If supply happens to be minimum, cross-off the row for further consideration and adjust the demand.

 

If demand happens to be minimum, cross-off the colunm for further consideration and adjust the supply.

 

(iii) The table is reduced and go to step (i) and continue the all occasion until all the supplies are exhausted and the demands are met.

 

Example 1. Find the initial BFS of the following T.P. using NWC rule.

Solution. Here, total supply = 100 = total demand. So the problem is balanced T.P.

 

The northwest comer cell is (1, 1) cell. So allocate min. (20, 30) = 20 in that cell. Supply exhausted. So cross-off the first row and demand is reduced to 10. The reduced table is 

Here the northwest comer cell is (2, l) cell. So allocate min. (15, 10) = 10 in that cell. Demand met. So cross-off the first column and supply is reduced to 5. The reduced table is

Here the northwest corner cell is (2, 2) cell. So allocate min. (5, 20) = 5 in that cell. Supply exhausted. So cross-off the second row (due to F2) and demand is reduced to 15. The reduced table is

Here the northwest corner cell is (3, 2) cell. So allocate min. (25, 15) = 15 in that cell. Demand met. So cross off the second column (due to M2) and supply is reduced to 10. The reduced table is

Here the northwest corner cell is (3, 3) cell. So allocate min. (10, 25) = 10 in that cell. Supply exhausted. So cross off the third row (due to F3) and demand is reduced to 15. The reduced table is

continuing we obtain the allocation 15 to (4, 3) cell and 25 to (4, 4) cell so that supply exhausted and demand met. The complete allocation is shown below :

Thus the initial BFS is

x11 = 20, x21 = 10, x22 = 5, x32 = 15, x33 = 10, x43 = 15, x44 = 25.

 

The transportation cost

= 20 * 3 + 10 * 2 + 5 * 4 + 15 * 5 + 10 * 2 + 5 * 1 + 25 * 4 = $ 310.

 

(b) Least Cost Entry Method (LCM) (or Matrix Minimum Method)

 

(i) Find the least cost from transportation table. If the least value is unique, then go for allocation.

 

If the least value is not unique then select the cell for allocation for which the contributed cost is minimum.

(ii) If the supply is exhausted cross-off the row and adjust the demand.

If the demand is met cross-off the column and adjust the supply.

Thus the matrix is reduced.

 

(iii) Go to step (i) and continue until all the supplies are exhausted and all the demands are met.

 

Example 2. Find the initial BFS of Example 1 using least cost entry method :

Solution. Here the least value is 1 and occurs in two cells {1, 4) and (4, 3). But the contributed cost due to cell (1, 4) is 1 x min (20, 25) i.e., 20 and due to cell (4, 3) is 1 x min. (40, 25) i.e.,

25. So we selected the cell (1, 4) and allocate 20. Cross-off the first row since supply exhausted and adjust the demand to 5. The reduced table is given below :

The least value is 1 and unique. So allocate min. (40, 25) = 25 in that cell. Cross-off the third column (due to M3) since the demand is met and adjust the supply to 15. The reduced table is. Given below :

The least value is 2 and unique. So allocate min. (15, 30) = 15 in that cell. Cross-off the second row (due to F2) since the supply exhausted and adjust the demand to 15. The reduced table is given below :

The least value is 3 and occurs in two cells (3, 1) and (4, 2). The contributed cost due to cell (3, 1) is 3 x min. (25, 15) = 45 and due to cell (4, 2) is 3 x min. (15, 20) = 45. Let us select the (3, 1) cell for allocation and allocate 15. Cross-off the first column (due to M1) since demand is met and adjust the supply to 10. The reduced table is given below :

Continuing the above method and we obtain the allocations in the cell ( 4, 2) as 15, in the cell (3, 2) as 5 and in the cell (3, 4) as 5. The complete allocation is shown below :

The initial BFS is

x14 = 20, x21 = 15, x31 = 15, x32 = 5, x34 = 5, x42 = 15, x43 = 25.

 

The transportation cost

= 20 * 1 + 15 * 2 + 15 * 3 + 5 * 5 + 5 * 6 + 5 * 3 + 25 * 1 = $ 220.

 

Note. If the least cost is only selected column wise then it is called 'column minima' method. If the least cost is only selected row wise then it is called 'row minima' method.

 

(c) Vogel's Approximation Method (VAM)

 

(i) Calculate the row penalties and column penalties by taking the difference between the lowest and the next lowest costs of every row and of every column respectively.

 

(ii) Select the largest penalty by encircling it. For tie cases, it can be broken arbitrarily or by analyzing the contributed costs.

 

(iii) Allocate in the least cost cell of the row/column due to largest penalty.

 

(iv)  If the demand is met, cross off the corresponding column and adjust the supply.

 

If the supply is exhausted, cross-off the corresponding row and adjust the demand.

 

Thus the transportation table is reduced.

 

(v) Go to Step (i) and continue until all the supplies exhausted and all the demands are met.

 

Example 3. Find the initial BFS of example 1 using Vogel’s approximation method.

Solution.

The initial BFS is

x14 = 20, x21 = 15, x31 = 15, x32 = 5, x34 = 5, x42 = 15, x43 = 25.

 

The transportation cost

= 20 * 1 + 15 * 2 + 15 * 3 + 5 * 5 + 5 * 6 + 5 * 3 + 25 * 1 = $ 220.

 

Note. If the least cost is only selected column wise then it is called 'column minima' method. If the least cost is only selected row wise then it is called 'row minima' method.

 

(c) Vogel's Approximation Method (VAM)

 

(i) Calculate the row penalties and column penalties by taking the difference between the lowest and the next lowest costs of every row and of every column respectively.

 

(ii) Select the largest penalty by encircling it. For tie cases, it can be broken arbitrarily or by analyzing the contributed costs.

 

(iii) Allocate in the least cost cell of the row/column due to largest penalty.

 

(iv)  If the demand is met, cross off the corresponding column and adjust the supply.

 

If the supply is exhausted, cross-off the corresponding row and adjust the demand.

 

Thus the transportation table is reduced.

 

(v) Go to Step (i) and continue until all the supplies exhausted and all the demands are met.

 

Example 3. Find the initial BFS of example 1 using Vogel’s approximation method.

Solution.

Since there is a tie in penalties, let us break the tie by considering the contributed costs. Due to M4, the contributed cost is 1 x min. (20, 25) = 20. While due to F 4, the contributed cost is 1 x min. (40, 25) = 25. So select the column due to M4 for allocation and we allocate min. (20, 25) i.e., 20 in (1, 4) cell. Then cross-off the first row as supply is exhausted and adjust the corresponding demand as 5. The reduced table is

Here the largest penalty is 2 which is due to F4. Allocate in (4, 3) cell as min. (40, 25) = 25.

Cross off the third column due to M3 since demand is met and adjust the corresponding supply to 15. The' reduced table is

Here the largest penalty is 2 which is due to F3. Allocate in (3, 1) cell as min. (25, 30) = 25. Cross-off the third row due to F3 since supply is exhausted and adjust the corresponding demand to 5. The reduced table is

Here the largest penalty is 2 which is due to M1. Allocate in (2, 1) cell as min. (15, 5)

5. Cross off the first column due to M1 since demand is met and adjust the supply to 10. The reduced table is

Here tie has occurred. The contributed cost is minimum due to (2, 4) cell which is 3 x min. (10, 5) = 15. So allocate min. (10, 5) = 5 in (2, 4) cell. Cross-off the fourth column which is due to M4 since demand is met and adjust the corresponding supply to 5. On continuation we obtain the allocation of 5 in (2, 2) cell and 15 in ( 4, 2) cell. The complete allocation in shown below :

The initial BFS is

x14 = 20, x21 = 5, x22 = 5, x24 = 5, x31 = 25, x42 = 15, x43 = 25.

 

The transportation cost

= 1 * 20 + 2 * 5 + 4 * 5 + 3 * 5 + 3 * 25 + 3 * 15 + 1 * 25 = $ 210.