Feasible Solution For The Transportation Problem

The transportation problem, a special type of Linear Programming Problem, is used to find the optimal way in which a product produced at various plants or sources can be transported to various destinations (demand points). The objective of the problem is to find the amount of commodity to be transported from each source to each destination so that the destination requirements within the operating production capacity constraints are satisfied at minimum transportation cost. Used in quantitative analysis to solve business problems related to physical distribution of products, the transportation problem comes under ‘Operations Research’, a field which uses techniques such as mathematical modelling and statistics to analyse complex situations and help businesses make more effective decisions and build more productive systems. The transportation problem helps companies minimise costs thereby maximise profits. A special case of the transportation problem is the assignment problem where the objective is to assign a number of resources to an equal number of activities so as to minimize total cost or maximize total profit of allocation. The difference between the assignment problem and transportation problem is that in the assignment problem supply constraints per origin and demand constraints per destination is taken to be one. The assignment problem is used to allocate jobs to workers in a business and allocate responsibilities to teachers so that efficiency is maximised and time minimised.

There are different types of transportation problems but the simplest of them is the classical transportation problem which was first presented by Hitchcock (1941), along with a constructive solution and later independently, by Koopman (1947). Koopman began to spearhead research on the potentialities of linear programs on the potentialities of linear programs for the study of the problems in economics. His historic paper ‘Optimum Utilization of the Transportation Systems’ was based on his war time experience. Because of this and work done earlier by Hitchcock, the classical transportation problem is often referred as the Hitchcock-Koopman’s transportation problem. Kantorovich (1942), Gavurin (1949) and Dantzig (1951) also helped in the improvisation of the transportation problem.

As stated before the transportation problem is a type of linear programming problem and so can be solved through the direct application of the simplex method. However, because of the problem’s very special mathematical structure, it was recognized that the simplex method applied to the Transportation Problem can be made quite efficient in terms of how to calculate the necessary simplex-method information (variable to enter the basis, variable to leave the basis and optimality conditions). So to solve the problem we will use an adaptation of the simplex method known as the primal simplex transportation method (PSTM).

The transportation problem has a large number of linear programming applications. Various methods have been developed to solve the transportation problem and obtain an optimal solution, such as the modified distribution (MODI) method. In order to proceed with these methods, it is necessary to obtain the initial feasible solution. A number of methods are proposed to find the basic feasible solution, among which are Vogel’s approximation method (VAM), the row minima method, the column minima method, minimum cost method, the north-west corner method and Russell’s method. One can use a similar techniques used in solving the assignment problem to find the initial feasible solution for the transportation problem. In this paper we will find out the heuristic that generates the best initial feasible solution so that less iteration are required to solve the optimum solution and so less time is spent in solving the problem. We would be finding the method that provides a solution closest to the optimum solution.

Mathematical Formulation of the Transportation Problem

The problem –

A homogenous product available at a finite number of origins m is to be transported to a finite number of destinations n. the total amount available at each of these origins is known and the total quantity required at each of the destinations is known. The unit transportation cost from each origin to each destination is given. The question here is to determine the amount of the products to be transported from these origins to destinations so as to minimize the total transportation cost. So from the question the assumptions are –

The total supply of the product from origin i is ai, where i = 1, 2…m

The total quantity demanded for the product at destination j is bj, where j = 1, 2…n

The transportation cost of sending one unit of the product from origin i to destination j is cij, where i = 1, 2…m and j = 1, 2…n.

The amount of product transported from origin i to destination j is xij, where i = 1, 2…m and j = 1, 2…n.

The transportation problem graphically can be shown as a network flow problem with m source nodes and n sink nodes and m-n arcs –

We now proceed to the linear programming formulation of this problem –

The decision variable of the problem is the amount of goods needed to be transported from each origin to each destination, which is xij.

Let us consider the shipment from origin i to destination j. for any i and any j, the transportation cost per unit is cij and the size of shipment is xij. Since we assume the cost function to be linear, the total cost of this shipment is given by cij – xij. Summing over all i and j will give us the total transportation cost, which is the objective function –

