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

282 NETWORK FLOW THEORY

4. If Nd \Sis empty, terminate.

5. Let Q = {j | j ∈Nd \S, (k

∗

,j) ∈Ac } be the set of nodes in set Nd \Sthat are

attached to node k

∗

by an arc. For j ∈Q,

if z

k

∗

+ d

k

∗

j

<z

j

, then set z

j

= z

k

∗

+ d

k

∗

j

and p

j

= k

∗

.

6. Set τ ← τ + 1 and go to Step 3.

Comment: In order to avoid searching all j ∈Nd \S on Step 3, one maintains an ordered

list of z

j

by updating the list of j ∈Qwhose label values z

j

have been lowered during the

execution of Step 5.

LEMMA 9.14 (Number of Operations in Dijkstra’s Algorithm) Algo-

rithm 9.3 requires m(m−1)/2 comparisons in Step 3 and requires at most m(m−1)/2

comparisons and additions in Step 5.

Proof. In iteration τ there are τ nodes in S and thus m − τ comparisons are

required in Step 3. Hence in a network with m nodes we need

1+2+···+(m − 1) = m(m − 1)/2

comparisons. Similarly, we need a maximum of m(m −1)/2 comparisons in Step 5.

Fewer may be needed, because at any iteration τ,nodek

∗

will typically have fewer

than m − τ nodes in Nd \Sconnected to it.

LEMMA 9.15 (Validity of Dijkstra’s Algorithm) Algorithm 9.3, with dis-

tances d

ij

≥ 0, ﬁnds the shortest path from the source to all nodes in the network.

 Exercise 9.25 Construct an example to show that Algorithm 9.3 can fail if there are

negative arc distances. Construct an example with some negative arc distances but where

the sum of distances around every cycle is nonnegative. Demonstrate that in this case

Algorithm 9.3 ﬁnds the shortest route from the source to the destination.

 Exercise 9.26 Construct an example to show that if the main post oﬃce has a collection

of shortest routes from it to every other post oﬃce, the collection of arcs along the route

is not necessarily a tree. Apply Dijkstra’s algorithm to your example to ﬁnd an equivalent

tree.

9.6 MINIMAL SPANNING TREE

Consider a connected network G =(Nd, Ac) with m nodes and n arcs; the distances

on the arcs are unrestricted in sign. The minimal spanning tree problem is one

of ﬁnding a tree connecting all m nodes such that the sum of the distances on

the arcs of the tree is minimized. The meaning of distance here is very similar

9.6 MINIMAL SPANNING TREE 283

.

..

.

1

.

..

.

..

.

2

.

..

.

3

.

2

(a)

.

..

.

1

.

..

.

..

.

2

.

..

.

3

.

..

.

4

.

2/

√

3

2/

√

32/

√

3

(b)

Figure 9-19: Minimal Spanning Tree Example

to that for the shortest route problem in that it can represent cost, time, etc.

The minimal spanning tree problem has been applied to design transportation and

communication networks; we do not need to have the network already built but just

to know what the distance (cost) would be if an arc were added between two nodes.

Example 9.15 (Minimal Spanning Tree and Artiﬁcial Node) Suppose that you

need to design a new freeway system connecting three equidistant points 1, 2, and 3. The

minimal spanning tree has a total distance of 4 miles, as shown in Figure 9-19(a). It is

interesting to note that a new freeway system can be built using only 2

√

3 < 4 miles by

building the freeway through an artiﬁcial node 4, as shown by the minimal spanning tree

in Figure 9-19(b).

 Exercise 9.27 Show that the minimal spanning tree remains the same if all arc dis-

tances are changed by a constant value β, i.e.,

¯

d

ij

← d

ij

+ β.

The solution process is very simple and is one of the rare cases where a greedy

algorithm (i.e., an algorithm in which one makes a locally best improvement at

each iteration) ﬁnds a global optimal solution. Since a spanning tree has exactly

m − 1 arcs, so will the optimal solution. An algorithm to do this chooses the arcs

one at a time in increasing order of their lengths, rejecting the selected arc only if

it forms a cycle with the arcs already chosen.

Example 9.16 (Illustration of Minimal Spanning Tree Algorithm) The steps of

