CHAPTER 9: THE TRANSPORTATION AND ASSIGNMENT PROBLEMS

9.1-1.
While growing continuously as a global company, Procter & Gamble faced the need to
restructure for enhanced effectiveness. The goal was to optimize work processes and to
minimize expenses while maintaining customer satisfaction. Lowered transportation costs
due to changes in the trucking industry and reduced product packages suggested that the
total transportation costs could be decreased. In the meantime, shorter product life cycles
justified smaller number of plants. Consequently, P&G had to decide on where to locate
the plants, what and how much to produce in each. This would be impossible without
reviewing the distribution system. Hence, two problems for each product category needed
to be solved: a distribution-location problem and a product-sourcing problem.
First, optimal distribution center (DC) locations and optimal customer assignments are
found by solving an uncapacitated facility-location model. The objective in this problem
is to minimize the total cost of transportation and supply while the primary restriction is
to satisfy customer demand. Fixed costs involved in locating DCs are ignored. The total
number of DCs is determined beforehand subjectively. The solution of this problem is an
input to the product sourcing problem.
With fixed DC locations and their capacities, product sourcing is modeled as a
transportation problem. Sources are plants, destinations are DCs and customers. The
location and capacity of the plants are specified by the product-strategy teams. Decision
variables are the amounts of demand at each destination to be met from each source. The
objective is to minimize the total cost while satisfying the demand at each destination
without exceeding the capacity of each source. The costs consist of manufacturing,
warehousing and transportation costs. An out-of-kilter algorithm is used to solve this
problem for each product category.
The benefits of this study included a reduction in the number of plants in North America
by 20% and savings of over $200 million per year. The reduction in manufacturing costs,
due to lowered number of plants and personnel coupled with improved efficiency of the
supply chain, outweighs the increase in delivery costs. The gains from this study led
P&G to making OR/MS a part of its decision-making process.
9.1-2.
(a)

9-1
(b)

(c)
Shipments Distribution Center
1 2 3 4 Total Shipped Supply
1 0 0 2 10 12 = 12
Plant 2 0 9 8 0 17 = 17
3 10 1 0 0 11 = 11
Total Received 10 10 10 10
= = = = Total Cost
Demand 10 10 10 10 $20,200

9.1-3.
(a) Let and be the number of pints purchased from Dick today and tomorrow
respectively, and be the number of pints purchased from Harry today and tomorrow
respectively.

9-2
(b)

(c)

9-3
9.1-4.
(a)

(b)

9-4
9.1-5.
Variable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$D$12 Bellingham Sacramento 0 15 464 1E+30 15
$E$12 Bellingham Salt Lake City 20 0 513 15 21
$F$12 Bellingham Rapid City 0 84 654 1E+30 84
$G$12 Bellingham Albuquerque 55 0 867 21 351
$D$13 Eugene Sacramento 80 0 352 15 1E+30
$E$13 Eugene Salt Lake City 45 0 416 21 15
$F$13 Eugene Rapid City 0 217 690 1E+30 217
$G$13 Eugene Albuquerque 0 21 791 1E+30 21
$D$14 Albert Lea Sacramento 0 728 995 1E+30 728
$E$14 Albert Lea Salt Lake City 0 351 682 1E+30 351
$F$14 Albert Lea Rapid City 70 0 388 84 1E+30
$G$14 Albert Lea Albuquerque 30 0 685 351 84

Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$D$15 Total Received Sacramento 80 -418 80 45 0
$E$15 Total Received Salt Lake City 65 -354 65 55 0
$F$15 Total Received Rapid City 70 -297 70 30 0
$G$15 Total Received Albuquerque 85 0 85 0 1E+30
$H$12 Bellingham Total Shipped 75 867 75 0 55
$H$13 Eugene Total Shipped 125 770 125 0 45
$H$14 Albert Lea Total Shipped 100 685 100 0 30

These ranges tell the management how much each individual cost can be changed
without changing the optimal solution.

9-5
9.1-6.
(a) Introduce a dummy customer 5 to represent the excess amount sent to customer 3 and
a dummy plant 4 to represent the units that are sold to, but not received by customers 4
and 5.
(a), (c), (d)
Unit Profit Customer
1 2 3 4 Dummy
1 $800 $700 $500 $200 $500
Plant 2 $500 $200 $100 $300 $100
3 $600 $400 $300 $500 $300
Dummy ($9,999) ($9,999) ($9,999) $0 $0

Shipments Customer
1 2 3 4 Dummy Total Shipped Supply
1 0 60 0 0 0 60 = 60
Plant 2 40 0 0 40 0 80 = 80
3 0 0 20 20 0 40 = 40
Dummy 0 0 0 0 60 60 = 60
Total Received 40 60 20 60 60
= = = = = Total Profit
Commitment 40 60 20 60 60 $90,000

(b), (e)
Unit Cost Customer
1 2 3 4 Dummy
1 ($800) ($700) ($500) ($200) ($500)
Plant 2 ($500) ($200) ($100) ($300) ($100)
3 ($600) ($400) ($300) ($500) ($300)
Dummy $9,999 $9,999 $9,999 $0 $0

Shipments Customer
1 2 3 4 Dummy Total Shipped Supply
1 0 60 0 0 0 60 = 60
Plant 2 40 0 0 40 0 80 = 80
3 0 0 20 20 0 40 = 40
Dummy 0 0 0 0 60 60 = 60
Total Received 40 60 20 60 60
= = = = = Total Cost
Commitment 40 60 20 60 60 -$90,000

The profit is $ .

9-6
9.1-7.
(a)

(b), (c)
Unit Cost Distribution Center
1 2 3 Dummy
Plant A $800 $700 $400 $0
B $600 $800 $500 $0

Shipments Distribution Center

1 2 3 Dummy Total Shipped Supply
Plant A 0 20 20 10 50 = 50
B 20 0 0 30 50 = 50
Total Received 20 20 20 40
= = = = Total Cost
Demand 20 20 20 40 $34,000

9.1-8.
(a) Let destination represent the demand of at center and destination
represent the extra demand up to shipped to center in the parameter table
below.

(b), (c)
Unit Cost Distribution Center
1 1 Extra 2 2 Extra 3 3 Extra Dummy
Plant A $800 $800 $700 $700 $400 $400 $0
Plant B $600 $600 $800 $800 $500 $500 $0
Dummy $99,999 $0 $99,999 $0 $99,999 $0 $999,999

Shipments Distribution Center

1 2 3 Dummy Total Shipped Supply
Plant A 0 0 10 0 10 20 10 50 = 50
Plant B 10 10 0 0 0 0 30 50 = 50
Dummy 0 10 0 20 0 0 0 30 = 30
Total Received 10 20 10 20 10 20 40
= = = = = = = Total Cost
Demand 10 20 10 20 10 20 40 $31,000

9-7
9.1-9.
(a) Let source be regular time production and be overtime production in month
. Let destination represent the contracted sales for product 1 and
represent the contracted sales for product 2 in month . Destination 7 is dummy.

(b)

Hence, the total cost is $ and no overtime is necessary.

9.2-1.
(a) Vogel's approximation method would choose as the first basic variable.

9-8
(b) Russell's approximation method would choose as the first basic variable.

(c) Initial BF solution using northwest corner rule:

9-9
9.2-2.
(a) Northwest Corner Rule

Cost:
(b) Vogel's Approximation Method

Cost:

9-10
(c) Russell's Approximation Method

Cost:
Note that Vogel's and Russell's approximation methods return an optimal solution.
9.2-3.
(a) Northwest Corner Rule

Cost:

9-11
(b) Vogel's Approximation Method

Cost:
Arbitrarily breaking the tie differently returns the solution below with cost .

(c) Russell's Approximation Method

Cost:

9-12
9.2-4.
(a) All the supply and demand values are integers. By the integer solutions property, the
resulting basic feasible solutions will be integral. All the supplies and demands are one,
so the only possible values of the variables in a basic feasible solution are and . The
's indicate the assignment of a source to a destination.
(b) There are basic variables in every basic feasible solution and of them are
degenerate.
(d) The variables are chosen in the order .

9-13
(c) - (e)

Optimal assignment (source,destination): , cost:

9-14
9.2-5.

Cost: $ , for all and , so the solution is optimal.

9.2-6.

9-15
The current solution is optimal: and
, with cost . The optimality condition for all and is met.

9-16
9.2-7.
(a) Northwest Corner Rule

3 iterations are required to reach optimality.

9-17
(b) Vogel's Approximation Method

The solution is optimal, no iteration of network simplex is needed.

(c) Russell's Approximation Method

The solution is optimal, no iteration of network simplex is needed.

9.2-8.
(a)

9-18
(b)

(c)

9-19
9-20
Optimal Solution: , cost: $ .

9.2-9.
(a) Since there is no limit on the electricity and natural gas available, let the supply of
electricity be the sum of demands for electricity, water and space heating and the supply
of natural gas be the sum of demands for water and space heating.

9-21
(b), (c)

9-22
9-23
The optimal solution is to meet 2 units of electricity with electricity, 1 units of space
heating with natural gas, 10 units of water heating with solar heating, and 2 units of
space heating with solar heating. The cost is $2,6 .

9-24
(d), (e) The initial basic feasible solution provides the same optimal solution as in (c).

(f) The initial basic feasible solution provides the same optimal solution as in (c).

(g) The initial BF solution using Vogel's and Russell's methods provides the same
optimal solution as in (c). The optimal solution obtained starting from each of the three
rules is the same. (c) required four iterations of the transportation simplex while (d) and
(f) required none..

9-25
9.2-10.
Vogel's Approximation Method

Optimal Solution:
Quantity Production Month Installation Month

This schedule incurs a cost of million dollars.

9-26
9.2-11.
(a)

(b)

9-27
9-28
The optimal solution is to send shipments from plant 1 to center 3, to center 4,
from plant 2 to center 2, to center 3, from plant 3 to center 1 and to center 2. This
has a total cost of $ .
9.2-12.

The optimal solution is to purchase pints from Dick tomorrow and pints from Harry
today, with a cost $ .

9-29
9.2-13.

9-30
9-31
9-32
Optimal Solution:

Cost: $

9-33
9.2-14.
Using Russell's approximation method:

9-34
The optimal solution is to ship units from plant 1 to customer 2, from plant 2 to
customer 1, from plant 2 to customer 4, from plant 3 to customer 3 and 4. This
offers a profit of $ .

9-35
9.2-15.
(a) - (b) - (c)
Using northwest corner rule:

With northwest corner rule, it took seconds to find the initial BF solution and its
objective value is % above the optimal cost. The two iterations took seconds.

9-36
Using Vogel's approximation method:

With Vogel's approximation method, it took seconds to find the initial BF solution and
its objective value is % above the optimal cost. One iteration took seconds.
Using Russell's approximation method:

9-37
With Russell's approximation method, it took seconds to find the initial BF solution
and its objective value is % above the optimal cost. The two iterations took seconds.
Let denote the initial BF solution. The results are summarized in the following table.
Method Time to Get Opt. Gap of No. Iter.'ns Time Iter.'ns Total Time
NW Corner seconds % seconds seconds
Vogel's seconds % seconds seconds
Russell's seconds % seconds seconds
9.2-16.
(a) - (b) - (c)
Using northwest corner rule:

9-38
With northwest corner rule, it took seconds to find the initial BF solution and its
objective value is % above the optimal cost. The seven iterations took minutes.
Using Vogel's approximation method:

With Vogel's approximation method, it took seconds to find the initial BF solution and
its objective value is % above the optimal cost. The two iterations took minute.
Using Russell's approximation method:

With Russell's approximation method, it took seconds to find the initial BF solution
and its objective value is % above the optimal cost. The five iterations took minutes.
Optimal Solution: cost

Let denote the initial BF solution. The results are summarized in the following table.
Method Time to Get Opt. Gap of No. Iter.'ns Time Iter.'ns Total Time
NW Corner seconds % minutes seconds
Vogel's seconds % minute seconds
Russell's seconds % minutes seconds

9-39
9.2-17.
(a) Initial solution using northwest corner rule:

Final tableau: cost

(b) minimize
subject to

Hence, the transportation simplex method takes one iteration while the general simplex
method takes four iterations. The computation times vary.

9-40
9.2-18.
Let

.
minimize
subject to

Initial simplex tableau:

Simplex tableau: variables and constraints

Transportation tableau: variables and constraints
Even though the transportation tableau is larger, it requires less work than the simplex
tableau.
9.2-19.
If we multiply the demand constraints by , each constraint column will have exactly
two nonzero entries, one and one . Summing all these constraints gives the
equality:
supplies demands ,
since the total supply equals the total demand. Hence, there is a redundant constraint.

9-41
9.2-20.
In the initialization step, after selecting the next basic variable, the allocation made is
equal to either the (remaining) supply or demand for that row or column. Since these
quantities are known to be integer, the allocation will be integer.
Given a current BF solution that is integer, step 3 of an iteration adds and subtracts,
around the chain-reaction cycle, the current value of the leaving basic variable. Since we
know this is an integer, and all the other basic variables on the cycle began with integer
values, the new BF solution must be all integer.
During the initialization step, we can select the next basic variable for allocation
arbitrarily from among the rows and columns not already eliminated. Thus, by altering
our selections, we can construct any BF solution as our initial one. Because we have
shown that the initialization step gives integer solutions, all BF solutions must be integer.
9.2-21.
(a) Let be the number of tons hauled from pit (North, South) to site .
minimize
subject to

Initial tableau:

(b) This table is much smaller than the simplex tableau and it stores the same information.

9-42
(c) The solution is not optimal, since .

(d)

9-43
The optimal solution is to haul tons from the north pit to site 1 and tons to site 3,
tons from the south pit to site 2 and tons from the south pit to site 3. This incurs a cost
of $ .
(e) From the reduced costs in the final tableau, we see that

.
If the contractor can negotiate a hauling cost per ton of or less from the north pit to
site 2, or of or less from the south pit to site 1, a new solution using these options
would give a cost at least as small as the current optimal cost $ .

