3.6 The Transportation Problem

This is the classic problem used to introduce Linear Programming. Although it rarely occurs in its classic form, it does occur frequently as part of a larger model. Specified quantities of some homogeneous material are available at a number of sources, and specified quantities must be delivered to each of a number of destinations. The cost of supplying each destination from each source is defined in $/tonne. What is the cheapest way to meet all the requirements?

The formulation is as follows:

Subscripts

i Source

j Destination

Sets

SIj Set of sources {i} which can supply destination j

SJi Set of destinations {j} to which source i can deliver

Constants

Ci, j Cost of transporting material from source i to destination j ($/tonne)

Ai Maximum amount of material available at source i (tonnes)

Dj Demand for material at destination j (tonnes)

The natural formulation for this problem is to write

xi, j for the quantity of material transported from i to j (tonnes).

Then we must:

minimize costs ($)

Σi Σj Ci, j xi, j

subject to

1. the availability constraint (tonnes)

Σ j єSJi xi, j ≤ Ai for all i

2. the demand constraint (tonnes)

Σi єSIj xi, j = Dj for all j

3. the (usually implicit) non-negativity constraints

xi, j ≥ 0 for all i, j

previous contents next

Comments