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 :
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, respectively. It returns a sequence of two elements: the total (minimal) cost c=∑_{i=1}^{m}∑_{j=1}^{n}c_{ij} x_{ij}^{*} of transportation and the optimal solution X^{*} .
Input :
Output :
If total supply and total demand are equal, i.e. if ∑_{i=1}^{m}s_{i}=∑_{j=1}^{n}d_{j} holds, transportation problem is closed or balanced. If total supply exceeds total demand or vice versa, the problem is unbalanced. The excess supply/demand is covered by adding a dummy demand/supply point with zero cost of “transportation” from/to that point. Function tpsolve handles such cases 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 the 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 :