Transportation,

Transshipment, and
Assignment Problems

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-1

The Transportation Model: Characteristics

■ A product is transported from a number of sources to a number of

destinations at the minimum possible cost.
■ Each source is able to supply a fixed number of units of the
product, and each destination has a fixed demand for the product.
■ The linear programming model has constraints for supply at each
source and demand at each destination.
■ All constraints are equalities in a balanced transportation model
where supply equals demand.
■ Constraints contain inequalities in unbalanced models where supply
does not equal demand.

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-2

Transportation Model Example
Problem Definition and Data
How many tons of wheat to transport from each grain
elevator to each mill on a monthly basis in order to
minimize the total cost of transportation?
Grain Elevator Supply Mill Demand
1. Kansas City 150 A. Chicago 220
2. Omaha 175 B. St. Louis 100
3. Des Moines 275 C. Cincinnati 300
Total 600 tons Total 600 tons

Transport Cost from Grain Elevator to Mill ($/ton)

Grain Elevator A. Chicago B. St. Louis C. Cincinnati
1. Kansas City $6 $8 $ 10
2. Omaha 7 11 11
3. Des Moines 4 5 12

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-3

Transportation Model Example
Transportation Network Routes

Figure 6.1 Network of transportation routes for wheat shipments

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-4
Transportation Model Example
Model Formulation
Minimize Z = $6x1A + 8x1B + 10x1C + 7x2A + 11x2B + 11x2C +
4x3A + 5x3B + 12x3C
subject to:
x1A + x1B + x1C = 150
x2A + x2B + x2C = 175
x3A + x3B + x3C = 275
x1A + x2A + x3A = 200
x1B + x2B + x3B = 100
x1C + x2C + x3C = 300
xij ³ 0
xij = tons of wheat from each grain elevator, i, i = 1, 2, 3,
to each mill j, j = A,B,C

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-5

Transportation Model Example
Computer Solution with Excel (1 of 4)

Objective function

=C7+D7+E7
Cost array in
=D5+D6+D7 Decision variables cells K5:M7
in cells C5:E7

Exhibit 6.1
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-6
Transportation Model Example
Computer Solution with Excel (2 of 4)

Supply constraints

Demand constraints

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Exhibit 6.2 6-7
Transportation Model Example
Computer Solution with Excel (3 of 4)

Exhibit 6.3
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-8
Transportation Model Example
Computer Solution with Excel (4 of 4)

Figure 6.2 Transportation network solution for wheat-shipping example

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-9
 Transportation Algorithm
n The steps of the transportation algorithm:
Step 1. Determine a starting basic feasible solution and go to
Step 2.
Step 2. Use the optimality condition of the simplex method
to determine the entering variable from among all the
nonbasic variables. If the optimality condition is
satisfied, stop. Otherwise, go to Step 3.
Step 3. Use the feasibility condition of the simplex method to
determine the leaving variable from among all the
current basic variables and find the new basic solution.
Return to Step 2.

6-10
 Example

n Sunray Transport company ships truckloads of grain

from three silos to four mills.
n The supply (in truckloads) and the demand (also in
truckloads) together with the unit transportation costs
per truckload on the different routes are summarized in
the transportation model.
n The unit transportation costs, cij, are hundreds of
dollars.
n The model seeks the minimum-cost shipping schedule
xij between silo i and mill j.
n Draw the transportation tableau!
6-11
6-12
 Determination of the Starting Solution
n m sources, n destinations
n m + n constraint equations

n Transportation model is always balanced (sum of the

supply = sum of the demand) è one of these
equations are redundant.
n The model has m + n - 1 independent constraint
equations è the starting basic solution consists of m
+n -1 basic variables.
n Starting solution of example has 3 + 4 – 1 = 6 basic
variables
6-13
 Determination of the Starting Solution
(cont’d)
n The special structure of the transportation problem allows
securing a non-artificial starting basic solution using one of three
methods:
n Northwest-Corner Method (NCM)

