This problem is ready made for a network flow model, and we use it to describe the several components of this model type. The network model is graphical in that it is presented as a collection of the nodes and arcs drawn in the figure. The nodes represent the cities of this problem, and we name them with the shortened names of the supply and demand cities. Arcs are the directed line segments of the figure. The nodes at its ends identify an arc. One arc in the figure originates at node Phoenix and terminates at node Chicago.

Flow is associated with the network, entering and leaving at the nodes and passing through the arcs. Flows entering or leaving a node from external sources are called external flows and are shown adjacent to the nodes in the square brackets. A positive external flow is a supply, flow that enters the network, and a negative external flow is a demand, flow that leaves the network. Flow is conserved at each node, implying that the total flow entering a node, either from arcs or external supplies, must equal the total flow leaving the node, either to arcs or to external demands. The arc flows are the decision variables for the network flow programming model.

Flow is limited in an arc by the lower and upper bounds on flow. In this example we specify 0 as the lower bound for all arcs and 200 as the upper bound. Sometimes the term capacity refers to the upper bound on flow. Within the restrictions imposed by conservation of flow for each node and the bounds on flow for each arc, there are usually many feasible flows (a flow is an assignment of an arc flow to each arc). The problem is to find a feasible flow, if one exists, and an optimal flow from the set of feasible flows.

The criterion for optimality is cost. Associated with each arc is a cost per unit of flow (the number in the parenthesis). If a flow x passes through the arc with unit cost c, a cost cx is incurred. The total cost for the network is the sum of the arc costs, and the goal of optimization is to find the feasible flow that minimizes this measure.

We call the model of this section a pure network flow model because the flow entering an arc at its origin node is equal to the flow leaving the arc at its terminal node. This is contrasted later to the generalized network flow model that does not have this limitation. The pure model has the important feature of integral optimum solutions. Whenever all node external flows and all arc upper and lower bounds are integer, the flow solution to the pure model is also integer. As we will see, this has important ramifications.

The model defined in Fig. 1 can be solved to find the optimum flows. The solution is shown on the next page.