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 S_{Ij} Set of sources {i} which can supply destination j
S_{Ji} Set of destinations {j} to which source i can deliver
Constants C_{i, j} Cost of transporting material from source i to destination j ($/tonne)
A_{i} Maximum amount of material available at source i (tonnes)
D_{j} Demand for material at destination j (tonnes)
The natural formulation for this problem is to write
x_{i, j} for the quantity of material transported from i to j (tonnes).
Then we must:
minimize costs ($)
Σ_{i} Σ_{j} C_{i, j} x_{i, j}
subject to
1. the availability constraint (tonnes)
Σ_{ j єSJi} x_{i, j} ≤ A_{i} for all i
2. the demand constraint (tonnes)
Σ_{i єSIj} x_{i, j} = D_{j} for all j
3. the (usually implicit) nonnegativity constraints
x_{i, j} ≥ 0 for all i, j
previous contents next