the algorithm are illustrated in Figure 9-20. We start by initializing labels u

j

for each node

j =1,...,6 to have the value 0 to imply no label, and we order the arcs by increasing

distance. When every node is labeled the same by a nonzero label, the algorithm will

terminate.

At iteration 1 we pick arc (2, 5) because it has the smallest distance d

25

= 1. The two

connecting nodes are relabeled as u

2

= u

5

= 1. Next, on iteration 2, from the remaining

arcs, we choose arc (3, 4) because it has a distance d

34

= 2 (we could equivalently have

chosen arc (4, 5)) and does not create a cycle with the previously chosen arcs. We set

284 NETWORK FLOW THEORY

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

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

.

3

8

3

1

5

2

4

2

7

u

1

=0

u

2

=0

u

3

=0

u

4

=0

u

5

=0

u

6

=0

Iteration 0: Initialization

τ={∅}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

1

u

1

=0

u

2

=1

u

3

=0

u

4

=0

u

5

=1

u

6

=0

Iteration 1: Arc (2,5) enters

τ={(2,5)}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

1

2

u

1

=0

u

2

=1

u

3

=2

u

4

=2

u

5

=1

u

6

=0

Iteration 2: Arc (3, 4) enters

τ={(2,5), (3,4)}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

..

.

1

2

u

1

=0

u

2

=1

u

3

=1

u

4

=1

u

5

=1

u

6

=0

Iteration 3: Arc (4, 5) enters

τ={(2,5), (3,4), (4,5)}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

31

2

u

1

=1

u

2

=1

u

3

=1

u

4

=1

u

5

=1

u

6

=0

Iteration 4: Arc (1, 2) enters

τ={(2,5), (3,4), (4,5), (1,2)}

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

6

.

31

2

4

u

1

=1

u

2

=1

u

3

=1

u

4

=1

u

5

=1

u

6

=1

Iteration 5: Arc (4, 6) enters

τ={(2,5), (3,4), (4,5), (1,2), (4,6)}

Figure 9-20: Illustration of Minimal Spanning Tree Algorithm

9.6 MINIMAL SPANNING TREE 285

the labels for the connecting nodes of this arc to be u

3

= u

4

= 2 because the nodes do

not intersect any of the other labeled nodes. Continuing, on iteration 3, we pick the next

shortest distance arc (4, 5), which does not create a cycle with the previously chosen arcs.

Now, 4 belongs to a diﬀerent set of previously labeled nodes than does 5. Hence, we set

the labels of the two sets to be equal; we arbitrarily set the labels to be 1 for nodes 2, 3,

4, and 5. We continue in this manner, picking arc (1, 2) on iteration 4 and arc (4, 6) on

the ﬁnal iteration.

Algorithm 9.4 (Minimal Spanning Tree) The algorithm starts by reindexing the

arcs α =1,...,m so that they are in the order of nondecreasing arc lengths. The nodes

will be partitioned into several membership classes, with each node assigned a unique

positive membership label u

j

> 0; upon termination all nodes will belong to only one

membership class. Initially all u

j

= 0, meaning that they do not belong yet to any

membership class. Let T be the set of arcs in the minimal spanning tree, let ν represent

the number of arcs assigned so far to the minimal spanning tree, let k represent the last

membership class label assigned to a node, and let α be the iteration counter, which is,

in this case, the index of the arc being considered for candidacy in the minimal spanning

tree.

1. Set T ← {∅}, ν ← 0, k ← 0, and α ← 1.

2. If ν = m − 1, terminate; we have found a minimal spanning tree.

3. Let arc α connect nodes i and j. We use the node labels to determine whether

candidate arc α forms a cycle with the arcs in T . If it forms a cycle, it is rejected;

otherwise it is accepted as belonging to the minimal spanning tree.

(a) Reject arc α if it will create a cycle with the arcs in T .Ifu

i

= u

j

= 0, i.e.,

nodes i and j both belong to the same membership class, then arc α will create

a cycle amongst arcs already selected as belonging to the minimal spanning

tree, and therefore arc α is rejected. Go to Step 4.

(b) Accept arc α if it does not create a cycle with the arcs in T . In this case set

T←T∪{α}, ν ← ν + 1, and update the labels of the membership classes by

