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

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

352 LINEAR EQUATIONS

CANONICAL SYSTEM

If the original system is consistent, the system formed by dropping the vacuous

equations from the reduced system is called its canonical equivalent with the pivotal

variables as basic:

, (B.24)

where

A is r × (n − r) and

is of length r.

UNIQUENESS OF A CANONICAL EQUIVALENT

The fundamental property of a canonical system resulting from the reduction pro-

cess of a consistent system of equations is that for any other system with the same

solution set, a reduction can be eﬀected using the same pivotal variables, and the re-

sulting canonical system will be identical if the equations are reordered (permuted)

so that the unit coeﬃcient of the corresponding basic variables is on the same row

in both systems (in detached coeﬃcient form).

Example B.8 (Canonical Equivalent) The following two canonical systems are clearly

equivalent if in the second system, the second row is exchanged with the ﬁrst row.

+2x

− 3x

and

− 3x

+2x

=5.

THEOREM B.6 (Uniqueness of a Canonical Equivalent) There is at most

one equivalent canonical system with respect to a ﬁxed ordered set of basic variables.

Proof. Let there be two equivalent canonical systems relative to the ordered set

of basic variables x

,... ,x

. We wish to show that the two canonical systems

are identical. Substituting x

r+1

= x

r+2

= ···= x

= 0 into the ﬁrst system, we get

, ···,x

. Because of equivalence, substitution into the second

system should yield the same values; this will only be true if their respective constant

terms

are the same. Similarly, substituting the values for independent variables

of x

r+1

= x

r+2

= ··· = x

= 0 except x

= 1 will show (after equating constant

terms) that their corresponding coeﬃcients ¯a

of x

are the same. It follows that

the corresponding coeﬃcients are the same for each s = r +1,r+2,...,n.

The above theorem can also be established by applying

LEMMA B.7 (Generating a System from its Canonical Equivalent) If a

system of equations S is equivalent to a canonical system, it can be generated from

the canonical system by a unique linear combination of the equations of the canonical

system, the weights being the coeﬃcients of the basic variables of the equation of the

system S being generated.

 Exercise B.13 Prove Lemma B.7. Use Lemma B.7 to prove Theorem B.6.

B.6 PIVOT THEORY 353

 Exercise B.14 Apply Lemma B.7 to test whether a system is equivalent to a canonical

system.

BASIC SOLUTIONS AND DEGENERATE SOLUTIONS

Basic solutions play a critical role in the solution of linear programs.

Deﬁnition (Basic Solution): The special solution obtained by setting the

independent variables equal to zero and solving for the dependent variables is

called a basic solution.

Thus if (B.17) is the canonical system of (B.16) with basic variables x

,... ,x

the corresponding basic solution is x

b and x

= 0, i.e.,

,...,x

; x

m+1

= x

m+2

= ···= x

=0. (B.25)

Deﬁnition (Degenerate Solution): A basic solution is degenerate if the value

of one or more of the dependent (basic) variables is zero. In particular, the

basic solution (B.25) is degenerate if

= 0 for at least one i.

BASIS

A set of columns (of a system of equations in detached coeﬃcient form) is said to

be a basis if they are linearly independent and each of the other columns can be

generated from them by a linear combination.

Deﬁnition (Basic Columns (Activities)): In accordance with the special usage

in linear programming, the term basis refers to the ordered set of columns of

the original independent system (in detached coeﬃcient form) corresponding

to the ordered set of basic variables of the canonical equivalent. The columns

of the basis are called basic columns (or basic activities).

Example B.9 (Basis) For example, the canonical equivalent of system (B.18) is (B.19)

with respect to variables (x

). Columns corresponding to this ordered set of variables

in (B.18) are



−21



It is easy to verify that these columns are linearly independent and any other column

can be generated from them by a linear combination and hence they form a basis. For

instance, A

•4

=1.A

•2

+3.A

•1

in the original system of equations (B.18) and the same

linear combination also works in the canonical system (B.19)—see Exercise B.9. In the

canonical system it is easy to ﬁnd what linear combination of basic columns will generate

column j; namely, the weights are the same as the coeﬃcients in column j. Thus the

weights (1, 3) are the same as

•4

in the canonical system (B.19).

354 LINEAR EQUATIONS