Subject to –

Supply at each source must be used –

The demand at each destination must be met –

Non-negativity of values –

Because of the constraints that the supply cannot exceed ai and the demand of the destination cannot be less than bi there will be m + n functional constraints. As it is a linear program there will be m – n decision variables and as the products are physical there will be no non negative value and so there are m – n non-negativity constraints.

To better understand the transportation problem we will take a numerical example and so we will need to specify m and n, and replace the ai’s, the bj’s, and the cij’s with explicit numerical values. So let m = 2 and n = 3; a1 = 30, a2 = 50, b1 = 20, b2 = 15 and b3 = 45; and c11 = 2, c12 = 3, c13 = 5, c21 = 3, c22 = 4 and c23 = 2. After substituting the value into the formulation shown previously we get the following problem –

OBJECTIVE FUNCTION –

Minimize Z = 2×11 + 3×12 + 5×13 + 3×21 + 4×22 + 2×23

(i.e. total cost of shipping)

Subject to –

x11

+ x12

+ x22

= 30 (a1)

x21

+ x22

+ x23

= 50 (a2)

x11

+ x21

= 20 (b1)

x12

+ x22

= 35 (b2)

x22

+ x23

= 45 (b3)

So we can see that the transportation problem is a linear programming problem. The problem can also be written in the form of a table with m rows and n columns. Specifically, each source will have a corresponding row; and each sink, a corresponding column. The following cell (i, j) located at the intersection of the ith row and jth column showcases the parameters to be entered in each cell of the table –

Sink j

cij

xij

ai

Source i

bj

That is, each row is labelled with its corresponding source name at the left margin; each column is labelled with its corresponding sink name at the top margin; the supply from source i is listed at the right margin of the ith row; the demand at sink j is listed at the bottom margin of the jth column; the transportation cost cij is listed in a sub cell located at the upper-left corner of cell (i, j); and finally, the value of xij is to be entered at the lower-right corner of cell (i, j). So the data used above can be represented in a tableau as shown below –

Sources

Sinks

b1

b2

b3

a1

2

3

5

30

x11

x12

x13

a2

3

4

2

50

x21

x22

x23

20

15

45

One can see from the above problem that a1 + a2 = b1 + b2 + b3. If this occurs in a problem we say that the problem is a balanced transportation problem as . The aforementioned property is known as the feasibility property as only when the consition is satisfied can the transportation problem be solved. If then the problem is known as the unbalanced transportation problem. Suppose then a dummy demand is considered with requirement and the unit cost of transportation to this destination from m origins is taken to be zero. On the contrary, suppose then a dummy origin can be taken with quantity and unit cost of transportation from fictitious origin to all the n destinations will be taken as zero. This way an unbalanced problem can become balanced without affecting the solution.

MOVING TOWARDS A SOLUTION –

Even though there will be m + n constraints in a transportation problem yet all these are not independent in a balanced transportation problem. Only m + n – 1 constraints are independent. This can be easily seen from the case when m=2 and n =3. The five constraints in this case are –

x11 + x12 + x13 = a1

x21 + x22 + x23 = a2

x11 + x21 = b1

x21 + x22 = b2

x31 + x32 = b3

As the problem is balanced, a1 + a2 = b1 + b2 + b3

We can see that by adding the last three equations and subtracting the second equation from this sum will give us the first equation. Hence the first equation is redundant and does not need to be included in the system. Generalizing, we note that any one of the equations from the system can be eliminated and the transportation problem can be reduced to m + n – 1 independent equations in m-n variables.

