### 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: `Subscriptsi Sourcej DestinationSetsSIj Set of sources {i} which can supply destination jSJi Set of destinations {j} to which source i can deliver ConstantsCi, 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`