This problem is ready made for
a network flow model, and we use Figure 1 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. |
through
. The network flow problem is to minimize total cost while
satisfying conservation of flow at each node.
The variables must also satisfy the simple upper and lower
bounds on arc flow.
