- NODES AND ARCS

- The network flow model consists of nodes and arcs. In the context of
modeling a problem, each node, shown as a circle, represents some aspect
of the problem such as a physical location, an individual worker, or a
point in time. For modeling purposes it is often convenient to assign names
to the nodes. Arcs are directed line segments. The nodes at its ends identify
an arc. The arc passes from its origin node to its terminal node. We use
*m*as the number of nodes and*n*as the number of arcs.

- ARC FLOW

- Flow is associated with the network, entering and leaving at the nodes
and passing through the arcs. The flow in arc
*k*is*xk*. Flow is conserved at the nodes, implying that the total flow entering a node must equal the total flow leaving the node. The arc flows are the decision variables for the network flow programming model.

- UPPER AND LOWER BOUNDS ON FLOW

- Flow is limited in an arc by the lower and upper bounds on flow. Sometimes
the term capacity refers to the upper bound on flow. We use
*uk*and*uk*for the lower and upper bounds of arc*k*.

- COST

- The criterion for optimality is cost. Associated with each arc
*k*, is the cost per unit of flow,*ck*. Negative values of*ck*model revenues.

- GAIN

- The arc gain,
*gk*, multiplies the flow at the beginning of the arc to obtain the flow at the end of the arc. When a flow*xk*is assigned to an arc, this flow leaves the origin node of the arc. The flow entering the terminal node of the arc is*gkxk*. The arc lower bound, upper bound, and cost all refer to the flow at the beginning of the arc. Gains less than 1 model losses such as evaporation or spoilage. Gains greater than 1 model growth in flow. - A network in which all arcs have unit gains is called a pure network. The optimum solution for a pure network with integer parameters always has integer flows. If some gains have values other than 1 the network is a generalized network, and the solution is not usually all integer.

- ARC PARAMETERS

- The set of arc parameters are shown adjacent to arcs enclosed in parenthesis:

(lower bound, upper bound, cost, gain).

- When a parameter is not shown, it assumes its default value. Default values are: 0 for lower bound, infinity for upper bound, 0 for cost and 1 for gain.

- EXTERNAL FLOWS

- The external flow at node
*i*,*bi*, is the flow that must enter or leave node*i*. A positive external flow enters the node, and a negative external flow leaves the node. We show the external flow adjacent to the node with square brackets.

- FEASIBLE FLOW

- An assignment of flow to the arcs that satisfies conservation of flow for each node and the bounds on flow for each arc.

- SIDE CONSTRAINTS

- Constraints on arc flows that cannot be modeled using the network structure, arc parameters or external flows.

- OPTIMAL FLOW

- The feasible flow minimizes total arc cost.

- THE GENERAL LINEAR PROGRAMMING MODEL

- Every network flow programming model has an equivalent linear programming
model.