Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

252 TRANSPORTATION AND ASSIGNMENT PROBLEM

Verify your solution by using the Transportation software option.

CHAPTER 9

NETWORK FLOW THEORY

Network theory concerns a class of linear programs having a very special network

structure. The combinatorial nature of this structure has resulted in the devel-

opment of very eﬃcient algorithms that combine ideas on data structures with

algorithms from computer science, and mathematics from operations research.

Networks arise in a wide variety of situations. For example, the transportation

problem discussed in Chapter 8 is a network representing the shipment of goods from

sources to destinations; see Figure 8-1. Networks arise naturally in electrical sys-

tems (circuit boards, distribution of electricity) and in communications (local-area

communication networks or wide-area communication networks) in which electricity

ﬂows from various points in the network to other points. Typically, the analysis

of networks requires ﬁnding either a maximal-ﬂow solution or a shortest-path solu-

tion or a minimal spanning tree solution or a least-cost solution (in the case of the

transportation problem), or determining the optimal sequence of tasks. The ability

to obtain, under certain conditions, integer-valued solutions has made it possible to

extend network analysis to many diﬀerent areas such as facilities location, project

planning (PERT, CPM), resource management, etc.

9.1 TERMINOLOGY

We shall illustrate deﬁnitions and concepts of directed networks by referring to

Figure 9-1.

NODES AND ARCS OF A NETWORK

In the ﬁgure, the circles numbered 1, 2, 3, and 4 are called nodes; the lines joining

them are called arcs; and the arrowheads on the arcs show the direction of ﬂow. In

all, there are four nodes and six directed arcs.

253

254 NETWORK FLOW THEORY

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

..

.

Figure 9-1: A Simple Directed Network

Deﬁnition (Graph):Agraph consists of a ﬁnite collection of nodes and a set

of node pairs called arcs.

Deﬁnition (Directed Network (or Digraph)):Adirected network,ordigraph,

consists of a set Nd of distinct elements indexed 1, 2,... called nodes and a

set Ac of ordered pairs of node indices, (i, j) ∈Ac, called directed arcs.



Thus

(j, i) is diﬀerent from (i, j)ifi = j



. In addition we will say that arc (i, j)

is outgoing from node i (or is leaving node i or has a tail at node i) and is

incoming to node j (or is entering node j or has a head at node j).

We will sometimes denote a directed network by G =[Nd; Ac]. Associated with a

directed network is an undirected network with the same node set Nd and set of

paired nodes Ac, except that the pairs are unordered.

Deﬁnition (Undirected Network):Anundirected network consists of a set Nd

of elements indexed 1, 2,... called nodes and a set Ac of unordered pairs of

these node indices, (i, j) ∈Ac, called undirected arcs.



Thus (j, i) is the same

as (i, j)



.

We will also say that a directed arc (i, j) connects i to j; and that an undirected

arc (i, j) connects i and j.

In the discussion to follow we shall assume that in a directed network, if there is

an arc connecting i to j it is unique. Moreover, we have assumed above that there

is no arc connecting i to itself, i.e., there are no arcs in Ac of the form (i, i).

Deﬁnition (Source, Destination, Intermediate Nodes): A node all of whose

arcs are outgoing is called a source (or origin) node; a node all of whose arcs

are incoming is called a destination (or sink or terminal) node. All other

nodes are called intermediate (or transshipment) nodes.

The classical Hitchcock-Koopmans transportation problem of Section 8.1 has

m source nodes, n destination nodes, and no intermediate nodes. In Figure 9-1 the

9.1 TERMINOLOGY 255

node labeled 1 is the place where ﬂow starts; i.e., it is the unique source node. On

the other hand, the node labeled 4 is the point where the ﬂows terminate; it is the

unique destination node. All other nodes are intermediate nodes.

In addition, we shall use the following notation:

Af (k)={j ∈Nd | (k, j) ∈Ac}, (9.1)

Bf (k)={i ∈Nd | (i, k) ∈Ac}, (9.2)

where Af (k) stands for “after” node k and Bf (k) stands for “before” node k.

Deﬁnition (Rank or Degree): The rank,ordegree,ofanodeisthenumber

of arcs that enter and leave it. The in-degree of a node is the number of arcs

that enter the node; the out-degree of a node is the number of arcs that leave

the node.

Using |S| to denote the number of elements in a set S, the in-degree of node k

is |Bf (k)| and the out-degree of node k is |Af (k)|.

PATHS, CHAINS, CIRCUITS, AND CYCLES

Deﬁnition (Path): In a directed network, a path (see Figure 9-2(a)) is deﬁned