A set of non-negative allocations xij ≥ 0 which satisfies the row and column restrictions is known as feasible solution. A feasible solution (not necessarily basic) is said to be optimal if it minimizes the total transportation cost. To solve a transportation problem first we need to find an initial basic feasible solution and then get an optimum solution. Since there are m + n – 1 independent equations, any basic feasible solution will contain m + n – 1 basic variables. If a basic feasible solution contains m + n – 1 positive components, we get a non-degenerate basic feasible solution but if less than m + n – 1 components are positive a degenerate solution is obtained. There are many methods to obtain the initial basic feasible solution and in this paper we will find the best method to find the initial basic feasible solution that is the one with the lowest transportation cost so that the number of iterations required to find the optimal solution is minimised.

Finding the best method to obtain an initial basic feasible solution –

Finding the best method to obtain an initial basic feasible solution –

The general transportation problem can be represented in a table form –

From To

D1

D2

Dn

Supply

S1

C11X11

C12X12

C1jX1j

a1

S2

C21X21

C22X22

C2jX2j

a2

Sm

Ci1Xi1

Ci2Xi2

CijXij

ai

Demand

b1

b2

bj

Requirements of an Initial Basic Feasible Solution –

Should have m + n – 1 variables – if not the transportation model will have a degenerate solution

The solution variables should not form a loop – in a transportation table, an ordered set of four or more cells is said to form a loop if –

Any two adjacent cells in the ordered set lie either in the same row or in the same column

Any three or more adjacent cells in the ordered set do not lie in the same row or the same column

Now we will discuss the different methods to find one the initial basic feasible solution for a balanced transportation problem and fin the best meth to obtain such a solution –

The north-west corner rule

The Matrix-minima method

The Row-minima method

The column-minima method

The Vogel’s approximation method

The assignment technique

Russel’s method

In order to understand each method we will use the following numerical example and find its initial basic feasible solution –

From To

D1

D2

D3

D4

Supply

S1

C11= 2

C12= 3

C13= 5

C14= 1

a1 = 100

S2

C21= 4

C22= 2

C23= 1

C24= 2

a2 = 70

S3

C31= 5

C32= 6

C33= 3

C34= 5

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Cost in rupees (Rs.)

The North-West corner Rule –

Step 1 – write the data in the form of a table

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11

C12= 3; X12

C13= 5; X13

C14= 1; X14

a1 = 100

S2

C21= 4; X21

C22= 2; X22

C23= 1; X23

C24= 2; X24

a2 = 70

S3

C31= 5; X31

C32= 6; X32

C33= 3; X33

C34= 5; X34

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Step 2 – select the upper-left hand cell which is called the North-West Corner and if the cell is X11 allocate min (a1, b1) to this cell. If X11 = a1 then row 1 (S1) is exhausted and b1 can be replaced by b1-a1 units. If X11 = b1 then column 1 (D1) is exhausted and a1 can be replaced by a1-b1 units. If X11 = b1 = a1 then row 1 (S1) and column 1 (D1) is exhausted and we move to X22. For example from the numerical example min (a1, b1) = b1 = 60

From To

D1

D2

D3

D4

Supply

S1

X11= 60

a1 = 10040

S2

a2 = 70

S3

a3 = 80

Demand

b1= 600

b2= 60

b3= 50

b4= 80

250

Step 3 – a new table of order (m-1) – n, m – (n-1) or (m-1) – (n-1) is formed. Again find out the north-west corner of the new table and repeat steps 1 and 2 until all quantities are exhausted. This is possible as it is a balanced transportation problem. We will continue with the example already in use –

From To

D1

D2

D3

D4

Supply

S1

X11= 60

X12= 40

a1 = 100400

S2

X22= 20

X23= 50

a2 = 70500

S3

X34= 80

a3 = 800

Demand

b1= 600

b2= 60200

b3= 500

b4= 800

250

Step 4 – find the initial basic feasible solution to the following transportation problem.

From To

D1

D2

D3

D4

Supply

S1

X11= 60; C11= 2

X12= 40; C12= 3

a1 = 100400

S2

X22= 20; C22= 2

X23= 50; C =1

a2 = 70500

S3

X34= 80; C =5

a3 = 800

Demand

b1= 600

b2= 60200

b3= 500

b4= 800

