Transportation Model

Formulations
The Transportation Model
A special class of LPPs that deals with
transporting(=shipping) a commodity from sources
(e.g. factories) to destinations (e.g. warehouses).
The objective is to determine the shipping
schedule that minimizes the total shipping cost
while satisfying supply and demand limits.
Assume that the shipping cost is proportional to
the number of units shipped on a given route.
Transportation Problem
DesMoines
(100 unit
capacity)
Fort Lauderdale
(300 units capacity)
Cleveland
(200 units Demand)
Evansville
(300 units
capacity)
Albuquerque
(300 units
Demand)
Boston
(200 units
Demand)
Consider:
m sources 1,2, , m and n destinations 1, 2, , n.
c
ij
the cost of shipping one unit from Source i to
Destination j
Assume that the availability at source i is a
i
(i=1, 2, ,
m) and the demand at the destination j is b
j
(j=1, 2, ,
n). We make an important assumption: the problem is
a balanced one. That is



n
j
j
m
i
i
b a
1 1
That is, total availability equals total demand.
a dummy source (if the total demand is more than
the total supply) or a dummy destination (if the
total supply is more than the total demand).
Let x
ij
be the amount of commodity to be shipped
from the source i to the destination j.
Thus the problem becomes the LPP

n
j
ij ij
m
i
x c z
1 1
Minimize
subject to
) ,..., 2 , 1 (
) ,..., 2 , 1 (
1
1
n j b x
m i a x
j
m
i
ij
i
n
j
ij

0
ij
x
Define problem
Set up transportation table (matrix)
Summarizes all data
Develop initial solution
Northwest corner/ Min Cost/ Vogels Methods
Find optimal solution
Transportation Simplex Method
Transportation Problem
Solution Steps
Advantages of the transportation
problem
Advantages of the transportation problem
and the minimum cost flow problem
Integer solutions
Very fast solution methods
Extremely common in modeling

Transportation Table
Destination
Source Supply
Demand
1
2
:
m
a
1
a
2
:
a
m
1 2 . . n
b
1
b
2
b
n
Quantity demanded or
required
Example 5.1-1
MG Auto has three plants in Los Angeles, Detroit,
and New Orleans, and two major distribution
centers in Denver and Miami. The capacities of the
three plants during the next quarter are 1000,
1500 and 1200 cars. The quarterly demands at the
two distribution centers are 2300 and 1400 cars.
The transportation cost per car from Los Angeles
to Denver and Miami are $80 and $215
respectively. The corresponding figures from
Detroit and New Orleans are 100, 108 and 102, 68
respectively.
mn decision variables xij and m+n constraints.
Since the sum of the first m constraints equals the
sum of the last n constraints (because the problem
is a balanced one), one of the constraints is
redundant and we can show that the other m+n-1
constraints are LI. Thus any BFS will have only
m+n-1 nonzero variables.
Though we can solve the above LPP by Simplex
method, we solve it by a special algorithm called
the transportation algorithm.
Example 5.1-2
MG Auto has three plants in Los Angeles, Detroit,
and New Orleans, and two major distribution
centers in Denver and Miami. The capacities of the
three plants during the next quarter are 1000,
1300 and 1200 cars. The quarterly demands at the
two distribution centers are 2300 and 1400 cars.
The transportation cost per car from Los Angeles
to Denver and Miami are $80 and $215
respectively. The corresponding figures from
Detroit and New Orleans are 100, 108 and 102, 68
respectively.
Formulate the transportation Model.
the total demand = 3700 > 3500 (Total supply)
dummy supply 3700-3500=200 units to
make the problem a balanced one.
If a destination receives u units from the
dummy source, it means that that destination
gets u units less than what it demanded. We
usually put the cost per unit of transporting
from a dummy source as zero (unless some
restrictions are there). Thus we get the
transportation tableau
80 215

1000

100

108

1300

102 68
1200
0

0

200

2300

1400
S
o
u
r
c
e
Destination
Denver Miami Supply
Demand
Los Angeles
Detroit
New Orleans
Dummy
We write inside the (i,j) cell the amount to be
shipped from source i to destination j. A blank
inside a cell indicates no amount was shipped.
Problem 5 Problem Set 5.1A Page 196
In the previous problem, penalty costs are levied at
the rate of $200 and $300 for each undelivered car
at Denver and Miami respectively. Additionally no
deliveries are made from the Los Angeles plant to
the Miami distribution center. Set up the
transportation model.
The above imply that the "cost" of transporting a car
from the dummy source to Denver and Miami are
respectively 200 and 300. The second condition
means we put a "high" transportation cost from Los
Angeles to Miami. We thus get the tableau
80 M

1000

100

108

1300

102 68
1200
200

300

200

2300

1400
S
o
u
r
c
e
Destination
Denver Miami Supply
Demand
Los Angeles
Detroit
New Orleans
Dummy
Note: M indicates a very "big" positive number. In
TORA it is denoted by "infinity".
Problem 8 Problem Set 5.1A Page 196
Three refineries with daily capacities of 6,5, and 8
million gallons, respectively, supply three
distribution areas with daily demands of 4,8, and 7
million gallons, respectively.Gasoline is distributed
to the three distribution areas through a network of
pipelines. The transportation cost is 10 cents per
1000 gallons per pipeline mile. The table below
gives the mileage between the refineries and the
distribution areas. Refinery 1 is not connected to
the distribution area 3.
Distribution Area
1 2 3
Refinery
1 120 180 -
2 300 100 80
3 200 250 120
Construct the associated transportation model.
(Solution in the next slide)
12 18 M

6

30

10 8

5

20 25 12
8
4

8 7
S
o
u
r
c
e
Destination
1 2 3 Supply
1
2
3
Demand
The problem is a balanced one. M indicates a
very "big" positive number.
Refinery
Distribution Area
The total cost will be 1000*
ij
i j
ij
x c

3
1
3
1
Problem 10 Problem Set 5.1A Page 197
In the previous problem, suppose that the daily
demand at area 3 drops to 4 million gallons.
Surplus production at refineries 1 and 2 is diverted
to other distribution areas by truck. The
transportation cost per 100 gallons is $1.50 from
refinery 1 and $2.20 from refinery 2. Refinery 3
can divert its surplus production to other chemical
processes within the plant.
Formulate the problem as a transportation model.
We introduce a dummy destination. Solution follows.
12 18 M

15
6

30

10 8

22
5

20 25 12 0
8
4

8 4 3
S
o
u
r
c
e
Destination
1 2 3 Dummy Supply

1

2

3
Demand
M indicates a very "big" positive number.
Refinery
Distribution Area
The total cost will be 1000*
ij
i j
ij
x c

3
1
3
1
Define problem
Set up transportation table (matrix)
Summarizes all data
Develop initial solution
Northwest corner/ Min Cost/ Vogels Methods
Find optimal solution
Transportation Simplex Method
Transportation Problem
Solution Steps
Determination of Starting
Basic Feasible Solution
Determination of the starting Solution
There are three methods to determine a starting
BFS.
As mentioned earlier, any BFS will have only m+n-
1 basic variables (which may assume non-zero
=positive values) and the remaining variables will
all be non-basic and so have zero values.
In any transportation tableau, we only indicate the
values of basic variables. The cells corresponding
to non-basic variables will be blank.
Degenerate BFS
If in a cell we find a zero mentioned, it means that
that cell corresponds to a basic variable which
assumes a value of zero. In simplex language, we
say that we have a degenerate BFS.
NORTH-WEST Corner Method
The method starts at the north-west corner cell
(i.e. cell (1,1)).
Step 1. We allocate as much as possible to the
selected cell and adjust the associated amounts of
supply and demand by subtracting the allocated
amount.
Step 2. Cross out the row (column) with zero
supply (zero demand) to indicate that no further
assignments can be made to that row(column).
If both a row and a column are simultaneously
satisfied then
if exactly one row or column is left uncrossed
make the obvious allocations and stop. Else cross
out one only (either the row or the column) and
leave a zero supply(demand) in the uncrossed out
row(column).
Step 3. If no further allocation is to be made,
stop. Else move to the cell to the right (if a
column has just been crossed out) or to the cell
below if a row has just been crossed out. Go to
Step 1.
Consider the transportation tableau:
3 7 6 4
5
2 4 3 2
2
4 3 8 5
3
3 3 2 2
Destination
1 2 3 4 Supply
Source
1
2
3
Demand
3
2
2
1
1
1
1
1
1
2
2
Total shipping cost = 48
2. LEAST COST Method
In this method we start assigning as much as possible
to the cell with the least unit transportation cost (ties
are broken arbitrarily) and the associated amounts of
supply and demand are adjusted by subtracting the
allocated amount.
Cross out the row (column) with zero supply
(zero demand) to indicate that no further
assignments can be made to that row(column).
If both a row and a column are simultaneously
satisfied then
if exactly one row or column is left uncrossed
make the obvious allocations and stop. Else cross
out one only (either the row or the column) and
leave a zero supply(demand) in the uncrossed out
row(column).
Next look for the uncrossed out cell with the
smallest unit cost and repeat the process until no
further allocations are to be made.
Consider the transportation tableau:
3 7 6 4
5
2 4 3 2
2
4 3 8 5
3
3 3 2 2
Destination
1 2 3 4 Supply
Source
1
2
3
Demand
Total shipping cost = 36
2
1
1
4
3
0
2 2 0
2
3. Vogels approximation method (VAM)
Step 1. For each row (column) remaining under
consideration, determine a penalty by subtracting the
smallest unit cost in the row (column) from the next
smallest unit cost in the same row(column). ( If two unit
costs tie for being the smallest unit cost, then the
penalty is 0).
Step2. Identify the row or column with the largest
penalty. Break ties arbitrarily. Allocate as much as
possible to the cell with the least unit cost in the selected
row or column.(Again break the ties arbitrarily.) Adjust
the supply and demand and cross out the satisfied row or
column.
If both a row and a column are simultaneously
satisfied then
if exactly one row or column is left uncrossed
make the obvious allocations and stop. Else cross
out one only (either the row or the column) and
leave a zero supply(demand) in the uncrossed out
row(column). (But omit that row or column for
calculating future penalties).
Step 3. If all allocations are made, stop. Else go to
step 1.

3 7 6 4
5
2 4 3 2
2
4 3 8 5
3
3 3 2 2
Destination
1 2 3 4 Supply Row Penalties
S
o
u
r
c
e
1
2
3
Demand
Total shipping cost = 32
Column
Penalties
1
0
1
1 1 3 2
2
0
1
-
1
1 4 - 1
3
0
3 0 0 2
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
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) u
i
and with each column we
associate a dual variable (also called a
multiplier) v
j
.
Note 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 x
j
dual constraint dual constraint
That is
ij j i ij ij
c v u c z " "
(Verify this by taking m=3 and n=4 !)
Since there are m+n-1 basic variables and
since
0
ij ij
c z
ij j i
c v u
for all such basic variables, we have m+n-1
equations
to determine the m+n variables
j i
v u ,
We arbitrarily choose one of them and equate
to zero and determine the remaining m+n-1 of
them. Then we calculate
ij j i ij ij
c v u c z
for all non-basic variables x
ij
. Then the entering
variable is that one for which
ij j i
c v u
is most positive.
We do all this on the transportation tableau itself
(and NOT separately) as the following example
shows.
3 7 6 4
5
2 4 3 2
2
4 3 8 5
3
3 3 2 2
Destination
Supply
S
o
u
r
c
e
Demand
3 2
1 1
1 2
Thus x
32
enters the basis.
u
1
=0
v
1
=3 v
2
=7
u
2
= -3
v
3
=6
u
3
= 2
v
4
=3
Total Cost =48
Starting
Tableau
0 -1
-2
-2
1 6
Determining the leaving variable
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.
3 7 6 4
5
2 4 3 2
2
4 3 8 5
3
3 3 2 2
Destination
Supply
S
o
u
r
c
e
Demand
3 2
1 1
1 2
Thus x
32
enters the basis.
u
1
=0
v
1
=3 v
2
=7
u
2
= -3
v
3
=6
u
3
= 2
v
4
=3
Total Cost =48
Starting Tableau
0 -1
-2
-2
1 6