n Least-Cost Method (LCM)

n Vogel Approximation Method (VAM)

n They differ in the quality (smaller objective value) of the starting

basic solution they produce.
n In general, not always, the Vogel Method yields the best starting
basic solution and the Northwest-Corner method yields the
worst.
n The tradeoff is that the NCM involves the least amount of
computations.
n We will learn these models on an example 6-14
Nortwest-Corner Method

6-15
6-16
6-17
Least cost Method

6-18
6-19
6-20
Vogel Approximation Method (VAM)

6-21
6-22
6-23
6-24
 Iterative Computations of the Transportation
Algorithm
Step 1. Use the simplex optimality condition to determine the entering
variable as the current nonbasic variable that can improve the
solution. If the optimality condition is satisfied, stop. Otherwise,
go to Step 2.

Step 2. Determine the leaving variable using the simplex feasibility

condition. Change the basis, and return Step 1.

n The optimality and feasibility conditions do not involve the

familiar row operations used in the simplex method. Instead, the
special structure of the transportation model allows simpler
computations.

6-25
n Method of multipliers:
n Ui and vj for row i and column j respectively
for each current basic variable Xij

n Evaluate nonbasic variables

6-26
6-27
6-28
6-29
6-30
6-31
6-32
6-33
The Transshipment Model
Characteristics
■ Extension of the transportation model.
■ Intermediate transshipment points are added between the sources
and destinations.
■ Items may be transported from:
§ Sources through transshipment points to destinations
§ One source to another
§ One transshipment point to another
S1 T1
§ One destination to another D1
§ Directly from sources to destinations S2 T2
§ Some combination of these

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-34

Transshipment Model Example
Problem Definition and Data
Extension of the transportation model in which
intermediate transshipment points are added between
sources and destinations.
Shipping Costs

Grain Elevator
Farm 3. Kansas City 4. Omaha 5. Des Moines
1. Nebraska $16 10 12
2. Colorado 15 14 17

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-35

Transshipment Model Example
Transshipment Network Routes

Figure 6.3 Network of transshipment routes

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-36
Transshipment Model Example
Model Formulation
Minimize Z = $16x13 + 10x14 + 12x15 + 15x23 + 14x24
+ 17x25 + 6x36 + 8x37 + 10x38 + 7x46 + 11x47
+ 11x48 + 4x56 + 5x57 + 12x58
subject to:
x13 + x14 + x15 = 300 Supply constraints for farms
x23 + x24 + x25 = 300 in Nebraska and Colorado
x36 + x46 + x56 = 200
x37 + x47 + x57 = 100 Demand constraints at
x38 + x48 + x58 = 300 the Chicago, St. Louis
x13 + x23 - x36 - x37 - x38 = 0 and Cincinnati mills
x14 + x24 - x46 - x47 - x48 = 0
x15 + x25 - x56 - x57 - x58 = 0
xij ³ 0
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-37
Transshipment Model Example
Computer Solution with Excel (1 of 3)

=SUM(B6:B7) Objective function

=SUM(B6:D6)

Cost arrays

=SUM(C13:C15) =SUM(C13:E13)

Constraints for transshipment flows;

i.e., shipments in = shipments out Exhibit 6.11
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-38
Transshipment Model Example
Computer Solution with Excel (2 of 3)

Transshipment
constraints in
cells C20:C22

Exhibit 6.12
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-39
Transshipment Model Example
Network Solution for Wheat Shipping (3 of 3)

Figure 6.4 Transshipment network solution for wheat-shipping example

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-40

The Assignment Model
Characteristics

■ Special form of linear programming model similar to the

transportation model.
■ Supply at each source and demand at each destination
limited to one unit.

■ In a balanced model supply equals demand.

■ In an unbalanced model supply does not equal demand.

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-41

