Previous Up Next

5.52.3 Solving the 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:

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.

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,


00210
0980
10100




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.

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,






00205
001000
00005
00080
90000
06000








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.

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,



2000075
700000
105030300
01500150





Previous Up Next