Transportation and Assignment Problems

Transportation and Assignment Problems

Chapter 7

Transportation and Assignment Problems

Learning Objectives

1. Be able to identify the special features of the transportation problem.

2. Become familiar with the types of problems that can be solved by applying a transportation model.

3. Be able to develop network and integer programming models of the transportation problem.

4. Know how to handle the cases of (1) unequal supply and demand, (2) unacceptable routes, and (3) maximization objective for a transportation problem.

5. Be able to identify the special features of the assignment problem.

6. Become familiar with the types of problems that can be solved by applying an assignment model.

7. Be able to develop network and integer programming models of the assignment problem.

8. Understand the following terms.

transportation problem

source/origin assignment problem

destination network model

Solutions:

4. a.

b. Let xij = Amount shipped from plant i to warehouse j

7 - XXX

Transportation and Assignment Problems

Min / 20x11 / + / 16x12 / + / 24x13 / + / 10x21 / + / 10x22 / + / 8x23 / + / 12x31 / + / 18x32 / + / 10x33
s.t.
x11 / + / x12 / + / x13 / £ / 300
x21 / + / x22 / + / x23 / £ / 500
x31 / + / x32 / + / x33 / £ / 100
x11 / + / x21 / + / x31 / = / 200
x12 / + / x22 / + / x32 / = / 400
x13 / + / x23 / + / x33 / = / 300

xij ³ 0 and integer, i = 1, 2, 3; j = 1, 2, 3

Storm Output using Transportation Module:

bubba - problem 7.4

TRANSPORTATION - OPTIMAL SOLUTION - SUMMARY REPORT

------Cell ------Unit Cell

Row Column Amount COST COST

P1 W2 300 16.0000 4800.0000

P1 Subtotal = 4800.0000

P2 W1 100 10.0000 1000.0000

P2 W2 100 10.0000 1000.0000

P2 W3 300 8.0000 2400.0000

P2 Subtotal = 4400.0000

P3 W1 100 12.0000 1200.0000

P3 Subtotal = 1200.0000

Total Cost = 10400.0000

Number of iterations = 1

c. The only change necessary, if the data are profit values, is to change the objective to one of maximization.

New Storm Output using Transportation Module:

bubba - problem 7.4c

TRANSPORTATION - OPTIMAL SOLUTION - SUMMARY REPORT

------Cell ------Unit Cell

Row Column Amount PAYOFF PAYOFF

P1 W3 300 24.0000 7200.0000

P1 Subtotal = 7200.0000

P2 W1 200 10.0000 2000.0000

P2 W2 300 10.0000 3000.0000

P2 Subtotal = 5000.0000

P3 W2 100 18.0000 1800.0000

P3 Subtotal = 1800.0000

Total Payoff = 14000.0000

Number of iterations = 1

8. The network model, the integer programming formulation, and the optimal solution are shown.

Decision Variables:

Note that the third “supply constraint” corresponds to the imaginary/dummy source. The variables x31, x32, x33, and x34 are the amounts “shipped” out of the dummy source [i.e., demands that are NOT met]; they do not appear in the objective function since they are given a coefficient of zero.

Storm Output using Transportation Module:

bubba - problem 7.8

TRANSPORTATION - OPTIMAL SOLUTION - SUMMARY REPORT

------Cell ------Unit Cell

Row Column Amount PAYOFF PAYOFF

CLIFTON SP D2 4000 34.0000136000.0000

CLIFTON SP D4 1000 40.0000 40000.0000

CLIFTON SP Subtotal = 176000.0000

DANVILLE D1 2000 34.0000 68000.0000

DANVILLE D4 1000 38.0000 38000.0000

DANVILLE Subtotal = 106000.0000

Dummy D2 1000 0.0000 0.0000

Dummy D3 3000 0.0000 0.0000

Dummy Subtotal = 0.0000

Total Payoff = 282000.0000

Number of iterations = 3

Interpretation of optimal solution:

The Clifton Springs plant should produce 4,000 units for customer D2 and 1,000 units for customer D4.

The Danville plant should produce 2,000 units for customer D1 and 1,000 units for customer D4.

(Customer D2’s demand for 1,000 units is NOT met; customer D3’s demand for 3,000 units is NOT met.)

This production schedule will yield a maximum profit of $282,000.

14. a.

b.

Max / 100x11 / + / 95x12 / + / 85x21 / + / 80x22 / + / 90x31 / + / 75x32
s.t.
x11 / + / x12 / £ / 1
x21 / + / x22 / £ / 1
x31 / + / x32 / £ / 1
x11 / + / x21 / + / x31 / = / 1
x12 / + / x22 / + / x32 / = / 1

xij = 0 or 1, i = 1,2,3; j = 1,2

Storm Output using Assignment Module:

bubba - problem 7.14

OPTIMAL SOLUTION

Row Column Cost

BOSTOCK SOUTHWEST 95

MILLER NORTHWEST 90

Total Cost = 185

Number of Iterations = 2

Optimal Solution: x12 = 1, x31 = 1 Optimal annual sales: $185 (000)

Assign Bostock to the Southwest territory and Miller to the Northwest territory.

15. Storm Output using Assignment Module:

bubba - problem 7.15

OPTIMAL SOLUTION

Row Column Cost

TERRY CLIENT 2 15

CARLE CLIENT 3 5

MCCLYMONDS CLIENT 1 6

Total Cost = 26

Number of Iterations = 3

Interpretation of Optimal Solution:

Assign Terry to Client 2.

Assign Carle to Client 3.

Assign McClymonds to Client 1.

Higley is unassigned.

Total completion time = 26 days

Note: An alternative optimal solution (also with total completion time of 26 days) is Terry → Client 2, Carle → unassigned, McClymonds → Client 3, and Higley → Client 1.

7 - XXX