5.47.3  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=(s1,s2,…,sm) , where sk∈ℤ , sk>0 is the maximum number of units that can be delivered from k -th source for k=1,2,…,m ,
• demand vector d=(d1,d2,…,dn) , where dk∈ℤ , dk>0 is the minimum number of units required by k -th destination for k=1,2,…,n ,
• cost matrix C=[cij]m× n , where cij∈ℝ , cij≥ 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*=[xij*]m× n , where xij* 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=1mj=1ncij xij* of transportation and the optimal solution X* .

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,[[0,0,2,10],[0,9,8,0],[10,1,0,0]]

If total supply and total demand are equal, i.e. if ∑i=1msi=∑j=1ndj 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 :

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,[[0,0,2,0,5],[0,0,10,0,0],[0,0,0,0,5],
[0,0,0,8,0],[9,0,0,0,0],[0,6,0,0,0]]

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 :

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,[[20,0,0,0,75],[70,0,0,0,0],
[105,0,30,30,0],[0,150,0,15,0]]