Testing the Optimality of Transportation Solution | Operations Research

This article throws light upon the top two methods used for testing the optimality of transportation solution. The methods are: 1. Stepping Stone Method 2. Modified Distribution (MODI) Method.

1. Stepping Stone Method:

This method content following steps:

Step (1):

Determine an initial basic feasible solution using any of the three methods discussed earlier.

Step (2):

Make sure that the number of occupied cells is exactly equal to m + n-1, where m is no. of rows and n is no. of columns.

Step (3):

Evaluate the cost – effectiveness of shipping goods via transportation routes not currently in solution.

This testing of each unoccupied cell is conducted by the following five steps as follows:

(a) Select an unoccupied cell, where a shipment should be made.

(b) Beginning at this cell, trace a closed path using the most direct route through at least three occupied cells used in the solution and then back to the original occupied cell and moving with only horizontal and vertical moves. Further, since only the cell at the turning points are considered to be on the closed path, both unoccupied and occupied boxes may be skipped over. The cell at the turning points are called “stepping stones” on the path.

(c) Assigning plus (+) and minus (-) signs alternatively on each corner cell of the closed path just traced, starting with a plus sign at the unoccupied cell to be evaluated.

(d) Compute the ‘net change in the cost’ along the closed path by adding together the unit cost in each square containing the minus sign.

(e) Repeat sub-step.

(a) Through sub-step.

(b) Until ‘net change’ in cost has been calculated for all unoccupied cells of the transportation table.

Step (4):

Check the sign of each of the net changes. If all net changes computed are greater than or equal to zero, an optimal solution has been reached. If not, it is possible to improve the current solution and decrease total shipping costs.

Step (5):

Select the unoccupied cells having the highest negative net cost change and determine the minimum number of units that can be assigned to a cell marked with a minus sign on the closed path corresponding to this cell. Add this number to the unoccupied cell and to all other cells on the path marked with a plus-sign. Subtract this number from cells on the closed path marked with a minus sign.

Step (6):

Go to step (2) and repeat the procedure until we get an optimal solution.

Example:

To understand clearly we discuss the initial solution given by least cost method as shown in table below:

Step 1:

The initial solution has 4+3-1 = 6 occupied cells and involves transpiration cost of Rs. 922.

Step 2:

Let us evaluate unoccupied cell (F₁, W₁). The shipment of one unit to this cell will incur an additional cost of Rs 21. This requires in turn that one unit be decreased from cell (F₁, W₄) which decreases cost by Rs 13. But to keep the balance between capacity and requirement we have to add one unit to cell (F₃, W₄) which increases cost by Rs. 41 and finally one unit is decreased from cell (F₃, W₁) which decreases cost by Rs. 32.

To determine the net cost change. Let us list down the changes as shown below:

This indicates that if the occupied cell (F₁, W₁) is made occupied then the total transportation cost will be increased by Rs 17 per unit supplied. This transfer of shipment of one unit is also shown in the right hand side table by making a close path. Similarly other unoccupied cell can also be evaluated proceeding in the same manner.

(3) Then we observe that only (F₃, W₃) for which the largest reduction in cost change being – 11 is -ve.

.^.. The unoccupied cell (F₃, W₃) will be considered for further reduction in the cell. The new solution thus obtained is shown below table (5.14)

The total transportation cost of the improved solution is (11×13) + (6×17) + (7×14) + (10×27) + (5×18) + (4×41) = Rs. 867

(4) Thus we observe that only (F₂, W₄) for which the largest reduction in cost change being-15 is -ve.

.^.. The unoccupied cell (F₂, W₄) will be considered for further reduction in cost.

.^..The second feasible shipment plan is shown below in table (5.16)

The total transportation cost associated with the improved solution is

(11 x 13)+ (6 x 17)+ (3 x 14)+ (4 x 23)+ (10 x 27)+ (9 x 18) = Rs. 811

(4) We now return to step 2 and examine it transportation costs can be reduced further by replacing any of the unoccupied cells with the one actually used in the second solution.

The net changes in costs for each of the unoccupied cells are as follows:

Thus the cell (F₂, W₂) with the negative value will be included in the new solution, because shipping one unit from factory F₂ to warehouse W₂ reduce the transportation cost by Rs. 8. Further since min (3, 10). 3 units can be shipped in cell (F₂, W₂) the third feasible solution is given below in table (5.17)

The corresponding shipping cost is

(11 x3) + (6x 17) + (3x 18) + (4×23) + (7×27) + (12x 18) = Rs. 796

(5) The next step is to evaluate again all the unoccupied cells of the improved solution and see whether the total cost can be further reduced. The unoccupied cells of this improved solution are evaluated as shown below.

Since all unoccupied ceils have positive values for the net cost change.

Hence we have reached the optimal solution.

