This textbook provides a self-contained introduction to linear programming using MATLAB Software to elucidate the development of algorithms and theory. Early chapters cover linear algebra basics, the simplex method, duality, the solving of large linear problems, sensitivity analysis, and parametric linear programming. In later chapters, the authors discuss quadratic programming, linear complementarity, interior-point methods, and selected applications of linear programming to approximation and classification problems.
Exercises are interwoven with the theory presented in each chapter, and two appendices provide additional information on linear algebra, convexity, and nonlinear functions and on available MATLAB commands, respectively. Readers can access MATLAB codes and associated mex files on the web site corresponding to this textbook.
Only a basic knowledge of linear algebra and calculus is required to understand this textbook, which is geared toward junior- and senior-level undergraduate students, first-year graduate students, and researchers unfamiliar with linear programming.
1 Introduction 1
2 Linear Algebra: A Constructive Approach 17
3 The Simplex Method 45
4 Duality 89
5 Solving Large Linear Programs 117
6 Sensitivity and Parametric Linear Programming 151
7 Quadratic Programming and Complementarity Problems 169
8 Interior-Point Methods 195
9 Approximation and Classification 217
A Linear Algebra, Convexity, and Nonlinear Functions 237
B Summary of Available MATLAB Commands 251