16.1.3  Transportation problem

The objective of a transportation problem is to minimize the cost of distributing a product from m sources to n destinations. It is determined by three parameters:

• s=(s₁,s₂,…,s_m), the supply vector, where s_k∈ℤ⁺ is the maximum number of units that can be delivered from the kth source for k=1,2,…,m.
• d=(d₁,d₂,…,d_n), the demand vector d=(d₁,d₂,…,d_n) , where d_k∈ℤ⁺ is the minimum number of units required by the kth destination for k=1,2,…,n.
• C=[c_ij]_{m× n}, the cost matrix, where c_ij∈ℝ⁺ is the cost of transporting one unit of product from the ith source to the jth destination, for i=1,2,…,m and j=1,2,…,n.

An optimal solution is represented by the matrix X^∗=(x_ij^∗), where x_ij^∗ is number of units that must be transported from the ith source to the jth destination for i=1,2,…,m and j=1,2,…,n.

The tpsolve command solves a transportation problem.

• tpsolve takes three arguments:
  • s, the supply vector.
  • d, the demand vector.
  • C, the cost matrix.
• tpsolve(s,d,C) returns a sequence c,X^∗, where X^∗ is the optimal solution and c=∑_i=1^m∑_j=1ⁿc_ij x_ij^∗ is the total (minimal) cost of transportation.
• If the total supply and total demand are equal, i.e. if ∑_i=1^m s_i=∑_j=1ⁿ d_j holds, the transportation problem is said to be closed or balanced, otherwise it is said to be unbalanced. The excess supply/demand is covered by adding a dummy demand/supply point with zero cost of “transportation” from/to that point. The tpsolve command handles such cases automatically.
• Sometimes it is desirable to forbid transportation on certain routes. That is achieved by setting a very high cost, represented by a symbol (e.g. M), to these routes. All instances of the symbol in the cost matrix are automatically replaced by a practically infinite number (precisely (m n+1)/epsilon, which forces the algorithm to avoid the associated routes.

Examples