9-44
9.2-22.
Variable Cells
Final Reduced Objective Allowable Allowable
Cell Name Value Cost Coefficient Increase Decrease
$C$11 Colombo River Berdoo 0 0 160 1E+30 0
$D$11 Colombo River Los Devils 5 0 130 20 1E+30
$E$11 Colombo River San Go 0 10 220 1E+30 10
$F$11 Colombo River Hollyglass 0 0 170 0 20
$C$12 Sacron River Berdoo 2 0 140 0 1E+30
$D$12 Sacron River Los Devils 0 20 130 1E+30 20
$E$12 Sacron River San Go 2.5 0 190 10 10
$F$12 Sacron River Hollyglass 1.5 0 150 20 0
$C$13 Calorie River Berdoo 0 10 190 1E+30 10
$D$13 Calorie River Los Devils 0 50 200 1E+30 50
$E$13 Calorie River San Go 1.5 0 230 10 20
$F$13 Calorie River Hollyglass 0 -190 0 1E+30 190

Constraints
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$C$14 Total To City Berdoo 2 180 2 2.5 1.5
$D$14 Total To City Los Devils 5 150 5 0 1.5
$E$14 Total To City San Go 4 230 4 3.5 1.5
$F$14 Total To City Hollyglass 1.5 190 1.5 2.5 1.5
$G$11 Colombo River From River 5 -20 5 1.5 0
$G$12 Sacron River From River 6 -40 6 1.5 2.5
$G$13 Calorie River From River 1.5 0 5 1E+30 3.5

(a) The optimal solution would change because the decrease of $ million is outside the
allowable decrease of $ million.
(b) The optimal solution would remain the same, since the allowable increase is .
(c) By the % rule for simultaneous changes, the optimal solution must remain the
same.
: $ $ % of allowable decrease %

: $ $ % of allowable decrease %

These sum up to %.
(d) By the % rule for simultaneous changes, the shadow prices may or may not
remain valid.
: $ $ % of allowable decrease %

: $ $ % of allowable decrease %

These sum up to %.

9-45
9.2-23.
(a) ,

The current feasible solution is feasible, but not optimal.

