OPIM 101 Decision Analysis

Session 5:

Distribution and Network Models:

Transportation, Assignment, and Transshipment

By: Low Chee Seng

1
Learning Objectives
1) Know the basic characteristics of the transportation problem.
2) Be able to draw the network representation/map
3) Be able to formulate the LP problem and solve the
transportation problem.
4) Know the basic characteristics of the assignment problem.
5) Be able to draw the network representation/map
6) Be able to formulate the LP problem and solve the assignment
problem.
7) Know the basic characteristics of the transshipment problem.
8) Be able to draw the network representation/map
9) Be able to formulate the LP problem and solve the
transshipment problem.
OPIM 101 DA - Low CS 2
 Distribution and Network Models
(Chapter 6)

Transportation Problem
• Network Representation
• General LP Formulation
Assignment Problem
• Network Representation
• General LP Formulation
Transshipment Problem
• Network Representation
• General LP Formulation

3
 Transportation, Assignment, and
Transshipment Problems

A network model is one which can be represented

by a set of nodes, a set of arcs, and functions (e.g.
costs, supplies, demands, etc.) associated with the
arcs and/or nodes.
Transportation, assignment, transshipment,
shortest-route, and maximal flow problems of this
chapter as well as the minimal spanning tree and
PERT/CPM problems are all examples of network
problems.

4
 Transportation, Assignment, and
Transshipment Problems
Each of the five models of this chapter can be
formulated as linear programs and solved by
general purpose linear programming codes.
For each of the five models, if the right-hand side
of the linear programming formulations are all
integers, the optimal solution will be in terms of
integer values for the decision variables.
However, there are many computer packages
(including The Management Scientist) that contain
separate computer codes for these models which
take advantage of their network structure.

5
 Transportation Problem

The transportation problem seeks to minimize the

total shipping costs of transporting goods from m
origins (each with a supply si) to n destinations
(each with a demand dj), when the unit shipping
cost from an origin, i, to a destination, j, is cij.
The network representation for a transportation
problem with two sources and three destinations is
given on the next slide.

6
 Transportation Problem

Network Representation

1 d1
c11
s1 1 c12
c13
2 d2
c21

s2 2 c22
c23
3 d3

Sources Destinations

7
 Transportation Problem
Linear Programming Formulation

Using the notation:

xij = number of units shipped from
origin i to destination j
cij = cost per unit of shipping from
origin i to destination j
si = supply or capacity in units at origin i
dj = demand in units at destination j
continued

8
 Transportation Problem

Linear Programming Formulation (continued)

m n
Min  c x
i =1 j =1
ij ij

x
j =1
ij  si i =1, 2, ,m Supply

x
i =1
ij  dj
= j =1, 2, ,n Demand

xij > 0 for all i and j

Note: The optimal solution to a transportation model will

consist of integer values for the decision variables as long
as all the supply and demand values are integers.
In general, there will be m x n decision variables.
9
 Transportation Problem

LP Formulation Special Cases

• The objective is maximizing profit or revenue:
Solve as a maximization problem.

• Minimum shipping guarantee from i to j:

xij > Lij
• Maximum route capacity from i to j:
xij < Kij
• Unacceptable route:
Remove the corresponding decision variable.

10
 Transportation Problem: Example

Acme Block Company has orders for 80 tons (per

week) of concrete blocks at three suburban locations
as follows: Northwood -- 25 tons,
Westwood -- 45 tons, and
Eastwood -- 10 tons. Acme
has two plants, each of which
can produce 50 tons per week.
Delivery cost per ton from each plant
to each suburban location is shown on the next slide.
How should end of week shipments be made to fill
the above orders?

11
 Transportation Problem: Example

Delivery Cost Per Ton

Northwood Westwood Eastwood

Plant 1 24 30 40
Plant 2 30 40 42

12
 Transportation Problem: Example

Excel Spreadsheet Showing Optimal Solution

Acme Block Company

X11 X12 X13 X21 X22 X23

Decision Variables 5 45 0 20 0 10
Cost per Ton Cij 24 30 40 30 40 42

Obj Funct - MIN 2490