Assignment Model Example
Problem Definition and Data
Problem: Assign four teams of officials to four games in
a way that will minimize total distance traveled by the
officials. Supply is always one team of officials, demand is
for only one team of officials at each game.

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-42

Assignment Model Example
Model Formulation
Minimize Z = 210xAR + 90xAA + 180xAD + 160xAC + 100xBR +70xBA
+ 130xBD + 200xBC + 175xCR + 105xCA +140xCD
+ 170xCC + 80xDR + 65xDA + 105xDD + 120xDC
subject to:
xAR + xAA + xAD + xAC = 1 xij ³ 0
xBR + xBA + xBD + xBC = 1
xCR + xCA + xCD + xCC = 1
xDR + xDA + xDD + xDC = 1
xAR + xBR + xCR + xDR = 1
xAA + xBA + xCA + xDA = 1
xAD + xBD + xCD + xDD = 1
xAC + xBC + xCC + xDC = 1

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-43

Assignment Model Example
Computer Solution with Excel (1 of 3)
Objective function

Decision
variables,
C5:F8

=C5+D5+E5+F5

=D5+D6+D7+D8

Mileage array

Exhibit 6.13
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-44
Assignment Model Example
Computer Solution with Excel (2 of 3)

Exhibit 6.14

Simplex LP

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-45

Assignment Model Example
Computer Solution with Excel (3 of 3)

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Exhibit 6.15 6-46
Assignment Model Example
Assignment Network Solution

Figure 6.5 Assignment network solution for ACC officials

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-47
 ASSIGNMENT MODEL
n “the best person for the job”
n Assignment of workers with varying degrees of skill to jobs
n Objective: to determine the minimum-cost assignment of
workers to jobs.
n n workers, n jobs (If the number of workers does not equal to
the number of jobs, add either a dummy worker or a dummy job
with a high cost, M)
n cij: cost of assigning worker i to job j
n Special case of the transportation model(workers à sources,
jobs à destinations)
n Supply and demand amount is 1.
n Can be solved by transportation algorithm
n Hungarian Method
n We see this method on an example 6-48
 Example 1.

n Joe’s three children, John, Karen and Terri, want to earn some money to take care of
personal expenses during a school trip to the local zoo.
n Joe has chosen three chores for his children: moving the lawn, painting the garage
door, and washing the family cars.
n To avoid anticipating sibling competition, he asks them to submit (secret) bids for
what they feel is fair pay for each of the three chores.
n Table 5.32 summarizes the bids received.
n Based on this information, how should Joe assign the chores?

Mow Paint Wash Supply

John $15 $10 $9 1
Karen $9 $15 $10 1
Terri $10 $12 $8 1
Demand 1 1 1

6-49
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-50
 Example 2.

n Assume that we have four children and four

chores in the previous example with the
following cost table:
1 2 3 4
1 $1 $4 $6 $3

2 $9 $7 $1 $9
0
3 $4 $5 $1 $7
1
4 $8 $7 $8 $5

6-51
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-52
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-53
Example Problem Solution
Transportation Problem Statement
A concrete company transports concrete from three
plants to three construction sites. The supply capacities of
the three plants, the demand requirements at the three
sites, and the transportation costs per ton are as follows:
Construction site
Plant A B C Supply (tons)
1 $8 $5 $6 120
2 15 10 12 80
3 3 9 10 80
Demand (tons) 150 70 100

Determine the linear programming model formulation and

solve using Excel.
Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-54
Example Problem Solution
Model Formulation

Minimize Z = $8x1A + 5x1B + 6x1C + 15x2A + 10x2B + 12x2C

+3x3A + 9x3B + 10x3C
subject to:
x1A + x1B + x1C = 120
x2A + x2B + x2C = 80
x3A + x3B + x3C = 80
x1A + x2A + x3A £ 150
x1B + x2B + x3B £ 70
x1C + x2C + x3C £ 100
xij ³ 0

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-55

Example Problem Solution
Computer Solution with Excel

Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-56