EXPLANATION FILE OF PROGRAM TRANSPOR
====================================
The Transport Model
-------------------
1. Kinds of problems
-----------------
The transport model, a particular case of linear programming, has for goal
to calculate the dispatching, at minimum cost, of a resource from some star-
ting points to other destination points.
For example:
- dispatch a product, at minimum cost, from different factories to various
locations.
- optimal dispatching of a liquid product through a distribution net.
- optimal dispatching of electric power from different sources to many cus-
tomers, etc.
2. The Model
---------
Data
----
To use the transport model, the decision-maker must perfectly know the fol-
lowing three kinds of data:
Destination Total Amount (DTA)
------------------------------
It is for each destination the required total quantity.
Origin Available Amount (OAA)
-----------------------------
It is for each starting point the total available quantity of products.
Unitary Transport Cost (UTC)
----------------------------
It is for each origin-destination couple the cost of delivery. This cost can
be replaced by miles to be minimized or any other useful unit, etc.
As for any discreet linear programming method, available data are presented
in a table such as:
-------------------------------------------
| Destination | D1 | D2 | ... | DAA |
| Origin | | | | |
-------------------------------------------
| O1 | C11 | C12 | ... | |
| O2 | C21 | C22 | ... | |
| ... | ... | ... | ... | |
-------------------------------------------
| DTA | | | | |
-------------------------------------------
Cij is the delivery cost from Oi to Dj.
Constraints
-----------
It is not obligatory that the number of origins equal the numbers of desti-
nations, but the total available amount of origins must equal the total requi-
red amount at destinations.
If this latter condition is not verified, two cases may occur:
Sum OAA < Sum DTA
-----------------
In this case, demand cannot be satisfied, the transport model cannot be
used.
Sum DTA < Sum DAA
-----------------
In this case, available amount is greater than required amount and a remai-
ning stock will exist after the dispatching. To use the transport model, you
must create a supplementary request with a UTC = 0 corresponding to the stock
to be kept (see table below):
----------------------------------------------------
| Destination | D1 | D2 | D3 | D4 | DAA |
| Origin | | | | sup. | |
----------------------------------------------------
| O1 | 2.5 | 3.0 | 0.5 | 0 $ | 500 |
| | | | | | |
| O2 | 2.0 | 1.0 | 1.5 | 0 $ | 900 |
----------------------------------------------------
| DTA | 500 | 300 | 400 | 200 | 1400 |
----------------------------------------------------
3. The Stepping Stone Algorithm
----------------------------
We first establish a starting solution by using the "NW Corner", then the
transport model uses the "Stepping Stone" algorithm to improve the solution.
This latter, by successive iterations, seeks to improve the current solu-
tion by trying different dispatching schemes. For that, according to the graph
theory, each Oi and Dj is associated to a marker and each arc betwwen to mar-
kers is associated to a unitary cost, and moving unitary quantities on unused
arcs until optimal distribution is obtained.
4. Example
-------
Wording
-------
A papermaker owns three factories respectively producing* monthly 5000,
10000 and 6000 tons. He has to deliver the following quantities respectively
to four customers in different cities: 2000 T (Paris), 11000 T (Lyon), 4000 T
(Marseille) and 4000 T (Grenoble) at the lowest total transportation cost.
The transport costs grid is the * following:
-----------------------------------------------------
| Destination | PARIS | LYON | MARSEILLE | GRENOBLE |
| Origin | | | | |
-----------------------------------------------------
| FACTORY 1 | 200 | 700 | 800 |very high |
| FACTORY 2 | 400 | 400 | 500 | 500 |
| FACTORY 3 | 400 | 500 | 600 | 600 |
-----------------------------------------------------
Resolution
----------
Let us first make the table with unitary costs, DAA and DTA:
-------------------------------------------------------
| Destination | D1 | D2 | D3 | D4 | DAA |
| Origin | | | | | |
-------------------------------------------------------
| O 1 | 200 | 700 | 800 |very high| 5000 |
| O 2 | 400 | 400 | 500 | 500 | 10000 |
| O 3 | 400 | 500 | 600 | 600 | 6000 |
-------------------------------------------------------
| DTA | 2000 |11000 | 4000 | 4000 | 21000 |
-------------------------------------------------------
The transport model cannot be used with such a table, some modification is
necessary.
Infinite Cost
-------------
You just have to replace "very high" by 9999 (greater than all other values)
to be sure that no transport will occur between O1 and D4.
Results
-------
Program Transpor with these data gives the following results:
TRANSPORT MODEL
ORIGIN 1 TO DESTINATION 1 : 2000
ORIGIN 1 TO DESTINATION 2 : 3000
ORIGIN 2 TO DESTINATION 2 : 8000
ORIGIN 2 TO DESTINATION 3 : 2000
ORIGIN 3 TO DESTINATION 3 : 2000
ORIGIN 3 TO DESTINATION 4 : 4000
TOTAL TRANSPORT COST : 10300000
Note: other optimal solutions may exist but this program only gives one
solution.
From [Modèles pratiques de décision Tome 2, By Jean-Pierre Blanger,
PSI Editions, France, 1982].
---------------------------------------------
End of file Transpor.txt