LHS RHS
Constraint #1 1 1 1 50 < 50
Constraint #2 1 1 1 30 < 50
Constraint #3 1 1 25 = 25
Constraint #4 1 1 45 = 45
Constraint #5 1 1 10 = 10

13
 Transportation Problem: Example

Partial Sensitivity Report (first half)

Final Reduced Objective Allowable Allowable

Cell Name Value Cost Coefficient Increase Decrease
$C$4 Decision Variables X11 5 0 24 4 4
$D$4 Decision Variables X12 45 0 30 4 1E+30
$E$4 Decision Variables X13 0 4 40 1E+30 4
$F$4 Decision Variables X21 20 0 30 4 4
$G$4 Decision Variables X22 0 4 40 1E+30 4
$H$4 Decision Variables X23 10 0 42 4 1E+30

14
 Transportation Problem: Example

Partial Sensitivity Report (second half)

Final Shadow Constraint Allowable Allowable

Cell Name Value Price R.H. Side Increase Decrease
$I$11 Constraint #3 LHS 25 30 25 20 20
$I$12 Constraint #4 LHS 45 36 45 5 20
$I$13 Constraint #5 LHS 10 42 10 20 10
$I$9 Constraint #1 LHS 50 -6 50 20 5
$I$10 Constraint #2 LHS 30 0 50 1E+30 20

15
 Transportation Problem: Example

Alternate Excel Setup

Cost per ton Northwood Westwood Eastwood

Plant 1 24 30 40
Plant 2 30 40 42

Decision VariablesNorthwood Westwood Eastwood Total Supply Capacity

Plant 1 5 45 0 50 50
Plant 2 20 0 10 30 50
Total Demand 25 45 10
Required 25 45 10

Objective Function
Total Cost (MIN) 2490

16
 Transportation Problem: Example

Optimal Solution

From To Amount Cost

Plant 1 Northwood 5 120
Plant 1 Westwood 45 1,350
Plant 2 Northwood 20 600
Plant 2 Eastwood 10 420
Total Cost = $2,490

17
 Assignment Problem

An assignment problem seeks to minimize the total

cost assignment of m workers to m jobs, given that the
cost of worker i performing job j is cij.
It assumes all workers are assigned and each job is
performed.
An assignment problem is a special case of a
transportation problem in which all supplies and all
demands are equal to 1; hence assignment problems
may be solved as linear programs.
The network representation of an assignment problem
with three workers and three jobs is shown on the
next slide.

18
 Assignment Problem

Network Representation

c11
1 1
c12
c13
Agents Tasks
c21
c22
2 2
c23
c31
c32
3 c33 3

19
 Assignment Problem

Linear Programming Formulation

Using the notation:

xij = 1 if agent i is assigned to task j

0 otherwise

cij = cost of assigning agent i to task j

continued

20
 Assignment Problem

Linear Programming Formulation (continued)

m n
Min  c x
i =1 j =1
ij ij

x
j =1
ij  1 i =1, 2, ,m Agents
m

x
i =1
ij = 1 j =1, 2, ,n Tasks

xij > 0 for all i and j, m > n

Note: As a special case of the transportation model, and with all the
supply and demand values equal 1, the optimal solution must be
integer valued and in this case, must be 0 or 1.

21
 Assignment Problem

LP Formulation Special Cases

•Number of agents exceeds the number of tasks:
Extra agents simply remain unassigned.

•Number of tasks exceeds the number of agents:

Add enough dummy agents to equalize the
number of agents and the number of tasks.
The objective function coefficients for these
new variable would be zero.

22
 Assignment Problem

LP Formulation Special Cases (continued)

•The assignment alternatives are evaluated in terms
of revenue or profit:
Solve as a maximization problem.
•An assignment is unacceptable:
Remove the corresponding decision variable.
•An agent is permitted to work t tasks:
n

x
j =1
ij t i =1, 2, ,m Agents

23
 Assignment Problem: Example

An electrical contractor pays his subcontractors a

fixed fee plus mileage for work performed. On a given
day the contractor is faced with three electrical jobs
associated with various projects. Given below are the
distances between the subcontractors and the projects.
Projects
Subcontractor A B C
Westside 50 36 16
Federated 28 30 18
Goliath 35 32 20
Universal 25 25 14
How should the contractors be assigned to minimize
total mileage costs?

