next up previous
Next: Unifying Model: Minimum Cost Up: Examples Previous: Transportation Problem

Assignment Problem

A special case of the transportation problem is the assignment problem which occurs when each supply is 1 and each demand is 1. In this case, the integrality implies that every supplier will be assigned one destination and every destination will have one supplier. The costs give the charge for assigning a supplier and destination to each other.

Example. A company has three new machines of different types. There are four different plants that could receive the machines. Each plant can only receive one machine, and each machine can only be given to one plant. The expected profit that can be made by each plant if assigned a machine is as follows:


This is a transportation problem with all supplies and demands equal to 1, so it is an assignment problem.

Note that a balanced problem must have the same number of supplies and demands, so we must add a dummy machine (corresponding to receiving no machine) and assign a zero cost for assigning the dummy machine to a plant.

Michael A. Trick
Sun Jun 14 13:20:08 EDT 1998