An organization has four destinations and three sources for supply of goods.

The transportation cost per unit is given in the next slide. The entire availability is 700 units which exceeds the cumulative demand of 600 units. Decide the optimal transportation scheme for this case.

Typical problem

Solution --Step 1
Check for balance of supply and demand
S Supply = 250 + 200 + 250 = 700 units

S Demand = 100 + 150 + 250 + 100 = 600 units

Decision Rule after step 1

(i)

If S Supply = S Demand

then go to next step. (ii) Else; if S Supply > S Demand

then, add a dummy destination with zero transportation cost. (iii) Or else; if S supply < S Demand

then, add a dummy source with zero transportation cost.

Since, in this problem .

S supply > D Demand
Hence; add a dummy destination (say D5) with zero

transportation cost and balance demand which is difference in supply and demand (= 100 units). The initial transportation matrix is now formulated with transportation cost in the small box of each route. Note that each cell of the transportation matrix represents a potential route.

Introducing dummy column for balancing the supply and demand

Step 2:
i)
(ii)

Decide the nature of problem : Minimization of transportation-cost

Make initial assignment

Initial assignment
Initial assignment may be done by using any of the

following approaches :
(i) (ii) (iii)

Least-cost method North-West corner method Vogel's approximation method

1.Least Cost method

Select the lowest transportation (or shipping) cost cell (or
Allocate the minimum of remaining balance of supply (in

route) in the initial matrix. For example: it is route S1D5, S2D5 and S3D5 in our problem with zero shipping cost. last column) and demand (in last row).

Let us select S1D5 route. One can also select other route

(S2D5 or S3D5) in case of tie. For S1D5, available supply is 250 and available demand is 100 units. The lower is 100 units. Hence, allocate 100 units-through this route (i.e, S1D5).

With 100 units allocation in route S1D5

Allocation 2
Next, least cost route is S1D1, with 13 per unit of

shipping cost. For this route, the demand is 100 units and remaining supply is 150 units. We allocate minimum of the two, i.e., 100 units in this route. With this destination, D1 is consumed but source S1 is still left with (150-100) = 50 units of supply. So, now leave the destination D1 and we get the following matrix.

Assignment for destination D1 and D5 consumed

Allocation 3
Now, we work on remaining matrix, which excludes

first column (D1) and last column (D5). Next assignment is due in the least cost route, which is route S2D4. For this route, we can allocate 100 units which is lesser of the corresponding demand (100 units) and (200 units). By this allocation in route S2D4, the demand of destination D4 is consumed. So, this column is now crossed out.

Assignment with destination D1, D4 and D5 consumed

Allocation 4.
Now, we work on the remaining matrix which excludes,

column, D1, D4 and D5. Next assignment is due in the least cost route of the remaining routes. Note that we have two potential routes: S1D2 and S2D3. Both have 16 units of transportation cost. In case of any tie (such as this), we select any of the routes. Let us select route, S1D2, and allocate 50 units (minimum of demand of 150 and supply of remaining 50 units). With this, all supply of source S1 is consumed. Therefore, cross out row of S1. We get the following matrix:

Destination D1, D4 and D5 source S1 are consumed

Allocation 5
Now, remaining allocation is done in route S2D3 (as 100

units). With this source, S2 is consumed. Next allocation of 100 units is done in route S3D2 and 150 units in route S3D3. Final initial assignment is as follows:

Final allocation.. Initial assignment by least cost method

Step 3: Count the number of filled (or allocated) routes.

Decision rule (i) If filled route = (m + n 1) then go for optimality check (i.e. step 5). (ii) If filled route < (m + n 1) then the solution is degenerate. Hence, remove degeneracy and go to step 4. Here, m = number of destinations, including dummy column, if any n = number of source, including dummy, row, if any For our problem (m + n- l) = 5 + 3-1 = 7. The number of filled route is equal to 7. Hence, problem is not degenerate. Therefore, proceed to optimality check

Initial solution by north west corner method

This approach is also for making initial assignment, as we

have done in the least cost method. Therefore, this approach should not be applied if initial assignment has already been made by any other method. In the North-West Corner (NWC) method, we start with the top-left (corner-most) route, which is S:Dr Irrespective of cost, allocation is made in this route for the minimum of supply or demand. In our case, demand for this route is 100 and supply is 250. Therefore, allocate 100 units in this route. With this, column corresponding to D1 is consumed.

Allocation 2
Now, work on the remaining matrix, which excludes

column Dr Again, select the top-left route. Now, it is cell S1D2. Allocate in the same way. Thus, 150 units are allocated in this route. Note that, with this, both D2 and S, are consumed.

Initial solution by north west corner method

Initial Assignment by Vogels Approximation Method (VAM)

In this method, we calculate the difference between

the two least-cost routes for each row and column. The difference is called as penalty cost for not using the least-cost route. Highest of all calculated penalty costs is for S3 and (S2). Therefore, allocation is to made in row of source S3. The route (or cell), which one must select, should be the lowest cost of this row. This route S3D5. Hence, first allocation is as follows.

First calculation in Vogels method

Rules for selecting the row and allocation

Highest of all calculated penalty costs is for S3 and (S2).
Therefore, allocation is to made in row of source S3. The route (or cell), which one must select, should be

the lowest cost of this row. This route S3D5. Hence, first allocation is as follows.

First allocation by VAM

Second calculation of Penalty cost in VAM

Second allocation in Vogels method

Allocation 3.
After second allocation, since destination D1 is

consumed, we leave this column and proceed for calculation of next penalty cost. Allocation is done in route S1D2. Since there is tie between all routes, we break the tie by arbitrarily selecting any route (S1D2 in this case.)

Third calculation of Penalty cost

Third allocation in Vogels method

Fourth calculation of Penalty cost in VAM

Fourth allocation in Vogels method

Final allocation Through VAM

Check for degeneracy

(m + n 1) = 7 Number of filled cell = 6, which is one less than (m + n - 1).

Hence, go to step 4 for removing the degeneracy.

Step 4: We allocate in the least-cost un-filled cell. This cell is route S1D5 or S2D5. Let us select route S1D5. Thus, we get following matrix after removing degeneracy.

Final allocation after removing degeneracy in Vogels method

Final allocation
With the fourth allocation, column D4 is consumed.
The only left column D3, the allocations of 100 units

and 150 units are done in route S2D3 and S4D3 respectively. Thus, we get the following allocations in the Vogels approximation method.

Check for optimality

Calculate the opportunity of non-allocated orunfilled

routes. For this, use the following equation: where ui = row value
vj = column value

Cij = unit cost of unassigned route

If the opportunity cost is negative for all unassigned

routes, the initial solution is optimal. If in case any of the opportunity costs is positive, then go to next step

Calculation of ui and vj for Vogel methods initial solutions

Opportunity cost of above assignment is as follows:

Unassigned route Opportunity cost (ui + vj Cij) S1D3 S1D4 S2D1 S2D2 S2D5 S3D1 S3D2 S3D4

0 + 17 19 = 2 0 + 16 17 = 1 1 + 13 17 = 5 1 + 16 19 = 4 1 + 0 0 = 1 0 + 13 15 = 2 0 + 16 17 = 1 0 + 16 16 = 0

Optimal assignment and optimal cost

Since all opportunity costs are negative or zero, the

initial assignment of Vogels solution is optimal with total cost of Rs. 9350. The optimal assignment of routes is 100 units in S1D2, 100 units in S2D3, 100 units in S2D4, and 150 units in S3D3. Note that this solution is different from NorthWest corner solution but total cost is same and minimum.

Initial assignment by least cost method and calculation of u,v values

Step 6: Calculate opportunity cost of un-assigned routes.

Unassigned route S1D3 S1D4 S2D1 S2D2 S2D5 S3D1 S3D4 S3D5 Opportunity cost (ui + vj Cij) 0 + 16 19 = 3 0 + 15 17 = 2 0 + 13 17 = 4 0 + 16 19 = 3 0+00=0 1 + 13 15 = 2 1 + 15 16 = 0 1 + 0 0 = +1

Since route S3D5 has positive opportunity cost, the solution is non-optimal; hence, we go to next step and make a loop as follows.

Closed loop for cell S3D5

Revised allocation in least-cost assignment

Final allocation through VAM

Initial cost comparison of three methods .

Total initialcost in Least cost method of assignment is

(13 100 + 16 50 + 100 0 + 16 100 + 15 100 + 17 150) or Rs. 9450. The total initialcost in North west corner method is (13 100 + 16 150 + 16 100 + 0 100) or Rs. 9350. The total initial cost for this allocation is (13 100 + 16 150 + 16 100 + 15 100 + 17 150 + 0 100) or equal to Rs. 9350:

Check for degeneracy

(m + n 1) = 7
Number of filled cell = 6, which is one less than (m + n

- 1). Hence, go to the next step for removing the degeneracy.

Removing Degeneracy
Allocate in the least-cost un-filled cell.
This cell is route S1D5 or S2D5. Let us select route S1D5.

Thus, we get following matrix after removing

degeneracy

Final allocation after removing degeneracy in Vogels method

Optimization of Initial Assignment

Check the optimality of the initial solution First, we start with any row (or column). Let us select row 1, i.e., source S1; For this row, let us define row value, u1 = 0. Now consider all filled routes of this row. For these routes, calculate column values v. using following equation: u1 + v1 = Cij (For any filled route) where u1 = row value vj = column value Cij = unit cost of assigned route Once first set of column values (vj is known, locate other routes of filled cells in these columns. Calculate next of ui (or vj values using above equation. In this way, for all rows and columns, ui and vj values are determined for a non- degenerate initial solution.