1 of 28

Transportation Problem

PROF. SNEHAL SUNIL DARJI

K.J.PATEL COLLEGE, NANI KADI

2 of 28

Introduction:

One Important application of linear programming is in the area of physical distribution (transportation) of goods and services from several centres to several demand centres.

It is easy to mathematically express a transportation problem in terms of an LP model, which can be solved by the simplex method.
It involves a large number of variables and constraints, it takes a long time to solve it.
However, transportation algorithms, namely Stepping Stone Method and the MODI (modified distribution) Method, have been developed for this purpose.

Prof. V. D. Zanzrukiya

3 of 28

Definition: Transportation problem is a special kind of linear programming problem in which goods are transported from a set of sources to a set of destinations subject to the supply and demand of the source and destination, respectively, such that the total cost of transportation is minimized.

Examples of Transportation Problem

Prof. V. D. Zanzrukiya

Source	Destination	Commodity	Objective
Plants	Markets	Finished Goods	Minimizing total cost of shipping
Plants	Finished goods warehouses	Finished Goods	Minimizing total cost of shipping
Finished goods Warehouses	Markets	Finished Goods	Minimizing total cost of shipping
Suppliers	Plants	Raw Materials	Minimizing total cost of shipping
Suppliers	Raw material warehouses	Raw Materials	Minimizing total cost of shipping
Raw material Warehouses	Plants	Raw materials	Minimizing total cost of shipping

4 of 28

General Mathematical Model of Transportation Problem

Prof. V. D. Zanzrukiya

5 of 28

Prof. V. D. Zanzrukiya

6 of 28

For easy presentation and solution, a transportation problem data is generally presented as shown in below table.

Prof. V. D. Zanzrukiya

To

From

7 of 28

Prof. V. D. Zanzrukiya

8 of 28

Remarks

When the total supply’s equal to the total demand, the problem is called balanced transportation problem, otherwise it is called an unbalanced transportation problem. The unbalanced transportation problem can be made balanced by adding a dummy supply centre (row) or a dummy demand centre (column) as the need arises.
When the number of positive allocations (values of decision variables) at any stage of the feasible solution is less than the required number (rows + columns –1), i.e. number of independent constraint equations, the solution is said to be degenerate, otherwise non-degenerate.
Cells in the transportation problem that have positive allocation are called occupied cells, otherwise they are known as empty or non-occupied cells.

Prof. V. D. Zanzrukiya

9 of 28

Prof. V. D. Zanzrukiya

10 of 28

Prof. V. D. Zanzrukiya

11 of 28

Prof. V. D. Zanzrukiya

Destination

Supply

1

2

3

4

Source

1

30

50

15

0

300

2

35

70

20

0

200

3

20

45

60

0

500

Demand

300

200

400

100

1000

Destination

Supply

1

2

3

Source

1

30

50

15

300

2

35

70

20

200

3

20

45

60

500

Demand

300

200

400

900/1000

12 of 28

THE TRANSPORTATION ALGORITHM

Step 1: Formulate the problem and arrange the data in the matrix form

The formulation of the transportation problem is similar to the LP problem formulation. Here the objective function is the total transportation cost and the constraints are the supply and the demand available at each source and destination, respectively.

Step 2: Obtain an initial basic feasible solution

North-West Corner Method (NWCM)
Least Cost Method (LCM)
Vogel’s Approximation (or Penalty) Method

The initial solution obtain by any of the three methods must satisfy the following conditions:

The solution must be feasible, i.e. it must satisfy all the supply and demand constraints (and also rim conditions).

Prof. V. D. Zanzrukiya

13 of 28

Prof. V. D. Zanzrukiya

14 of 28

Prof. V. D. Zanzrukiya

15 of 28

Prof. V. D. Zanzrukiya

Supply

Demand

Supply

Demand

16 of 28

Least Cost Method (LCM)

Step 1: Select the cell with the lowest unit cost in the entire transportation table and allocate as much as possible to this cell. Then eliminate(line out) that row or column in which either the supply or demand is exhausted. If a row and a column are both satisfied simultaneously, then only one may be crossed out.

In case the smallest unit cost cell is not unique, then select the cell where the maximum allocation can be made.

Step 2: After adjusting the supply and demand for all uncrossed-out rows and columns repeat the procedure with the next lowest unit cost among the remaining rows and columns of the transportation table and allocate as much as possible to this cell. Then eliminate (line out) that row and column in which either supply or demand is exhausted.

Step 3: Repeat the procedure until the entire available supply at various sources and demand at various destinations is satisfied. The solution so obtained need not be non-degenerate.

Prof. V. D. Zanzrukiya

17 of 28

Prof. V. D. Zanzrukiya

Supply

Demand

Supply

Demand

18 of 28

Vogel’s Approximation Method (VAM) (Penalty or Regret Method)

Step 1: Calculate the penalties for each row (column) by taking difference between smallest and next smallest unit transportation cost in the same row (column). This difference indicates the penalty or extra cost that has to be paid if one fails to allocate to the cell with the minimum unit transportation cost.

Step 2: Select the row or column with largest penalty and allocate as much as possible in the cell that has the least cost in the selected row or column and satisfies the rim conditions. If there is a tie in the values of penalties, it can be broken by selecting the cell where the maximum allocation can be made.

Step 3: Adjust the supply and demand and cross out the satisfied row or column. If a row and a column are satisfied simultaneously, only one of them is crossed out and the remaining row (column) is assigned a zero supply (demand). Any row or column with zero supply or demand should not be used in computing future penalties.

Step 4: Repeat Steps 1 to 3 until the entire available supply at various sources and demand at various destinations are satisfied.

Prof. V. D. Zanzrukiya

19 of 28

Prof. V. D. Zanzrukiya

Supply

Demand

20 of 28

Prof. V. D. Zanzrukiya

Supply

Demand

Row Differences

Column Differences

21 of 28

Prof. V. D. Zanzrukiya

22 of 28

Prof. V. D. Zanzrukiya

23 of 28

Prof. V. D. Zanzrukiya

24 of 28

Prof. V. D. Zanzrukiya

Supply

Demand

25 of 28

Applying Vogel’s approximation method to obtain an initial basic feasible solution shown in the following table.

Prof. V. D. Zanzrukiya

Supply

Demand

Row Differences

Column Differences

26 of 28

Prof. V. D. Zanzrukiya

Supply

Demand

27 of 28

Prof. V. D. Zanzrukiya

Supply

Demand

28 of 28

Prof. V. D. Zanzrukiya

Supply

Demand