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*=(xij*), where xij* 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.
Example.
Input:
s:=[12,17,11];d:=[10,10,10,10]; |
C:=[[50,75,30,45],[65,80,40,60],[40,70,50,55]]; |
tpsolve(s,d,C) |
Output:
2020, | ⎡ ⎢ ⎢ ⎣ |
| ⎤ ⎥ ⎥ ⎦ |
If the total supply and total demand are equal, i.e. if ∑i=1m si=∑j=1n dj 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:
s:=[7,10,8,8,9,6];d:=[9,6,12,8,10]; |
C:=[[36,40,32,43,29],[28,27,29,40,38],[34,35,41,29,31], |
[41,42,35,27,36],[25,28,40,34,38],[31,30,43,38,40]]; |
tpsolve(s,d,C) |
Output:
1275, | ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ |
| ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ |
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:
s:=[95,70,165,165];d:=[195,150,30,45,75]; |
C:=[[15,M,45,M,0],[12,40,M,M,0],[0,15,25,25,0],[M,0,M,12,0]] |
tpsolve(s,d,C) |
Output:
2820, | ⎡ ⎢ ⎢ ⎢ ⎣ |
| ⎤ ⎥ ⎥ ⎥ ⎦ |