to be a sequence of nodes i

1

,i

2

,... ,i

m

, m ≥ 2, such that (i

k

,i

k+1

) ∈Ac for

k =1,...,m−1. A simple path has m distinct nodes, whereas in a nonsimple

path the nodes can repeat.

Deﬁnition (Chain): In a directed network, a chain (see Figure 9-2(b)) is

deﬁned to be a sequence of nodes i

1

,i

2

,... ,i

m

, m ≥ 2, such that either

(i

k

,i

k+1

) is an arc or (i

k+1

,i

k

) is an arc for k =1,...,m− 1. Thus, a chain

is essentially the same as a path except that in “going” from i

1

to i

m

we do

not require the directed arcs to be traversed all in the same direction. In an

undirected network a path and chain are identical because (i

k

,i

k+1

)isthe

same as (i

k+1

,i

k

).

Deﬁnition (Circuit and Cycle):Acircuit (see Figure 9-2(c)) is a path from

some node i

1

to node i

n

where i

n

= i

1

, n ≥ 2; i.e., a circuit is a closed path.

Similarly, a cycle is (see Figure 9-2(d)) a chain from some node i

1

to node i

n

where i

n

= i

1

; i.e., a cycle is a closed chain.

NODE-ARC INCIDENCE MATRIX

A convenient way to represent the structure of a network mathematically is through

the use of a node-arc incidence matrix. The nodes correspond to the rows of such

a matrix and the arcs correspond to the columns of the matrix. Since each arc

connects two nodes, a column corresponding to an arc has exactly two nonzero

256 NETWORK FLOW THEORY

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

(a) Path

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

(b) Chain

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

..

.

......................................................

.

(c) Circuit

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

..

.

......................................................

.

(d) Cycle

Figure 9-2: A Path, Chain, Circuit, and Cycle

entries; in the directed case, the entries are +1 (corresponding to the tail end of

the arc) and −1 (corresponding to the head of the arc), in the undirected case the

entries are +1 and +1.

Thus, in the directed case, for a column corresponding to arc (i, j) we use the

convention that its entry in row i is +1 and its entry in row j is −1. All other

entries in the column corresponding to arc (i, j) are zero. Denoting the node-arc

incidence matrix by A, and letting s be the column of the matrix corresponding to

arc (i, j),

A

is

=1

A

js

= −1

A

ks

=0ifk = i, k = j.

(9.3)

That is, in matrix notation, A

•s

= e

i

− e

j

, where e

i

is a unit vector with a one

in position i and zeros elsewhere, and, similarly e

j

is a unit vector with a one in

position j and zeros elsewhere.

In the undirected case for a column corresponding to arc (i, j) we use the con-

vention that its entry in row i is +1 and its entry in row j is also +1. All other

entries in the column corresponding to arc (i, j) are zero.

Example 9.1 (Node-Arc Incidence Matrix) The node-arc incidence matrix corre-

sponding to Figure 9-1 is shown below, with the row labels being the node numbers and

9.1 TERMINOLOGY 257

column labels being the arcs.







(1, 2) (1, 3) (2, 3) (3, 2) (2, 4) (3, 4)

1 110000

2 −101−110

30−1 −1101

4 0000−1 −1







. (9.4)

In this example, if we let x =(x

12

,x

13

,x

23

,x

32

,x

24

,x

34

)

T

≥ 0 be a nonnegative ﬂow vector

such that component x

ij

represents the ﬂow from node i to node j, we see that the product

of row i of the node-arc incidence matrix and the vector x gives the vector of net ﬂow into

and out of node i. If a node net ﬂow is nonnegative, it is the net ﬂow out; if negative, its

absolute value is the net ﬂow in. For example, the ﬁrst component of the product Ax is

1x

12

+1x

13

, which is the net ﬂow out of node 1.

CONNECTED NETWORKS AND TREES

Deﬁnition (Connected Network): Two nodes are said to be connected if there

is at least one chain that joins the two nodes. A connected network is a network

in which every pair of nodes is connected. The circuit of Figure 9-2(c) and

the cycle of Figure 9-2(d) are examples of connected networks (if there are no

other nodes).

Deﬁnition (Weakly and Strongly Connected): Sometimes a connected net-

work as deﬁned above is referred to as being weakly connected, in which case,

a strongly connected network is deﬁned as one in which there is a chain con-

necting every pair of nodes.

Deﬁnition (Complete Graph): If each node of a graph connected by an arc

to every other node, the graph is called a complete graph.