250

Initial basic feasible solution –

Z = 2-60 + 40-3 + 20-2 + 50-1 + 80-5 = 120 + 120 + 40 + 50 + 400 = Rs. 730

We can see from the North West corner rule the number of variables found are 5 and not equal to m + n -1 variables that is 6 variables and so the solution is a degenerate basic feasible solution. So to make this solution non degenerate we add a cell with value 0 at a position where the cell does not create a loop. So the extra cell will be at x13 as shown –

From To

D1

D2

D3

D4

Supply

S1

X11= 60; C11= 2

X12= 40; C12= 3

a1 = 100400

S2

X22= 20; C22= 2

X23= 50; C =1

a2 = 70500

S3

X13= 0; C31= 5

X34= 80; C =5

a3 = 800

Demand

b1= 600

b2= 60200

b3= 500

b4= 800

250

Minimum Cost Method –

Minimum cost / matrix minima method is a method for computing the basic feasible solution of a transportation problem where the basic variables are selected according to the unit cost

Step 1 – write the data in the form of a table

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11

C12= 3; X12

C13= 5; X13

C14= 1; X14

a1 = 100

S2

C21= 4; X21

C22= 2; X22

C23= 1; X23

C24= 2; X24

a2 = 70

S3

C31= 5; X31

C32= 6; X32

C33= 3; X33

C34= 5; X34

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Step 2 – locate the cell that has minimum cost element cij and allocate maximum quantity allowed in that cell by taking xij = min (ai, bj). If there are two or more cells with the minimum cost chose the cell corresponding to a lower numbered row. If the cells are in the same row chose the cell corresponding to a lower numbered column. For example in the data C14 = C23 = 1 and as C14 is at a lower numbered row we chose this cell to allocate maximum possible quantity

From To

D1

D2

D3

D4

Supply

S1

C11= 2

C12= 3

C13= 5

C14= 1

a1 = 100

S2

C21= 4

C22= 2

C23= 1

C24= 2

a2 = 70

S3

C31= 5

C32= 6

C33= 3

C34= 5

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Step 3 – If Xij = ai then row i is exhausted and bj can be replaced by bj-ai units. If Xij = bj then column j is exhausted and ai can be replaced by ai-bj units. This can be seen though the following example –

From To

D1

D2

D3

D4

Supply

S1

C14= 1; X14= 80

a1 = 10020

S2

a2 = 70

S3

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 800

250

We can see that x14 = min (100, 80) = 80 and so column b4 is exhausted and 20 units are left in a1.

Step 4 – repeat the first three steps with the reduced matrix till all quantities are allocated. And then find the initial basic feasible solution –

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11= 20

C14= 1; X14= 80

a1 = 100200

S2

C22= 2; X22= 20

C23= 1; X23= 50

a2 = 70 200

S3

C31= 5; X31= 40

C32= 6; X32= 40

a3 = 80400

Demand

b1= 60400

b2= 60400

b3= 500

b4= 800

250

So the initial basic feasible solution –

Z = 2-20 + 1-80 + 2-20 + 1-50 + 5-40 + 6-40 = 40 + 80 + 40 + 50 + 200 + 240 = Rs. 650

Unlike the North West corner method the minimum cost method has m + n – 1 variables and so the solution is non-degenerate.

Row Minima Method –

In the matrix minima method we started the solution with the cell with the lowest cost but in this method we will start with the lowest cost of the cell in each of the rows

Step 1 – write the data in the form of a table

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11

C12= 3; X12

C13= 5; X13

C14= 1; X14

a1 = 100

S2

C21= 4; X21

C22= 2; X22

C23= 1; X23

C24= 2; X24

a2 = 70

S3

C31= 5; X31

C32= 6; X32

C33= 3; X33

