Package com.imsl.math

Class Transport

java.lang.Object
com.imsl.math.Transport
All Implemented Interfaces:
Serializable
public class Transport extends Object implements Serializable
Solves a Transportation problem.

Class Transport solves the transportation problem which can be described as follows: Let \(nw\) sources (or warehouses) be given that store \(w_i\) (\(i=1,..,nw\)) units of a commodity. The sources are connected with \(ns\) destinations (or sinks) that demand \(s_j\) (\(j = 1,...,ns\)) units of the commodity. The transportation costs per unit from source i to destination j are \(c_{ij}\). The goal is to transport the commodity from the sources to the destinations in such a way that all demands are met and the total transportation costs are minimized. If \(x_{ij}\) denotes the desired quantity of the commodity transported from source i to destination j, then the mathematical formulation of the transportation problem is $$ \min \sum_{i=1}^{nw}\sum_{j=1}^{ns}c_{ij}x_{ij}$$ subject to the constraints $$\sum_{j=1}^{ns}x_{ij} \le w_i, i = 1,\ldots,nw \\ \sum_{i=1}^{nw}x_{ij} = s_j, j = 1,\ldots,ns \\ x_{ij} \ge 0, i=1,\ldots,nw, j=1,\ldots,ns. $$
The revised simplex method is used to solve a very sparse linear programming problem with nw + ns constraints and nw * ns variables. If nw = ns = k, the work per iteration is \(O(k^2)\), compared with \(O(k^3)\) when a dense simplex algorithm is used. For more details, see Sewell (2014), Section 4.6.
Alternatively, the interior point method implemented in class SparseLP can be used to solve the transportation problem.
Denoting the dual solution of the transportation problem as dual, dual[i] gives the decrease in total cost per unit increase in sources[i], for small increases, and dual[nw + j] gives the increase in total cost per unit increase in destinations[j].

References
Sewell, Granville (2014), Computational Methods of Linear Algebra, third edition, World Scientific Publishing, Singapore.

See Also:

  • Constructor Details

    • Transport

      public Transport(double[] sources, double[] destinations, double[][] costs)
      Construct the transportation problem from given sources, destinations and costs.
      Parameters:
      sources - a double array containing the source capacities. Since no internal copy of the array is made, the user should not change its content during the existence of the related Transport object.
      destinations - a double array containing the destination requirements. Since no internal copy of the array is made, the user should not change its content during the existence of the related Transport object.
      costs - a double matrix containing the cost matrix. If nw is the length of sources and ns the length of destinations, then costs is of size nw by ns, and costs[i][j] is the per unit cost to ship from source i to destination j. Since no internal copy of the matrix is made, the user should not change its content during the existence of the related Transport object.

    • Transport

      public Transport(Transport transportProblem)
      Copy constructor for the transportation problem.
      Parameters:
      transportProblem - the Transport object to be copied

  • Method Details