Linear Programming: 1: Introduction (Springer Series in Operations Research and Financial Engineering) (v. 1)

✍ Scribed by George B. Dantzig, Mukund N. Thapa

• Publisher: Springer
• Year: 1997
• Tongue: English
• Leaves: 474
• Edition: 1
• Category: Library

✦ Synopsis

This book provides a comprehensive introduction to linear programming which encompasses all the major topics students will encounter in courses on the subject. The authors aim to teach both the underlying mathematical foundations and how these ideas are implemented in practice. The book illustrates all the concepts with both worked examples and plenty of exercises. In addition, Windows software is provided with the book so that students can try out numerical methods using the examples and exercises and hone their skills in interpreting the results. As a result, this will make an ideal textbook for all those coming to the subject for the first time.Authors'note: A problem recently found with the software is due to a bug in Formula One, the third party commercial software package that was used for the development of the interface. It occurs when the date currency, etc. format is set to a non-United States version. Please try setting your computer date/currency option to the United States. The new version of Formula One, when ready, will be posted on WWW.

✦ Table of Contents

Contents......Page 10
List of Figures......Page 16
List of Tables......Page 20
FOREWORD......Page 22
OUTLINE OF CHAPTERS......Page 34
DEFINITION OF SYMBOLS......Page 38
1 THE LINEAR PROGRAMMING PROBLEM......Page 40
1.1 SOME SIMPLE EXAMPLES......Page 41
1.2 MATHEMATICAL STATEMENT......Page 46
1.3 FORMULATING LINEAR PROGRAMS......Page 47
1.4 EXAMPLES OF MODEL FORMULATION......Page 51
1.5 BOUNDS......Page 60
1.6 AXIOMS......Page 61
1.7 NOTES & SELECTED BIBLIOGRAPHY......Page 62
1.8 PROBLEMS......Page 64
2.1 TWO-VARIABLE PROBLEM......Page 74
2.2 TWO-EQUATION PROBLEM......Page 76
2.3 FOURIER-MOTZKIN ELIMINATION......Page 82
2.4 INFEASIBILITY THEOREM......Page 91
2.5 NOTES & SELECTED BIBLIOGRAPHY......Page 92
2.6 PROBLEMS......Page 93
3 THE SIMPLEX METHOD......Page 102
3.2 THE SIMPLEX ALGORITHM......Page 103
3.3 SIMPLEX METHOD......Page 115
3.4 BOUNDED VARIABLES......Page 122
3.5 REVISED SIMPLEX METHOD......Page 128
3.6 NOTES & SELECTED BIBLIOGRAPHY......Page 136
3.7 PROBLEMS......Page 137
4 INTERIOR-POINT METHODS......Page 152
4.1 BASIC CONCEPTS......Page 154
4.2 PRIMAL AFFINE / DIKIN S METHOD......Page 157
4.3 INITIAL SOLUTION......Page 160
4.4 NOTES & SELECTED BIBLIOGRAPHY......Page 161
4.5 PROBLEMS......Page 163
5.1 DUAL AND PRIMAL PROBLEMS......Page 168
5.2 DUALITY THEOREMS......Page 173
5.3 COMPLEMENTARY SLACKNESS......Page 174
5.4 OBTAINING A DUAL SOLUTION......Page 175
5.5 NOTES & SELECTED BIBLIOGRAPHY......Page 177
5.6 PROBLEMS......Page 178
6.1 RESTRICTED VARIABLES......Page 184
6.2 UNRESTRICTED (FREE) VARIABLES......Page 185
6.3 ABSOLUTE VALUES......Page 186
6.4 GOAL PROGRAMMING......Page 189
6.5 MINIMIZING THE MAXIMUM OF LINEAR FUNCTIONS......Page 191
6.6 CURVE FITTING......Page 193
6.7 PIECEWISE LINEAR APPROXIMATIONS......Page 196
6.9 PROBLEMS......Page 201
7 PRICE MECHANISM AND SENSITIVITY ANALYSIS......Page 210
7.1 THE PRICE MECHANISM OF THE SIMPLEX METHOD......Page 211
7.2 INTRODUCING A NEW VARIABLE......Page 223
7.3 INTRODUCING A NEW CONSTRAINT......Page 225
7.4 COST RANGING......Page 227
7.5 CHANGES IN THE RIGHT-HAND SIDE......Page 229
7.6 CHANGES IN THE COEFFICIENT MATRIX......Page 231
7.7 THE SUBSTITUTION EFFECT OF NONBASIC ACTIVITIES ON BASIC ACTIVITIES......Page 237
7.9 PROBLEMS......Page 238
8.1 THE CLASSICAL TRANSPORTATION PROBLEM......Page 244
8.2 STANDARD TRANSPORTATION ARRAY......Page 251
8.3 FINDING AN INITIAL SOLUTION......Page 253
8.4 FAST SIMPLEX ALGORITHM FOR THE TRANSPORTATION PROBLEM......Page 261
8.5 THE ASSIGNMENT PROBLEM......Page 268
8.6 EXCESS AND SHORTAGE......Page 272
8.7 PRE-FIXED VALUES AND INADMISSIBLE SQUARES......Page 278
8.8 THE CAPACITATED TRANSPORTATION PROBLEM......Page 279
8.9 NOTES & SELECTED BIBLIOGRAPHY......Page 283
8.10 PROBLEMS......Page 284
9.1 TERMINOLOGY......Page 292
9.2 FLOWS AND ARC-CAPACITIES......Page 297
9.3 AUGMENTING PATH ALGORITHM FOR MAXIMAL FLOW......Page 301
9.4 CUTS IN A NETWORK......Page 314
9.5 SHORTEST ROUTE......Page 316
9.6 MINIMAL SPANNING TREE......Page 321
9.7 MINIMUM COST-FLOW PROBLEM......Page 325
9.8 THE NETWORK SIMPLEX METHOD......Page 327
9.9 THE BOUNDED VARIABLE PROBLEM......Page 338
9.10 NOTES & SELECTED BIBLIOGRAPHY......Page 340
9.11 PROBLEMS......Page 343
A.1 SCALARS, VECTORS, AND MATRICES......Page 354
A.2 ARITHMETIC OPERATIONS WITH VECTORS AND MATRICES......Page 356
A.3 LINEAR INDEPENDENCE......Page 359
A.5 NORMS......Page 360
A.6 VECTOR SPACES......Page 363
A.8 MATRICES WITH SPECIAL STRUCTURE......Page 365
A.9 INVERSE OF A MATRIX......Page 368
A.10 INVERSES OF SPECIAL MATRICES......Page 369
A.11 DETERMINANTS......Page 370
A.12 EIGENVALUES......Page 372
A.13 POSITIVE-DEFINITENESS......Page 375
A.15 PROBLEMS......Page 376
B.1 SOLUTION SETS......Page 380
B.2 SYSTEMS OF EQUATIONS WITH THE SAME SOLUTION SETS......Page 382
B.3 HOW SYSTEMS ARE SOLVED......Page 384
B.4 ELEMENTARY OPERATIONS......Page 385
B.5 CANONICAL FORMS, PIVOTING, AND SOLUTIONS......Page 388
B.6 PIVOT THEORY......Page 393
B.8 PROBLEMS......Page 396
A......Page 400
B......Page 401
C......Page 405
D......Page 407
F......Page 426
G......Page 430
H......Page 435
J......Page 437
K......Page 438
L......Page 440
M......Page 442
N......Page 445
P......Page 446
R......Page 447
S......Page 449
T......Page 452
V......Page 454
W......Page 456
Z......Page 457
Index......Page 460