Iterative computations of the Transportation algorithm

Iterative computations of the Transportation algorithm

After determining the starting BFS by any one of the three methods discussed earlier, we use the following algorithm to determine the optimum solution
Step1: Use the Simplex optimality condition to determine the entering variable as a current non-basic variable that can improve the solution. If the optimality condition is satisfied by all non-basic variables, the current solution is optimal and we stop. Otherwise we go to Step 2.

Step 2. Determine the leaving variable using the Simplex feasibility condition. Change the basis and go to Step 1.
The determination of the entering variable from among the current non-basic variables is done by the method of multipliers. In the method of multipliers, we associate with each row a dual variable (also called a multiplier) ui and with each column we associate a dual variable (also called a multiplier) vj.

Noting that each row corresponds to a constraint and each column corresponds to a constraint we recall from duality theory that
At any simplex iteration ,
Primal z-equation Left hand side Right hand side coefficient of = of corresponding - of corresponding variable xj dual constraint dual constraint

That is

" zij cij " ui v j cij

(Verify this by taking m=3 and n=4 !)

Since there are m+n-1 basic variables and since

zij cij 0
i j ij

for all such basic variables, we have m+n-1 equations u v c

to determine the m+n variables ui , v j We arbitrarily choose one of them and equate to zero and determine the remaining m+n-1 of them. Then we calculate zij cij ui v j cij for all non-basic variables xij. Then the entering variable is that one for which ui v j cij is most positive.

We do all this on the transportation tableau itself (and NOT separately) as the following example shows.

Destination

Starting Tableau
v1=3 3

Total Cost =48

S o u r c e

v2=7 v3=6 v4=3 Supply 7 6 4 5 u1=0 3 2 0 -1 2 4 3 2 2 u2= -3 1 1 -2 -2 4 3 8 5 u3= 2 3 1 2 1 6

Demand

Thus x32 enters the basis.

Determining the leaving variable

We first construct a closed loop that starts and ends at the entering variable cell. The loop consists of connected horizontal and vertical segments only (no diagonals are allowed). Except for the entering variable cell, each vertex (or corner) of the closed loop must correspond to a basic variable cell. The loop can cross itself and bypass one or more basic variables. The amount to be allocated to the entering variable cell is such that it satisfies all the demand and supply restrictions and must be non-negative. Usually

 is the minimum of the amounts allocated to the basic cells adjacent to the entering variable cell. Having decided about the amount to be allocated to the entering cell, for the supply and demand limits to remain satisfied, we must alternate between subtracting and adding the amount at the successive corners of the loop. In this process one of the basic variables will drop to zero. In simplex language, we say it leaves the basis. We repeat this process till optimality is reached. We illustrate with a numerical example.

Destination

Starting Tableau
v1=3 3

Total Cost =48

S o u r c e

v2=7 v3=6 v4=3 Supply 7 6 4 5 u1=0 3 2 0 -1 2 4 3 2 2 u2= -3 1 1 -2 -2 4 3 8 5 u3= 2 3 1 2 1 6

Demand

Thus x32 enters the basis.

Thus will become 1 and in the process both the basic variables x22 and x33 will become simultaneously zero. Since only one of them should leave the basis we make x22 leave the basis and keep x33 in the basis but with value zero. Thus the transportation cost reduces by 6 (as x23 increases by 1) and we say one iteration is over. The resulting new tableau is on the next slide.

Destination

Start of Iteration 2
v1=3 3

Total Cost =42

S o u r c e

v2=7 v3=12 v4=9 Supply 7 6 4 5 3 2 u1=0 5 6 2 4 3 2 2 u2= -9 2 -2 -8 -6 4 3 8 5 u3= -4 3 1 0 2 -5

Demand

Thus x13 enters the basis.

Thus will become 0 and x32 leaves the basis. Again the BFS is degenerate . But the transportation cost remains the same and we say the second iteration is over. The resulting new tableau is on the next slide.

Destination

Start of Iteration 3
v1=3 3 v2=7 v3=6 7 6

Total Cost =42

v4=9 Supply 4 5 5 2 2 4 5 3 2

