asdasdasd

Introduction
to Linear Optimization

ATHENA SCIENTIFIC SERIES
IN OPTIMIZATION AND NEURAL COMPUTATION
1 . Dynamic Programming and Optimal Control, Vols. I and II, by Dim­
itri P. Bertsekas, 1995.

2.

Nonlinear Programming, by Dimitri P. Bertsekas, 1995.

3. Neuro-Dynamic Programming, by Dimitri P. Bertsekas and John N.
Tsitsiklis, 1996.
4. Constrained Optimization and LagrangeMultiplier Methods, by Dim­
itri P. Bertsekas, 1996.

5. Stochastic Optimal Control: The Discrete-Time Case, by Dimitri P.
Bertsekas and Steven E. Shreve, 1996.
6. Introduction to Linear Optimization, by Dimitris Bertsimas and John
N. Tsitsiklis, 1997.

Introduction
to Linear Optimization
Dimitris Bertsimas
John

N.

Tsitsiklis

Massachusetts Institute of Technology

~

AthenaScientific, Belmont, Massachusetts

Athena Scientific
Post Office Box 391
Belmont, Mass. 02178-9998
U.S.A.
Email: athenasc@world.std.com
and orders: http://world.std.com;- athenasc/

WWW information

Cover Design:

Ann Gallager

©

1997 Dimitris Bertsimas and John N. Tsitsiklis
All rights reserved. No part of this book may be reproduced in any form
by any electronic ormechanical means ( including photocopying, recording,
or information storage and retrieval ) without permission in writing from
the publisher.

Publisher's Cataloging-in-Publication Data
Bertsimas, Dimitris, Tsitsiklis, John N.
Introduction to Linear Optimization
Includes bibliographical references and index
1. Linear programming. 2. Mathematical optimization.
3. Integer programming. 1. Title.96-78786
519.7
T57.74.B465 1997

ISBN 1-886529-19-1

To Georgia,
and to George Michael, who left us so early
To Alexandra and Melina

Contents

Preface . . . . . . . . . . . . . . . . . . . . . xi
1.

Introduction . . . . . . . . . . . .

1

1.1.
1.2.
1.3.
1.4.
1.5.
1.6.
1. 7.
1.8.

Variants o f the linear programming problem .
Examples o f linear programming problemsPiecewise linear convex objective functions
Graphical representation and solution
Linear algebra background and notation
Algorithms and operation counts
Exercises . . . . . . . .
History, notes, and sources

2
6
15
21
26
32
34
38

2.

The geometry of linear programming

41

2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.
2.8.
2.9.
2. 10.
2.11.

Polyhedra and convex sets . .. . . . . . . . .
Extreme points, vertices, and basic feasible solutions
Polyhedra in standard form
Degeneracy . . . . . . . .
Existence of extreme points .
Optimality of extreme points
Representation of bounded polyhedra *
Projections of polyhedra: Fourier-Motzkin elimination *
Summary . . . .
Exercises . .
.
Notes and sources

42
46
53
58
62
65
67
70
75
75
79

3.

Thesimplex method

81

3.1.
3.2.
3.3.

Optimality conditions
. . . . . .
Development o f the simplex method .
Implementations of the simplex method

.

.
.

82
87
94
vii

Contents

viii

3.4.
3.5.
3.6.
3.7.
3.8.
3.9.
3. 10.

Anticycling: lexicography and Bland's rule
Finding an initial basic feasible solution
Column geometry and the simplex method
Computationalefficiency of the simplex method
Summary . . . .
Exercises . . . .
Notes and sources

108
111
119
124
128
129
137

4.

Duality theory . .

139

4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
4.7.
4.8.
4.9.
4. 10.
4.11.
4.12.
4. 13.

Motivation . . . .
The dual problem . .
The duality theorem .
Optimal dual variables as marginal costs
Standard form problems and the dual simplexmethod
Farkas' lemma and linear inequalities . .
From separating hyperplanes to duality*
Cones and extreme rays . . . . .
Representation of polyhedra . . . .
General linear programming duality*
Summary . . . .
Exercises . . . .
Notes and sources

140
142
146
155
156
165
169
174
179
183
186
187
199

5.

Sensitivity analysis

201

5.1.
5.2.
5.3.
5.4.
5.5.
5.6....