B.6 PIVOT THEORY

The purpose of this section is to extend the discussion regarding properties of pivot

operations and other characteristics of pivot operations. The ﬁrst important prop-

erty of the pivot operation is its irreversibility except in certain situations.

THEOREM B.8 (Canonical Form After a Pivot Operation) If a system

is in canonical form before a pivot operation, then it is in canonical form after the

pivot operation.

Proof. Suppose that the system is in canonical form with respect to the variables

,... ,x

, i.e.,

Pivoting on ¯a

, where s>m, is the same as multiplying on the left by M given

by Equation (B.21), that is,

+ M

= M

b. (B.26)

Column s − m of M

A is e

, as we have seen earlier. This together with columns

1,...,r − 1,r +1,...,m of M shows that the system is in canonical form with

respect to 1,...,r− 1,s,r+1,...,m.

COROLLARY B.9 (Inverse of a Pivot Operation) If a system is in canon-

ical form, the inverse of a pivot operation is a pivot operation.

COROLLARY B.10 (Pivoting on a Canonical Subsystem of a General

System) Let S be a subsystem of equations S

,... ,S

that is in canonical

form and let E be the remaining equations E

,... ,E

such that there are coef-

ﬁcients of zero for basic variables in the noncanonical equations. That is,

: S

+ Tx

: E

If the pivot term is selected in an equation of S, then the corresponding subsystem

after a pivot operation is in canonical form; the inverse of the pivot operation is

also a pivot operation.

COROLLARY B.11 (Inverse of a Pivot Operation on a Subsystem) Con-

sider the systems S and E deﬁned in Corollary B.10. If the pivot term is selected

in an equation E not in S, then the subsystem corresponding to {S, E} after a pivot

operation is in canonical form; the inverse of the pivot operation is not a pivot

operation on {S, E} unless {S, E} was in canonical form initially.

 Exercise B.15 Prove Corollaries B.9, B.10, and B.11.

B.6 PIVOT THEORY 355

The second important property of the pivot operation is that there is a one-

to-one correspondence between the original system of equations and the system of

equations derived by pivoting. Furthermore, easily deﬁned subsets of the original

and the derived systems are equivalent.

Deﬁnition (Pivotal Subsystem): The pivotal subsystem P is that set of equa-

tions of the original system corresponding to those selected for pivot terms in

a sequence of pivot operations.

It is clear that the number of equations in the pivotal subsystem increases or

remains the same during a sequence of pivot operations, depending on whether or

not the successive pivot terms are selected from among equations corresponding to

the pivotal system or from among the remainder.

THEOREM B.12 (Equivalence and Canonical Form) Let S



be the system

obtained after a sequence of pivot operations on S using rows corresponding to P

of S, and let P



be the set of equations of S



corresponding to the pivotal subsystem

P of S. The system S



is equivalent to S; in particular, P



is equivalent to P and

moreover, P



is in canonical form.

THEOREM B.13 (Pivotal Subsystem Properties) The pivotal subsystem

P is independent and solvable.

 Exercise B.16 Prove Theorems B.12 and B.13.

THEOREM B.14 (Redundancy and Inconsistency Tracing Theorem) If

an equation E



of a reduced system is vacuous (or inconsistent), then in the original

system, E

is either redundant with respect to the pivotal system P or a linear

combination of the equations of P and E

can form an inconsistent equation.

Proof. Let S be the equations of the original system, P be the pivotal subset,

and R be the remainder. Let S



, P



, and R



be the corresponding equations after

pivoting. If equation E

in R is not originally vacuous but becomes so after pivoting,

then

+ λ

+ ···+ λ

+ E

= E



, (B.27)

where (E

,...,E

) are the pivotal equations (not necessarily the ﬁrst k) and E



alternatively either a vacuous or an inconsistent equation. Hence, if E



is vacuous,

is dependent on the others.

The third important property of the pivoting operation is that it provides a

way to show whether or not two systems have the same solution set by trying to

reduce them simultaneously by pivoting step by step, each step using the same

pivotal variables in both systems. The same process will test the equivalence of two

systems.

356 LINEAR EQUATIONS

Deﬁnition (Homogeneous System): It is convenient at this point to recall the

deﬁnition of a homogeneous system. A system Ax = b is homogeneous if the

