Difference: TransportationProblem (10 vs. 11)

Revision 112008-04-02 - MichaelOSullivan

Line: 1 to 1
META TOPICPARENT name="NetworkOptimisation"
%BEGINLATEXPREAMBLE% \usepackage{amsmath}
Line: 60 to 60

Unbalanced Transportation Problems

The transportation problem we consider here must be balanced, i.e., $\sum_{i \in {\cal S}} s_i = \sum_{j \in {\cal D}} d_j$, for the problem to be feasible. If a problem is not balanced then either there is an excess supply or an excess demand. These two factors can be incorporated by adjusting the relational operators on the constraints, e.g., for over supply change the supply constraint to
\[ \sum_{j \in {\cal D}} x_{ij} \leq s_i, i \in {\cal S} \]

However, if the problem data changes, then the formulation may need to change. An easier way to deal with unbalanced transportation is to add dummy nodes to either the supply nodes (in the case of excess demand) or the demand nodes (in the case of excess supply). The supply (respectively demand) for the dummy node is simply the excess amount of demand (supply, respectively). There could also be a cost associated with goods coming from a dummy supply node, e.g., a penalty cost for buying in extra goods, or goods going to a dummy demand node, e.g., a salvage cost for unwanted items.


Restricting the Arcs

The arcs between the supply nodes and demand nodes may be restricted in two ways:
  1. there may be bounds on the amount of goods that an arc may carry;
  2. some arcs may not exist, i.e., there is no way to transport goods from a particular supply node to a particular demand node.

Dealing with bounds is done by adding bounds to the decision variables, i.e.,

\[ l_{ij} \leq x_{ij} \leq u_{ij}, (i, j) \in {\cal A} \]

Dealing with non-existent arcs is more complicated. One way is to price the arc out of the solution, i.e., add a big cost (often referred to as a big-$M$ cost), so the arc will not be used. Sometimes it is not easy to determine a cost that is big enough to remove the arc from the final solution, but not so big that it distorts the solution process. The easiest way is to introduce bounds with default values, e.g., 0 for the lower bounds and $\infty$ for the upper bounds, and then set the upper bound of the banned arcs to be 0. This way no goods will be delivered along this arc.

Naturally Integer Solutions

The transportation problem is often an integer programme as the quantity of good delivered along the arcs must be integer. However, if the supply, demand and variable bounds are integer, then the transportation problem will have naturally integer solutions. This means that any solution found using linear programming will have integer values. This is a property that is common to other network optimisation problems, e.g., TransshipmentProblem[the transshipment problem.]]


Solving the Transportation Problem with OR Software

Line: 104 to 122
META FILEATTACHMENT attachment="latexdf1dbc2dbff3bfa69c22d8d69793785b.png" attr="h" comment="" date="1207100534" name="latexdf1dbc2dbff3bfa69c22d8d69793785b.png" stream="GLOB(0xab64c7c)" tmpFilename="latexdf1dbc2dbff3bfa69c22d8d69793785b.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex5ce74a16471abe432c6ec35438168cd6.png" attr="h" comment="" date="1207100534" name="latex5ce74a16471abe432c6ec35438168cd6.png" stream="GLOB(0xab64cf4)" tmpFilename="latex5ce74a16471abe432c6ec35438168cd6.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexbcc6e99f03dee0cb32688e788dfdefa0.png" attr="h" comment="" date="1207100786" name="latexbcc6e99f03dee0cb32688e788dfdefa0.png" stream="GLOB(0x9c519e8)" tmpFilename="latexbcc6e99f03dee0cb32688e788dfdefa0.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex83d7c7f807cec62b693bb2cc62d9dd74.png" attr="h" comment="" date="1207101760" name="latex83d7c7f807cec62b693bb2cc62d9dd74.png" stream="GLOB(0x936f598)" tmpFilename="latex83d7c7f807cec62b693bb2cc62d9dd74.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latexf71a111fbbaad6d789e5dcaa9054e142.png" attr="h" comment="" date="1207101760" name="latexf71a111fbbaad6d789e5dcaa9054e142.png" stream="GLOB(0x936f544)" tmpFilename="latexf71a111fbbaad6d789e5dcaa9054e142.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex1d194c3592697ffbdaac41a7785f3053.png" attr="h" comment="" date="1207101761" name="latex1d194c3592697ffbdaac41a7785f3053.png" stream="GLOB(0x93662ac)" tmpFilename="latex1d194c3592697ffbdaac41a7785f3053.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex1491154a3e17d62121b17d82acdf1f97.png" attr="h" comment="" date="1207101828" name="latex1491154a3e17d62121b17d82acdf1f97.png" stream="GLOB(0xaa4724c)" tmpFilename="latex1491154a3e17d62121b17d82acdf1f97.png" user="MichaelOSullivan" version="1"
META FILEATTACHMENT attachment="latex3cfdbee2d162c4de8a8f9904b37b5e1b.png" attr="h" comment="" date="1207101852" name="latex3cfdbee2d162c4de8a8f9904b37b5e1b.png" stream="GLOB(0xaaf75d0)" tmpFilename="latex3cfdbee2d162c4de8a8f9904b37b5e1b.png" user="MichaelOSullivan" version="1"
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback