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:
An optimal solution is represented by the 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.
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 be unbalanced. 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.
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 a very high cost, represented by a symbol (usually M), to these routes. Hence all instances of a symbol in the cost matrix are automatically replaced by a practically infinite number (precisely (m n + 1)/ε, where ε is returned by epsilon), which forces the algorithm to avoid the associated routes.
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, | ⎡ ⎢ ⎢ ⎢ ⎣ |
| ⎤ ⎥ ⎥ ⎥ ⎦ |