USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

OPTIMALITY TEST BY MODI METHOD OR UV METHOD

Step 1. Set up cost matrix only for cells in which allocation have been made.

Vj

P

Q

R

S

Uj

A

200

300

B

100

C

500

1500

900

 

Step 2. Enter a set of numbers Vj 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.

U1+ V1 = 200

U1+V1=300

U3+V1 =500

If V1 = 0, U1 = 200

U2 = -300, V3 = 1000

U3+V4=900

U2+V4=100

U2 + V3 = 1500

V2 = 300, U3 = 500, V4 = 400

So the matrix may be re-written as

Vj/Ui

V1=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 Ui and Vj. This is shown below:

Vj/Ui

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.

1100-1200

1700-600

100+300

0+200

600-700

800-600

 

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 non-negative. 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 north-west 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. north-west corner cell) = 4, the smaller amount, Here S1 = 6 and D1 = 4 and so proceed to cell F, W1as D < S.

Step 2. Compare the number of units available in F, and row (2) and the demand in column W1(7) and so set 2 in row F1 W2. Since D > S in this case, we have to proceed vertically, so move to cell F1W1.

Step 3. Here supply is 8 and demand is 5. So we set 5 in cell F1W1 and proceed horizontally (D<S) to cell F3W3.

Step 4. In cell F2W3, supply is 3 and demand is 6 so we set 3 in cell F2W3 and proceed vertically (D >S) to cell F3W3.

Step 5. In cell F3W3 the demand is 16 and requirement is 3 so we set 3 in F3W3.

Step 6. Allocate 13 in cell F3W4.

North West Corner Method

F1W1      14 × 4 = 56

F1W2      25 × 2 = 50

F2W2      25 × 5 = 125

F2W3      35 × 3 = 105

F3W3      65 × 3 = 195

F3W4      15×13=195

Total cost = 726

Example 5.3. Determine an initial basic feasible solution to the following transportation problem using north-west 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 X12 = 12 X13= 1, X14 = 9, X21= 15, X31 = 7, X33 = 1

Example 5.5. Find the initial basic feasible solution to the following transportation problem by

(a)             Minimum cost method

(b)             North-west 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) North-west 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 W2 is the column with greatest difference. The lowest cost cell in this is F3W2, so we allot 8 in this cell.

Step 2. Strike out the column W2 since it completely satisfied the requirements. The shrunken matrix is shown below.

Step 3. Column W1 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 W1 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 F2 we can allot to cell F2W3. Now since column W3 is fully satisfied we can cross it out. In cell F1W4 we can allot 2 to satisfy row F1 and in cell F2W4 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