Operations Research on Transportation Problem

Description
A key problem managers face is how to allocate scarce resources among various activities or projects. Linear programming, or LP, is a method of allocating resources in an optimal way.

Transportation Problem: A Special Case
for Linear Programming Problems
J. Reeb and S. Leavengood
EM 8779 • June 2002
$3.50
James E. Reeb, Extension
forest products manufacturing
specialist; and Scott
Leavengood, Extension forest
products, Washington County;
both of Oregon State
University.
PERFORMANCE EXCELLENCE
IN THE WOOD PRODUCTS INDUSTRY
A
key problem managers face is how to allocate scarce
resources among various activities or projects. Linear
programming, or LP, is a method of allocating resources
in an optimal way. It is one of the most widely used operations
research tools and has been a decision-
making aid in almost all manufacturing
industries and in financial and service
organizations.
In the term linear programming,
programming refers to mathematical pro-
gramming. In this context, it refers to a
planning process that allocates resources—
labor, materials, machines, capital—in the
best possible (optimal) way so that costs are
minimized or profits are maximized. In LP,
these resources are known as decision
variables. The criterion for selecting the
best values of the decision variables (e.g.,
to maximize profits or minimize costs) is
known as the objective function. Limita-
tions on resource availability form what is
known as a constraint set.
The word linear indicates that the crite-
rion for selecting the best values of the decision variables can be
described by a linear function of these variables; that is, a mathe-
matical function involving only the first powers of the variables
with no cross-products. For example, 23X
2
and 4X
16
are valid
decision variables, while 23X
2
2
, 4X
16
3
, and (4X
1
* 2X
1
) are not.
O
perations research (OR) is concerned
with scientifically deciding how to best
design and operate people–machine systems,
usually under conditions requiring the
allocation of scarce resources.
1
This publication, one of a series, is
offered to supervisors, lead people, middle
managers, and anyone who has responsibility
for operations planning in manufacturing
facilities or corporate planning over multiple
facilities. Practical examples are geared to
the wood products industry, although
managers and planners in other industries
can learn OR techniques through this series.
1
Operations Research Society of America
OPERATIONS RESEARCH
2
We can solve…
relatively large
transportation
problems by hand.
The entire problem can be expressed in terms of straight lines,
planes, or analogous geometrical figures.
In addition to the linear requirements, non-negativity restrictions
state that variables cannot assume negative values. That is, it’s not
possible to have negative resources. Without that condition, it
would be mathematically possible to “solve” the problem using
more resources than are available.
In earlier reports (see OSU Extension publications list, page 35),
we discussed using LP to find optimal solutions for maximization
and minimization problems. We also learned we can use sensitivity
analysis to tell us more about our solution than just the final opti-
mal solution. In this publication, we discuss a special case of LP,
the transportation problem.
The transportation problem
One of the most important and successful applications of quanti-
tative analysis to solving business problems has been in the
physical distribution of products, commonly referred to as trans-
portation problems. Basically, the purpose is to minimize the cost
of shipping goods from one location to another so that the needs of
each arrival area are met and every shipping location operates
within its capacity. However, quantitative analysis has been used
for many problems other than the physical distribution of goods.
For example, it has been used to efficiently place employees at
certain jobs within an organization. (This application sometimes is
called the assignment problem.)
We could set up a transportation problem and solve it using the
simplex method as with any LP problem (see Using the Simplex
Method to Solve Linear Programming Maximization Problems,
EM 8720, or another of the sources listed on page 35 for informa-
tion about the simplex method). However, the special structure of
the transportation problem allows us to solve it with a faster, more
economical algorithm than simplex. Problems of this type, contain-
ing thousands of variables and constraints, can be solved in only a
few seconds on a computer. In fact, we can solve a relatively large
transportation problem by hand.
There are some requirements for placing an LP problem into the
transportation problem category. We will discuss those require-
ments on page 6, after we formulate our problem and solve it using
computer software.
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
3
Computer solution
First, let’s formulate our problem and set it up as a “regular” LP
problem that we will solve using the LP software LINDO.*
The XYZ Sawmill Company’s CEO asks to see next month’s log
hauling schedule to his three sawmills. He wants to make sure he
keeps a steady, adequate flow of logs to his sawmills to capitalize
on the good lumber market. Secondary, but still important to him,
is to minimize the cost of transportation. The harvesting group
plans to move to three new logging sites. The distance from each
site to each sawmill is in Table 1. The average haul cost is $2 per
mile for both loaded and empty trucks. The logging supervisor
estimated the number of truckloads of logs coming off each harvest
site daily. The number of truckloads varies because terrain and
cutting patterns are unique for each site. Finally, the sawmill
managers have estimated the truckloads of logs their mills need
each day. All these estimates are in Table 1.
*Solver Suite: LINDO, LINGO, WHAT’S BEST. LINDO Systems Inc., Chicago.
382 pp. This product is mentioned as an illustration only. The Oregon State
University Extension Service neither endorses this product nor intends to
discriminate against products not mentioned.
The next step is to determine costs to haul from each site to each
mill (Table 2).
Table 1.—Supply and demand of sawlogs for the XYZ Sawmill Company.
Logging Distance to mill (miles) Maximum truckloads/day
site Mill A Mill B Mill C per logging site
1 8 15 50 20
2 10 17 20 30
3 30 26 15 45
Mill demand
(truckloads/day) 30 35 30
Table 2.—Round-trip transportation costs for XYZ Sawmill Company.
Logging
site Mill A Mill B Mill C
1 $ 32* $ 60 $ 200
2 40 68 80
3 120 104 60
*(8 miles x 2) x ($2 per mile) = $32
We can set the LP problem up as a cost minimization; that is,
we want to minimize hauling costs and meet each of the sawmills’
OPERATIONS RESEARCH
4
daily demand while not exceeding the maximum number of
truckloads from each site. We can formulate the problem as:
Let X
ij
= Haul costs from Site i to Mill j
i = 1, 2, 3 (logging sites) j = 1, 2, 3 (sawmills)
Objective function:
MIN 32X
11
+ 40X
21
+ 120X
31
+ 60X
12
+ 68X
22
+
104X
32
+ 200X
13
+ 80X
23
+ 60X
33
Subject to:
X
11
+ X
21
+ X
31
> 30 Truckloads to Mill A
X
12
+ X
22
+ X
32
> 35 Truckloads to Mill B
X
13
+ X
23
+ X
33
> 30 Truckloads to Mill C
X
11
+ X
12
+ X
13
< 20 Truckloads from Site 1
X
21
+ X
22
+ X
23
< 30 Truckloads from Site 2
X
31
+ X
32
+ X
33
< 45 Truckloads from Site 3
X
11
, X
21
, X
31
, X
12
, X
22
, X
32
, X
13
, X
23
, X
33
> 0
For the computer solution: in the edit box of LINDO, type in the
objective function, then “Subject to,” then list the constraints.
Note, the non-negativity con-
straint does not have to be typed in
because LINDO knows that all LP
problems have this constraint.
That’s it! The software will
solve the problem. It will add
slack, surplus, and artificial vari-
ables when necessary. (For an
explanation of slack, surplus, and
artificial variables, see an earlier
report in this series or consult
another of the references on
page 35.)
The LINDO (partial) output for the XYZ Sawmill Company
transportation problem:
LP OPTIMUM FOUND AT STEP 3
OBJECTIVE FUNCTION VALUE
1) 5760.000
Objective function:
MIN 32X
11
+ 40X
21
+ 120X
31
+ 60X
12
+ 68X
22
+
104X
32
+ 200X
13
+ 80X
23
+ 60X
33
Subject to:
X
11
+ X
21
+ X
31
> 30
X
12
+ X
22
+ X
32
> 35
X
13
+ X
23
+ X
33
> 30
X
11
+ X
12
+ X
13
< 20
X
21
+ X
22
+ X
23
< 30
X
31
+ X
32
+ X
33
< 45
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
5
VARIABLE VALUE REDUCED COST
X11 20.000000 0.000000
X21 10.000000 0.000000
X31 0.000000 44.000000
X12 0.000000 0.000000
X22 20.000000 0.000000
X32 15.000000 0.000000
X13 0.000000 184.000000
X23 0.000000 56.000000
X33 30.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 –76.000000
3) 0.000000 –104.000000
4) 0.000000 –60.000000
5) 0.000000 44.000000
6) 0.000000 36.000000
7) 0.000000 0.000000
NO. ITERATIONS = 3
Interpretation of the LINDO output
It took three iterations, or pivots, to find the optimal solution of
$5,760. (To solve this small LP by hand would have required
computations for at least three simplex tableaus.)
The $5,760 represents the
minimum daily haul costs for
the XYZ Sawmill Company
from the three logging sites to
the three sawmills. We can
use the values in the VALUE
column to assign values to
our variables and determine
the log truck haul schedules.
For variable X
11
, which is Site
1 to Mill A, the VALUE—
number of truckloads per
day—is 20 (Table 3). For
variable X
21
, which is Site 2
to Mill A, the VALUE is 10;
and from X
31
, Site 3 to Mill A, the VALUE is zero, so no loads will
be hauled from Site 3 to Mill A. For X
22
, Site 2 to Mill B, the daily
number of truckloads will be 20, and so on.
Table 3.—XYZ Sawmill Company log truck haul schedule.
Logging Truckloads Cost Total
site Mill per day per load cost
1 A 20 $ 32 $ 640
1 B 0 60 0
1 C 0 200 0
2 A 10 40 400
2 B 20 68 1,360
2 C 0 80 0
3 A 0 12 0
3 B 15 104 1,560
3 C 30 60 1,800
Total daily transportation costs for XYZ Sawmill Co.: $ 5,760
OPERATIONS RESEARCH
6
Transportation problem solution
Let’s solve this problem using the transportation problem
method, actually a simplified version of the simplex technique.
For this type of problem, all units available must be supplied.
From the above problem, we see this in fact occurs: the sawmills
use all 95 truckloads available. But isn’t this unreasonable? How
likely is it that supply always will equal demand? For practical
purposes, it doesn’t matter. As long as supply is adequate to meet
demand, we can ignore the surplus and treat the total supply as
equal to the total requirement.
Also, the number of constraints must equal the number of rows
and number of columns when we set up our transportation prob-
lem. We have met this requirement also: three rows plus three
columns equals six constraints, as shown above when we set up the
problem to enter into the computer.
Another requirement is that the number of routes should equal
the number of sources (sites), S, plus the number of destinations
(mills), D, minus one, or
R = S + D – 1
For problems in which S + D – 1 does not equal the number of
routes, either excess routes or degeneracy (more than one exiting
cell) can occur. We will talk about these problems on page 14.
Let’s set up our problem in a table format (Table 4). There are a
number of methods of
solving transportation
problems. We will look at a
common one, the northwest
corner method (Table 5a).
The northwest corner
method is easy to use and
requires only simple
calculations. For other
methods of solving transportation problems, refer to publications
listed on page 35.
As the method’s name implies, we start work in the northwest
corner, or the upper left cell, Site 1 Mill A. Make an allocation to
this cell that will use either all the demand for that row or all the
supply for that column, whichever is smaller. We see that Site 1’s
supply is smaller than Mill A’s demand, so place a 20 in cell Site 1
Mill A. This eliminates row Site 1 from further consideration because
we used all its supply. The next step is to move vertically to the next
Table 4.—Hauling costs, log truckloads available, and log truckloads demanded.
Logging Available
sites Mill A Mill B Mill C truckloads
Site 1 $ 32 $ 60 $ 200 20
Site 2 40 68 80 30
Site 3 120 104 60 45
Sawmill demand: 30 35 30
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
7
cell, Site 2 Mill A, and use
the same criteria as before.
Now the smaller value is
column Mill A (versus 30 in
row Site 2); there are only
10 truckloads demanded
because 20 have been
supplied by Site 1. So,
move 10 into this cell. Now
we can eliminate column
Mill A from further consid-
eration. Hint: when doing this with pencil and paper, it is convenient
to draw a line across rows and down columns when they are no longer
considered. This is especially useful when working on larger problems
with more sources and destinations.
Move to the next cell, Site 2 Mill B (Table 5b). Move the
smaller of the supply or demand values into this cell. Site 2 supply
is 20 (remember, we used 10 of the 30 in Site 2 Mill A); Mill B
demand is 35, so move 20 into this cell. We can eliminate row
Site 2 from further consideration since all its supply (30) is used.
Move to cell Site 3 Mill B. The smaller of the margin values is
15. (Mill B demand is 15 because 20 of 35 truckloads have been
supplied by Site 2.) Place
15 in this cell and elimi-
nate column Mill B from
further consideration since
its demand has been met.
Finally, move to cell Site 3
Mill C. Margin values are
tied at 30 (v
millC
= 30 and
u
site 3
= 30 because we
previously allocated 15 of
the 45 available to Site 3
Mill B), so place 30 in this
cell. We check to see
whether we’ve met the requirement that the number of routes
equals the number of sites plus the number of mills minus 1. In
fact, we have met the requirement (3 + 3 – 1 = 5) and we have five
routes.
Our initial basic feasible solution is:
32X
11
+ 40X
21
+ 68X
22
+ 104X
32
+ 60X
33
$32(20) + $40(10) + $68(20) + $104(15) + $60(30) = $5,760
Table 5b.—XYZ Sawmill Company transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
32 60 200
20
30
35
20
68 80
10
40
120 104 60
45
30 30 95
20
15 30
Table 5a.—XYZ Sawmill Company transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
32 60 200
20
30
35
20
68 80
10
40
120 104 60
45
30 30 95
OPERATIONS RESEARCH
8
However, this may not be our optimal solution. (Actually, we
know it is optimal because of our LINDO solution, above.) Let’s
test to see whether the current tableau represents the optimal
solution. We can do this because of duality theory (for a discussion
of duality, see Using Duality and Sensitivity Analysis to Interpret
Linear Programming Solutions, EM 8744, or another of the refer-
ences on page 35). We can introduce two quantities, u
i
and v
j
,
where u
i
is the dual variable associated with row i and v
j
is the dual
variable associated with column j. From duality theory:
X
ij
= u
i
+ v
j
(Eq. 1)
We can compute all u
i
and v
j
values from the initial tableau using
Eq. 1.
X
11
= u
1
+ v
2
= 32
X
21
= u
2
+ v
1
= 40
X
22
= u
2
+ v
2

= 68
X
32
= u
3
+ v
2
= 104
X
33
= u
3
+ v
3
= 60
Since there are M + N unknowns and M + N – 1 equations, we
can arbitrarily assign a value to one of the unknowns. A common
method is to choose the row with the largest number of allocations
(this is the number of cells where we have designated truckloads of
logs). Row Site 2 and row Site 3 both have two allocations. We
arbitrarily choose row Site 2 and set u
2
= 0. Using substitutions, we
calculate:
u
2
= 0
X
21
= u
2
+ v
1
= 40 0 + v
1
= 40 v
1

= 40
X
22
= u
2
+ v
2
= 68 0 + v
2
= 68 v
2
= 68
X
11
= u
1
+ v
1
= 32 u
1
+ 40 = 32 u
1
= –8
X
32
= u
3
+ v
2
= 104 u
3
+ 68 = 104 u
3
= 36
X
33
= u
3
+ v
3
= 60 36 + v
3
= 30 v
3
= –6
Arrange the u
i
and v
j
values around the table
margin (Table 5c).
Here’s how to recognize
whether this tableau repre-
sents the optimal solution:
for every nonbasic variable
(those cells without any
allocations), X
ij
– u
i

– v
j

> 0
(Eq. 2). If Eq. 2 is true in
every case, then the current
Table 5c.—XYZ Sawmill Company transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
32 60 200
20
30
35
20
68 80
10
40
120 104 60
45
30 30 95
20
15 30
–8
0
36
40 68 –6
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
9
tableau represents the optimal solution; if it is false in any one
case, there is a better solution.
For cell Site 1 Mill B: 60 – (–8) – 68 > 0 is true.
For cell Site 1 Mill C: 200 – (–8) – (–6) > 0 is true.
For cell Site 2 Mill C: 80 – 0 – (–6) > 0 is true.
For cell Site 3 Mill A: 120 – 36 – 40 > 0 is true.
We know this represents the optimal solution and that $5,760 is
our lowest cost to ship logs.
New XYZ Sawmill Company
transportation problem
Let’s examine another transportation problem. Suppose that the
transportation schedule to the sawmills looks like that shown in
Table 6a.
Demand equals supply:
45 truckloads. We will
solve this problem using
the northwest corner
method. Start in Site 1
Mill A (northwest corner).
Place a 5 in this cell
(smaller of the truckloads
demanded and those
available). Since all the
Mill A demand is satisfied,
eliminate that row from
further consideration
(Table 6b).
Table 6b.—New XYZ Sawmill Company log transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
90 100 130
20
15
20
140 100 100
100 80 80
10
5 20 45
5
Table 6a.—New XYZ Sawmill Company log transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
90 100 130
20
15
20
140 100 100
100 80 80
10
5 20 45
OPERATIONS RESEARCH
10
Move to Site 1 Mill B (Table 6c). Place 15 in this cell. Remem-
ber, only 15 truckloads are available from Site 1 since 5 were used
by Mill A, which is less than the 20 in Mill B demand margin. All
20 truckloads are used from Site 1, so we can eliminate this row
from further consideration.
Move to Site 2 Mill B (Table 6d). Place 5 (20 – 15 truckloads
supplied by Site 1) in this cell. This eliminates column Mill B from
further consideration.
Now we evaluate Site 2 Mill C. Place 10 in this cell and elimi-
nate row Site 2 from further consideration (Table 6d).
In cell Site 3 Mill C,
place 10 (Table 6d). At this
point, all constraints are
satisfied.
Hauling costs are: $90(5)
+ $100(15) + $140(5)
+ $100(10) + $80(10)
= $4,450
An analogy to the sim-
plex method may help
those familiar with that
method of solving LP
problems to better understand the transportation procedure.
Remember that when using simplex to solve LP minimization
problems, we seek a neighboring corner (referring to a corner in
dimensional space, not a corner in our transportation tables) to
evaluate, choosing the one that improves costs the most. We reach
this corner through a pivot procedure; that is, certain cells
exchange status. A current nonempty cell (in the basis) becomes
empty, or nonbasic, and an empty cell (currently not in the basis)
becomes basic (or part of the solution). The new nonempty cell is
Table 6c.—New XYZ Sawmill Company log transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
90 100 130
20
15
20
140 100 100
100 80 80
10
5 20 45
5 15
Table 6d.—New XYZ Sawmill Company log transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
90 100
130
20
15
20
140 100 100
100 80 80
10
5 20 45
5 15
5 10
10
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
11
called the entering cell, and the cell it replaces is called the exiting
cell (just as in simplex). This will result in a less expensive ship-
ping schedule. As with simplex, we continue this procedure until
we reach a point where we can no longer improve; that is, we reach
the most attractive corner and therefore the optimal solution.
Let’s check to see whether the solution of $4,450 is optimal. We
can check as we did with the preceding problem. Since there are
M + N unknowns and M + N – 1 equations, we can arbitrarily
assign a value to one of the unknowns and solve for the others. As
above, choose the row that has the largest number of allocations
(this is the number of cells where we have designated truckloads of
logs). Site 1 and Site 2 have two allocations each, whereas Site 3
has only one allocation. We arbitrarily choose row Site 1 and set u
1
= 0.
Using substitutions, we calculate:
u
1
+ v
1
= 90 0 + v
1
= 90 v
1
= 90
u
1
+ v
2
= 100 0 + v
2
= 100 v
2
= 100
u
2
+ v
2