doing one of the following:

• If u

i

= u

j

= 0, i.e., nodes i and j do not belong to any membership class,

then set k ← k + 1 followed by setting u

i

← k and u

j

← k.

• If 0 = u

i

= u

j

= 0 then the nodes i and j belong to diﬀerent membership

classes. We merge the two membership classes labeled u

i

and u

j

into one.

That is, we change the labels of all nodes p such that u

p

= u

j

to u

p

← u

i

.

• If u

i

= 0, but u

j

= 0 set u

j

← u

i

.

• If u

j

= 0, but u

i

= 0 set u

i

← u

j

.

4. Set α ← α + 1. Go to Step 2.

LEMMA 9.16 (Spanning Tree in a Connected Network) A connected

network contains a spanning tree.

 Exercise 9.28 Prove Lemma 9.16.

286 NETWORK FLOW THEORY

.

T

.

T

1

T

2

Figure 9-21: Disconnecting an Arc of T Results in Two Trees: T

1

and T

2

 Exercise 9.29 Prove that Algorithm 9.4 ﬁnds a minimal spanning tree for a connected

network. How would you modify the algorithm so that it could be used on any network?

(If the network is not connected your modiﬁed algorithm should determine that it was

unconnected.)

 Exercise 9.30 Show how using linked lists can make the operations of merging mem-

bership classes in Step 3b of Algorithm 9.4 eﬃcient. Show that you can make it even more

eﬃcient by merging the smaller membership class with the larger one.

LEMMA 9.17 (Disconnecting an Arc of a Tree) Disconnecting an arc (i, j)

ofatreeT results in decomposing T into two trees, T

1

and T

2

.

Example 9.17 (Disconnecting an Arc of a Tree) Figure 9-21 demonstrates how

disconnecting an arc of a tree results in two trees.

 Exercise 9.31 Prove Lemma 9.17

LEMMA 9.18 (End Nodes in a Tree) Any tree has at least two end nodes.

 Exercise 9.32 Verify Lemma 9.18 for the tree illustrated in Figure 9-21.

 Exercise 9.33 Prove Lemma 9.18.

9.7 MINIMUM COST-FLOW PROBLEM

The minimum cost-ﬂow problem is to ﬁnd ﬂows x

ij

through a directed network

G =(Nd, Ac) with m nodes indexed 1,...,mand n arcs, such that the total cost of

9.7 MINIMUM COST-FLOW PROBLEM 287

the ﬂows is minimized. It can be stated as a standard linear programming problem

with very special structure:

Minimize



(i,j)∈Ac

c

ij

x

ij

= z

subject to



i∈Af (k)

x

ki

−



j∈Bf (k)

x

jk

= b

k

for all k ∈Nd,

l

ij

≤ x

ij

≤ h

ij

for all (i, j) ∈Ac,

(9.16)

where c

ij

is the cost per unit ﬂow on the arc (i, j); b

k

is the net ﬂow at node k; l

ij

is a lower bound on the ﬂow in arc (i, j); and h

ij

is an upper bound on the ﬂow in

arc (i, j). Note that b

k

takes on values that depend on the type of node k:

b

k

is







> 0ifk is a source (supply) node;

< 0ifk is a destination (demand) node;

=0 ifk is a node for transshipment only.

Deﬁnition (Feasible Flow): A set of arc ﬂows x

ij

that satisﬁes the conser-

vation of ﬂow constraints and the capacity constraints in (9.16) is called a

feasible ﬂow.

 Exercise 9.34 Show that a necessary condition for feasibility of the system (9.16) is

that



i∈Nd

b

i

=0.

THEOREM 9.19 (Feasibility of a Minimum Cost-Flow Problem) The

minimum cost-ﬂow problem (9.16) with l

ij

=0, h

ij

= ∞ for all (i, j) ∈Ac has a

feasible solution if and only if



i∈Nd

b

i

=0

and the cut value of every cut Q =(X,

¯

X) satisﬁes

C(Q) ≥



i∈X

b

i

.

 Exercise 9.35 Through a simple example, demonstrate one particular instance of The-

orem 9.19. Prove it in general.

The minimum cost-ﬂow formulation has many applications. In fact a number

of the problems in this book can be expressed in terms of a minimum cost-ﬂow

formulation. Some of these are illustrated through the examples and exercises that

follow.

288 NETWORK FLOW THEORY

Example 9.18 (Transportation/Assignment Problem) The transportation prob-

lem (8.3) is a special case of the minimum cost-ﬂow problem. Here there are no interme-

diate nodes; only source and destination nodes. Furthermore, the upper bounds on the

ﬂows are implied by the formulation.

The assignment problem given by (8.20), (8.21), (8.22), and (8.23) is a special case of

the transportation problem in which all b

i

at supply nodes are +1 and all b

i

at demand

nodes are −1. Thus, it too can be represented as a minimum cost-ﬂow problem.

Example 9.19 (Maximal Flow Problem) The maximal ﬂow problem of Section 9.3

is almost in the minimum cost-ﬂow format. It can be easily converted to a maximal ﬂow

problem as shown in Exercise 9.7 on Page 264.

 Exercise 9.36 (Shortest Path Problem) Show how the shortest path problem of

Section 9.5 can be set up as a minimum cost-ﬂow problem. Hint: Reformulate the problem

into one of sending exactly one unit of ﬂow from the source to the destination.

9.8 THE NETWORK SIMPLEX METHOD

In this section we show how to simplify the Simplex Method so that it can be applied

to solve graphically, by hand, a minimum cost-ﬂow network problem with, say, less

than 100 nodes. The methodology can also be applied eﬃciently to solve, with a

computer, larger problems using special data structures. There are three ways in

which we can get computational savings:

1. Exploiting the fact that (by deleting a redundant node balance equation or

adding an artiﬁcial variable) every basis is triangular.

2. Exploiting the fact that all calculations involve additions and subtractions

only because the elements of every basis are +1, −1, or 0.

3. Exploiting the fact that typically not all the prices need to be updated when

a new column corresponding to an arc enters the basis.

We have already seen a specialized version of the Simplex Method applied to

the transportation problem in Chapter 8. The network version developed here has

similarities and can be used to solve the minimum cost-ﬂow problem very eﬃciently.

We assume that the minimum cost-ﬂow problem is in, what we call, standard

form; namely, it is one in which the arc ﬂows are nonnegative with no speciﬁed

upper bounds:

Minimize



(i,j)∈Ac

c

ij

x

ij

= z

subject to



i∈Af (k)

x

ki

−



j∈Bf (k)

x

jk

= b

k

for all k ∈Nd,

0 ≤ x

ij

≤∞ for all (i, j) ∈Ac,

(9.17)

9.8 THE NETWORK SIMPLEX METHOD 289

.

..

.

1

.

..

.

2

.

..

.

3

.

..

.

4

.

..

.

5

.

..

.

..

.

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

.

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

.

b

1

=8

b

2

=7

b

3

=−5

b

5

=−10

c

12

=1

c

13

=2

c

24

=3

c

34

=1

c

14

=2 c

45

=4

c

23

=2

c

25

=3

c

35

=1

Figure 9-22: Example of a Minimum Cost-Flow Problem

where



k∈Nd

b

k

=0.

Recall from Section 9.1 that the ﬂow through a network is represented by a

node-arc incidence matrix where each column corresponding to an arc (i, j) has

exactly two nonzero entries: +1 in row i and −1inrowj. In matrix notation, each

column of A corresponding to an arc s =(i, j) in the network can be written as

A

•s

= e

i

− e

j

, (9.18)

where e

i

is a unit-vector with 1 in position i and e

j

is a unit-vector witha1in

position j.

Example 9.20 (Minimum Cost-Flow Problem) An example of a minimum cost-ﬂow

problem in standard form is shown in Figure 9-22. The costs c

ij

and the demand/supply

b

i

are shown on the network. The resulting coeﬃcient matrix is shown below:

A =







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

1 111000000

2 −100111000

30−10−100110

400−10−10−101

5 00000−10−1 −1







and

b

T

=(8 7 −50−10 ) .

 Exercise 9.37 Show that an undirected arc (i, j) with cost c

ij

≥ 0, regardless of whether

the ﬂow is from i to j or from j to i, can be replaced by two directed arcs (i, j) and (j, i)