C34= 5; X34

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Step 2 – choose the cell with the minimum cost in the first row. Let the cell be x1j and so allocate min (a1, bj) units to this cell. If the min (ai , bj) = ai, then the availability of the ith row is exhausted and demand at the jth column remains as bj-ai and the ith row is deleted from the table and we move on to the next row. Again if min (ai, bj) = bj, then demand at the jth destination is fulfilled and the availability at the ith origin remains to be ai-bj and the jth column is deleted from the table and we will reconsider the row after this cancellation occurs. For example in the table given the minimum cost of the first row is c14 = 1 and so we distribute x14 = min (a1, b4) = 80 units. As 80 = b4 we delete the fourth column. Next minimum cost in the first row is c11 = 2 and so we allocate x11 = min (a1, b1) = 20 units and we the delete the first row.

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11= 20

C14= 1; X14= 80

a1 = 10020 0

S2

a2 = 70

S3

a3 = 80

Demand

b1= 6040

b2= 60

b3= 50

b4= 800

250

Step 3 – revise the table after the first row is exhausted and repeat steps 1 and 2 until the initial basic feasible solution is found. We will continue with the numerical example – in the second row the lowest cost is C23 = 1 and so X23 = min (a2, b3) = 50. Then we delete the third column and move to the next cell with the lowest cost in row 2. We continue doing the same method until a solution is obtained.

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11= 20

C14= 1; X14= 80

a1 = 100200

S2

C22= 2; X22= 20

C23= 1; X23= 50

a2 = 70 200

S3

C31= 5; X31= 40

C32= 6; X32= 40

a3 = 80 400

Demand

b1= 60400

b2= 60 400

b3= 500

b4= 800

250

So from above we can see that we obtain a non-degenerate basic feasible solution which is equal to –

Z = 2-20 + 1-80 + 2-20 + 1-50 + 5-40 + 6-40 = 40 + 80 + 40 + 50 + 200 + 240 = Rs. 650

We see that the solution from the row minima method is the same as the solution of the matrix minima method.

Column Minima method –

The column minima method is similar to the row minima method with the only difference being that the initial allocation method starts with the first column and the method progresses with increasing column number.

Step 1 – write the data in the form of a table

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11

C12= 3; X12

C13= 5; X13

C14= 1; X14

a1 = 100

S2

C21= 4; X21

C22= 2; X22

C23= 1; X23

C24= 2; X24

a2 = 70

S3

C31= 5; X31

C32= 6; X32

C33= 3; X33

C34= 5; X34

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Step 2 – choose the cell with the minimum cost in the first column. Let the cell be xi1 and so allocate min (ai, b1) units to this cell. If the min (ai , bj) = bj, then the availability of the jth column is exhausted and units remaining at the ith row remains as ai-bj and the jth column is deleted from the table and we move on to the next column. Again if min (ai, bj) = ai, then availability at the ith origin is fulfilled and the demand at the jth destination remains to be bj-ai and the ith row is deleted from the table and we will reconsider the column after this cancellation occurs. For example in the table given the minimum cost of the first column is c11 = 2 and so we distribute x11 = min (a1, b4) = 60 units. As 60 = b1 we delete the first column and move on to the second column.

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11= 60

a1 = 10040

S2

a2 = 70

S3

a3 = 80

Demand

b1= 600

b2= 60

b3= 50

b4= 80

250

Step 3 – revise the table after the first column is exhausted and repeat steps 1 and 2 until the initial basic feasible solution is found. We will continue with the numerical example – in the second column the lowest cost is C22 = 2 and so X22 = min (a2, b2) = 60. Then we delete the third column and move to the next column. We continue doing the same method until a solution is obtained.

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11

C12= 3; X12

C13= 5; X13

C14= 1; X14

a1 = 100

S2

C21= 4; X21

C22= 2; X22

C23= 1; X23

C24= 2; X24

a2 = 70

S3

C31= 5; X31

C32= 6; X32

C33= 3; X33

C34= 5; X34

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11= 60

C14= 1; X14= 40

a1 = 100400

S2

C22= 2; X22= 60

C23= 1; X23= 10

a2 = 70 100

S3

C33= 3; X33= 40

