Transportation Task
A Transportation Task is an optimization task that ...
- Example(s):
- an Assignment Task.
- See: Disjoint Sets, Subset, Euclidean Plane, Bijection, Assignment Problem, Cost Curve, Convex Function, Concave Function, Economy of Scale, Real Line.
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Transportation_theory_(mathematics)#Motivation Retrieved:2014-8-22.
- Suppose that we have a collection of n mines mining iron ore, and a collection of n factories which consume the iron ore that the mines produce. Suppose for the sake of argument that these mines and factories form two disjoint subsets M and F of the Euclidean plane R2. Suppose also that we have a cost function c : R2 × R2 → [0, ∞), so that c(x, y) is the cost of transporting one shipment of iron from x to y. For simplicity, we ignore the time taken to do the transporting. We also assume that each mine can supply only one factory (no splitting of shipments) and that each factory requires precisely one shipment to be in operation (factories cannot work at half- or double-capacity). Having made the above assumptions, a transport plan is a bijection T : M → F– i.e. an arrangement whereby each mine m ∈ M supplies precisely one factory T(m) ∈ F. We wish to find the optimal transport plan, the plan T whose total cost :[math]\displaystyle{ c(T) := \sum_{m \in M} c(m, T(m)) }[/math]
is the least of all possible transport plans from M to F. This motivating special case of the transportation problem is in fact an instance of the assignment problem.
- Moving books: the importance of the cost function===
The following simple example illustrates the importance of the cost function in determining the optimal transport plan. Suppose that we have n books of equal width on a shelf (the real line), arranged in a single contiguous block. We wish to rearrange them into another contiguous block, but shifted one book-width to the right. Two obvious candidates for the optimal transport plan present themselves:
- move all n books one book-width to the right; ("many small moves")
- move the left-most book n book-widths to the right and leave all other books fixed. ("one big move")
- If the cost function is proportional to Euclidean distance (c(x, y) = α|x − y|) then these two candidates are both optimal. If, on the other hand, we choose the strictly convex cost function proportional to the square of Euclidean distance (c(x, y) = α|x − y|2), then the "many small moves" option becomes the unique minimizer.
Interestingly, while mathematicians prefer to work with convex cost functions,economists prefer concave ones. The intuitive justification for this is that once goods have been loaded on to, say, a goods train, transporting the goods 200 kilometres costs much less than twice what it would cost to transport them 100 kilometres. Concave cost functions represent this economy of scale.
- Suppose that we have a collection of n mines mining iron ore, and a collection of n factories which consume the iron ore that the mines produce. Suppose for the sake of argument that these mines and factories form two disjoint subsets M and F of the Euclidean plane R2. Suppose also that we have a cost function c : R2 × R2 → [0, ∞), so that c(x, y) is the cost of transporting one shipment of iron from x to y. For simplicity, we ignore the time taken to do the transporting. We also assume that each mine can supply only one factory (no splitting of shipments) and that each factory requires precisely one shipment to be in operation (factories cannot work at half- or double-capacity). Having made the above assumptions, a transport plan is a bijection T : M → F– i.e. an arrangement whereby each mine m ∈ M supplies precisely one factory T(m) ∈ F. We wish to find the optimal transport plan, the plan T whose total cost :[math]\displaystyle{ c(T) := \sum_{m \in M} c(m, T(m)) }[/math]