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, in that order. It returns a sequence of two elements: total (minimal) cost of transportation c=∑_{i=1}^{m}∑_{j=1}^{n}c_{ij} x_{ij}^{*} 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 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 :