Step 1. Set up cost matrix only for cells in which allocation have been made.
V_{j} → 
P 
Q 
R 
S 

U_{j }↓ 
A 
200 
300 

B 
100 

C 
500 
1500 
900 
Step 2. Enter a set of numbers V_{j} across the top of the matrix and a set of numbers U, across the left side so that their sum is equal to the cost entered in step I.
U_{1}+ V_{1} = 200
U_{1}+V_{1}=300
U_{3}+V_{1} =500
If V_{1} = 0, U_{1} = 200
U_{2} = 300, V_{3} = 1000
U_{3}+V_{4}=900
U_{2}+V_{4}=100
U_{2} + V_{3} = 1500
V_{2} = 300, U_{3} = 500, V_{4} = 400
So the matrix may be rewritten as
V_{j}/U_{i} 
V_{1}=0 
100 
1000 
400 
200 
200 
300 

300 
100 

500 
500 
1500 
900 
Step 3. Let us fill the vacant cells with the sums of U_{i} and V_{j}. This is shown below:
V_{j}/U_{i} 
0 
100 
1000 
600 
200 
… 
… 
1200 
600 
300 
300 
200 
700 
… 
500 
… 
600 
… 
… 
Step 4. Now let us subtract the cell values of the matrix of step 3 from the original cost matrix.
… 
… 
11001200 
1700600 
100+300 
0+200 
600700 
… 
… 
800600 
… 
… 
P 
Q 
R 
S 