24
 Assignment Problem: Example

Network Representation
50
West. A
36
Subcontractors 16 Projects
28
Fed.
30 B
18
35 32

Gol. C
20
25 25
Univ.
14
25
 Assignment Problem: Example

Linear Programming Formulation

Min 50x11+36x12+16x13+28x21+30x22+18x23
+35x31+32x32+20x33+25x41+25x42+14x43
s.t. x11+x12+x13 < 1
x21+x22+x23 < 1
Agents
x31+x32+x33 < 1
x41+x42+x43 < 1
x11+x21+x31+x41 = 1
x12+x22+x32+x42 = 1 Tasks
x13+x23+x33+x43 = 1
xij = 0 or 1 for all i and j

26
 Assignment Problem: Example

The optimal assignment is:

Subcontractor Project Distance

Westside C 16
Federated A 28
Goliath (unassigned)
Universal B 25
Total Distance = 69 miles

27
 Assignment Problem: In-Class Exercise
Sweeney Chapter 6

28
Assignment Problem: In-Class Exercise

29
 Assignment Problem: In-Class Exercise
DCs Los Angeles Chicago Columbus Atlanta Newark Kansas Denver Dallas
Plano X11 X12 X13 X14 X15 X16 X17 X18
Nashville X21 X22 X23 X24 X25 X26 X27 X28
Flagstaff X31 X32 X33 X34 X35 X36 X37 X38
Springfield X41 X42 X43 X44 X45 X46 X47 X48
Boulder X51 X52 X53 X54 X55 X56 X57 X58

DCs Los Angeles Chicago Columbus Atlanta Newark Kansas Denver Dallas
Plano 70 47 22 53 98 21 27 13
Nashville 75 38 19 58 90 34 40 26
Flagstaff 15 78 37 82 111 40 29 32
Springfield 60 23 8 39 82 36 32 45
Boulder 45 40 29 75 86 25 11 37

DCs Los Angeles Chicago Columbus Atlanta Newark Kansas Denver Dallas Sum RHS
Plano 0 0 0 0 0 1 0 1 2 < 3
Nashville 0 0 0 0 0 0 0 0 0 < 3
Flagstaff 1 0 0 0 0 0 0 0 1 < 3
Springfield 0 1 1 1 0 0 0 0 3 < 3
Boulder 0 0 0 0 1 0 1 0 2 < 3
Sum 1 1 1 1 1 1 1 1

Total Cost 216

30
 Transshipment Problem

Transshipment problems are transportation problems

in which a shipment may move through intermediate
nodes (transshipment nodes) before reaching a
particular destination node.
Transshipment problems can be converted to larger
transportation problems and solved by a special
transportation program.
Transshipment problems can also be solved by
general purpose linear programming codes.
The network representation for a transshipment
problem with two sources, three intermediate nodes,
and two destinations is shown on the next slide.

31
 Transshipment Problem

Network Representation

c36
3
c13
s1 1
c37 6 d1
c14
c15 c46
Supply 4 c47 Demand
c23
c24 c56
s2 2 7 d2
c25
5 c57
Sources Destinations
Intermediate Nodes

32
 Transshipment Problem

Linear Programming Formulation

Using the notation:

xij = number of units shipped from node i to node j
cij = cost per unit of shipping from node i to node j
si = supply at origin node i
dj = demand at destination node j
continued

33
 Transshipment Problem

Linear Programming Formulation (continued)

Min cx
all arcs
ij ij

s.t. 
arcs out
xij − x
arcs in
ij  si Origin nodes i


arcs out
xij − x
arcs in
ij =0 Transhipment nodes

x
arcs in
ij − 
arcs out
xij = d j Destination nodes j

xij > 0 for all i and j

continued

34
 Transshipment Problem

LP Formulation Special Cases

• Total supply not equal to total demand
• Maximization objective function
• Route capacities or route minimums
• Unacceptable routes
The LP model modifications required here are
identical to those required for the special cases in
the transportation problem.

35
 Transshipment Problem: Example

The Northside and Southside facilities

of Zeron Industries supply three firms
(Zrox, Hewes, Rockrite) with customized
shelving for its offices. They both order
shelving from the same two manufacturers,
Arnold Manufacturers and Supershelf, Inc.
Currently weekly demands by the users
are 50 for Zrox, 60 for Hewes, and 40 for
Rockrite. Both Arnold and Supershelf can
supply at most 75 units to its customers.
Additional data is shown on the next
slide.

36
 Transshipment Problem: Example

Because of long standing contracts based on

past orders, unit costs from the manufacturers to the
suppliers are:

Zeron N Zeron S
Arnold 5 8
Supershelf 7 4
The costs to install the shelving at the various
locations are:

Zrox Hewes Rockrite

Zeron N 1 5 8
Zeron S 3 4 4

37
 Transshipment Problem: Example

Network Representation
ZROX

Zrox 50
5 1
Zeron
75 Arnold
ARNOLD
N 5
8 8
Hewes
HEWES 60

7 3

75
Super Zeron
WASH 4
Shelf S
4 BURN
4 Rock-
Rite 40

38
 Transshipment Problem: Example

Linear Programming Formulation

• Decision Variables Defined
xij = amount shipped from manufacturer i to supplier j
xjk = amount shipped from supplier j to customer k
where i = 1 (Arnold), 2 (Supershelf)
j = 3 (Zeron N), 4 (Zeron S)
k = 5 (Zrox), 6 (Hewes), 7 (Rockrite)
• Objective Function Defined
Minimize Overall Shipping Costs:
Min 5x13 + 8x14 + 7x23 + 4x24 + 1x35 + 5x36 + 8x37
+ 3x45 + 4x46 + 4x47

39
 Transshipment Problem: Example

Constraints Defined
Amount Out of Arnold: x13 + x14 < 75
Amount Out of Supershelf: x23 + x24 < 75
Amount Through Zeron N: x13 + x23 - x35 - x36 - x37 = 0
Amount Through Zeron S: x14 + x24 - x45 - x46 - x47 = 0
Amount Into Zrox: x35 + x45 = 50
Amount Into Hewes: x36 + x46 = 60
Amount Into Rockrite: x37 + x47 = 40

Non-negativity of Variables: xij > 0, for all i and j.

40
 Transshipment Problem: Example

Zeron Industries

x13 x14 x23 x24 x35 x36 x37 x45 x46 x47
Decision Variables 75 0 0 75 50 25 0 0 35 40 Value
Obj Function Coeff 5 8 7 4 1 5 8 3 4 4 1150

LHS RHS
Const #1 1 1 75 < 75
Const #2 1 1 75 < 75
Const #3 1 1 -1 -1 -1 0 = 0
Const #4 1 1 -1 -1 -1 0 = 0
Const #5 1 1 50 = 50
Const #6 1 1 60 = 60
Const #7 1 1 40 = 40

41
 Transshipment Problem: Example

Solution
ZROX
Zrox 50

5 75 1
Zeron
75 Arnold
ARNOLD
N 5
8 8
Hewes
HEWES 60
7 3 4
Super Zeron
75 Shelf
WASH
S
4 BURN
4 Rock-
Rite 40

42
 Transshipment Problem: Example
Variable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$B$4 Decision Variables x13 75 0 5 2 2
$C$4 Decision Variables x14 0 2 8 1E+30 2
$D$4 Decision Variables x23 0 4 7 1E+30 4
$E$4 Decision Variables x24 75 0 4 2 1E+30
$F$4 Decision Variables x35 50 0 1 3 1E+30
$G$4 Decision Variables x36 25 0 5 2 2
$H$4 Decision Variables x37 0 3 8 1E+30 3
$I$4 Decision Variables x45 0 3 3 1E+30 3
$J$4 Decision Variables x46 35 0 4 2 2
$K$4 Decision Variables x47 40 0 4 3 1E+30

Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$L$10 Const #3 LHS 0 5 0 0 75
$L$11 Const #4 LHS 0 6 0 0 25
$L$12 Const #5 LHS 50 6 50 0 50
$L$13 Const #6 LHS 60 10 60 0 25
$L$14 Const #7 LHS 40 10 40 0 25
$L$8 Const #1 LHS 75 0 75 1E+30 0
$L$9 Const #2 LHS 75 -2 75 25 0 43
End of Session

44