each with the same cost c

ij

= c

ji

. Show that this reduction to a linear program is not

valid if c

ij

< 0.

290 NETWORK FLOW THEORY

.

..

.

..

.

..

.

..

.

..

.

..

.

..

.

..

.

..

.

Root Node

Artiﬁcial Arc

Figure 9-23: Rooted Spanning Tree

BASES, TREES, AND INTEGRAL PROPERTY

Note that the system (9.17) contains at least one redundant equation.

LEMMA 9.20 (Rank of a Connected Network) The node-arc incidence

matrix A of a connected network with m ≥ 2 nodes has rank m −1.

 Exercise 9.38 Demonstrate that the system shown in Example 9.20 contains exactly

one redundant equation.

 Exercise 9.39 Since the rank of any m − 1 rows of the node-arc incidence matrix of a

connected network is rank m − 1, show that any row may be regarded as dependent on

the remaining m − 1 rows and may be dropped as redundant.

 Exercise 9.40 Show that if the network is not connected, there is more than one

redundant equation.

We now know that the rank of A is m −1 and we know from Exercise 9.39 that

we can drop any row of the matrix and solve the resulting problem. Instead of

dropping a row, we can augment the columns by an artiﬁcial unit-vector column,

say e

m

, and associate with it an artiﬁcial variable x

n+1

≥ 0. This will make the

rank equal to m. If we were now to apply the Simplex Method to the resulting linear

program, x

n+1

will be zero in every solution, feasible or otherwise, and therefore it

does not matter what cost we assign to the artiﬁcial variable.

 Exercise 9.41 Prove this last statement.

Adding such an artiﬁcial variable x

n+1

corresponds to augmenting the directed

network by a symbolic arc that starts at node m and has no head node. We will

refer to such an arc as an artiﬁcial arc (see Figure 9-23).

9.8 THE NETWORK SIMPLEX METHOD 291

Deﬁnition (Root Node): The node associated with the artiﬁcial arc is referred

to as a root node. If the root node corresponds to the last row, then the

artiﬁcial arc corresponds to the column e

m

, the unit vector with 1 in the mth

position. The artiﬁcial arc will be denoted by (k,∞) if the root arc is incident

at node k.

Deﬁnition (Rooted Spanning Tree): A spanning tree in a directed network

with a designated root node (and associated artiﬁcial arc) is called a rooted

spanning tree.

THEOREM 9.21 (Basis for the Network) In a connected network, if we

designate a node as the root node and add an artiﬁcial arc starting at the root, then

the node-arc incidence matrix of any rooted spanning tree is a basis matrix for the

network.

 Exercise 9.42 Prove Theorem 9.21.

Because the basis is triangular, it is easy to eﬃciently ﬁnd a solution to Bx

B

= b

and B

T

π = c

B

. Furthermore, because the elements of B are all +1, −1, or 0, it is

easy to see that if b is integral then so is x

B

and if c

B

is integral then so is π. This

property is formalized through the next two exercises.

 Exercise 9.43 Show that if b

i

are integral and the capacity bounds are integral, then

the solution to any of the minimum cost-ﬂow problems (9.16) or (9.17) is integral.

 Exercise 9.44 Every element of the inverse of the basis matrix B is +1, −1, or 0. Hint:

Recall that column j of B

−1

is the solution to By = e

j

.

 Exercise 9.45 Show that the representation of nonbasic columnA

•s

in terms of the

basis B, namely B

−1

A

•s

, consists only of +1, −1, and 0 components.

SOLVING FOR THE BASIC VARIABLES

Because the system of equations is triangular, it is straightforward to solve the

system Bx

B

= b for the values of the basic variables x

B

. These values can be

obtained directly by examining the tree (or subgraph) corresponding to the basis.

We start by examining all the end nodes; there are at least two end nodes. Because

exactly one arc is incident to each end node, the corresponding equation in the

system Bx

B

= b contains only one variable, and because their coeﬃcient is +1 or

−1, it can be easily evaluated. If the arc points out of end node k, the arc ﬂow is

set to b

k

; if the arc points into the end node k, the arc ﬂow is set to −b

k

. Once

this is done, the nodes are examined to see which have all its incident arcs assigned

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

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