previous				contents				next

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 ($)

Si Sj  Ci, j xi, j

subject to

1. the availability constraint (tonnes)

S j ÎSJi  xi, j  £  Ai 				" i

2. the demand constraint (tonnes)

S i ÎSIj  xi, j  =  Dj				" j

3. the (usually implicit) non-negativity constraints

xi, j    ³  0					" i, j

previous				contents				next