CHAPTER V
INTEGER PROGRAMMING:
TRANSPORTATION
ALGORITHM
Prepared by:
Engr. Romano A. Gabrillo
MEngg-MEM
Transportation Algorithm
A transportation algorithm involves m sources,
each of which requires ai (i=1,2,,m) units of a
homogeneous product, and n destinations, each
of which requires bj (j=1,2,,n) units of this
product.
The cost cij of transporting one unit of product
from the ith source to the jth destination is given
for each i and j.
The objective is to develop an integral
transportation schedule that meets all demands
from current inventory at a minimum total
shipping cost.
Standard Mathematical Model
It is assumed that total supply and total
demand are equal; that is:
m
a b
i 1
j 1
Let xij represent the (unknown) number of
units to be shipped from source i to
destination j. The standard mathematical
model for this problem is:
m
minimize : z cij xij
i 1 j 1
subject to : xij ai (i 1,2,...,m)
j 1
x
i 1
ij
b j ( j 1,2,...,n)
with : all xij nonnegative and integral.
The Transportation Algorithm
The transportation algorithm is the
simplex method specialized to the
format of the Transportation Tableau, it
involves:
1. Finding an initial, basic feasible solution
2. Testing the solution for optimality
3. Improving the solution when it is not optimal;
and
4. Repeating steps 2 and 3 until the optimal
solution is obtained.
The Transportation Tableau
Destination
1
c11
2
c12
3
c13
Supply
ui
x1n
D1
u1
x2n
D2
u2
X3n
D3
u3
Dm
um
x11
c21
x12
c22
x13
c23
2
x21
n
c1n
S
o
u
r
c
e
s
c31
x22
c32
x23
c33
x31
x32
cm2
c3n
x33
cm1
c2n
cm3
cmn
m
xm1
xm2
xm3
Xmn
Demand
b1
b2
b3
v1
v2
v3
Bn
vj
Vn
Example No. 1
A car rental company is faced with an
allocation problem resulting from rental
agreements that allow cars to be returned
to locations other than those at which they
were originally rented. At the present
time, there are two locations (sources)
with 15 and 13 surplus cars, respectively,
and four locations (destinations) requiring
9, 6, 7, and 9 cars, respectively.
Unit transportation costs (in dollars)
between the locations are as follows:
Dest.
1
Dest.
2
Dest.
3
Dest.
4
Source
1
45
17
21
30
Source
2
14
18
19
31
Set-up the initial transportation
tableau for the minimum-cost schedule.
7
Solution
Since the total demand (9 + 6 + 7 + 9 = 31)
exceeds the total supply (15 + 13 = 28), a dummy
source is created having the supply equal to the
3-unit shortage.
In reality, shipments from this fictitious source
are never made, so the associated shipping costs
are taken as zero.
Positive allocations from this source to a
destination represents cars that cannot be
delivered due to a shortage of supply, they are
shortages a destination will experience under an
optimal shipping schedule.
8
Transportation Tableau
The xij, ui, vj are not yet entered since
they are unknown for the moment.
Destination
1
45
2
17
3
21
15
14
18
19
31
2
Dummy
3
Demand
vj
ui
30
1
S
o
u
r
c
e
s
Supply
13
0
0
9
0
6
0
7
3
9
Tableau 1A
9
Northwest Corner Rule
Beginning with cell (1,1) in the Transportation
Tableau, allocate to x11, as many units as
possible without violating the constraints. This
will be the smaller of a1 and b1. Thereafter,
continue by moving one cell to the right, if some
supply remains, or if not, one cell down.
At each step, allocate as much as possible to the
cell (variable) under considerations without
violating the constraints. The sum of the ith row
allocations cannot exceed ai, the sum of the jth
column allocations cannot exceed bj, and no
allocation can be negative. The allocation may be
zero.
10
1. An Initial Basic Solution
Variables that are assigned values by either one
of these starting procedures (becomes the basic
variables in the initial solution. The unassigned
variables are non-basic and, therefore, zero.
The northwest corner rule is simpler than other
rules to apply. However, another method, the
Vogels Method (which will be discussed later),
which takes into account the unit shipping costs,
usually results in a closer-to-optimal starting
solution.
11
Example No. 2
Use the Northwest Corner Rule to obtain
an initial allocation to Example No. 1
Solution
1. Begin with x11, and assign it the minimum of
a1 = 15 and b1 = 9. Thus x11 = 9, leaving 6
surplus cars at the first source.
2. Move one cell to the right and assign x12 = 6.
These allocations together exhaust the
supply at the first source, move one cell
down.
12
Destination
1
45
17
1
S
o
u
r
c
e
s
21
9
14
Demand
18
19
31
13
ui
15
0
0
Supply
30
Dummy
3
3
9
vj
Consider x22, observe however, that the demand
at the second destination has been satisfied by
the x12 allocation.
Since we cannot deliver additional cars to it
without exceeding its demand, we must assign
x22 = 0 and move one cell to the right.
13
Degenerate Solution
Continuing in this manner, we obtain the
degenerate solution (fewer than 4 + 3 1 =
6 positive entries) below:
Destination
1
45
17
S
o
u
r
c
e
s
9
14
Demand
vj
Supply
15
19
31
0
0
7
0
6
0
3
9
ui
30
6
18
21
Dummy
3
13
Tableau 1B
14
DEGENERACY
The northwest corner rule always
generates an initial basic solution, but it
may fail to provide values n + m - 1
positive values, thus yielding a degenerate
solution.
Improving a degenerate solution may
result in replacing one basic variable
having a zero value by another such.
Although the two degenerate solutions are
effectively the same-only the designation
of the basic variables has changed, not
their values.
15
2. Test for Optimality
Assign one (any one) of the ui or vj in the
tableau the value zero and calculate the
remaining ui and vj so that for each basic
variable ui + vj = cij
Then, for each nonbasic variable,
calculate the quantity cij ui vj. If all
these latter quantities are nonnegative, the
current solution is optimal, otherwise, the
current solution is not optimal and needs
to be improved.
16
Example No. 3
Solve the transportation problem in
Example No. 1.
Solution:
To determine whether the initial
allocation found in Tableau 1B is optimal,
first calculate the terms ui and vj with
respect to the basic-variable cells of the
tableau. Arbitrarily choosing u2 = 0 (since
the second row contains more basic
variables than any other row or column.
17
This choice will simplify the computations giving:
(2, 2) cell: u2 + v2 = c22
(2, 3) cell: u2 + v3 = c23
(2, 4) cell: u2 + v4 = c24
(1, 2) cell: u1 + v2 = c12
(1, 1) cell: u1 + v1 = c11
(3, 4) cell: u3 + v4 = c34
0 + v2 = 18 or v2 = 18
0 + v3 = 19 or v3 = 19
0 + v4 = 31 or v4 = 31
u1 + 18 = 17 or u1 = -1
-1 + v1 = 45 or v1 = 46
u3 + 31 = 0 or u3 = -31
Place these values in Tableau 1C and calculate
the quantities cij ui vj for each nonbasicvariable cells in Tableau 1B
18
Tableau 1C
1
45
19
ui
15
-1
13
-31
31
0
0
Supply
30
6
18
21
9
14
Dummy
17
S
o
u
r
c
e
s
Destination
7
0
6
0
Demand
vj
46
18
19
31
(1, 3) cell: c13 u1 v3 = 21 (-1) 19 = 3
(1, 4) cell: c14 u1 v4 = 30 (-1) 31 = 0
(2, 1) cell: c21 u2 v1 = 14 0 46 = -32
19
(3, 1) cell: c31 u3 v1 = 0 (-31) 46 = -15
(3, 2) cell: c32 u3 v2 = 0 (-31) 18 = 13
(3, 3) cell: c33 u3 v3 = 0 (-31) 19 = 12
The results are recorded in Tableau 1C below
enclosed in parentheses: Destination
1
45
17
18
(0)
7
0
(-15)
ui
15
-1
13
31
0
0
(3)
19
(-32)
Supply
30
Dummy
21
9
14
S
o
ur
ce
s
6
0
(13)
(12)
Demand
vj
46
18
19
31
-31
20
3. Improving the Solution by
Looping
Since at least one of these (cij ui vj)-values is
negative, the current solution is not optimal.
Loop a sequence of cells in the
Transportation Tableau such that:
i.
Each pair of consecutive cells lie in either
the same row or the same column
ii. No three consecutive cells lie in the same
row or column
iii. The first and last cells of the sequence lie in
the same row or column
iv. No cell appears more than once in the
sequence.
21
Example No. 4
The sequences
{(1,2),(1,4),(2,4),(2,6),(4,6)(4,2)}
illustrated below is a loop.
1
22
Improving The Tableau
A better solution can be obtained by increasing
the allocation to the variable (cell) having the
largest negative entry, here (2,1) cell of Tableau
1C.
Do it by placing a boldface plus sign (signaling an
increase) in the (2,1) cell and identify a loop
containing, besides this cell, only basic-variable
cells.
23
Increase the allocation to (2,1) cell as
much as possible, simultaneously
adjusting the other cell allocations in the
loop so as not to violate the supply,
demand or nonnegativity constraints.
Any positive allocation to the (2, 1) cell
would force x22 to become negative. To
avoid this, but still make x21 basic, assign
x21 = 0 and remove x22 from the set of
basic variables.
24
Looping
Destination
45
17
21
14
6
18
(3)
19
(0)
(-32) +
0
Dummy
0
0
15
-1
13
-31
31
2
S
o
u
r
c
e
s
ui
30
Supply
7
0
6
0
(-15)
(13)
(12)
Demand
vj
46
18
19
31
25
Tableau 1D
1
Destination
45
17
21
Supply
30
15
9
14
6
18
19
31
13
2
S
o
ur
c
e
s
0
0
Dummy
ui
7
0
6
0
3
3
Demand
vj
26
Now, check whether Tableau 1D is
optimal. Calculate the new ui and vj with
respect to the new basic variables, and
then compute cij ui vj. Again we
arbitrarily choose u2 = 0.
The results is shown in Tableau 1E. Since
two entries are negative, the current
solution in not yet optimal, and a better
solution can be obtained by increasing the
allocation to the (1,4) cell.
27
Tableau 1E
Destination
45
17
21
14
6
18
(-29)
19
(-32)
0
0
Dummy
(32)
0
7
0
(45)
31
13
-31
6
0
(17)
15
31
2
S
o
u
r
c
e
s
ui
30
Supply
(12)
Demand
vj
14
-14
19
31
28
The loop whereby this is
accomplished in indicated in Tableau
1E. Any amount added to cell (1,4)
must be simultaneously subtracted
from cells (1,1) and (2,4) and then
added to cell (2,1), so as not to
violate the supply-demand
constraints.
The new nondegenerate solution is
shown in Tableau 1F
29
Tableau 1F
Destination
45
17
21
Supply
30
15
3
14
6
18
6
19
31
13
2
S
o
ur
ce
s
6
0
Dummy
ui
7
0
3
Demand
vj
30
After one further optimality test and
consequent change of basis, we
obtain Tableau 1H, which also shows
the results of the optimality test of
the new basic solution.
It is seen that each cij ui vj is
nonnegative; hence the new solution
is optimal.
31
Tableau 1H
Destination
45
1
17
21
(29)
14
S
o
ur
ce
s
3
19
6
31
9
0
Dummy
(3)
0
ui
15
13
-2
-30
30
6
18
Supply
4
0
(3)
0
(14)
(13)
(9)
Demand
vj
16
17
21
30
That is, x*12 = 6, x*13 = 3, x*14 = 6, x*21 =9, x*23 = 4, x*34 =
3, with all other variables nonbasic and, therefore, zero.
Furthermore:
z* = 6(17) + 3 (21) + 6 (30) + 9(14) + 4(19) + 3(0) = $547
32
Break Time
33
Vogels Method
For each row and each column having some
supply or some demand remaining, calculate its
difference, which is the nonnegative difference
between the two smallest shipping costs cij
associated with unassigned variables in that row
or column.
Consider the row having the largest difference; in
case of a tie, arbitrarily choose one. In this row
or column, locate that unassigned variable (cell)
having the smallest unit shipping cost and
allocate to it as many units as possible without
violating constraints. Recalculate the new
differences and repeat the above procedure until
all demands are satisfied.
34
Example No. 5
Use Vogels Method to determine an initial basic
solution to the transportation problem in Example
No. 1
Solution:
The two smallest costs in row 1 of
Transportation Tableau are 17 and 21; their
difference is 4. The two smallest costs in row 2
are 14 and 18; their difference is also 4. The two
smallest costs in row 3 both 0; so their difference
is 0. repeating this analysis on the columns, we
generate the differences shown in Tableau 2.
35
Tableau 2
Difference
45
17
21
Supply
30
14
S
o
ur
c
e
s
18
19
31
0
Dummy
15
13
3
Demand
ui
14
17
19
30
vj
Difference
Since, the largest of these difference is 30, occurs in column 4, we
locate the variable in this column having the unit shipping cost and
allocate to it as many units as possible. Thus, x34 = 3, exhausting the
supply of source 3 and eliminating row 3 from further consideration.
36
Tableau 2B
1
Difference
45
17
21
Supply
30
S
o
u
r
c
e
s
14
18
19
31
9
0
Dummy
15
4 4
13
4 4
Demand
ui
14
17
19
30
31
0 X
vj
Difference
The largest difference is in column 1, and the variable in this column
having the smallest cost is x21. We assign x21 = 9, thereby meeting the
demand of destination 2 and removing column 2 from further
calculations.
37
Final Optimal Solution
1
45
17
21
S
o
u
r
c
e
s
Supply
18
19
31
9
Dummy
3
4
0
15
4 4 4 9
13
4 4 1 12
0
3
Difference 14
17
19
30
31
Demand
ui
30
6
14
Difference
0 X X X
vj
The result is the allocation shown in Tableau 1H
38
Assignment No. 5
A plastics manufacturer has 1200
boxes of transparent wrap in stock at
one factory and another 1000 boxes
at its second factory. The
manufacturer has orders for this
product from three different retailers,
in quantities of 1000, 700, and 500
boxes, respectively.
39
The unit shipping costs (in cents per
box) from the factories to the
retailers are as follows:
Retailer 1
Retailer 2
Retailer 3
Factory 1
14
13
11
Factory 2
13
13
12
Determine a minimum-cost shipping
schedule for satisfying all demands
from current inventory using BOTH
the TRANSPORTATION ALGORITHM
and VOGELS METHOD.
40
End of Chapter 5
41