right-hand side vector is b =0.

Deﬁnition (Homogeneous Solution): A solution x = x

is called a homo-

geneous solution associated with Ax = b, b =0orb =0,ifAx

=0. A

fundamental property of homogeneous solutions is that any scalar multiple of

a homogeneous solution is a homogeneous solution. A homogeneous solution

is called nontrivial if x

=0.

THEOREM B.15 (Equivalence of Homogeneous Systems) Two homoge-

neous systems Ax =0and



Ax =0are equivalent if and only if it is possible to pivot

on both systems with respect to the same set of variables and after pivoting, the two

systems are identical or can be made so after row permutations.

Proof. Let us suppose ﬁrst that it is possible to reduce two homogeneous systems

using the same set of pivot variables. We assume that the equations of the canonical

parts are reordered so that both subsystems are canonical with the same set of basic

variables. If the two systems are to be equivalent, it is necessary that their canonical

parts be identical (see proof of Theorem B.6).

Next let us suppose that the two homogeneous systems are equivalent. By

Theorem B.6 there is at most one equivalent canonical system with respect to a

ﬁxed ordered set of variables for each system. Thus, by the deﬁnition of equivalence,

if it is possible to pivot on one system with respect to a ﬁxed set of variables, it is

also possible to pivot on the second system with respect to the same ﬁxed set of

variables.

COROLLARY B.16 (Equivalence of Linear Systems) Two systems Ax = b

and



Ax =

b are equivalent if and only if Ax − bx

=0and



Ax −

=0are

equivalent.

Proof. It is clear that if a linear combination of Ax = b results in



Ax =

b then the

same linear combination when applied to Ax −bx

= 0 also results in



Ax −

=0.

The converse also is clearly true.

THEOREM B.17 (Equivalent Systems Have Same Solution Sets) Two

solvable systems have the same solution sets if and only if they are equivalent.

 Exercise B.17 Prove Theorem B.17.

The fourth important property of pivoting is that it provides a way to prove a

number of interesting theorems concerning the number of independent and depen-

dent equations of a system.

B.7 NOTES & SELECTED BIBLIOGRAPHY 357

THEOREM B.18 (Number of Equations in Equivalent Systems) Two

equivalent, independent, and consistent systems have the same number of equations.

Proof. Since the two systems are equivalent, independent, and consistent, it is

possible simultaneously to reduce by pivoting the two systems to canonical forms

that are identical. No vacuous equations can happen during the process because

pivoting is actually a sequence of elementary operations, so that by Theorem B.5,

the appearance of such equations would imply the presence of redundant equations

in the original systems, contrary to the assumption of independence. Therefore, the

identical canonical equivalents have the same number of equations as their respective

original systems.

The following three theorems are consequences of the above.

THEOREM B.19 (Equations in Equivalent Canonical Systems) Two

equivalent canonical systems have the same number of equations.

THEOREM B.20 (Number of Equations in the Canonical Equivalent) If

a system can be partitioned into r independent equations and a set of equations de-

pendent on it, then the canonical equivalent of the original system has r equations.

THEOREM B.21 (Independent Set Can Generate the Others) If a sys-

tem has a canonical equivalent with r equations, then any r independent equations

of the system can generate the remainder by linear combinations.

 Exercise B.18 Prove Theorems B.19, B.20, and B.21. Show that r in Theorem B.20

is the rank of the system.

B.7 NOTES & SELECTED BIBLIOGRAPHY

For additional discussions on canonical forms and pivoting see Dantzig [1963]. For a

discussion on LU factorizations and the numerical solution of systems of linear equations

see Linear Programming 2.

B.8 PROBLEMS

B.1 Find a basis for the solution sets of:

358 LINEAR EQUATIONS

(a)

+2x

+3x

+5x

+6x

+8x

+9x

=0.

(b)

− x

+10x

− 2x

+ x

=0.

(c)

+ x

+5x

=0.

(d)

+ x

− 4x

+2x

+ x

− 3x

+3x

− 11x

+3x

− x

+5x

− 5x

=0.

B.2 Determine whether or not there exist solutions to the following systems of equa-

tions

(a)

+2x

+3x

+5x

+6x

+8x

+9x

=1.

(b)