S o u r c e

u1=0
u2= -3 u3= -4 2

-2 4
-5

0 3 8

2
-6

1
3

Demand

Thus x14 enters the basis.

Sometimes it might be difficult to find the closed loop from the entering cell by inspection. In that case the following method can be used to find the closed loop. We sketch the flowchart of the sequence in which the variables ui and vj were determined. For example in the above case the flowchart is on the next slide. Now to find the loop emanating from the non-basic cell (1,4), join u1 and v4 by a dotted line (as shown). Then the closed loop is:
(1,4) (1,2) (2,3) (3,4) (1,4)

v1=3

u1=0

v2=7 v3=6

u3= -4 u2= -9 (3,4)

v4= 9

Thus the closed loop is (1,4) (1,2) (2,3)

(1,4)

Thus will become 2 and in the process both the basic variables x12 and x32 will become simultaneously zero. Since only one of them should leave the basis we make x32 leave the basis and keep x12 in the basis but with value zero. Also x32 becomes 3. Thus the transportation cost reduces by 1*2+4*2=10 and we say third iteration is over. The resulting new tableau is on the next slide.

Destination

Start of Iteration 4
v1=3 3

Total Cost =32

v2=7 v3=6 v4=4 Supply 7 6 4 5 2 0 0 4 3

S o u r c e

u1=0
u2= -3 u3= -4 2

-2 4
-5

0 3 8

2
-6

-1 5
-5

2 3

3
3 2

Demand

Thus this is the optimal tableau. Alt Opt solutions exist.

Problem 4 Problem Set 5.3B

Page 193

In the unbalanced transportation problem given in the table below, if a unit from a source is not shipped out (to any of the destinations) a storage cost is incurred at the rate of $5, $4, and $3 per unit for sources 1,2, and 3 respectively. Additionally all the supply at source 2 must be shipped out completely to make room for a new product. Use VAM to determine the starting solution and determine the optimum solution.

1 1 2 3 1 3 2

2 2 4 3

3 1 5 3 20 40 30

30 20 20 To balance the problem, we introduce a dummy destination with transportation costs $5, $M, $3 respectively.
(Solution in the next slide)

Destination 3 Dummy Supply

Row Penalties

S 3 4 5 M o 2 30 10 u 2 3 3 3 r 3 10 0 20 c e Demand 30 20 10 20 0 20
Column Penalties

20

20

0 - - -

40 10 1 1 1 1 30 10 1 11 0

1 1
1 -

1 1
1 1

2 -

2
M-3

Total shipping cost = 240

Destination

Starting Tableau
v1=2 1

Total Cost =240

S o u r c e

v2=3 v3=3 v4=3 Supply 2 1 5 20 20 u1=-2 -1 -1 -4 3 4 5 M 40 u2= 1 30 10 -1 4-M 2 3 3 3 u3= 0 30 0 10 20 0

Demand

30

20

20

20

Thus this is the optimal tableau. Alt Opt solutions exist.

Problem 5 Problem Set 5.3 B Page 193

In a 33 transportation problem, let xij be the amount shipped from source i to destination j and cij be the corresponding transportation cost per unit. The amounts of supply at sources 1, 2, and 3 are 15, 30, and 85 units, respectively; and the demands at destinations 1, 2, and 3 are 15, 30, and 85 units, respectively. Assume that the northwest corner solution is optimal and that the associated values of the multipliers are

given by u1 = -2, u2 = 3, u3 = 5, v1 = 2, v2 = 5, and v3 = 10. (a) Find the associated optimal cost

(b) Determine the smallest values of cij associated with each non-basic variable that will maintain the optimality of the northwest corner solution.

v1=2 u1=-2 u2=3

v2=5
3 8
10

v3=10 8

Supply
15 30 85 25

0 5 7

15 5

25
5
30

13
15

u3=5

80
80

Demand

20 5

5 1475

Associated cost =

Problem 8.1-6 Page 393 Hillier and Lieberman (Operations Research 7th Edition)
The Onenote Co. produces a single product at three plants for four customers. The three plants will produce 60, 80, and 40 units respectively. The firm has made a commitment to sell 40 units to customer 1, 60 units to customer 2, and at least 20 units to customer 3. Both customers 3 and 4 also want to buy as many of the remaining units as possible. The net profit associated with shipping a unit from plant i to customer j is given by the following table.

