6.52.3  Solving the transportation problems: tpsolve

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.

The optimal solution is represented as 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 the 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.

Example.
Input:

Output:

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 beunbalanced. 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.

Example.
Input:

Output:

Sometimes it is desirable to forbid transportation on certain routes. That is usually achieved by setting very high cost to these routes, represented by the symbol M. If tpsolve detects this symbol in the cost matrix and assigns it 100 times the largest numeric element of C to the corresponding routes, which forces the algorithm to avoid them.

Example.
Input:

Output: