- 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.
- 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
- 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.
- 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.
- 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.
- 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.
- An assignment of flow to the arcs that satisfies conservation of flow
for each node and the bounds on flow for each arc.
- Constraints on arc flows that cannot be modeled using the network structure,
arc parameters or external flows.
- The feasible flow minimizes total arc cost.
- THE GENERAL LINEAR PROGRAMMING MODEL
- Every network flow programming model has an equivalent linear programming