+ x

− 4x

+ x

= −3

+3x

− 11x

− x

+5x

= −5.

(c)

+2x

−2x

+ x

− 3x

=4.

(d)

+2x

+3x

+4x

+7x

+8x

+9x

=10

+3x

+ x

− x

= −2.

B.3 Give the values of λ for which the following system of linear equations

+2x

+7x

+(λ +5)x

+(λ + 11)x

=10

+(λ +3)x

+11x

=10

has (a) no solutions, (b) exactly one solution, and (c) inﬁnitely many solutions.

B.4 Reduce the following system Ax = b to canonical form

+ x

+2x

+ x

+2x

+9x

+4x

+13x

+11x

+2x

=10.

(a) What is the rank of A? What is the rank of [Ab]?

(b) Change the right-hand side of the third equation from a 10 to an 11. Show

that the system is infeasible by ﬁnding the infeasibility multipliers for this

system of equations. Now what is the rank of A? What is the rank of [Ab]?

B.5 Show by a sequence of pivots and row permutations that the following canonical

systems are equivalent:

+ x

and

−x

+ x

−x

+ x

=1.

Use the result just obtained to determine the inverse of the following matrix:



001

101

111



B.8 PROBLEMS 359

which consists of some of the coeﬃcients of the system on the left. Explain

brieﬂy where you got your answer. Change one of the coeﬃcients in the second

system and show that the two systems are not equivalent in general.

B.6 Given the system

Ix + Bu =0, (B.28)

where I is an m × m matrix and B is square and nonsingular, prove that in m

pivots one can convert (B.28) to an equivalent canonical form

−1

x + Iu =0. (B.29)

Discuss how this can be viewed as an algorithm for ﬁnding the inverse of B.

B.7 Let A be an m × n matrix and suppose that we pivot on element (r, s)ofA in

the canonical form [I

| A] and in the resulting tableau exchange columns r

and m + s to obtain [I

A]. Show that if we pivot on element (s, r)of−A

the canonical form [I

|−A

] and in the resulting tableau exchange columns s

and m + r, then we obtain [I

|−

This page intentionally left blank

REFERENCES

Abadie, J. (1965). Verbal Communication to Dantzig.

Abrahamson, P.G. (1983). “A Nested Decomposition Approach for Solving Staircase Lin-

ear Programs,” Technical Report SOL 83-4, Department of Operations Research,

Stanford University, Stanford, CA.

Ackoﬀ, R.L. and Rivett, P. (1963). A Manager’s Guide to Operations Research, Wiley,

New York.

Adler, I. (1976). “Equivalent Linear Programs,” Department of IE & OR, University of

California, Berkeley, California.

Adler, I. and

Ulk¨uc¨u, A. (1973). “On the Number of Iterations in the Dantzig-Wolfe

Decomposition,” in D. M. Himmelblau (ed.), Decomposition of Large Scale Problems,

North-Holland, Amsterdam, the Netherlands, 181–187.

Adler, I., Karmarkar, N., Resende, M.G.C. and Veiga, G. (1990). “Data Strucutres and

Programming Techniques for the Implementation of Karmarkar’s Algorithm,” ORSA

Journal on Computing 1, 84–106.

Adler, I., Resende, M.G.C., Veiga, G., and Karmarkar, N. (1989). “An Implementation of

Karmarkar’s Algorithm for Linear Programming,” Mathematical Programming 44,

297–336.

Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1991). “Network Flows,” in G.L. Nemhauser,

A.H.G. Rinnooy Kan, and M.J. Todd (eds.), Handbooks in Operations Research and

Management Science, Vol 1: Optimization, North-Holland, Amsterdam, the Nether-

lands, 211–369.

Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory, Algorithms,

and Applications, Prentice-Hall, Inc., Englewood Cliﬀs, New Jersey.

Ahuja, R.K., Mehlhorn, K., Orlin, J.B., and Tarjan, R.E. (1990). “Faster Algorithms for

the Shortest Path Problem,” Journal of the Association for Computing Machinery,

37, 211–369.

Ali, A.I., Helgason, R.V., Kennington, J.L., and Lall, H.S. (1978). “Primal Simplex

Network Codes: State of the Art Implementation Technology,” Networks, 8, 315–

339.

361