= 140 u
2

+ 100 = 140 u
2
= 40
u
2
+ v
3
= 100 40 + v
3
= 100 v
3
= 60
u
3
+ v
3
= 80 u
3
+ 60 = 80 u
3
= 20
Arrange the u
i
and v
j
around the table as shown in Table 6e.
Check for the optimal solution using Eq. 2 (X
ij
– u
i
– v
j
> 0) for
each nonbasic cell. Remember, the nonbasic cells are those without
an allocation. If the equation is true for each cell, then we have the
optimal solution, and our lowest shipping cost is $4,450.
For cell Site 1 Mill C: 130 – 0 – 60 > 0 is true.
For cell Site 2 Mill A: 100 – 40 – 90 > 0 is false.
The second statement is false, so we know we can find a less
costly shipping schedule. In order to continue, we need to deter-
mine the values in the
remaining nonbasic cells.
We are interested when
the equation is false (when
the answer is negative).
Place –30 value in cell
Site 2 Mill A
(Table 6f, page 12).
Table 6e.—New XYZ Sawmill Company log transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
90 100 130
20
15
20
140 100 100
100 80 80
10
5 20 45
5 15 0
20
40 5 10
10
90 100 60
OPERATIONS RESEARCH
12
Table 6f.—New XYZ Sawmill Company log transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
90 100 130
20
15
20
140 100 100
100 80 80
10
5 20 45
5 15 0
20
40 5 10
10
90 100 60
–30
–10 –40
For cell Site 3 Mill A: 100 – 20 – 90 > 0 is false. Place –10 in cell
Site 3 Mill A (Table 6f).
For cell Site 3 Mill B: 80 – 20 – 100 > 0 is false. Place –40 in cell
Site 3 Mill B (Table 6f).
We will use what’s
known as the closed loop
path for further iterations.
Some rules will help us
determine the closed loop
path. One rule is there can
be only one increasing and
one decreasing cell in any
row or column; and, except
for the entering cell, all
changes must involve
nonempty (basic) cells.
For simplex (minimiza-
tion problems), we choose the largest negative number as the new
entering variable, and we do the same in this case. Site 3 Mill B
has the largest negative value; therefore, we can reduce costs the
most by allocating truckloads to this cell. We want to increase the
value as much as possible, so place a “+” in cell Site 3 Mill B
(Table 6g).
Since we want to
increase this as much as
possible, move to the next
basic cell in the current
solution, Site 2 Mill B. We
need to keep everything in
equilibrium, so place “–” in
this cell (take 5 truckloads
from here and allocate to
Site 3 Mill B). Remember,
we want to make a closed
loop and keep supplies and
demands balanced. Next,
turn and go to the next basic cell in row Site 2 (Mill C) and place a
“+” in this cell to indicate it must be increased by 5 to maintain
equality in this row. Next, go to Site 3 Mill C and place a “–” in
this cell. This completes a circuit. We have shifted the solution, and
if we have completed the circuit correctly, equalities in our rows
and columns have been maintained.
Table 6g.—New XYZ Sawmill Company log transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
90 100 130
20
15
20
140 100 100
100 80 80
10
5 20 45
5 15 0
20
40 5 – 10 +
10 –
90 100 60
–30
–10 –40
+
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
13
The following summarizes the changes.
Variable Cell in closed loop Before Change Now
X
32
Site 3 Mill B Empty +5 5
X
22
Site 2 Mill B 5 –5 Empty
X
23
Site 2 Mill C 10 +5 15
X
33
Site 3 Mill C 10 –5 5
This procedure must always make a complete circuit, starting
and ending with the new entering variable. For any entering cell,
the closed loop path is unique. It must step only into basic cells (all
nonbasic cells are overstepped and ignored). At each cell where a
“+” or “–” is entered, a junction is made; that is, turning either
from vertical to horizontal or from horizontal to vertical. Some-
times this requires stepping over basic as well as nonbasic cells. If
we reach a cell from which we cannot turn (because all other cells
in its column or row are empty), then we must backtrack to the last
turning point and go the other way or move forward to another
nonempty cell in the same row or column.
Quantities will shift only in cells at the corners of the closed
loop path. The amount shifted will equal the smallest quantity in
the losing (–) cells. This is because each affected cell will change
by plus or minus this value. If we used something greater than the
smallest quantity, we would supply or demand quantities that are
not available.
We now have the following solution.
$90X
11
+ $100X
12
+ $100X
23
+ $80X
32
+ $80X
33
$90(5) + $100(15) + $100(15) + $80(5) + $80(5) = $4,250
We see that we did improve our costs: by $200, from $4,450 to
$4,250. This new schedule is illustrated in Table 6h.
Calculate new margin
values; that is, new u
i
and
v
j
values. Look for the
row with the most alloca-
tions. Sites 1 and 3 both
have two allocations; row
Site 2 has only one. We
arbitrarily choose row
Site 1 and set u
1
= 0
(Table 6h). Determine the
other margin values
through substitution.
Table 6h.—New XYZ Sawmill Company log transportation problem.
Mill A Mill B Mill C Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
90 100 130
20
15
20
140 100 100
100 80 80
10
5 20 45
5 15 0
–20
0 15
5
90 100 100
5
OPERATIONS RESEARCH
14
u
1
= 0
u
1
+ v
1
= 90 0 + v
1
= 90 v
1
= 90
u
1
+ v
2
= 100 0 + v
2
= 100 v
2
= 100
u
3
+ v
2
= 80 u
3
+ 100 = 80 u
3
= –20
u
3
+ v
3
= 80 –20 + v
3
= 80 v
3
= 100
u
2
+ v
3
= 100 u
2
+ 100 = 100 u
2
= 0
We can now check to see whether our solution is optimal. Using
Eq. 2, X
ij
– u
i
– v
j
> 0, determine the values for the nonbasic cells
(empty cells without any allocations):
For cell Site 1 Mill C: 130 – 0 – 100 > 0 is true.
For cell Site 2 Mill A: 100 – 0 – 90 > 0 is true.
For cell Site 2 Mill B: 140 – 0 – 100 > 0 is true.
For cell Site 3 Mill A: 100 – (–20) – 90 > 0 is true.
Because all statements are true, we know that $4,250 is the
optimal solution and the lowest cost for our shipping schedule.
Integer solutions
When solving LP problems using simplex, an integer (whole
number) solution is not guaranteed. We could end up with an
optimal solution that makes fractions of things that really don’t
make much sense as fractions, such as producing 15.66 pickup
trucks. But in transportation problems, if all the numbers represent-
ing the sources and the destinations are integers, then the answer
also will be an integer. Because of this, some problems that have
nothing to do with transporting goods are designed to be solved
using the transportation method to ensure an integer answer.
Degeneracy in transportation problems
On page 6, we said if Sources + Destinations – 1 does not equal the
number of routes, then either excess routes or degeneracy can
occur when solving LP problems using the transportation method.
When nonempty cells are fewer than necessary, it is impossible to
obtain a unique set of row and column margin numbers (u
i
and v
j
)
and, in some cases, to form closed-loop circuits. The program
never converges on an optimal solution but continues to cycle
through the same solutions over and over again.
Consider the following problem. XYZ Sawmill Company
purchased another sawmill and formulated a new logging schedule
(Table 7a). We will use the northwest corner rule to get the initial
solution to the tableau.
Some problems...
that have nothing to do
with transporting
goods are designed to
be solved using the
transportation method
to ensure an integer
answer.
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
15
Again, we put
the cost to ship a
truckload of logs
from a site to a
mill in the upper
right corner.
Looking at supply
and demand, we
place the smallest
value, 10, in the
northwest corner
cell. Row Site 1
now can be eliminated from further consideration.
Move down to Site 2 Mill A and again assign the smallest value.
This is 5 (from the demand margin, because 10 have been assigned
already), and we place that value in cell Site 2 Mill A (Table 7b).
Column Mill A can now be eliminated from further consideration.
Move to Site 2 Mill B and place the smallest of the margin
values, 10, in that
cell (Table 7b).
Mill B column can
now be eliminated
from further
consideration.
Continuing to
work in Table 7b,
move to Site 2
Mill C cell and
assign the smallest
margin value to
this cell. In this
case, we will assign only 15 of the 20 to keep the equality of the
row supply. Move to Site 3 Mill C and assign the remaining 5 from
the demand margin to this cell. Finally, move to the Site 3 Mill D
cell and assign 15 from the demand margin to this cell. If we have
assigned all our values correctly, then all row and column equali-
ties will have been preserved. In other words, all constraints will
have been satisfied.
Our initial feasible solution is:
Table 7a.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7 3
10
21
18 15
11 14 15 22
15 20 15
10
21
10
6
30
20
60
Table 7b.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7
3
10
21
18 15
11 14 15 22
15 20 15
10
21
10
6
30
20
60
5 15 10
5 15
Daily shipping costs = $19(10) + $15(5) + $21(10) + $18(15) + $15(5) + $22(15) = $1,150
OPERATIONS RESEARCH
16
We check to see whether this is an optimal solution. Start by
calculating u
i
and v
j
values. Row Site 2 has the most allocations, so
assign u
2
a value of zero and solve for the remainder of the margin
values:
u
2
= 0
u
2
+ v
1
= 15 0 + v
1
= 15 v
1
= 15
u
1
+ v
1
= 19 u
1
+ 15 = 19 u
1
= 4
u
2
+ v
2
= 21 0 + v
2
= 21 v
2
= 21
u
2
+ v
3
= 18 0 + v
3
= 18 v
3
= 18
u
3
+ v
3
= 15 u
3
+ 18 = 15 u
3
= –3
u
3
+ v
4
= 22 –3 + v
4
= 22 v
4
= 25
Place the margin values into Table 7c. Use Eq. 2 to determine
whether this is the optimal solution.
For Cell Site 1 Mill B: 7 – 4 – 21 > 0 is false. Therefore, we know
this is not the optimal solution. Place –18 in Site 1 Mill B
(Table 7c).
For Cell Site 1 Mill C: 3 – 4 – 18 > 0 is false.
Place –19 in Site 1 Mill C (Table 7c).
For Cell Site 1 Mill D: 21 – 4 – 25 > 0 is false.
Place –8 in Site 1 Mill D (Table 7c).
For Cell Site 2 Mill D: 6 – 0 – 25 > 0 is false.
Place –19 in Site 2 Mill D (Table 7c).
For Cell Site 3 Mill A: 11 – (–3) – 15 > 0 is false.
Place –1 in Site 3 Mill A (Table 7c).
For Cell Site 3 Mill B: 14 – (–3) – 21 > 0 is false.
Place –4 in Site 3 Mill B (Table 7c).
Remember, just
as for the simplex
LP method, we
choose the largest
negative number as
the new entering
variable. Site 1 Mill
C and Site 2 Mill D
tie for the largest
negative value. We
can reduce costs
the most by allocat-
ing truckloads to
one of these cells.
Table 7c.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7 3
–4
21 18 15
11 14 15 22
–1
15
15
10
21
10
6
30
20
60
5
15 10
5
–19
21 15
15
–3
20 10
–8
–19
–18
4
0
18 25
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
17
As with most LP
ties, we can
choose either one.
We arbitrarily
choose Site 1 Mill
C. We want to
increase the value
as much as pos-
sible, so put a “+”
in Site 1 Mill C
(Table 7d). To
keep the supply
equality for Site 1,
place a “–” in
Site 1 Mill A. Continue along the closed loop circuit, making sure
not to violate supply and demand equalities. Place a “+” in
Site 2 Mill A and, finally, a “–” in Site 2 Mill C (Table 7d).
Now we can change the trucking schedule. Remember that
changes occur only at the corners. Summarizing the changes:
Table 7e shows the trucking schedule change. Site 1 Mill A
becomes empty and therefore is the exiting cell. Next, we calculate
our new trucking costs: $3(10) + $15(15) + $21(10) + $18(5) +
$15(5) + $22(15) = $960.
We improved
our shipping costs
by $190, from
$1,150 to $960.
But, is this the
optimal solution?
We can check by
calculating the u
i
and v
j
values and
then using Eq. 2.
Cell in closed loop Before Change Now
Site 1 Mill C Empty +10 10
Site 1 Mill A 10 –10 Empty
Site 2 Mill A 5 +10 15
Site 2 Mill C 15 –10 5
Table 7d.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7
3
–4
21 18 15
11 14 15
22
–1
15
15
10 –
21
10
6
30
20
60
5+ 15– 10
5
–19
21 15
15
–3
20 10
–8 –19 –18
4
0
18 25
+
Table 7e.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7
3
10
21
18 15
11 14 15
22
15 20 15
10
21
10
6
30
20
60
15 5 10
5 15
OPERATIONS RESEARCH
18
Site 2 row has the most allocations, so set u
2
= 0 and solve for
the other values:
u
2
= 0
u
2
+ v
1
= 15 0 + v
1
= 15 v
1
= 15
u
2
+ v
2
= 21 0 + v
2
= 21 v
2
= 21
u
2
+ v
3
= 18 0 + v
3
= 18 v
3
= 18
u
1
+ v
3
= 3 u
1
+ 18 = 3 u
1
= –15
u
3
+ v
3
= 15 u
3
+ 18 = 15 u
3
= –3
u
3
+ v
4
= 22 –3 + v
4
= 22 v
4
= 25
Place these values
in Table 7f and use
Eq. 2 to check for
an optimal solu-
tion. For Eq. 2, use
the nonbasic cells
(those with no
allocation). If all
statements are true,
we have the opti-
mal solution; that
is, the lowest cost
trucking schedule.
For cell Site 1 Mill A: 19 – (–15) – 15 > 0 is true.
For cell Site 1 Mill B: 7 – (–15) – 21 > 0 is true.
For cell Site 1 Mill D: 21 – (–15) – 25 > 0 is true.
For cell Site 2 Mill D: 6 – 0 – 25 > 0 is false. We know this is not
the optimal solution. Place –19 in Site 2 Mill D (Table 7f).
For cell Site 3 Mill A: 11 – (–3) – 15 > 0 is false. Place –1 in Site 3
Mill A (Table 7f).
For cell Site 3 Mill B: 14 – (–3) – 21 > 0 is false. Place –4 in Site 3
Mill B (Table 7f).
Continuing to work with Table 7f, we see that Site 2 Mill D is
our new entering variable (that with the largest negative value and
therefore the one that can reduce costs the most). Place a “+” in
this cell. Complete the closed loop by placing a “–” in Site 2
Mill C, a “+” in Site 3 Mill C, and a “–” in Site 3 Mill D.
Table 7f.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7 3
–4
21 18 15
11 14 15 22
–1
15
15 –
10
21
10
6
30
20
60
15 5 – 10
5 +
21
15
15
–3
20 10
–19
–15
0
18 25
+
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
19
Summarizing the changes:
Cell in closed loop Before Change Now
Site 2 Mill D Empty +5 5
Site 2 Mill C 5 –5 Empty
Site 3 Mill C 5 +5 10
Site 3 Mill D 15 –5 10
Table 7g.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7
3
–23
21 18 15
11 14 15
22
–20
15
10 –
10
21
10
6
30
20
60
15 10 –
10
21 15
15
16
20 10
–1
+
–18
4
0
–1 6
5 +
The new schedule
is in Table 7g. The
new solution is:
$3(10) + $15(15)
+ $21(10) + $6(5)
+ $15(10) +
$22(10) = $865.
We improved our
shipping costs by
$95, from $960 to
$865. Check to
see whether this is
the optimal solu-
tion. Row Site 2
has the most allocations, so set u
2
= 0. Solve for the other values
and place into Table 7g.
u
2
= 0
u
2
+ v
1
= 15 0 + v
1
= 15 v
1
= 15
u
2
+ v
2
= 21 0 + v
2
= 21 v
2
= 21
u
2
+ v
4
= 6 0 + v
4
= 6 v
4
= 6
u
3
+ v
4
= 22 u
3
+ 6 = 22 u
3
= 16
u
3
+ v
3
= 15 16 + v
3
= 15 v
3
= –1
u
1
+ v
3
= 3 u
1
+ (–1) = 3 u
1
= 4
Use Eq. 2 to check whether this is the optimal solution:
For cell Site 1 Mill A: 19 – 4 – 15 > 0 is true.
For cell Site 1 Mill B: 7 – 4 – 21 > 0 is false. Place –18 in Site 1
Mill B (Table 7g).
For cell Site 1 Mill D: 21 – 4 – 6 > 0 is true.
For cell Site 2 Mill C: 18 – 0 – (–1) > 0 is true.
For cell Site 3 Mill A: 11 – 16 – 15 > 0 is false. Place –20 in Site 3
Mill A (Table 7g).
For cell Site 3 Mill B: 14 – 16 – 21 > 0 is false. Place –23 in Site 3
Mill B (Table 7g).
OPERATIONS RESEARCH
20
Choose the largest negative value (this will reduce costs the
most) as the new entering variable. Place a “+” in Site 3 Mill B.
Move to Site 2 Mill B, place a “–” in it, then place a “+” in Site 2
Mill D (we have to jump over the nonbasic cell), and then close the
loop by placing a “–” in Site 3 Mill D (we ignore Site 2 Mill C and
Site 3 Mill C).
Summarizing the changes in the trucking schedule:
Cell in closed loop Before Change Now
Site 3 Mill B Empty +10 10
Site 2 Mill B 10 –10 Empty
Site 2 Mill D 5 +10 15
Site 3 Mill D 10 –10 Empty
Remember that the empty cell becomes the exiting cell. For this
iteration, though, we have a tie. Both Site 2 Mill B and Site 3
Mill D cells have become empty. Both cells lose all their allocation
and are reduced to zero. However, now we have two routes fewer
than the number of rows and columns. When there are fewer than
S + D – 1 routes, sometimes it is not possible to form closed loops,
and we cannot solve for a unique set of row and column margin
numbers (u
i
and v
j
). Too few routes also can lead to degeneracy. To
avoid degeneracy, we need to treat one of the exiting cells as a
nonempty or basic cell. Again, because ties almost always can be
arbitrarily broken in LP problems, we can choose either one as the
exiting cell and treat the other as a basic cell. We will choose Site 2
Mill B as the exiting cell and place a zero in Site 3 Mill D cell. Our
new shipping schedule is reflected in Table 7h.
Our new shipping cost is: $3(10) + $15(15) + $6(15) + $14(10)
+ $15(10) + $22(0)
= $635. Our cost
has been reduced
from $865 to $635
for an improvement
of $230.
Table 7h.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7 3
10
21
18 15
11 14 15 22
15 20 15
10
21
10
6
30
20
60
15 15
10 10 0
–12
–16
0
17 14 15 22
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
21
Site 3 row has three allocations, so we can set u
3
= 0 and solve
for the other margin values (Table 7h):
u
3
= 0
u
3
+ v
2
= 14 0 + v
2
= 14 v
2
= 14
u
3
+ v
3
= 15 0 + v
3
= 15 v
3
= 15
u
3
+ v
4
= 22 0 + v
4
= 22 v
4
= 22
u
2
+ v
4
= 6 u
2
+ 22 = 6 u
2
= –16
u
2
+ v
1
= 15 –16 + v
1
= 15 v
1
= 17
u
1
+ v
3
= 3 u
1
+ 15 = 3 u
1
= –12
Use Eq. 2 to check to see whether this is the optimal solution.
For cell Site 1 Mill A: 19 – (–12) – 17 > 0 is true.
For cell Site 1 Mill B: 7 – (–12) – 14 > 0 is true.
For cell Site 1 Mill D: 21 – (–12) – 22 > 0 is true.
For cell Site 2 Mill B: 21 – (–16) – 14 > 0 is true.
For cell Site 2 Mill C: 18 – (–16) – 15 > 0 is true.
For cell Site 3 Mill A: 11 – 0 – 17 > 0 is false. Place –6 in Site 3
Mill A (Table 7i).
The new enter-
ing cell is Site 3
Mill A, and we
place a “+” in this
cell. Increasing the
allocation to this
cell will save $6
per truckload. To
finish the closed
loop, place a “–”
in Site 2 Mill A, a
“+” in Site 2
Mill D, and a “–” in Site 3 Mill D (Table 7i).
We have a problem because one of the cells to be reduced—that
is, one with a minus sign in it—is the zero cell, Site 3 Mill D.
When this occurs, we can shift the zero to a cell that is to be
increased rather than reduced. As long as we keep the zero in the
same row or column, we do not change the shipping schedule or
violate a constraint. We know we want to increase the allocation to
Site 3 Mill A cell. Shifting the zero to the Site 3 Mill A cell gives
us the new shipping schedule in Table 7j (page 22).
Table 7i.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7 3
21
18 15
11 14 15 22
15 15
10
21
10
6
30
20
60
15 – 15 +
10 10 0 –
–6
10 20
+
OPERATIONS RESEARCH
22
The cost for this
schedule is exactly
the same, but we no
longer need to
worry about reduc-
ing a cell that is
already zero. Make
the changes by
moving 10 from
Site 3 Mill C to
Site 2 Mill C and
moving 10 from
Site 2 Mill A to Site 3 Mill A. Summarizing the changes:
Note that the
solution is no
longer degenerate
(more than one
exiting cell). The
new shipping
schedule is in
Table 7k.
The new shipping
schedule is: $3(10)
+ $15(5) + $18(10)
+ $6(15) + $11(10) + $14(10) = $625. We reduced our shipping
costs from $635 to $625 for a savings of $10. But, is this the
optimal solution?
Calculate our margin values by setting u
2
= 0 and solving for the
other values:
u
2
= 0
u
2
+ v
1
= 15 0 + v
1
= 15 v
1
= 15
u
2
+ v
3
= 18 0 + v
3
= 18 v
3
= 18
u
2
+ v
4
= 6 0 + v
4
= 6 v
4
= 6
u
3
+ v
1
= 11 u
3
+ 15 = 11 u
3
= –4
u
3
+ v
2
= 14 –4 + v
2
= 14 v
2
= 18
u
1
+ v
3
= 3 u
1
+ 18 = 3 u
1
= –15
Table 7j.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7 3
10
21
18 15
11 14 15 22
15 20 15
10
21
10
6
30
20
60
15 – 15
10 10 – 0 +
+
Cell in closed loop Before Change Now
Site 3 Mill C 10 –10 Empty
Site 2 Mill C Empty +10 10
Site 2 Mill A 15 –10 5
Site 3 Mill A 0 +10 10
Table 7k.—XYZ Sawmill Company’s three harvesting sites and four sawmills.
Mill A Mill B Mill C Mill D Supply u
i
Site 1
Site 2
Site 3
Demand
v
j
19 7
3
10
21
18 15
11 14 15
22
15 20 15
10
21
10
6
30
20
60
5 15
10 –4 10
–15
0 10
15 18 6 18
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
23
Use Eq. 2 to see whether this is the optimal solution.
For cell Site 1 Mill A: 19 – (–15) – 15 > 0 is true.
For cell Site 1 Mill B: 7 – (–15) – 18 > 0 is true.
For cell Site 1 Mill D: 21 – (–15) – 6 > 0 is true.
For cell Site 2 Mill B: 21 – 0 – 18 > 0 is true.
For cell Site 3 Mill C: 15 – (–4) – 18 > 0 is true.
For cell Site 3 Mill D: 22 – (–4) – 6 > 0 is true.
All statements are true, so we cannot improve the solution
further. Our optimal shipping cost for this schedule is $625.
Assignment problem
and Vogel’s Approximation
As stated earlier, problems other than transportation problems
can be solved using the transportation method. To illustrate, we
will solve an assignment problem using the transportation method.
For this example, we will use another starting procedure called
Vogel’s Approximation. Vogel’s Approximation is somewhat more
complex than the northwest corner method, but it takes cost infor-
mation into account and often gives an initial solution closer to the
optimal solution. You should be able to use either the northwest
corner method or Vogel’s Approximation to solve transportation or
assignment problems.
Example: Job-shop assignment problem
Six individuals are to work on six different machines at the
ACME Furniture Company. The machines shape, surface, and drill
to make a finished wood component. The work will be sequential
so that a finished
component is
produced at the end
of the manufactur-
ing process. All
individuals are
skilled on all
machines, but each
worker is not
equally skilled on
each machine.
Table 8 lists the time it takes a worker to complete a task at a
machine center.
Table 8.—Average number of seconds required to complete a task.
Machine center
Individual Surfacer Lathe Sander 1 Router Sander 2 Drill
Worker 1 13 22 19 21 16 20
Worker 2 18 17 24 18 22 27
Worker 3 20 22 23 24 17 31
Worker 4 14 19 13 30 23 22
Worker 5 21 14 17 25 15 23
Worker 6 17 23 18 20 16 24
OPERATIONS RESEARCH
24
The average time to complete a task takes the place of unit
shipping costs in the transportation examples above. Instead of
reducing transportation costs, we are reducing the time to process a
piece of wood into a finished component. We can set up our first
table, Table 9a.
Margin
values are
the num-
ber of
workers
available
and the
number of
workers
required
to run a
machine,
one in each case. The number of workers available equals the
number of workers required: six. This meets the criterion we
established for the transportation examples, where supply had to at
least equal demand.
The objective is to minimize the total amount of time (labor) it
takes to process a finished wood component. What about the cell
values? They are the average time a worker spends at a machine
center, represented as:
X
ij
= amount of time worker i (i = 1 – 6) is assigned to machine
center j (j = 1 – 6), as shown in Table 9b.
Let C
ij
= average time to complete a task in row i and column j.
Table 9a.—Job-shop assignment problem for ACME Furniture Company.
Available
Surfacer Lathe Sander 1 Router Sander 2 Drill workers
Worker 1 13 22 19 21 16 20 1
Worker 2 18 17 24 18 22 27 1
Worker 3 20 22 23 24 17 31 1
Worker 4 14 19 13 30 23 22 1
Worker 5 21 14 17 25 15 23 1
Worker 6 17 23 18 20 16 24 1
# of Workers 1 1 1 1 1 1 6
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
25
*Available workers
**Row differences between lowest C
ij
’s
***Column differences between lowest C
ij
’s
First, use Vogel’s Approximation to find a starting cell. Find the
difference between the two lowest costs (shortest times) in each
row and column. (In this case, time to complete a task is treated
the same as shipping costs.) For row 1, the two shortest times are
for Surfacer, 13 seconds, and Sander 2, 16 seconds. The difference
(16 – 13) is 3. For column 1, the two shortest times are for
Worker 1, 13 seconds, and Worker 4, 14 seconds. The difference
(14 – 13) is 1. Find the difference for the two shortest times for all
other rows and columns and place in Table 9b (shown in italics, as
RD and CD).
Table 9b.—Job-shop assignment problem for ACME Furniture Company.
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13
X
11
22
X
12
19
X
13
21
X
14
16
X
15
20
X
16
1
3
Worker 2
18
X
21
17
X
22
24
X
23
18
X
24
22
X
25
27
X
26
1
1
Worker 3
20
X
31
22
X
32
23
X
33
24
X
34
17
X
35
31
X
36
1
3
Worker 4
14
X
41
19
X
42
13
X
43
30
X
44
23
X
45
22
X
46
1
1
Worker 5
21
X
51
14
X
52
17
X
53
25
X
54
15
X
55
23
X
56
1
1
Worker 6
17
X
61
23
X
62
18
X
63
20
X
64
16
X
65
24
X
66
1
1
# of Workers 1 1 1 1 1 1 6
CD*** 1 3 4 2 1 2
OPERATIONS RESEARCH
26
Look for the largest value: 4, in column 3. Make the maximum assignment (in
this case, 1) to the cheapest (shortest time) cell in column 3; that is, put a 1 in cell
X
43
(Table 9c). We can cross out row 4 (Worker 4) and column 3 (Sander) since
we’ve met the requirements for that row and that column. New differences are
calculated using the cells that remain (Table 9d). The greatest difference, 4, is in
Table 9c.—Job-shop assignment problem for ACME Furniture Company.
*Available workers
**Row differences between lowest C
ij
’s
***Column differences between lowest C
ij
’s
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13 22 19 21 16 20 1
3
Worker 2
18 17 24 18 22 27 1
1
Worker 3
20 22 23 24 17 31 1
3
Worker 4
14 19 13
1
30 23 22 1
1
Worker 5
21 14 17 25 15 23 1
1
Worker 6
17 23 18 20 16 24 1
1
# of Workers 1 1 1 1 1 1 6
CD*** 1 3 4 2 1 2
Table 9d.—Job-shop assignment problem for ACME Furniture Company.
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13 22 19 21 16 20 1
3
Worker 2
18 17 24 18 22 27 1
1
Worker 3
20 22 23 24 17 31 1
3
Worker 4
14 19 13
1
30 23 22 1
6
Worker 5
21 14 17 25 15 23 1
1
Worker 6
17 23 18 20 16 24 1
1
# of Workers 1 1 1 1 1 1 6
CD*** 4 3 4 2 1 3
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
27
Table 9e.—Job-shop assignment problem for ACME Furniture Company.
Table 9f.—Job-shop assignment problem for ACME Furniture Company.
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13
1
22 19 21 16 20 1
3
Worker 2
18 17 24 18 22 27 1
1
Worker 3
20 22 23 24 17 31 1
5
Worker 4
14 19 13
1
30 23 22 1
6
Worker 5
21 14 17 25 15 23 1
1
Worker 6
17 23 18 20 16 24 1
2
# of Workers 1 1 1 1 1 1 6
CD*** 1 3 4 2 1 1
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13
1
22 19 21 16 20 1
3
Worker 2
18 17 24 18 22 27 1
1
Worker 3
20 22 23 24 17 31 1
5
Worker 4
14 19 13
1
30 23 22 1
6
Worker 5
21 14 17 25 15 23 1
1
Worker 6
17 23 18 20 16 24 1
4
# of Workers 1 1 1 1 1 1 6
CD*** 1 3 4 2 1 1
column 1. The cheapest unshaded cell in column 1 is X
11
. We assign the maximum
allowed allocation, 1, to this cell (Table 9e). Since neither row 1 nor column 1 can
receive more allocations, cross them out (Table 9e).
Calculate new differences for remaining unshaded rows and columns (Table 9f).
The greatest difference is 5 from row 3. The cheapest unshaded cell is X
35
with a
value of 17. Assign the maximum allocation, 1, to this cell and cross out row 3 and
column 5 (Table 9g).
OPERATIONS RESEARCH
28
Calculate new differences of unshaded cells for rows and col-
umns. Find the greatest difference and allocate the maximum, 1, to
the cheapest cell (Table 9h). The greatest difference is 9 in row 5,
and the cheapest unshaded cell is X
52
with a value of 14.
Continuing to work with Table 9h, allocate the maximum of 1 to
this cell and cross out row 5 and column 2. Calculate differences
for rows and columns. The greatest difference is 9 for row 2. The
cheapest unshaded cell is X
24
with a value of 18. Assign 1 to this
cell and block out row 2 and column 4 (Table 9i). There is only one
unshaded cell remaining. We can assign 1 to cell X
66
(Table 9i).
Table 9g.—Job-shop assignment problem for ACME Furniture Company.
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13
1
22 19 21 16 20 1
3
Worker 2
18 17 24 18 22 27 1
1
Worker 3
20 22 23 24 17
1
31 1
5
Worker 4
14 19 13
1
30 23 22 1
6
Worker 5
21 14 17 25 15 23 1
1
Worker 6
17 23 18 20 16 24 1
4
# of Workers 1 1 1 1 1 1 6
CD*** 1 3 4 2 1 1
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
29
Table 9h.—Job-shop assignment problem for ACME Furniture Company.
Table 9i.—Job-shop assignment problem for ACME Furniture Company.
*Available workers
**Row differences between lowest C
ij
’s
***Column differences between lowest C
ij
’s
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13
1
22 19 21 16 20 1
3
Worker 2
18 17 24 18 22 27 1
1
Worker 3
20 22 23 24 17
1
31 1
5
Worker 4
14 19 13
1
30 23 22 1
6
Worker 5
21 14 17 25 15 23 1
9
Worker 6
17 23 18 20 16 24 1
3
# of Workers 1 1 1 1 1 1 6
CD*** 1 3 4 2 1 1
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13
1
22 19 21 16 20 1
3
Worker 2
18 17 24 18 22 27 1
9
Worker 3
20 22 23 24 17
1
31 1
5
Worker 4
14 19 13
1
30 23 22 1
6
Worker 5
21 14
1
17 25 15 23 1
9
Worker 6
17 23 18 20 16 24
1
1
4
# of Workers 1 1 1 1 1 1 6
CD*** 1 3 4 2 1 3
OPERATIONS RESEARCH
30
Table 9j.—Job-shop assignment problem for ACME Furniture Company.
Table 9j shows the assignment schedule using Vogel’s
Approximation.
Unlike the northwest corner method, Vogel’s Approximation
does not always result in the required number of nonempty cells.
Remember that in order to use the transportation method to solve
LP problems, the number of routes (or, in this case, assignments)
must equal the number of sources or sites (in this case, workers)
plus the number of destinations (in this case, jobs) minus one; that
is, Assignments = Workers + Jobs – 1; that is, Assignments = 6 + 6
– 1. We can see that for our problem, we have six nonempty cells
but need eleven. We need to assign zeroes to five empty cells.
Using the transportation method, find the marginal row and
column values. In the preceding transportation problems, we
assigned a row value of zero to the row that had the most shipping
routes (analogous to our job assignments). Since all rows have the
same allocation of 1, we will arbitrarily assign a margin value of
zero to row 1 (Table 9k).
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* RD**
Worker 1
13
1
22 19 21 16 20 1
Worker 2
18 17 24 18
1
22 27 1
Worker 3
20 22 23 24 17
1
31 1
Worker 4
14 19 13
1
30 23 22 1
Worker 5
21 14
1
17 25 15 23 1
Worker 6
17 23 18 20 16 24
1
1
# of Workers 1 1 1 1 1 1 6
CD***
*Available workers
**Row differences between lowest C
ij
’s
***Column differences between lowest C
ij
’s
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
31
Table 9k—Job-shop assignment problem for ACME Furniture Company.
We are able to calculate v
1
= 13, 0 + 13 = 13. To continue, we
need another nonempty cell (Table 9k). We check for the cheapest
(least time) nonempty cell and place a zero in it. This would be cell
X
41
, with a value of 14 seconds (Table 9k). We can now calculate
u
4
as 1.
Next we see that we can calculate v
3

as 1 + 12 = 13. Again, we
have reached a point where no further calculations can be made.
Look at column 2 and place a zero in the cheapest empty cell, X
22
.
Calculate the margin value for row 2: 8 + 9 = 17. Next, calculate
the margin value for column 4 as 8 + 10 = 18. Calculate the margin
value for row 6 as 10 + 10 = 20. Next, calculate the margin value
for column 6 as 10 + 14 = 24.
Again, we have reached an impasse. We need to find margin
values for row 3 and column 5. If we place a zero in cell X
36
we
will be able to find our two remaining margin values. Calculate the
margin value for row 3 as 17 + 14 = 31, and the margin value for
column 5 as 17 + 0 = 17 (Table 9k).
Now, we have the required Assignments = Workers + Jobs – 1.
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* u
i
Worker 1
13
1
22 19 21 16 20 1
0
Worker 2
18 17
0
24 18
1
22 27 1
8
Worker 3
20 22 23 24 17
1
31
0
1
17
Worker 4
14
0
19 13
1
30 23 22 1
1
Worker 5
21 14
1
17
0
25 15 23 1
5
Worker 6
17 23 18 20
0
16 24
1
1
10
# of Workers 1 1 1 1 1 1 6
v
j
13 9 12 10 0 14
OPERATIONS RESEARCH
32
Use the margin values to determine the empty cell differences
and place these in the left bottom corner of each empty cell
(Table 9l). For example, cell X
12
, 0 + 9 + value = 22. Therefore the
value = 13. Fill in the remainder of the empty cell differences
(Table 9l).
Table 9l—Job-shop assignment problem for ACME Furniture Company.
The most negative cell, X
31
with a value of –10, is the new
entering cell. Use the closed-loop path to determine the exiting cell
(Table 9m). Lines with arrows highlight the closed-loop path. Note
that all the losing cells contain zeroes. Therefore, the maximum
quantity to be reallocated along the path is zero, and one of the
losing cells will go blank in the next solution. Break the tie by
choosing the most expensive losing cell, X
31
, and move the zero
from cell X
36
to cell X
31
. Since the value is zero, however, the total
time savings is 10 x 0 = 0.
We will leave it up to you to go through the next few iterations.
They involve only moving zeroes; therefore, this assignment is
optimal and leads to the fastest processing time.
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* u
i
Worker 1
13
1
22
13
19
7
21
11
16
16
20
6
1
0
Worker 2
18
–3
17
0
24
4
18
1
22
14
27
5
1
8
Worker 3
20
–10
22
–4
23
–6
24
–3
17
1
31
0
1
17
Worker 4
14
0
19
9
13
1
30
19
23
22
22
7
1
1
Worker 5
21
3
14
1
17
0
25
10
15
10
23
4
1
5
Worker 6
17
–6
23
4
18
–4
20
0
16
6
24
1
1
10
# of Workers 1 1 1 1 1 1 6
v
j
13 9 12 10 0 14
*Available workers
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
33
Surfacer Lathe Sander 1 Router Sander 2 Drill AW* u
i
Worker 1
13
1
22
13
19
7
21
11
16
16
20
6
1
0
Worker 2
18
–3
17
0 –
24
4
18
1 +
22
14
27
5
1
8
Worker 3
20
+
–10
22
–4
23
–6
24
–3
17
1
31
0 –
1
17
Worker 4
14
0 –
19
9
13
1 +
30
19
23
22
22
7
1
1
Worker 5
21
3
14
1 +
17
0 –
25
10
15
10
23
4
1
5
Worker 6
17
–6
23
4
18
–4
20
0 –
16
6
24
1 +
1
10
# of Workers 1 1 1 1 1 1 6
v
j
13 9 12 10 0 14
The processing time is calculated as:
Worker 1 Surfacer 13 sec
Worker 2 Router 18 sec
Worker 3 Sander 2 17 sec
Worker 4 Sander 1 13 sec
Worker 5 Lathe 14 sec
Worker 6 Drill 24 sec
Total processing time/component 99 sec
There is an alternative optimal solution to this assignment
problem, but we leave it to you to discover.
Table 9m.—Job-shop assignment problem for ACME Furniture Company.
?
?
?
?
?
?
?
?
?
?
OPERATIONS RESEARCH
34
Conclusion
Transportation problems can be solved using the simplex
method; however, the simplex method involves time-consuming
computations. And, it is easy to make a mistake when working the
problems by hand.
An advantage to the transportation method is that the solution
process involves only the main variables; artificial variables are
not required, as they are in the simplex process. In fact, after
applying the northwest corner rule, the problem is as far along as it
would be using simplex after eliminating the artificial variables.
Simplex requires a minimum of iterations (each represented by
another simplex tableau) equal to the number of rows plus columns
minus 1. This is the minimum; many problems require more
iterations. Calculations are much easier to obtain with a new
transportation table than a new simplex tableau. After practice, a
relatively large transportation problem can be solved by hand. This
is not true when solving large LP problems using the simplex
method.
Finally, some LP computer programs are set up to solve both
simplex and transportation problems. When the problems are
introduced as transportation problems, the computer algorithms
can solve them much faster.
Although developed to solve problems in transporting goods
from one location to another, the transportation method can be
used to solve other problems—such as the assignment example
above—as long as the problem can be set up in the transportation
problem form.
To learn more about transportation problems, check out the
references below.
References
Bierman, H., C. P. Bonini, and W. H. Hausman. 1977. Quantitative
Analysis for Business Decisions. Homewood, IL: Richard D.
Irwin, Inc. 642 pp.
Dykstra, D. P. 1984. Mathematical Programming for Natural
Resource Management. New York: McGraw-Hill, Inc. 318 pp.
Hillier, F. S. and G. J. Lieberman. 1995. Introduction to Operations
Research, 6th ed. New York: McGraw-Hill, Inc. 998 pp.
TRANSPORTATION PROBLEM: A SPECIAL CASE FOR LINEAR PROGRAMMING PROBLEMS
35
Ignizio, J. P., J. N. D. Gupta, and G. R. McNichols. 1975. Opera-
tions Research in Decision Making. New York: Crane, Russak &
Company, Inc. 343 pp.
Institute for Operations Research and the Management Sciences,
901 Elkridge Landing Road, Suite 400, Linthicum, MD.http://www.informs.org/
Lapin, L. L. 1985. Quantitative Methods for Business Decisions
with Cases, 3rd ed. San Diego: Harcourt Brace Jovanovich.
780 pp.
Ravindran, A., D. T. Phillips, and J. J. Solberg. 1987. Operations
Research: Principles and Practice, 2nd ed. New York: John
Wiley & Sons. 637 pp.
Reeb, J. and S. Leavengood. 1998. Using the Graphical Method to
Solve Linear Programs, EM 8719. Corvallis: Oregon State
University Extension Service. 24 pp. $2.50
Reeb, J. and S. Leavengood. 1998. Using the Simplex Method to
Solve Linear Programming Maximization Problems, EM 8720.
Corvallis: Oregon State University Extension Service. 28 pp.
$3.00
Reeb, J. and S. Leavengood. 2000. Using Duality and Sensitivity
Analysis to Interpret Linear Programming Solutions, EM 8744.
Corvallis: Oregon State University Extension Service. 24 pp.
$2.50
Solver Suite: LINDO, LINGO, WHAT’S BEST. Chicago: LINDO
Systems Inc. 382 pp.
Ordering information
To order additional copies of this publication, send the complete
title and series number, along with a check or money order for
$3.50 payable to OSU, to:
Publication Orders
Extension & Station Communications
Oregon State University
422 Kerr Administration
Corvallis, OR 97331-2119
Fax: 541-737-0817
We offer a 25-percent discount on orders of 100 or more copies
of a single title.
You can view our Publications and Videos catalog and many
Extension publications on the Web athttp://eesc.oregonstate.edu
OPERATIONS RESEARCH
36
© 2002 Oregon State University
This publication was produced and distributed in furtherance of the Acts of Congress of May 8 and June 30, 1914.
Extension work is a cooperative program of Oregon State University, the U.S. Department of Agriculture, and
Oregon counties.
Oregon State University Extension Service offers educational programs, activities, and materials—without discrimi-
nation based on race, color, religion, sex, sexual orientation, national origin, age, marital status, disability, or
disabled veteran or Vietnam-era veteran status. Oregon State University Extension Service is an Equal Opportunity
Employer.
Published June 2002.
This publication is part of a series, Performance
Excellence in the Wood Products Industry. The various
publications address topics under the headings of wood
technology, marketing and business management,
production management, quality and process control,
and operations research.
For a complete list of titles in print, contact OSU
Extension & Station Communications (see page 35) or
visit the OSU Wood Products Extension Web site athttp://wood.orst.edu
PERFORMANCE EXCELLENCE
IN THE WOOD PRODUCTS INDUSTRY
ABOUT THIS SERIES

doc_409210790.pdf