Deﬁnition (Tree):Atree is a connected network with no cycles.

Deﬁnition (Spanning Tree): Given a network with m nodes, a spanning tree

is a tree that connects all m nodes in the network.

The path of Figure 9-2(a) and the chain of Figure 9-2(b) are examples of span-

ning trees. A more general example of a tree is shown in Figure 9-3; it is a spanning

tree since its arcs connect all the nodes of the network.

 Exercise 9.1 Count the number of nodes and arcs in the tree shown in Figure 9-3.

THEOREM 9.1 (Arcs in a Spanning Tree) For a network with m nodes,

every spanning tree has exactly m − 1 arcs.

258 NETWORK FLOW THEORY

.

Figure 9-3: A Tree

Another way to state the theorem is that m − 1 is the minimum number of arcs

needed to generate the tree and it is also the maximum number of arcs that can be

in the tree without creating undirected cycles.

COROLLARY 9.2 (When a Network Is a Spanning Tree) A connected

network with m nodes, m − 1 arcs, and no cycles is a spanning tree.

COROLLARY 9.3 (A Basis Is a Spanning Tree) Let A be the node-arc

incidence matrix of a network. Assuming that the rank of A is m − 1, the graph

associated with any m − 1 independent columns of A is a spanning tree.

 Exercise 9.2 Prove Theorem 9.1, Corollary 9.2, Corollary 9.3.

9.2 FLOWS AND ARC-CAPACITIES

We shall sometimes use x to denote a ﬂow vector, i.e., a vector consisting of all

the arc ﬂows x

ij

for all (i, j) ∈Ac in the network. In some applications x

ij

≥ 0

need not hold. For example, in the maximum ﬂow problem that we will consider in

Section 9.3, we require that

l

ij

≤ x

ij

≤ h

ij

, (9.5)

where the only qualiﬁcations on the bounds are that l

ij

≤ h

ij

for all (i, j).

Deﬁnition (Flow Capacity):Ifh

ij

≥ 0 and l

ij

= 0 then h

ij

is referred to as

the ﬂow capacity of the arc.

In the network in Figure 9-4 each upper bound h

ij

on the ﬂow is shown by the

number on the tail of the arc.

Consider a network with a single source node, s = 1, and a single destination

node, t = m, connected by several intermediate nodes. Except for the nodes 1

and m (the source and destination nodes), the ﬂows into and out of each node

9.2 FLOWS AND ARC-CAPACITIES 259

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

..

.

h

12

h

13

h

23

h

24

h

32

h

34

Figure 9-4: A Simple Directed Network with Arc-Capacities

k must balance; such a relation is called conservation of ﬂows (in physics, the

condition that the quantity of electrons ﬂowing into a point of an electrical network

must equal the amount ﬂowing out is referred to as Kirchoﬀ’s Law). That is, for

an intermediate node k,



i∈Bf (k)

x

ik

−



j∈Af (k)

x

kj

=0, for k =2,...,m− 1, (9.6)

where the ﬁrst summation is over all arcs that have node k as a head node and the

second summation is over all arcs that have node k as a tail node. If we denote by

F the exogenous ﬂow into the source s = 1 from outside the network, then

F −



j∈Af (1)

x

1j

=0, (9.7)

because there are no arcs incoming into the source node. If we denote by H the

exogenous ﬂow from the destination node t to outside the network, then



i∈Bf (m)

x

im

− H =0. (9.8)

If we sum the m − 2 relations in (9.6) and (9.7), then each variable x

ij

appears

in exactly two equations with opposite signs (recall the node-arc incidence matrix)

and hence cancels, resulting in F = H. Therefore



i∈Bf (m)

x

im

− F =0. (9.9)

THEOREM 9.4 (Exogenous Flow Balance) The exogenous ﬂow F into the

source node s equals the exogenous ﬂow H out of the destination node t.

Example 9.2 (Exogenous Flow Balance) Figure 9-5 illustrates an exogenous ﬂow

F = 4 into node 1, the exogenous ﬂow H = 4 out of node 6, and the conservation

equations (9.6), (9.7), and (9.9).

260 NETWORK FLOW THEORY

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

...........................................................................................

.

....................................................................................

.

F =4

...........................................................................................................................................

.

H =4=F

1

3

5

1

4

0

41

.

..

.

..

.

...............................................

.

...............................................

.

..

.

..

.

..

.

..

.

Figure 9-5: Exogenous Flow Balance

 Exercise 9.3 For the network in Figure 9-5, write down the conservation equations in