C34= 5; X34= 40

a3 = 80 400

Demand

b1= 600

b2= 600

b3= 50 400

b4= 80 400

250

So from above we can see that we obtain a non-degenerate basic feasible solution (m + n – 1 = 6) which is equal to –

Z = 2-60 + 1-40 + 2-60 + 1-10 + 3-40 + 5-40 = 120 + 40 + 120 + 10 + 120 + 200 = Rs. 610

We see that the solution from the column minima method is lower than the basic feasible solution of the row minima method and the matrix minima method.

Vogel’s Approximation method –

This method is an improved version of the minimum cost method.

Step 1 – write the data in the form of a table

From To

D1

D2

D3

D4

Supply

S1

C11= 2; X11

C12= 3; X12

C13= 5; X13

C14= 1; X14

a1 = 100

S2

C21= 4; X21

C22= 2; X22

C23= 1; X23

C24= 2; X24

a2 = 70

S3

C31= 5; X31

C32= 6; X32

C33= 3; X33

C34= 5; X34

a3 = 80

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Step 2 –

Find the lowest cost cij for each row and subtract this cost from the next lowest cost in that row cik. This difference of cik – cij is called the penalty of that row. Display the penalties of each row alongside the respective rows. Similarly find the penalties for each of the column and display these values alongside each column. We can see this clearly from the following example. The lowest cost for the first row is 1 while the second lowest cost cik is 2 and so the penalty for the first row is 2 – 1 = 1. We do the above method for each row and column and note down the penalty.

From To

D1

D2

D3

D4

Supply

Penalty

S1

C11= 2; X11

C12= 3; X12

C13= 5; X13

C14= 1; X14

a1 = 100

1

S2

C21= 4; X21

C22= 2; X22

C23= 1; X23

C24= 2; X24

a2 = 70

1

S3

C31= 5; X31

C32= 6; X32

C33= 3; X33

C34= 5; X34

a3 = 80

2

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Penalty

2

1

2

1

Step 3 –

We identify the row or column with the largest difference or the largest penalty among all rows and columns. If there is a tie we choose a cell arbitrarily. Let the largest difference correspond to the ith row and let cij be the smallest cost in that row. Then we allocate maximum quantity allowed in that cell by taking xij = min (ai, bj). If xij = ai then row i is exhausted and bj can be replaced by bj-ai units. If xij = bj then column j is exhausted and ai can be replaced by ai-bj units. This can be seen from the example where there are three points with the largest penalty at 2. We choose a random row or column and so we start with row S3. The lowest cost in this row is C33 and so maximum allocations are made at this cell. So x33 = min (80, 50) = 50 units.

From To

D1

D2

D3

D4

Supply

Penalty

S1

C11= 2; X11

C12= 3; X12

C13= 5; X13

C14= 1; X14

a1 = 100

1

S2

C21= 4; X21

C22= 2; X22

C23= 1; X23

C24= 2; X24

a2 = 70

1

S3

C31= 5; X31

C32= 6; X32

C33= 3; X33

C34= 5; X34

a3 = 80

2

Demand

b1= 60

b2= 60

b3= 50

b4= 80

250

Penalty

2

1

2

1

From To

D1

D2

D3

D4

Supply

Penalty

S1

a1 = 100

1

S2

a2 = 70

1

S3

C33= 3; X33= 50

a3 = 8030

2

Demand

b1= 60

b2= 60

b3= 500

b4= 80

250

Penalty

2

1

2

1

Step 4 – we then revise the table again after the allocations are made and repeat steps 1, 2 and 3 until all the constraints are exhausted. In the example after column D3 is exhausted a new table is formed with new penalties.

From To

D1

D2

D4

Supply

Penalty

S1

C11= 2; X11

C12= 3; X12

C14= 1; X14

a1 = 100

1

S2

C21= 4; X21

C22= 2; X22

C24= 2; X24

a2 = 70

0

S3

C31= 5; X31

C32= 6; X32

C3