Network models
What is a network?
We return to the network model described here. We consider a network (directed graph) having nodes connected by directed arcs (ordered pairs ). We assume there is at most one arc from node to node , and no self-loops. We define the arc-node incidence matrix to be the matrix with coefficients if arc starts at node , if it ends there, and otherwise. Note that the column sums of are zero: .
|
The figure shows the graph associated with the arc-node incidence matrix
|
Flows
A flow (of traffic, information, charge) is represented by a vector , and the {em total flow leaving node } is then .
Minimum cost network flow
The minimum cost network flow problem has the LP form
where is the cost of flow through arc , provide upper and lower bounds on and is an external supply vector. This vector may have positive or negative components, as it represents supply and demand. We assume that , so that the total supply equals the total demand. The constraint represents the balance equations of the network.
Maximum flow
A more specific example is the max flow problem, where we seek to maximize the flow between node (the source) and node (the sink). It bears the form
with .
|