Thus will become 1 and in the process both
the basic variables x
22
and x
33
will become
simultaneously zero. Since only one of them
should leave the basis we make x
22
leave the
basis and keep x
33
in the basis but with value
zero.
Thus the transportation cost reduces by 6 (as
x
23
increases by 1) and we say one iteration is
over. The resulting new tableau is on the next
slide.
3 7 6 4
5
2 4 3 2
2
4 3 8 5
3
3 3 2 2
Destination
Supply
S
o
u
r
c
e
Demand
3 2
2
0 2
Thus x
13
enters the basis.
u
1
=0
v
1
=3 v
2
=7
u
2
= -9
v
3
=12
u
3
= -4
v
4
=9
Total Cost =42
Start of Iteration 2
6
5
-8
-2
-5
-6
1

Thus will become 0 and x
32
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.
3 7 6 4
5
2 4 3 2
2
4 3 8 5
3
3 3 2 2
Destination
Supply
S
o
u
r
c
e
Demand
3 2
2

2
Thus x
14
enters the basis.
u
1
=0
v
1
=3 v
2
=7
u
2
= -3
v
3
=6
u
3
= -4
v
4
=9
Total Cost =42
Start of Iteration 3
-6
5
-2
4
-5
0
1
0
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 u
i
and v
j
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) (3,2) (3,4) (1,4)
u1=0
v1=3
v2=7
v3=6
u2= -9
u3= -
4
v4= 9
Thus the closed loop is
(1,4) (1,2) (2,3) (3,4)
(1,4)
Thus will become 2 and in the process both
the basic variables x
12
and x
32
will become
simultaneously zero.
Since only one of them should leave the basis
we make x
32
leave the basis and keep x
12
in
the basis but with value zero.
x
32
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.
3 7 6 4
5
2 4 3 2
2
4 3 8 5
3
3 3 2 2
Destination
Supply
S
o
u
r
c
e
Demand
3 0
2
2
Thus this is the optimal tableau. Alt Opt solutions exist.
u
1
=0
v
1
=3 v
2
=7
u
2
= -
3
v
3
=6
u
3
= -4
v
4
=4
Total Cost =32
Start of Iteration 4
-6 -5
-2
-1
-5
0
3
0
Problem 4 Problem Set 5.3B Page 217
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 2 3
1 1 2 1
2 3 4 5
3 2 3 3
To balance the problem, we introduce a
dummy destination with transportation costs
20
40
30
30 20 20
$5, $M, $3 respectively.
(Solution in the next slide)
1
1 2 1 5
20
3 4 5 M
40
2 3 3 3
30
30 20 20 20
Destination
1 2 3 Dummy Supply Row Penalties
S
o
u
r
c
e
1
2
3
Demand
Total shipping cost =
240
Column
Penaltie
s
0
1
1
1 1 2 2
10
0
-
1
1 1 -
M-3
20
30
10
20
0
10
10
-
1
1
1 1
- -
10
-
1
0
- 1
- -
1 2 1 5
20
3 4 5 M
40
2 3 3 3
30
30 20 20 20
Destination
Supply
S
o
u
r
c
e
Demand
3
0
10
20
0
Thus this is the optimal tableau. Alt Opt solutions exist.
u
1
=-2
v
1
=2 v
2
=3
u
2
= 1
v
3
=3
u
3
= 0
v
4
=3
Total Cost =240
Starting Tableau
-1
-4 -1
4-M
0
-1
10
20