(b)
We can revise the tableau by changing from to . This causes to
change to , to , and to .
(reduced cost (reduced cost (reduced cost
(reduced cost (reduced cost
(reduced cost (reduced cost

9-46
The basic solution remains feasible and optimal.
(c)

The basic solution remains feasible and optimal.

9-47
(d) and

This solution satisfies the optimality criterion, but it is infeasible.

9.3-1.
(a)

9-48
(b)

(c), (d)
Unit Cost Task
1 2 3 4
A $8 $6 $5 $7
Assignee B $6 $5 $3 $4
C $7 $8 $4 $6
D $6 $7 $5 $6

Assignments Task Total

1 2 3 4 Assignments Supply
A 0 1 0 0 1 = 1
Assignee B 0 0 0 1 1 = 1
C 0 0 1 0 1 = 1
D 1 0 0 0 1 = 1
Total Assigned 1 1 1 1
= = = = Total Cost
Demand 1 1 1 1 $20

9.3-2.
(a) Ships are assignees and ports are assignments.
(b)

Optimal Solution:

This incurs a cost of $ .

9-49
(c)

(d) - (e)

9-50
9-51
One optimal assignment is: , where the first entry is ship and
the second port.

9-52
(f) Continuing to pivot where reduced costs are zero:

Alternative optimal matching:

Alternative optimal matching:

9-53
Alternative optimal matching:
9.3-3.
(a)

(b) The optimal cost is $34,960.

9-54
(c)

(d)

The initial solution from Vogel's approximation method is optimal. Plant 2 produces
product 3, plant 4 produces product 2, plant 5 produces product 1. This incurs a cost of
$34,960.

9-55
9.3-4.
(a) After adding a dummy stroke, which everyone can swim in zero seconds, the problem
becomes that of assigning swimmers to strokes. The optimal solution turns out to be
the following: David swims the backstroke, Tony swims the breaststroke, Chris swims
the butterfly, and Carl swims the freestyle.

(b) Cost:

9.3-5.
(a)

(b) - (c)

Since all the reduced costs are nonnegative, this solution is optimal.

9-56
(d)

This is identical to the table in (a) except that plants 1 and 2 have been split into two
plants each.
(e)

The basic feasible solution for the transformed problem above corresponds to that given
in part (c).

9-57
9.3-6.

9-58
This solution corresponds to that given in Section 9.3; although the set of basic variables
is different, the values of the variables are the same.

9-59
9.3-7.
(a) Let assignees 1 and 2 represent plant A, assignees 3 and 4 represent plant B, and the
tasks be the distribution centers.

(b) Cost:

(c)

(d)

(e)

9-60
(f)

9.3-8.
(a)

(b)

(c)

(d) A transportation problem of size has basic variables. Since

for the assignment problem, there are basic variables, but only
assignments. Thus, basic variables are degenerate, they equal zero. Assignment
problems are always highly degenerate. This can be seen using the interactive routine in
the OR Courseware.
(e) and one of are nonbasic, too. and one of are
basic and equal zero.

9-61
Dual variables:

Looking at , we see that the allowable ranges for this solution to stay optimal
are: .
9.3-9.

minimize

subject to for

for

for
The table of constraint coefficients is identical to that for the transportation problem
(Table 9.6). The assignment problem has a more special structure because and
for every .
9.4-1.
Start with:

9-62
Subtract the minimum element from each element in the column and continue the
algorithm.

One optimal solution is to assign ships to ports , with cost .

9.4-2.
Subtract the minimum element in each row from each element in the row and continue
the algorithm.

One optimal solution is that David swims the backstroke, Tony the breaststroke, Chris
the butterfly and Carl the freestyle. The total time is .

9-63
9.4-3.
Cost:

9.4-4.
Subtract the minimum element in each row from every element in the row and continue
the algorithm. This gives an optimal solution with cost .

9.4-5.
Subtract the minimum element in each column from every element in the column and
continue the algorithm.

An optimal assignment is , with cost .

9-64
9.4-6. Subtracting the minimum element in each row from each element in the row, and
then continuing the algorithm, we get:

An optimal assignment is (A, 1), (B, 3), (C, 4), (D, 2). Cost = 16.information is needed to
determine this.

9-65
Case%9.1%
! Option!1!(Shipping!by!Rail):!

!
!
! Option!2!(Shipping!by!Ship):!

!
!

9-66
! Option!3!(Shipping!by!Best!Available!for!each!Route):!

!
!
! When!comparing!the!three!options,!it!is!best!to!use!the!combination!plan,!while!
shipping!entirely!by!rail!leads!to!the!highest!costs.!
!
If!costs!of!shipping!by!water!are!expected!to!rise!considerably!more!than!for!
shipping!by!rail,!stay!with!rail!and!use!Option!1.!!If!the!reverse!is!true,!then!use!
Option!2.!!If!the!cost!comparisons!will!remain!roughly!the!same,!use!Option!3.!!
Option!3!is!clearly!the!most!feasible!but!may!not!be!chosen!if!it!is!too!logistically!
cumbersome.!!More!knowledge!of!the!situation!is!necessary!to!determine!this.!
%

9-67
Case%9.2%
! a)! $20!million!is!saved!in!comparison!with!the!results!in!Figure!6.13!by!shipping!20!
million!fewer!barrels!to!Charleston!and!20!million!more!to!St.!Louis.!
B C D E F G H I J
3 Refineries
4 Unit Cost ($millions) New Orleans Charleston Seattle St. Louis
5 Texas 2 4 5 1
6 Oil California 5 5 3 4
7 Fields Alaska 5 7 3 7
8 Middle East 2 3 5 4
9
10
11 Shipment Quantity Refineries
12 (millions of barrels) New Orleans Charleston Seattle St. Louis Total Shipped Supply
13 Texas 0 0 0 80 80 = 80
14 Oil California 0 0 0 60 60 = 60
15 Fields Alaska 20 0 80 0 100 = 100
16 Middle East 80 40 0 0 120 = 120
17 Total Received 100 40 80 140
18 <= <= <= <= Total Cost
19 Capacity 100 60 80 150 ($millions)
20 940 !
! b)! $40!million!is!saved!in!comparison!with!the!results!in!Figure!6.17.!
B C D E F G H I J
3 Distribution Center
4 Unit Cost ($millions) Pittsburgh Atlanta Kansas City San Francisco
5 New Orleans 6.5 5.5 6 8
6 Refineries Charleston 7 5 4 7
7 Seattle 7 8 4 3
8 St. Louis 4 3 1 5
9
10
11 Shipment Quantity Distribution Center
12 (millions of barrels) Pittsburgh Atlanta Kansas City San Francisco Total Shipped Supply
13 New Orleans 60 40 0 0 100 = 100
14 Refineries Charleston 0 40 0 0 40 = 40
15 Seattle 0 0 0 80 80 = 80
16 St. Louis 40 0 80 20 140 = 140
17 Total Received 100 80 80 100
18 = = = = Total Cost
19 Demand 100 80 80 100 ($millions)
20 1,390

!
!
The!cost!of!shipping!both!crude!oil!and!finished!product!under!this!plan!is!$940!
million!+!$1,390!million!=!$2,330!million!or!$2.33!billion!—!a!savings!of!$60!
million!compared!to!the!original!results!in!Table!6.20.!

9-68
! c)! $35!million!is!saved!in!comparison!with!the!results!in!part!(b).!!
$75!million!is!saved!in!comparison!with!the!results!in!Figure!6.17.!
B C D E F G H I J
3 Distribution Center
4 Unit Cost ($millions) Pittsburgh Atlanta Kansas City San Francisco
5 New Orleans 6.5 5.5 6 8
6 Refineries Charleston 7 5 4 7
7 Seattle 7 8 4 3
8 St. Louis 4 3 1 5
9
10
11 Shipment Quantity Distribution Center
12 (millions of barrels) Pittsburgh Atlanta Kansas City San Francisco Total Shipped Capacity
13 New Orleans 50 20 0 0 70 <= 100
14 Refineries Charleston 0 60 0 0 60 <= 60
15 Seattle 0 0 0 80 80 <= 80
16 St. Louis 50 0 80 20 150 <= 150
17 Total Received 100 80 80 100
18 = = = = Total Cost
19 Demand 100 80 80 100 ($millions)
20 1,355 !
! d)! This!solution!costs!$40!million!more!than!the!solution!in!part!(a).!
This!solution!costs!$20!million!more!than!the!solution!is!Figure!6.13.!
B C D E F G H I J
3 Refineries
4 Unit Cost ($millions) New Orleans Charleston Seattle St. Louis
5 Texas 2 4 5 1
6 Oil California 5 5 3 4
7 Fields Alaska 5 7 3 7
8 Middle East 2 3 5 4
9
10
11 Shipment Quantity Refineries
12 (millions of barrels) New Orleans Charleston Seattle St. Louis Total Shipped Supply
13 Texas 0 0 0 80 80 = 80
14 Oil California 0 0 0 60 60 = 60
15 Fields Alaska 10 0 80 10 100 = 100
16 Middle East 60 60 0 0 120 = 120
17 Total Received 70 60 80 150
18 = = = = Total Cost
19 Demand 70 60 80 150 ($millions)
20 980

!
!
The!total!cost!of!shipping!both!crude!oil!and!finished!product!under!this!plan!is!
$1,355!million!+!$980!million!=!$2,335!million!or!$2.335!billion.!This!is!$5!
million!more!than!the!cost!of!the!combined!total!obtained!in!part!(b),!but!$55!
million!less!than!the!total!in!Table!6.20.!

9-69
! e)! The!two!transportation!problems!(shipping!to!refineries!and!shipping!to!
distributions!centers)!are!combined!into!a!single!model.!The!amount!shipped!to!
the!refineries!is!constrained!to!be!no!more!than!capacity:!
TotalReceived(D16:G16)!≤!Capacity(D18:G18).!The!total!shipped!out!of!the!
refineries!is!constrained!to!equal!the!total!amount!shipped!in:!
ShippedOut(H31:H34)!=!ShippedIn(J31:J34).!The!goal!is!to!minimize!the!total!
combined!cost!(in!J45)!which!is!the!sum!of!the!two!intermediate!costs!(in!J20!
and!J39).!
!
A B C D E F G H I J
1 Shipping to Refineries
2 Refineries
3 Unit Cost ($millions) New Orleans Charleston Seattle St. Louis
4 Texas 2 4 5 1
5 Oil California 5 5 3 4
6 Fields Alaska 5 7 3 7
7 Middle East 2 3 5 4
8
9
10 Shipment Quantity Refineries
11 (millions of barrels) New Orleans Charleston Seattle St. Louis Total Shipped Supply
12 Texas 0 0 0 80 80 = 80
13 Oil California 0 0 0 60 60 = 60
14 Fields Alaska 20 0 80 0 100 = 100
15 Middle East 80 30 0 10 120 = 120
16 Total Received 100 30 80 150
17 <= <= <= <= Cost
18 Capacity 100 60 80 150 (Oil Fields --> Refineries)
19 ($millions)
20 Shipping to Distribution Centers 950
21 Distribution Center
22 Unit Cost ($millions) Pittsburgh Atlanta Kansas City San Francisco
23 New Orleans 6.5 5.5 6 8
24 Refineries Charleston 7 5 4 7
25 Seattle 7 8 4 3
26 St. Louis 4 3 1 5
27
28
29 Shipment Quantity Distribution Center
30 (millions of barrels) Pittsburgh Atlanta Kansas City San Francisco Shipped Out Shipped In
31 New Orleans 100 0 0 0 100 = 100
32 Refineries Charleston 0 10 0 20 30 = 30
33 Seattle 0 0 0 80 80 = 80
34 St. Louis 0 70 80 0 150 = 150
35 Total Received 100 80 80 100
36 = = = = Cost
37 Demand 100 80 80 100 (Refineries --> D.C.'s)
38 ($millions)
39 1,370
40
41 Combined
42 Total
43 Cost
44 ($millions)
45 2,320

!
!
The!total!combined!cost!is!$2,320!million!or!$2.32!billion,!which!is!$10!million!
less!than!in!part!(b),!$15!million!less!than!in!part!(d),!and!$70!million!less!than!in!
Table!6.20.!

9-70
! f)! If!the!Los!Angeles!refinery!is!chosen!instead,!then!the!combined!shipping!cost!is!
$2,450!million.!
!
A B C D E F G H I J
1 Shipping to Refineries
2 Refineries
3 Unit Cost ($millions) New Orleans Charleston Seattle Los Angeles
4 Texas 2 4 5 3
5 Oil California 5 5 3 1
6 Fields Alaska 5 7 3 4
7 Middle East 2 3 5 4
8
9
10 Shipment Quantity Refineries
11 (millions of barrels) New Orleans Charleston Seattle St. Louis Total Shipped Supply
12 Texas 40 0 0 40 80 = 80
13 Oil California 0 0 0 60 60 = 60
14 Fields Alaska 0 0 80 20 100 = 100
15 Middle East 60 60 0 0 120 = 120
16 Total Received 100 60 80 120
17 <= <= <= <= Cost
18 Capacity 100 60 80 150 (Oil Fields --> Refineries)
19 ($millions)
20 Shipping to Distribution Centers 880
21 Distribution Center
22 Unit Cost ($millions) Pittsburgh Atlanta Kansas City San Francisco
23 New Orleans 6.5 5.5 6 8
24 Refineries Charleston 7 5 4 7
25 Seattle 7 8 4 3
26 Los Angeles 8 6 3 2
27
28
29 Shipment Quantity Distribution Center
30 (millions of barrels) Pittsburgh Atlanta Kansas City San Francisco Shipped Out Shipped In
31 New Orleans 80 20 0 0 100 = 100
32 Refineries Charleston 0 60 0 0 60 = 60
33 Seattle 20 0 60 0 80 = 80
34 St. Louis 0 0 20 100 120 = 120
35 Total Received 100 80 80 100
36 = = = = Cost
37 Demand 100 80 80 100 (Refineries --> D.C.'s)
38 ($millions)
39 1,570
40
41 Combined
42 Total
43 Cost
44 ($millions)
45 2,450
!

9-71
! ! If!the!Galveston!refinery!is!chosen!instead,!then!the!combined!shipping!cost!is!
$2,470!million.!
!
A B C D E F G H I J
1 Shipping to Refineries
2 Refineries
3 Unit Cost ($millions) New Orleans Charleston Seattle Galveston
4 Texas 2 4 5 1
5 Oil California 5 5 3 3
6 Fields Alaska 5 7 3 5
7 Middle East 2 3 5 3
8
9
10 Shipment Quantity Refineries
11 (millions of barrels) New Orleans Charleston Seattle Galveston Total Shipped Supply
12 Texas 0 0 0 80 80 = 80
13 Oil California 0 0 0 60 60 = 60
14 Fields Alaska 10 0 80 10 100 = 100
15 Middle East 90 30 0 0 120 = 120
16 Total Received 100 30 80 150
17 <= <= <= <= Cost
18 Capacity 100 60 80 150 (Oil Fields --> Refineries)
19 ($millions)
20 Shipping to Distribution Centers 870
21 Distribution Center
22 Unit Cost ($millions) Pittsburgh Atlanta Kansas City San Francisco
23 New Orleans 6.5 5.5 6 8
24 Refineries Charleston 7 5 4 7
25 Seattle 7 8 4 3
26 Galveston 5 4 3 6
27
28
29 Shipment Quantity Distribution Center
30 (millions of barrels) Pittsburgh Atlanta Kansas City San Francisco Shipped Out Shipped In
31 New Orleans 100 0 0 0 100 = 100
32 Refineries Charleston 0 0 30 0 30 = 30
33 Seattle 0 0 0 80 80 = 80
34 Galveston 0 80 50 20 150 = 150
35 Total Received 100 80 80 100
36 = = = = Cost
37 Demand 100 80 80 100 (Refineries --> D.C.'s)
38 ($millions)
39 1,600
40
41 Combined
42 Total
43 Cost
44 ($millions)
45 2,470
!
! ! !
! Total!Cost! Total!Cost! Operating!Cost! Total!
! of!Shipping! of!Shipping! for!New! Variable!
Site! Crude!Oil! Finished!Product! Refinery! Cost!
Los!Angeles! $880!million! $1.57!billion! $620!million! $3.07!billion!
Galveston! 870!million! 1.60!billion! 570!million! 3.12!billion!
St.!Louis! 950!million! 1.37!billion! 530!million! 2.92!billion!
!
! g)! Answers!will!vary.!
!

9-72
Case%9.3%
! a)! Assign!one!scientist!to!each!of!the!five!projects!to!maximize!the!total!number!of!
bid!points.!
!
A B C D E F G H I
1 Bid Project Up Project Stable Project Choice Project Hope Project Release
2 Dr. Kvaal 100 400 200 200 100
3 Dr. Zuner 0 200 800 0 0
4 Dr. Tsai 100 100 100 100 600
5 Dr. Mickey 267 153 99 451 30
6 Dr. Rollins 100 33 33 34 800
7
8 Total
9 Assignment Project Up Project Stable Project Choice Project Hope Project Release Assignments Supply
10 Dr. Kvaal 0 1 0 0 0 1 = 1
11 Dr. Zuner 0 0 1 0 0 1 = 1
12 Dr. Tsai 1 0 0 0 0 1 = 1
13 Dr. Mickey 0 0 0 1 0 1 = 1
14 Dr. Rollins 0 0 0 0 1 1 = 1
15 Total Assigned 1 1 1 1 1
16 = = = = = Total Bid Points
17 Demand 1 1 1 1 1 2551

!
!
To!maximize!the!scientists!preferences!you!want!to!assign!Dr.!Tsai!to!lead!
project!Up,!Dr.!Kvaal!to!lead!project!Stable,!Dr.!Zuner!to!lead!project!Choice,!Dr.!
Mickey!to!lead!project!Hope,!and!Dr.!Rollins!to!lead!project!Release.!
!
! b)! Since!there!are!only!four!assignees,!we!introduce!a!dummy!assignee!with!
preferences!of!–1.!The!task!that!gets!assigned!the!dummy!assignee!will!not!be!
done.!!
!

!
!
Project!Up!would!not!be!done.!

9-73
! c)! Since!two!of!the!assignees!can!do!two!tasks,!we!need!to!double!them.!We!include!
assignees!Zunerg1,!Zunerg2,!Mickeyg1,!and!Mickeyg2!into!the!problem.!In!order!
to!have!an!equal!number!of!assignees!and!tasks!we!also!need!to!include!one!
dummy!task.!In!order!to!ensure!that!neither!Dr.!Kvall!nor!Dr.!Tsai!can!get!
assigned!the!dummy!task!and!thus!no!project,!we!insert!a!large!negative!number!
as!their!point!bid!for!the!dummy!project.!!
!