Plant

Customer 1 2 1 $800 $700 2 $500 $200 3 $600 $400

3 $500 $100 $300

4 $200 $300 $500

Management wants to know how many units to sell to customers 3 and 4 and how many units to ship from each of the plant to each of the customers to maximize profits. Formulate the problem as a transportation model and solve it.

There are 3 sources, viz. Plants 1, 2 and 3. Right now there are 4 destinations, viz. customers 1, 2, 3, and 4. The supplies ai at the three sources are 60, 80, and 40 respectively. The demands at the three destinations are: b1 = 40, b2 = 60, b3 20, b4 = ?
Since in a transportation model, all constraints are equalities, we shall put b3 = 80 ( since customer 3 must get at least 20 units) and b4= 60 as the supply remaining after satisfying the three customers 1, 2, and 3 is 60 and since customers 3 and 4 will buy as much as possible.

But now the demand has become 240 and so we introduce a dummy source SF with supply 60. Since the customers 1, 2 must definitely get 40 and 60 units respectively, the dummy source cannot send any amount to these destinations. This is achieved by putting the cost from the dummy to these destinations as big M. Now the cost from dummy to the destinations 3 and 4 are put as zero. Also since these are actually profits, and since the transportation model is a minimization problem, to maximize the total profit we take cij as negative of the profits given. The starting tableau is given below.

1 1 -8 -5 -6 M 40 -7 -2 -4

2 60

Destination 3 4 Supply -5 -1 -3 20 0 0 -2 -3 40 -5 0 6020

60 0 80 40

1 - - -

S o u r c e

2 3

2 2 2 1 1 2 2 0 0 0 0

20 40 20

SF

M 60

60

60

Demand 40

80

2 1 -

3 -

2 2 2 3

2 2 2 5

Destination v1= -9 u1= 0 -8

v2= -7 v3= -5

v4= -7

-7
-1 60

-5
0

-2
-5

S o u r c e

u2= 4 -5

-2
40
-5

-1
0

-3
40

u3= 2

-6
-1

-4
-9

-3
20

-5
20

M
u4= 5

M
-4-M
-2-M

60

0
-2

This is the optimal tableau. Max Profit = - min z = - (-900) = $900.

Compre Question I Semester 2003-2004

The table below gives the times taken by 3 persons to complete 4 tasks( i.e. cell (i,j) is the time taken by person i to complete the task j).
Tasks
1
1 Person 2 3 4 6 5

2
1 4 2

3
2 3 6

4
6 5 4

If each task is to be allocated to a person (i.e. no splitting of the task between 2 or more persons is allowed) and if each person can be assigned at most two tasks, find the optimum allocation of the jobs to the persons to minimize the total time taken to complete all the 4 tasks. This can be formulated as a transportation model with three sources (persons) and 4 destinations (tasks). The demands at the three destinations are bj = 1 for j=1,2,3,4. But the availabilities are ai = 2 for i=1, 2, 3 as each person can be assigned a maximum of two tasks. Thus to balance the problem, we introduce a dummy task with demand 2 and time 0. Thus we get the starting tableau:

Destination

Starting Tableau
1 2 1 4 3 2 3 4 6 5 4 1
Dummy Supply

S o u r c e

1 2 3

4 6 5

0 0

2 1

1 1 3 3 - 2 22

2 2

1
1

0
1 0

1
1

0
2 0

Demand

1 1 1

1 1 1

1 4 -

1 2 2

0 -

Destination

Starting Tableau
v1=5 v2=2 v3=3 v4=4 v5=0 Supply S 4 1 2 6 0 2 o u1= -1 1 1 0 -3 -1 u 6 4 3 5 0 r u2= 0 2 2 -1 -2 0 -1 c 5 2 6 4 0 e 2 1 0 1 u3= 0 -3 Demand 1 1 1 1 2

Thus this is the optimal tableau. Optimal cost = 12