A 
… 
… 
100 
100 
B 
400 
200 
100 
… 
C 
… 
200 
… 
… 
This is called the cell evaluation matrix.
Step 5. Now since two of the cell evaluations are negative, it means the basic feasible solution is not optimal. Hence, we will take steps to find an optimal solution.
Step 6. Identify in the evaluation cell, the cell with most negative entry. In the present example there are two cells i.e., AR and BR cells with same negative values of 100. So let us take cell AR.
Step 7. Write the initial feasible solution in the matrix. The cell value with most negative value is called the identified cell and is marked (√).
Step 8. Trace a path in this matrix consisting of a series of alternatively horizontal and vertical lines. The path begins and terminates in the identified cell. All comers of the path lie in the cells for which allocation have already been made. As the path has to begin and end at the identified cell, it may skip over any number of occupied or vacant cells. This is shown in the table below.
Step 9. Mark the identified cell (AR) as +ve and each occupied cell at the comers of the path alternatively +ve and ve and so on.
Step 10. Make a new allocation in the identified cell (AR) by entering the minimum allocation on the path that has been assigned a ve sign. Now add or subtract as the case may be, these new allocation from the original values of the cells on the corners or the path traced, keeping the row and column requirement at the back of the mind. This makes one basic cell as zero and the other cells become nonnegative. That basic cell whose allocation has become zero (AP in this case) leaves the solution. The matrix of the second feasible solution can be rewritten.
The total cost for this feasible solution is
= Rs (300 × 5 + 1100 × 1 + 100 × 1500 × 7 + 1500 × 2 + 900 × 1)
= Rs. 10,100
which is less than the cost found in the original feasible solution.
Example 5.2 Find the feasible solution of the following transportation problem using northwest corner method.
Initial feasible solution
Sol. Since requirement (4 + 7 + 6 + 13) is equal to the supply (6 + 8 + 16) it is a balanced problem.
Step 1. Set X (i.e. northwest corner cell) = 4, the smaller amount, Here S_{1} = 6 and D_{1} = 4 and so proceed to cell F, W_{1}as D < S.
Step 2. Compare the number of units available in F, and row (2) and the demand in column W_{1}(7) and so set 2 in row F_{1} W_{2}. Since D > S in this case, we have to proceed vertically, so move to cell F_{1}W_{1}.
Step 3. Here supply is 8 and demand is 5. So we set 5 in cell F_{1}W_{1 }and proceed horizontally (D<S) to cell F_{3}W_{3}.
Step 4. In cell F_{2}W_{3}, supply is 3 and demand is 6 so we set 3 in cell F_{2}W_{3} and proceed vertically (D >S) to cell F_{3}W_{3}.
Step 5. In cell F_{3}W_{3} the demand is 16 and requirement is 3 so we set 3 in F_{3}W_{3}.
Step 6. Allocate 13 in cell F_{3}W_{4}.
North West Corner Method
F_{1}W_{1 }14 × 4 = 56
F_{1}W_{2 }25 × 2 = 50
F_{2}W_{2 }25 × 5 = 125
F_{2}W_{3 }35 × 3 = 105
F_{3}W_{3 }65 × 3 = 195
F_{3}W_{4 }15×13=195
Total cost = 726
Example 5.3. Determine an initial basic feasible solution to the following transportation problem using northwest corner rule.
Sol. Since demand and availability both are equal, it is a balanced problem.
Step 1. Set the north west corner AP = 20, the lesser out of demand (40) and availability (20) as D >S, we proceed vertically to cell BP.
Step 2. Here in cell BP availability is 30 and demand is 20 so we set 20 in this cell and proceed horizontally to cell BQ as D < S.
Step 3. In cell BQ availability is 10 and demand is 6. So we set 6 and proceed horizontally to cell BR as D <S.
Step 4. In cell BR availability is 4 and demand is 8 so we set 4 in this cell. We proceed vertically down to cell CR as D > S.
Step 5. In cell CR availability is 15 and demand is 4 so we set 4 in this cell. We proceed horizontally to cell CS as D <S.
Step 6. In cell CS availability is 11 and demand is 18 so we set II in this cell. We proceed vertically down to cell DS as D > S.
Step 7. In cell DS availability is 13 and demand is 7 so we set 7 in this cell. We proceed horizontally to cell DT as D < S.
Step 8. We allot 6 in cell DT.
Example 5.4. Determine an initial basic feasible solution to the following transportation problem using row minima method.
Sol. Let us allot as much as possible in row A to the cell in which there is minimum cost i.e. a AQ in which cost is 2 we allocate 12 in this cell. As the demand of the column Q is completely satisfied, we cross off the column.
Then next lowest cost cell in row A is AS. We allot 9 to this cell and hence S column can be crossed off as demand of column S is fully satisfied.
Out of the rest matrix, the lowest cost in row A is in column AR. We can allot I in this cell. Now row is completely satisfied so row A is struck off.
Let us now take row B in which minimum cost is in cell BR and we allot 15 in this cell so row B completely satisfied and row B can be struck off.
Now let us take row C in which we have to allocate resources in cell CP as it is the minimum cost cell. We allot 7 in this cell. Which strikes off column P : only CR has been left in which only 1 can be allotted.
Hence X_{12} = 12 X_{13}= 1, X_{14} = 9, X_{21}= 15, X_{31} = 7, X_{33} = 1
Example 5.5. Find the initial basic feasible solution to the following transportation problem by
(a) Minimum cost method
(b) Northwest corner rule.
State which of the methods is better.
(a) Minimum cost method
The lowest cost cells are BR and DP let us allot 7 in cell DP and 8 in cell BR. Now we move to cells AP and DR as both have the next lowest cost i.e., 2. In cell AP only 0 can be allotted. In cell DR we can allot 7. The next minimum cost cells are BP and BQ in BP we can allot only 0 similarly in BQ we can allot only .0. The next minimum cost cells are CQ and AR. In cell CQ we can allot 7 and in cell AR we can allot 3.
The next minimum cost cell is CP with cost 5. In this cell we allocate 0. In next lowest cost cell DQ, we can allot 0. The next lowest cost cells are AQ and CR. In AQ we allot 2 and in CR we allot 0.
The cost of transportation associated with this solution is
Z = Rs. (7 × 2 + 3 + 1 × 8 + 4 × 7 + 1 × 7 + 2 × 7)
=Rs. (14+ 12 + 8 +28 +7 + 14)
= Rs.83
(b) Northwest corner rule
Step 1. We start with cell AP (top left) so in this cell we allot 5 since in this case D > S, we proceed vertically to cell BP.
Step 2. In cell BP we allot 2 and since D < S we proceed horizontally to cell BQ.
Step 3. In cell BQ we can allot only 6 since in this case D > S, proceed vertically to cell CQ.
Step 4. In cell CQ we can allot only 3 and since here D <S, we proceed horizontally to cell CR.
Step 5. In cell CR we can allot only 4 since in this cell D < S, proceed vertically to cell DR.
Step 6. In cell DR we can allot 14.
Now for this solution for transportation cost is
Z = Rs. (2 × 5 + 3 × 2 + 6 × 3 + 3 × 4 + 7 × 4 + 2 × 14)
= Rs. (10 + 6 + 18 + 12 + 28 + 28)
= Rs. 102.
It is clear that minimum cost method gives a better solution.
Example 5.6. Find the initial basic feasible solution of the following transportation problem by Vogel’s approximation method.
Sol. By Vogel’s approximation method (VAM)
Step 1 Write down the cost matrix and enter the difference between the lowest and the second lowest element in columns and rows under the respective columns and on the right side of the respective rows.
Column W_{2 }is the column with greatest difference. The lowest cost cell in this is F_{3}W_{2}, so we allot 8 in this cell.
Step 2. Strike out the column W_{2} since it completely satisfied the requirements. The shrunken matrix is shown below.
Step 3. Column W_{1} has the greatest difference so we make as much as possible allocation in the minimum cost cell of this column i.e., F, W, (19) only 5 can be allotted in this cell since column W_{1} is completely satisfied, it is crossed out and the resulting matrix is shown below:
Step 4. Now row F3 has the greatest difference (12) and the least cost cell in this row F3W4 hence we allot 10 in this cell and resultant matrix is as shown below:
In row F_{2} we can allot to cell F_{2}W_{3}. Now since column W_{3} is fully satisfied we can cross it out. In cell F_{1}W_{4} we can allot 2 to satisfy row F_{1} and in cell F_{2}W_{4} we can allot 2 to satisfy column 4.
All allocation made can now be written in a single matrix as shown below.
The cost associated with this solution is
Z = Rs (5 × 19 + 2 × 10 + 7 × 40 + 2 × + 8 x 8 + 10 × 20)
= Rs. (95 + 20 + 280 + 120 + 64 + 200)
= Rs 779
Recent Comments