Transport problem

transportation problem

One of the most important special cases of the general problem of linear programming. The formulation of the transportation problem is as follows.

Suppose that at points $ A _ {1} \dots A _ {m} $ some homogeneous commodity is produced, where the volume of output of the commodity at $ A _ {i} $ consists of $ a _ {i} $ units, $ i = 1 \dots m $. The goods produced at these production points have to be delivered to consumer points $ B _ {1} \dots B _ {n} $, where the volume of consumption at $ B _ {j} $ consists of $ b _ {j} $ units of goods. It is assumed that transportation of the finished product is possible from any production point to any consumer point and that the transportation cost necessary for the transfer of a unit of goods from $ A _ {i} $ to $ B _ {j} $ is $ c _ {ij} $ monetary units. Then the problem consists of organizing a plan of shipment such that the total transportation cost is a minimum.

Formally, the problem is posed in the following way. Let $ x _ {ij} $ be the quantity of goods shipped from $ A _ {i} $ to $ B _ {j} $. It is required to determine a set of $ mn $ quantities $ x _ {ij} $ satisfying the conditions

$$ \tag{1 } \left . and minimizing the linear form $$ L ( X) = \sum _ {i = 1 } ^ { m } \sum _ {j = 1 } ^ { n } c _ {ij} x _ {ij} . $$ The set of constraints (1) refers to the fact that the volume shipped from each production point is exactly equal to the volume produced at this point, while the volume received at a consumer point corresponds exactly to its requirements. Under these constraints, a necessary and sufficient condition for the solvability of the transportation problem is that the following balance condition should hold: $$ \tag{2 } \sum _ {i = 1 } ^ { m } a _ {i} = \ \sum _ {j = 1 } ^ { n } b _ {j} . $$

The following two circumstances are specific to the transportation problem: a) each of the variables $ x _ {ij} $ enters into two equations of the system (1); b) all the coefficients of the variables $ x _ {ij} $ in the constraints take the values 0 or 1 only. Conditions a) and b) enable one to devise algorithms for the solution of the transportation problem that are essentially simpler than the simplex method, which is one of the basic methods for solving linear programming problems.

The best known of these algorithms are the method of potentials and the so-called Hungarian method. The method of potentials is a method of successive improvement of the plan (of shipments) using the second duality theorem for verifying optimality [1]. The Hungarian method is a method of successively constructing an admissible plan, which automatically turns out to be optimal. At the basis of the Hungarian algorithm is the method of alternating chains [2].

Two generalizations of the classical transportation problem are known; they reflect situations encountered in practice. The open model of the transportation problem: a transportation problem in which the balance condition (2) does not hold; this means that either the total volume produced exceeds the total volume required, or vice versa. This problem reduces to the classical transportation problem by introducing a fictitious production (or consumer) point with production (or consumption) capacity equal to the difference between the volumes produced and required.

Multi-index transportation problems retain the general problem of minimizing transportation costs, but take into account inhomogeneity of the goods (output devices) and inhomogeneity of the means of transportation.

In non-Russian literature, the transportation problem is sometimes called the Hitchcock problem.

References

[1]	E.G. Gol'shtein, D.B. Yudin, "Linear programming" , Israel Program Sci. Transl. (1965) (Translated from Russian)
[2]	O. Ore, "Theory of graphs" , Amer. Math. Soc. (1963)
[3]	V.A. Emelichev, M.M. Kovalev, M.K. Kravtsov, "Polyhedra. Graphs. Optimization" , Moscow (1981) (In Russian)

References

[a1]	A. Schrijver, "Theory of linear and integer programming" , Wiley (1986)
[a2]	G.L. Nemhauser, L.A. Wolsey, "Integer and combinatorial optimization" , Wiley (1988)