A typical transportation problem is shown in Fig. 9. It deals
with sources where a supply of some commodity is available
and destinations where the commodity is demanded. The classic
statement of the transportation problem uses a matrix with
the rows representing sources and columns representing destinations.
The algorithms for solving the problem are based on this matrix
representation. The costs of shipping from sources to destinations
are indicated by the entries in the matrix. If shipment is
impossible between a given source and destination, a large
cost of M is entered. This discourages the solution from using
such cells. Supplies and demands are shown along the margins
of the matrix. As in the example, the classic transportation
problem has total supply equal to total demand.
Figure 9. Matrix model of a transportation problem.
The network model of the transportation problem is shown
in Fig. 10. Sources are identified as the nodes on the left
and destinations on the right. Allowable shipping links are
shown as arcs, while disallowed links are not included.
Figure 10. Network flow model of the transportation
Only arc costs are shown in the network model, as these are
the only relevant parameters. All other parameters are set
to the default values. The network has a special form important
in graph theory; it is called a bipartite network since the
nodes can be divided into two parts with all arcs going from
one part to the other.
On each supply node the positive external flow indicates
supply flow entering the network. On each destination node
a demand is a negative fixed external flow indicating that
this amount must leave the network. The optimum solution for
the example is shown in Fig. 11.
Figure 11. Optimum solution, z = 46.
Variations of the classical transportation problem are easily
handled by modifications of the network model. If links have
finite capacity, the arc upper bounds can be made finite.
If supplies represent raw materials that are transformed into
products at the sources and the demands are in units of product,
the gain factors can be used to represent transformation efficiency
at each source. If some minimal flow is required in certain
links, arc lower bounds can be set to nonzero values.