6.54.7  Solving 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 :

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

The optimal solution is represented as matrix X^*=[x_ij^*]_{m× n} , where x_ij^* is number of units that must be transported from i -th source to j -th destination for i=1,2,…,m and j=1,2,…,n .

Function tpsolve accepts three arguments: supply vector, demand vector and cost matrix, in that order. It returns a sequence of two elements: total (minimal) cost of transportation c=∑_i=1^m∑_j=1ⁿc_ij x_ij^* and the optimal solution X^* .

Input :

Output :

If total supply and total demand are equal, i.e. if ∑_i=1^ms_i=∑_j=1ⁿd_j holds, transportation problem is said to be closed or balanced. If total supply exceeds total demand or vice versa, the problem is unbalanced. Such cases are handled by adding a dummy demand resp. supply point to cover the excess and setting cost of “transportation” from resp. to dummy point to zero. In case of unbalanced problem, function tpsolve adds dummy supply/demand point automatically.

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 symbol M . If tpsolve detects a symbol in cost matrix, it interprets it as M and assigns 100 times larger cost than the largest numeric element of C to the corresponding routes, which forces the algorithm to avoid them.

Input :

Output :