Transportatopn Problem

Transportation Problem & Degeneration

Presented By : Abhishek Upadhyay , Akhil Bhadrecha , Anshul K. Singh , Avijit Das , Kesharpu Sekhar & Saurabh Tamrakar

Transportation Problem Aim: To find out optimum transportation schedule keeping in mind cost of transportation to be minimized.

Transportation Problem 

The transportation problem is a special type of LPP where the objective is to minimize the cost of distributing a product from a number of sources or origins to a number of destinations. Because of its special structure the usual simplex method is not suitable for solving transportation problems. These problems require special method of solution. The origin of a transportation problem is the location from which shipments are dispatched. The destination of a transportation problem is the location to which shipments are transported. The unit transportation cost is the cost of transporting one unit of the consignment from an origin to a destination.

Methods of solving Transportation Problem 

North West Corner Method (NWCM)



Least Cost Method (LCM)



VOGEL’S APPROXIMATION METHOD (VAM)

Problem A manager has three factories (i.e. origins) and four warehouses (i.e. destinations). The quantities of goods available in each factory, the requirements of goods in each warehouse and the costs of transportation of a product from each factory to each warehouse are given below. W1

W2

W3

W4

Supply

F1

19

30

50

12

7

F2

70

30

40

60

10

F3

40

10

60

20

18

Demand

5

8

7

15

Determine the optimum transportation schedule and transportation cost using: i. North West Corner Method (NWCM) ii. Least Cost Method (LCM) iii. VOGEL’S APPROXIMATION METHOD (VAM)

Steps involved in solving Transportation Problem by VAM method: 

Step I – Check whether the given problem is a balanced problem (i.e. Requirement = Capacity). In case not then add dummy row (origin) or column (destination) with zero cost to make an unbalanced transportation problem balanced.

Steps involved in solving Transportation Problem by VAM method: 

Step II – Find a solution using VAM method  



  

 

Calculate penalties for each row and each column. By “penalties” we mean the difference between two best possibilities. Give priority to the largest penalty. It belongs to a row or a column. In that row or column make allocation to the smallest cost cell. Cut off that row or column which is exhausted. Continue in the same way with the rest of the table until two squares are left. Then fill up the smallest cost square out of the remaining two. Finally fill up the last square.

Steps involved in solving Transportation Problem by VAM method: 

Step III – Check for Basic 

Initial Basic Solution = m + (n – 1) = Number of allocation where, m is Row and n is Column



If Basic then go to next step.



Else - Covert first the Non-Basic into Basic by making an artificial allocation with zero units in the smallest cost cell.

Steps involved in solving Transportation Problem by VAM method: 

Step IV – MODI Check Procedure 

Copy down the VAM solution along with cost matrix.



Find out the values of formulae







ri

and kj for stone cells using the

cij=ri+kj (Put r1 = 0)

For each unallocated cell(water cell) find: cij-(ri+kj). This is called check number for that cell. If all check number are greater than or equal to zero (>=0 ) then that solution is the optimal solution (i.e. solution obtained is an initial basic feasible solution). In case any check number is positive then revision is required. Hence go to next step.

Steps involved in solving Transportation Problem by VAM method: 

Step V – Procedure for Revision 

To revise the transportation table a loop is to be drawn and loop is made up of horizontal and vertical lines travelling through the cost matrix by starting and ending at the same point with the following conditions.  





Condition 1 – The starting point should be an open cell. Condition 2 – All the other cells travelled should be closed cells or allocated cells. Condition 3 – In horizontal or vertical travel exactly two cells can be travelled including the starting cell. Condition 4 – Jumping of a cell is permitted

Steps involved in solving Transportation Problem by VAM method: 

Step VI – Procedure for Revision 

Step for Revision: 

 

Step 1 – Of all check number choose the negetive check number and put a cross mark. Step 2 – Form the loop for this cross mark square. Step 3 – Prepare the revised cell that is put in the cross mark cell the smallest number from Step 4. Continue along the loop with minus, plus and minus signs (- + -). Do not disturb other number not on loop.

Steps involved in solving Transportation Problem by VAM method: 

Step VII – Prepare the Optimum Transportation Schedule.



Step VIII – Find the minimum Transportation Cost.

Degeneracy 



Degeneracy in a transport problem arises when the number of occupied cells is less then: number of columns(m) + number of rows(n)-1. Failure to meet the test for degeneracy in the transportation problem is indicated in two ways: 1) There may be an excessive number of allocated cells in a solution; the number of allocated cells is greater than (m+n-1). This type of degeneracy arises only in developing the initial solution and is caused by an improper assignment or an error in formulating the problem. In such cases, one must modify the

initial solution in order to get a solution which satisfies the rule of rim requirement minus 1.

2)There may be an insufficient number of stone squares in a solution. Degeneracy of this type may occur either in the initial solution or in subsequent solutions. It is this type of degeneracy which requires special procedures to resolve.

 

RESOLVING DEGENERACY: To resolve degeneracy a zero allocation is assigned to one of the unallocated cells. The general procedure, when using the Northwest Corner Rule, is to assign it to a cell in such a way that it maintains an unbroken chain of allocated cells. But while using the VAM Method, the zero allocation is carried in a least cost independent cell. An independent cell in this context means that a cell which will not lead to a closed-path on such allocation.

Thank You