The transportation schedule is shown in table below and the total transportation cost of the optimal solution is as given below.

2. Modified Distribution Method (MODI):

In the modified distribution method all evaluations of all the unoccupied cells are calculated simultaneously thus only one closed path with most negative cell evaluation is traced. Therefore it provides considerable time saving as compared to the stepping stone method.

The steps are as follow:

Step (1):

Find an initial basic feasible solution consisting of m + n -1 allocations in independent position using any of the three methods.

Step (2):

Calculate a set of numbers for each row and each column. To compute u_i (i = 1, 2 . . m) for each row and u (j = 1, 2 … n) for each column.

Set C_ij = u_i + v_j for each of the m+n-1 occupied cells used in the initial solution.

Step (3):

For unoccupied cells calculate opportunity cost by using the relationship

Δ_ij = c_ij – (u_i + v_i); I = 1, 2. . m

j = 1, 2. . n

Step (4):

(i) If all Δ_ij > 0. then current basic feasible solution is optimal.

(ii) If Δ_ij =0. then current basic feasible solution will remain unaffected but an alternative solution, exists.

(iii) If any of Δ_ij < 0, then an improved solution can be obtained by entering unoccupied cell (i, j) in the basis. An unoccupied cell with the largest negative value of A is chosen for entering into the basic solution.

Step (5):

Construct a closed path or loop for the unoccupied cell with the largest negative opportunity cost, start the loop with unoccupied cell and mark a plus (+) sign in this cell, trace the loop along the rows (or column) to an occupied cell, mark the corner with minus (-1) sign and continue down the column (or row) to an occupied cell and mark the corner with (+) sign and (-) sign alternatively. Close the loop back to the selected unoccupied cell.

Step (6):

Select the smallest quantity amongst the cell on the corner of closed loop marked with (-) sign. Allocate this value to the selected unoccupied cell and add it to other occupied cells marked with (+) sign and subtract it from the occupied cells marked with (-) sign, so that the solution remains feasible.

Step (7):

By allocating units to the unoccupied cell as per step (6) a new improved solution is obtained. Calculate the total transportation cost for then improved solution.

Step (8):

Test the improved solution for optimality. The procedure terminates when all d_ij ≥ 0 for unoccupied cells.

The steps of MODI method can also be described by the following flow chart:

Example 1:

To understand clearly MODI method we have to take initial solution obtained by Vogel’s method. Then check of optimality.

Step (1):

Here we have altered the transportation table by assigning an additional row and column.

Since the no. of occupied cells are m + n – 1 = 3 + 4 – 1 = 6 the initial solution is non – degenerate. Thus an optimal solution can be obtained. The total transportation cost is = (13 x 11) + (6 x 17) + (3 x 18) + (4 x 23) + (7 x 27) + (12 x 18) = Rs. 798.

Step (2):

Here u_i indicate row values & v_j indicate column values.

u_i — value for the i^th row (factory) i = 1,2,3

v_j = – – j^th column (warehouse) j= 1,2,3,4

For the occupied cell e_ij = u_i + v_j.

Here for six occupied cells which can be described as

Step (3):

We now proceed to calculate Δ_ij = c_ij – (u_i + v_j) for all the unoccupied cell

Step (4):

Here all Δ_ij > 0 then current basic feasible solution is optimal. The following table represents the solution of the problem with corresponding row and column numbers.

According to the optimality criteria for minimization transportation problem the current solution is optimal one, since the opportunity costs of the unoccupied cells are all zero or positive.

Example 2:

Determine the optimum basic feasible solution to the following transportation problem:

Solution:

Step 1:

To find initial basic feasible solution using least cost method:

Here the lowest cost (Rs. 20 appears in cell (P₁, W₁). Because production at company P₁ and warehouse requirement of W₁ are 50 and 100 units respectively.

We assign x₁₁ = 50

This allocation meets the requirements of warehouse W₁ and still have a Demand of 50 units. Consequently we delete the first row adjust the demand at company P₂, & P₃, and reduce the capacity of company P₂ to zero as shown in following table:

Because the capacity of plant P₃ is 150 & Demand of warehouse W₃ is 22. We allocate x₃₃ = 22 and cross out third row.

Because there are 1 row and 3 column not yet crossed out, we go back to step 1. The smallest entry in the remaining cost matrix is 40 which has in warehouse W₄ and W₅.

Then we assign x₃₄ = 40 and x₄₀ = 40 and crossed again third row.

Similarly we apply this process. Then the complete initial basic feasible solution is shown below:

Step (2):

To find optimality

Using MODI:

Method determine the row no. u_i (i = 1,2,3) and column no. v_j(1,2,3, 4, 5) using relation c_ij = u_i + v_j for all the basic cell.

Starting with u₁, = 0

Here for seven occupied cell which can be described as:

Here since one of the opportunity cost (Δ_ij) are still negative the solution can further be improved by entering variable (P₃, W₁) it is negative then we construct a closed path we find that 20 units should be shipped from (P₃, W₂)or(P₂, W₁)to (P₃, W₁). This yield the new solution as shown in the next table.

Then again we repeat process to find u_i & v_j & Δ_ij. This has been shown in table (2) again some Δ_ij are still negative the solution can further be improved by introducing the cell (P₂ W₅) are dropping the cell W_{) as shown in table (3).

In table (3) some of the Δ_ij again negative the solution can further be improved by introducing the cell (P₁, W₂) and dropping the cell (P₃, W₅) from the basic as shown in table (4) next.

Now since all current opportunity cost (Δ_ij) are non – negative, an optimal solution is arrived at and the optimal allocation is given by according to which the optimal transportation cost is

Transportation cost = (40×20) + (10×28) + (60×36) + (40×25) + (60×35) + (50×22) + (40 x 45) = Rs. 9240.

Example 3:

Find initial basic feasible solution for the given transportation model by:

(1) North-west corner rule.

(2) Least cost method.

(3) VAM method.

Where A, B, C are sources of supply and D, E, F the destination of demand. The matrix indicates the cost of transportation per unit item from source A, B, C to the destination D, E.F

Solution (1):

By North – West Corner Rule:

By this method, the assignments for the matrix given are obtained as given next:

The total cost of transportation = (6×20) + (4×30) + (8×40) + (4×25) + (2×35) = Rs. 730

Here initial demand of 20 for destination D has been met from A, starting from VW corner. Since supply for A can be 50, we move horizontally and allocate remaining 30 to destination E. This satisfies demand for D and total supply from A.

Now we move vertically down to meet further demand of E (total 95, remaining 65 – 40 = 25 has to be allocated from C, which can supply 60 units, 25 are allocated to E and the remaining 35 to F as indicated on the matrix. Now we have reached SE corner of the matrix satisfying all supply/demand requirements.

Feasibility of the solution:

After all the allocations, we have to check for feasibility, for this, we should have m + n – 1 occupied cells, then we have a feasible solution. In the above case, there are 5 allocation which is m + n- 1 =3 + 3-0 1 =5.

Hence the solution obtained is feasible one.

(II) By least – Cost Method:

First check for the balanced problem i.e., demand-supply. Here is it balanced problem.

Step (1):

Minimum cost in the matrix is 1 at cell AF.

Step (2):

We allocate 35 units to cell AF, being the maximum of supply and demand for cell AF.

Step (3):

Since Demand for F has been satisfied the column F has been eliminated.

Step (4):

Adjusted cost matrix will become

Step (5):

Repeating steps (1) to (4). we get the allocations as:

Calculating the cost as per these allocations, we get

Total transportation Cost = (3×20) + (4×15) + (8 x 20) + (4×60) + (1×35)

= 60 + 60 + 160 + 240 + 35

= Rs. 555

This value of transportation cost is lesser than the cost obtained by the North-West corner rule. Thus, this is an improved method and should be used as initial solution for optimality test.

Feasibility checking:

If allocation are m + n-1 = 1, then the solution is feasible.

In this case, m + n – 1 = 5 and we have 5 allocations or occupied cells. Hence the solution obtained is feasible.

(III) By Vogel’s Approximation Method:

Row A has minimum element as 1 and next least as 4, the difference is 4 – 1= 3 is written against iteration I in Row A, similarly for row B, the difference of least cells will be 7-3=4 and is so indicated under iteration I, row B.

The process is repeated for C row and all the columns. Maximum of values in row and column differences, i.e., 3, 4, 2, 1, 0, 1 is 4 and hence allocations (max = 20) is made to the cell of least cost i.e. cell BD. This satisfies column D and is scored out.

Repeating same process during iteration II. We allocate 35 units at cell AF [cell with least cost in row AJ. This satisfies column F fully and hence column F] is scored out, due to its demand having been met fully. Other allocations are made based on supply/demand positions.

It can be seen that total cost involved in VAM comes to 555. a solution better than the one obtained by NW corner rule involving a total cost of 730, but similar to that obtained by the least cost method.

Solution is also feasible as there are m + n-1=3 + 3-1=5 occupied cells in the above solution.

Test the Optimality by Stepping Stone Method:

Applying Stepping Stone Method for the above problem, let us consider allocation to the unoccupied cell AD with closed loop AD → AE → BE → BD (AE, BE and BD are three occupied cells).

It indicates increase of cost by changing allocation for one unit at cell AD. Hence, solution has not improved.

Let us consider other routes as follows:

Since any allocation to any empty cell increases the cost, the solution obtained is optimal. Similarly, while testing the optimality of the initial basic feasible solution obtained by VAM. we find that solution are identical and optimal.