!
!
Dr.!Kvaal!leads!project!Stable,!Dr.!Zuner!leads!project!Choice,!Dr.!Tsai!leads!
project!Release,!and!Dr.!Mickey!leads!the!projects!Hope!and!Up.!
! d)! Under!the!new!bids!of!Dr.!Zuner!the!assignment!does!not!change:!
!

!
! e)! Certainly!Dr.!Zuner!could!be!disappointed!that!she!is!not!assigned!to!project!
Stable,!especially!when!she!expressed!a!higher!preference!for!that!project!than!
the!scientist!assigned.!The!optimal!solution!maximizes!the!preferences!overall,!
but!individual!scientists!may!be!disappointed.!We!should!therefore!make!sure!to!
communicate!the!reasoning!behind!the!assignments!to!the!scientists.!

9-74
! f)! Whenever!a!scientist!cannot!lead!a!particular!project!we!use!a!large!negative!
number!as!the!point!bid.!
!

!
!
Dr.!Kvaal!leads!project!Stable,!Dr.!Zuner!leads!project!Choice,!Dr.!Tsai!leads!
project!Release,!Dr.!Mickey!leads!project!Up,!and!Dr.!Rollins!leads!project!Hope.!
! g)! When!we!want!to!assign!two!assignees!to!the!same!task!we!need!to!duplicate!
that!task.!
!

!
!
Project!Up!is!led!by!Dr.!Mickey,!Stable!by!Dr.!Kvaal,!Choice!by!Dr.!Zuner,!Hope!by!
Dr.!Arriaga!and!Dr.!Santos,!and!Release!by!Dr.!Tsai!and!Dr.!Rollins.!
! h)! No.!Maximizing!overall!preferences!does!not!maximize!individual!preferences.!
Scientists!who!do!not!get!their!first!choice!may!become!resentful!and!therefore!
lack!the!motivation!to!lead!their!assigned!project.!For!example,!in!the!optimal!
solution!of!part!(g),!Dr.!Santos!clearly!elected!project!Release!as!his!first!choice,!
but!he!was!assigned!to!lead!project!Hope.!
!
In!addition,!maximizing!preferences!ignores!other!considerations!that!should!be!
factored!into!the!assignment!decision.!For!example,!the!scientist!with!the!highest!
preference!for!a!project!may!not!be!the!scientist!most!qualified!to!lead!the!
project.!

9-75