algebraic form and in matrix form using the node-arc incidence matrix.

 Exercise 9.4 Prove that a set of x

ij

= x

o

ij

≥ 0 satisfying capacity constraints 0 ≤ x

ij

≤

h

ij

and the conservation equations (9.6), (9.7), and (9.9) can be replaced by another set

x



ij

with the same total ﬂow F in which either x



ij

or x



ji

is zero by setting

x



ij

= x

o

ij

− min(x

o

ij

,x

o

ji

) and x



ji

=0 if x

o

ij

≥ x

o

ji

x



ji

= x

o

ij

− min(x

o

ij

,x

o

ji

) and x



ij

=0 if x

o

ji

≥ x

o

ij

.

(9.10)

Comment: When l

ij

= 0, it follows from Exercise 9.4 that we need only consider

ﬂows where either x

ij

=0orx

ji

= 0. Thus, for example, if on the directed arc

joining nodes i and j the ﬂow x

ij

= 4 appears, it will imply that x

ji

= 0. Hence we

could, if we wanted to, replace all the ﬂow variables x

ij

and x

ji

by their diﬀerence:

¯x

ij

= x

ij

− x

ji

, (9.11)

in which case

¯x

ij

> 0 corresponds to ¯x

ij

= x



ij

and x



ji

=0,

¯x

ij

< 0 corresponds to −¯x

ij

= x



ji

and x



ij

=0.

 Exercise 9.5 Show that upon making the substitution for ¯x

ij

, the arc-capacity con-

straints (9.5) with l

ij

= 0 and the conservation equations (9.6), (9.7), and (9.9) for a

network deﬁned by Nd and Ac become

−h

ji

≤ ¯x

ij

≤ h

ij

, (i, j) ∈Ac,



i

¯x

ik

=0,k=2,...,m− 1,

F +



i

¯x

i1

=0,

−F +



i

¯x

im

=0.

(9.12)

9.2 FLOWS AND ARC-CAPACITIES 261

 Exercise 9.6 Given a feasible solution to (9.12), ﬁnd a corresponding feasible solution

that satisﬁes the conservation equations (9.6), (9.7), (9.9) and bounds that satisfy (9.5)

with l

ij

=0.

FLOW AUGMENTATION

Suppose that we are given a network (Nd, Ac) with lower and upper bound con-

straints l

ij

≤ x

ij

≤ h

ij

on arcs (i, j) ∈Ac and a set of feasible ﬂows l

ij

≤ x

o

ij

≤ h

ij

.

Deﬁnition (Associated Path): For any chain of arcs connecting node i

p

to

node i

q

, the associated path P is the path formed by reversing, if necessary,

the direction of some of the arcs along the chain.

Deﬁnition (θ Path Flow): Given any path, a θ path ﬂow is a ﬂow with value

θ on every arc (i, j) along the path and zero elsewhere.

Deﬁnition (θ-Flow Augmentation): Let C be a chain joining s to t and let

P be the associated path. Let C

+

be the arcs of the chain that are oriented

in the direction of the path P and let C

−

, be the remaining arcs of C. The

θ-ﬂow augmentation of a feasible solution x = x

o

is x

ij

= x

o

ij

+θ if (i, j) ∈C

+

,

x

ij

= x

o

ij

− θ if (i, j) ∈C

−

and x

ij

= x

o

ij

otherwise.

Deﬁnition (θ-Path Flow Augmentation is Maximal):Aθ-path ﬂow augmen-

tation is maximal if θ is the maximum value for which the augmentation

remains feasible.

Example 9.3 (Chain ﬂow, θ Path ﬂow, θ-ﬂow Augmentation) A chain ﬂow, θ

path ﬂow, and a chain ﬂow after a θ-ﬂow augmentation are illustrated in Figure 9-6. The

numbers in brackets at the tail of each arc represent the lower and upper bounds on the

ﬂow through the arc. In order for the chain ﬂows to remain feasible after a θ augmentation

along the associated path, we need θ to satisfy

2 ≤ 3+θ ≤ 5, 4 ≤ 5 − θ ≤ 6, 1 ≤ 2+θ ≤ 4.

The maximum θ augmentation that maintains feasibility is θ = 1, because the augmenta-

tion is blocked by the lower bound on x

32

.

FLOW DECOMPOSITION

The next theorem shows that a ﬂow can be decomposed into a sum of ﬂows along

simple paths and circuits. It is useful because it shows that a solution to a ﬂow

problem corresponds to our intuitive notion that items start from nodes of surplus

and move from one node to the next without losing their identity along the way.

Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

Подождите немного. Документ загружается.