文档介绍：Linear Programming: Foundations and Extensions
Robert J. Vanderbei
DEPARTMENT OF OPERATIONS RESEARCH AND FINANCIAL ENGINEERING,
PRINCETON UNIVERSITY, PRINCETON, NJ 08544
E-mail address: ******@
LINEAR PROGRAMMING: FOUNDATIONS AND EXTENSIONS
Second Edition
Copyright
c 2001 by Robert J. Vanderbei. All rights reserved. Printed in the United States of America. Except as permitted
under the United States Copyright Act of 1976, no part of this publication may be reproduced or distributed in any form or
by any means, or stored in a data base or retrieval system, without the prior written permission of the publisher.
ISBN 0-0000-0000-0
The text for this book was formated in Times-Roman and the mathematics was formated in Michael Spivak’s Mathtimes
using AMS-LATEX(which is a macro package for Leslie Lamport’s LATEX, which itself is a macro package for Donald
Knuth’s TEXtext formatting system) and converted from device-independent to postscript format using DVIPS. The fig-
ures were produced using SHOWCASE on a Silicon Graphics, Inc. workstation and were incorporated into the text as
encapsulated postscript files with the macro package called .
To my parents, Howard and Marilyn,
my dear wife, Krisadee,
and the babes, Marisa and Diana
Contents
Preface xiii
Preface to 2nd Edition xvii
Part 1. Basic Theory—The Simplex Method and Duality 1
Chapter 1. Introduction 3
1. Managing a Production Facility 3
2. The Linear Programming Problem 6
Exercises 8
Notes 10
Chapter 2. The Simplex Method 13
1. An Example 13
2. The Simplex Method 16
3. Initialization 19
4. Unboundedness 22
5. Geometry 22
Exercises 24
Notes 27
Chapter 3. Degeneracy 29
1. Definition of Degeneracy 29
2. Two Examples of Degenerate Problems 29
3. The Perturbation/Lexicographic Method 32
4. Bland’s Rule 36
5. Fundamental Theorem of Linear Programming 38
6. Geometry 39
Exercises 42
Notes 43
Chapter 4. Efficiency of the Simplex Me