### Transportation Problem

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 problem.

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.