Transportation, Assignment, and

Transshipment Problems
 Transportation Problem
•Network Representation and LP Formulation
•Transportation Simplex Method
•Transportation Algorithms
 North-West Corner Method

 Least Cost Method

 Vogel’s Approximation Method

 Optimality Test : Modified Distribution Method

Slide 1
 Assignment Problem
•Network Representation and LP Formulation
•Hungarian Method
 The Transshipment Problem
•Network Representation and LP Formulation

Slide 2
 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.

Slide 3
 Transshipment Problem

 Network Representation
c36
3
c13
c37
s1 1 c14 6 d1
c15 c46
Supply 4 c47 Demand
c23
c24 c56
s2 2 7 d2
c25
5 c57

SOURCES INTERMEDIATE DESTINATIONS

NODES

Slide 4
 Transshipment Problem

 Linear Programming Formulation

xij represents the shipment from node i to node j

Min cijxij
ij
s.t. xij < si for each origin i
j
xik - xkj = 0 for each intermediate
i j node k
xij = dj for each destination j
i
xij > 0 for all i and j

Slide 5
 Example: Transshipping

Thomas Industries and Washburn Corporation

supply three firms (Zrox, Hewes, Rockwright) 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 Rockwright. Both
Arnold and Supershelf can supply at most 75 units to
its customers.
Additional data is shown on the next slide.

Slide 6
 Example: Transshipping

Because of long standing contracts based on past

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

Thomas Washburn
Arnold 5 8
Supershelf 7 4

The costs to install the shelving at the various

locations are:

Zrox Hewes Rockwright

Thomas 1 5 8
Washburn 3 4 4

Slide 7
 Example: Transshipping

 Network Representation
Zrox
ZROX
50
N5

1
Arnold 5 Thomas
75 N1
ARNOLD
N3 5
8 8
Hewes
HEWES
N6 60

7 3
Super Wash-
4
75 Shelf Burn
WASH

N2 4 BURN
N4 4 Rock-
Wright 40
N7

Slide 8
 Example: Transshipping

 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 (Thomas), 4 (Washburn)
k = 5 (Zrox), 6 (Hewes), 7 (Rockwright)
•Objective Function Defined
Minimize Overall Shipping Costs:
Min 5x13 + 8x14 + 7x23 + 4x24 + 1x35 + 5x36 + 8x37
+ 3x45 + 4x46 + 4x47

Slide 9
 Example: Transshipping

 Constraints Defined
Amount Out of Arnold: x13 + x14 < 75
Amount Out of Supershelf: x23 + x24 < 75
Amount Through Thomas: x13 + x23 - x35 - x36 - x37 = 0
Amount Through Washburn: x14 + x24 - x45 - x46 - x47 = 0
Amount Into Zrox: x35 + x45 = 50
Amount Into Hewes: x36 + x46 = 60
Amount Into Rockwright: x37 + x47 = 40

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

Slide 10
 Example: Transshipping

 Optimal Solution (from The Management Scientist )

Objective Function Value = 1150.000

Variable Value Reduced Costs
X13 75.000 0.000
X14 0.000 2.000
X23 0.000 4.000
X24 75.000 0.000
X35 50.000 0.000
X36 25.000 0.000
X37 0.000 3.000
X45 0.000 3.000
X46 35.000 0.000
X47 40.000 0.000

Slide 11
 Example: Transshipping

 Optimal Solution
ZROX
Zrox 50

75 1
5
75 ARNOLD
Arnold Thomas 5
8 8
Hewes
HEWES 60

7 3 4
Super Wash-
75 Shelf
WASH
Burn
4 BURN
4
Rock-
Wright 40

Slide 12
 Example: Transshipping

 Optimal Solution (continued)

Constraint Slack/Surplus Dual Prices

1 0.000 0.000
2 0.000 2.000
3 0.000 -5.000
4 0.000 -6.000
5 0.000 -6.000
6 0.000 -10.000
7 0.000 -10.000

Slide 13
 Example: Transshipping

 Optimal Solution (continued)

OBJECTIVE COEFFICIENT RANGES

Variable Lower Limit Current Value Upper Limit
X13 3.000 5.000 7.000
X14 6.000 8.000 No Limit
X23 3.000 7.000 No Limit
X24 No Limit 4.000 6.000
X35 No Limit 1.000 4.000
X36 3.000 5.000 7.000
X37 5.000 8.000 No Limit
X45 0.000 3.000 No Limit
X46 2.000 4.000 6.000
X47 No Limit 4.000 7.000

Slide 14
 Example: Transshipping

 Optimal Solution (continued)

RIGHT HAND SIDE RANGES

Constraint Lower Limit Current Value Upper Limit
1 75.000 75.000 No Limit
2 75.000 75.000 100.000
3 -75.000 0.000 0.000
4 -25.000 0.000 0.000
5 0.000 50.000 50.000
6 35.000 60.000 60.000
7 15.000 40.000 40.000

Slide 15
Slide 16