Dantzig G., Thapa M. Linear programming. Vol.1. Introduction
Подождите немного. Документ загружается.
312 NETWORK FLOW THEORY
9.21 Show that conditions 0 ≤ x
ij
≤ 1,
(i,j)∈A
x
ij
= m −1,
(i,j)∈A
w
ij
x
ij
= min
are necessary but not sufficient conditions for a minimal spanning tree even if
the system solves in integers.
9.22 Suppose that in a minimum cost-flow problem restrictions are placed on the
total flow leaving a node k; i.e.,
¯
θ
l
k
≤
j∈Af (k)
x
kj
≤
ˆ
θ
l
k
.
Show how to modify these restrictions to convert the problem into a minimum
cost-flow problem of the form (9.16).
9.23 A variation of the minimum cost-flow problem (9.16) is to place upper and lower
bounds on the conservation of flow constraints at each node; i.e.,
Minimize
(i,j)∈Ac
c
ij
x
ij
= z
subject to b
l
k
≤
j∈Af (k)
x
kj
−
i∈Bf (k)
x
ik
≤ b
u
k
for all k ∈Nd,
l
ij
≤ x
ij
≤ h
ij
for all (i, j) ∈Ac,
where b
l
k
and b
u
k
, the lower and upper bounds on the conservation of flow at
each node k, are given. Show how to convert this problem into the standard
minimum cost-flow form (9.16).
9.24 Pick arbitrary scalars β
i
for each node i ∈Nd for the minimum cost-flow prob-
lem. Show that the optimal flow vectors are unaffected if the arc costs c
ij
are
replaced by
ˆc
ij
= c
ij
+ β
j
− β
i
.
How is
ˆz =
(i,j)∈Ac
ˆc
ij
x
ij
related to
z =
(i,j)∈Ac
C
ij
x
ij
?
9.25 The Caterer Problem (Jacobs[1964] in Dantzig[1963]). A caterer has booked
his services for the next T days. He requires r
t
fresh napkins on the tth day,
t =1,...,T. He sends his soiled napkins to the laundry, which has three speeds
of service, f = 1, 2, or 3 days. The faster the service, the higher the cost c
f
of
laundering a napkin. He can also purchase new napkins at a cost c
o
. He has an
initial stock of s napkins. The caterer wishes to minimize his total outlay.
(a) Formulate as a network problem. Hint: Define the caterer at time t as a
“source point” in an abstract network for soiled napkins that are connected
to “laundry points” t +1, t +2, t + 3. The reverse arc is not possible. The
laundry point t is connected to a fresh napkin “destination point t,” which
in turn is connected to the same type point for t +1.
(b) Assign values to the various parameters and solve the problem.
9.11 PROBLEMS 313
9.26 Suppose that the linear cost function for the minimum cost-flow problem is
replaced by a separable piecewise linear function (see Section 6.7.3). Show how
to convert this problem to the standard minimum cost-flow problem form (9.16).
This page intentionally left blank
APPENDIX A
LINEAR ALGEBRA
In this chapter we briefly review some key concepts of linear algebra. Some of these
concepts are elaborated upon in the rest of the book. For details on the concepts
discussed here, the reader should refer to any of the standard linear algebra texts.
In this book we have assumed that the reader has working knowledge of linear
algebra. However, we start with the basics and briefly cover all the relevant linear
algebra required to understand the concepts discussed in this book.
A.1 SCALARS, VECTORS, AND MATRICES
In this section we define scalars, vectors, and matrices.
Definition (Scalar):Ascalar is a real or complex number. In this book
scalars will often be denoted by lowercase Greek letters in order to distinguish
them from vectors and matrices.
Definition (Vector):Avector is an ordered collection of scalars.
Vectors will be represented by lower case letters of the alphabet. A subscript on a
vector will denote a particular element of the vector. For example, x
4
will denote
the fourth element of the vector x. Superscripts on a vector will denote different
vectors. For example, x
k
will be a vector different from the vector x
n
.
A vector per se is just an ordered collection ( x
1
,x
2
,... ,x
n
), neither a row nor
column vector. A row vector is one whose elements are displayed horizontally, and
a column vector is a vector whose elements are displayed in a vertical column.
315
316 LINEAR ALGEBRA
In this book, a vector, unless otherwise specified, will be understood to be a
column vector and have the form
x =
x
1
x
2
.
.
.
x
n
. (A.1)
To represent a column vector x as a row vector, we will take the transpose of x,
denoted by x
T
(“x-transpose”).
Definition (Vector Transpose): The transpose of a vector x, denoted by x
T
,is
defined as the same ordered collection of scalars as in x but with the ordering
going from left to right, i.e.,
x
T
=(x
1
,x
2
,... ,x
n
) . (A.2)
Definition (Matrix):Amatrix is a rectangular array of numbers. It may be
viewed as an ordered collection of column vectors each of which is of the same
dimension, or as an ordered collection of row vectors each of which is of the
same dimension.
Matrices will be represented by uppercase letters of the alphabet. A double sub-
script will denote a particular element of the matrix. For example, a
34
and A
34
will
both denote the element in row 3 and column 4 of the matrix A. Furthermore A
•j
will denote the jth column of A, and A
i•
will denote the ith row of A.
The transpose operation is also defined for a matrix.
Definition (Matrix Transpose): The transpose of a matrix, denoted by A
T
,
is a new matrix that is the collection of the transpose of the column vectors
in the same order as the columns of the original matrix. Thus, the net effect
is to interchange the roles of the row and column indices. For example, if the
element in the ith row and jth column of A is A
ij
, then the element in the
jth row and ith column of A
T
is A
ij
.
Example A.1 (Transpose) Consider, for example, the matrix A given by
A =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
a
m2
... a
mn
.
The transpose of A is given by
A
T
=
a
11
a
21
... a
m1
a
12
a
22
... a
m2
.
.
.
.
.
.
.
.
.
.
.
.
a
1n
a
2n
... a
mn
.
A.2 ARITHMETIC OPERATIONS WITH VECTORS AND MATRICES 317
Definition (Diagonal, Off-diagonal, Super-Diagonal, Sub-Diagonal): The ma-
trix elements on the diagonal, that is, a
ii
, are called diagonal elements. All
other elements a
ij
, i = j are called off-diagonal elements. The off-diagonal
elements are further classified as super-diagonal and sub-diagonal elements.
Super-diagonal elements are the elements above the diagonal, that is, a
ij
for
all j>i. Sub-diagonal elements are the elements below the diagonal, that is,
a
ij
for all i>j.
A.2 ARITHMETIC OPERATIONS WITH
VECTORS AND MATRICES
Arithmetic operations with vectors and matrices are similar to arithmetic operations
performed with scalars. The main difference is that the operations are ordered in
a special way to take into account the ordering in the definition of vectors and
matrices.
Definition (Equal Matrices):Twom × n matrices A and B are equal if and
only if each element of A is equal to the corresponding element of B.
That is, A and B are equal if and only if
a
ij
= b
ij
for i =1,...,m, j =1,...,n. (A.3)
Similarly two n dimensional vectors x and y are equal if and only if each element
of x is equal to the corresponding element of y.
Multiplication of a vector (or matrix) by a scalar amounts to multiplying each
element of the vector (or matrix) by the scalar. That is,
αA =
αa
11
αa
12
... αa
1n
αa
21
αa
22
... αa
2n
.
.
.
.
.
.
.
.
.
.
.
.
αa
m1
αa
m2
... αa
mn
. (A.4)
The sum of two n-dimensional vectors is another n-dimensional vector whose el-
ements are the sums of the corresponding elements in each of the two vectors. Sim-
ilarly, the sum of two m ×n matrices is another m × n matrix formed by summing
the corresponding elements in the matrix. The operation of addition is illustrated
below for two n-dimensional vectors x and y.
x + y =
x
1
x
2
.
.
.
x
n
+
y
1
y
2
.
.
.
y
n
=
x
1
+ y
1
x
2
+ y
2
.
.
.
x
n
+ y
n
. (A.5)
The rules for matrix (and vector) multiplication are a bit more involved as
discussed next.
318 LINEAR ALGEBRA
Definition (Scalar (Dot) Product): The scalar (inner, dot) product of two
vectors is a scalar that is the sum of the products of the corresponding elements
of the two vectors, i.e.,
x
T
y =(x
1
,x
2
,... ,x
n
)
y
1
y
2
.
.
.
y
n
=
n
j=1
x
j
y
j
= x
1
y
1
+ x
2
y
2
+ ···+ x
n
y
n
. (A.6)
The scalar product of two n-dimensional vectors x and y is denoted by x
T
y (or, in
some books, by x, y). It is defined in a manner similar to the product between
two scalars. The one exception to this is the fact that the product of two nonzero
scalars cannot be zero, whereas the scalar product of two nonzero vectors can be
zero as can be seen by taking the scalar product of the two vectors x and y shown
below:
x =
1
0
0
and y =
0
1
0
.
Definition (Outer Product): The outer product of two vectors, denoted by
xy
T
, is a matrix as illustrated in (A.7):
xy
T
=
x
1
x
2
.
.
.
x
n
( y
1
,y
2
,... ,y
n
)=
x
1
y
1
x
1
y
2
... x
1
y
n
x
2
y
1
x
2
y
2
... x
2
y
n
.
.
.
.
.
.
.
.
.
.
.
.
x
n
y
1
x
n
y
2
... x
n
y
n
. (A.7)
The matrix xy
T
is special and is called a rank-one matrix (See Section A.7).
The product of an m × n matrix A times an n-dimensional vector x is another
vector Ax. This product Ax is defined only if the number of columns of A is equal
to the dimension of the vector x. The product of a matrix A times a vector x can
be thought of in one of two ways. The first way is to think of each element of the
resultant vector Ax as the scalar product of the corresponding row of the matrix A
times the vector x. That is,
Ax =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
a
m2
... a
mn
x
1
x
2
.
.
.
x
n
=
n
j=1
a
1j
x
j
n
j=1
a
2j
x
j
.
.
.
n
j=1
a
mj
x
j
=
A
1•
x
A
2•
x
.
.
.
A
m•
x
. (A.8)
Before looking at the second way of representing Ax, we need to define linear
combinations of vectors.
A.2 ARITHMETIC OPERATIONS WITH VECTORS AND MATRICES 319
Definition (Linear Combination):Alinear combination of the n vectors
v
1
,v
2
,... ,v
n
is another vector, say v, defined by
v = α
1
v
1
+ α
2
v
2
+ ···+ α
n
v
n
,
where α
i
, i =1,...,n, are scalars.
With the definition of a linear combination of vectors, it is straightforward to
see that the second way to think of Ax is to consider Ax as being the vector formed
by taking linear combinations of the columns of the matrix A with the weight on
the jth column of A being x
j
. This is illustrated below.
Ax =
a
11
a
21
.
.
.
a
m1
x
1
+
a
12
a
22
.
.
.
a
m2
x
2
+ ···+
a
1n
a
2n
.
.
.
a
mn
x
n
=
n
j=1
A
•j
x
j
. (A.9)
The product of an m × n matrix A times an n × p matrix B is another matrix
C = AB, which is of dimension m × p. This product AB is defined only if the
number columns of matrix A is equal to the number of rows of matrix B. The
product of a matrix A times a matrix B can be thought of in one of two ways.
The first way is to think of the ijth element of the resultant matrix C = AB as
the scalar product of the ith row of the matrix A times the the jth column of the
matrix B. That is, the ijth element of C is given by
c
ij
=
n
k=1
a
ik
b
kj
= A
i•
B
•j
. (A.10)
The second way to think of the matrix product C = AB is to think of each
column of C as having been generated by taking linear combinations of the columns
of the matrix A. That is, the jth column of the matrix C uses the elements of the
jth column of the matrix B as the weights to form the linear combination of the
columns of the matrix A. For example,
C
•j
=
n
k=1
A
•k
b
kj
.
From the above discussion on vector/matrix operations, the reader can easily
verify that:
1. Matrix (vector) addition satisfies
associativity: A +(B + C)=(A + B)+C;
commutativity: A + B = B + A.
320 LINEAR ALGEBRA
2. The scalar product for vectors satisfies
commutativity: x
T
y = y
T
x;
distributivity over vector addition: x
T
(y + z)=x
T
y + x
T
z.
3. Matrix multiplication satisfies
associativity: A(BC)=(AB)C;
distributivity over matrix addition: A(B + C)=AB + AC.
An additional property that matrix multiplication satisfies is
(AB)
T
= B
T
A
T
. (A.11)
However, note that matrix multiplication does not satisfy the property of
commutativity even if the matrices are square. That is, in general,
AB = BA. (A.12)
Exercise A.1 Prove (A.12).
A.3 LINEAR INDEPENDENCE
In this section we describe linear independence of vectors.
Definition (Linearly Independent): The vectors x
1
,x
2
,... ,x
n
are said to be
linearly independent if and only if all nontrivial linear combinations of the
vectors are nonzero. That is,
α
1
x
1
+ α
2
x
2
+ ···+ α
n
x
n
= 0 unless α
1
= α
2
= ···= α
n
=0.
Example A.2 (Dependence and Independence) As an illustration of the concept
of dependence and linear independence consider the following three 3-dimensional vectors:
v
1
=
2
0
4
,v
2
=
0
3
−4
,v
3
=
4
3
4
.
It is easy to see that v
3
=2v
1
+v
2
,or2v
1
+v
2
−v
3
= 0. That is, v
3
is a linear combination
of v
1
and v
2
, or, in other words, v
3
is dependent on v
1
and v
2
. On the other hand, any
two of the three vectors v
1
, v
2
, v
3
are linearly independent, since neither of them can be
written as a multiple of only one of the other vectors.
A.4 ORTHOGONALITY 321
A.4 ORTHOGONALITY
The concept of orthogonality plays an important role in the solution of least squares
problems and also for the solution of linear programs using interior point methods.
Definition (Orthogonal and Orthornormal): The vectors q
1
,q
2
,... ,q
n
are
said to be orthogonal to each other if and only if
(q
i
)
T
q
j
=0ifi = j and (q
i
)
T
q
j
=0ifi = j. (A.13)
The vectors are said to be orthonormal if they are orthogonal and
(q
i
)
T
q
j
= 1 when i = j. (A.14)
THEOREM A.1 (Orthogonality Implies Independence) A set of orthog-
onal vectors are linearly independent.
Proof. In order to prove this, consider any linear combination of the n orthogonal
vectors q
1
,q
2
,... ,q
n
that equals zero. That is,
α
1
q
1
+ α
2
q
2
+ ···+ α
n
q
n
=0.
Take the scalar product of the above vector equation with the vector q
j
for arbi-
trary j. Then, by the definition of orthogonality, all scalar products of the form
(q
j
)
T
q
i
must vanish whenever i = j. Thus, the equation reduces to
α
j
(q
j
)
T
q
j
=0.
Since we know that (q
j
)
T
q
j
=0,α
j
must be zero. We showed this for arbitrary
α
j
,thusα
i
= 0 for i =1,...,n, and the result follows from the definition of linear
independence.
Exercise A.2 A set of n nonzero vectors p
1
,p
2
,... ,p
n
are said to be conjugate, or
G-orthogonal, with respect to a matrix G if they satisfy
(p
i
)
T
Gp
j
= 0 for all i = j.
If G is a positive-definite symmetric n × n matrix, show that the vectors p
1
,p
2
,... ,p
n
are
linearly independent.
A.5 NORMS
The norm of a vector or a matrix provides a means for measuring the size of the
vector or matrix.