This textbook for undergraduate courses on linear programming (LP) is intended for students in various disciplines, including informatics, mathematics, and engineering. The book provides a comprehensive treatment of LP problems under a linear algebra approach, necessary for understanding the philosophy of the solving algorithms. MATLAB code is used in an educational manner, in order to explain the fundamental principles and computational details of the LP algorithms. The number of detailed examples enhances the book’s readability, as well as readers’ understanding of the concepts. The book is organized into nine chapters and two appendices.

Chapter 1 introduces the basic notions of optimization under constraints, especially LP, using a simple example. The notions related to LP are described by mathematical formulation and graphical representation. The general formulation of LP problems is defined with the aid of matrices. The same chapter discusses a number of mathematical problems that can be converted to LP problems, like linear fitting, load balancing, resource allocation, classification, and network flow. The chapter concludes with a brief presentation of the basic algorithmic methods for the solution of LP problems.

Chapter 2 starts with the linear algebra process known as Jordan exchange, fundamental for the solution of systems and for understanding the simplex method. The process is described mathematically, providing the corresponding MATLAB code. Next, other relevant linear algebra concepts and tools are discussed, including linear independence, matrix inversion, solution of linear systems, and LU decomposition.

Chapter 3 is devoted to the simplex method. First, the basic definitions are given, and the geometrical representation of the simplex procedure is presented via a numerical example. In a special section, the key concept of a vertex is discussed in detail. Next, the full simplex algorithm is presented in two phases, and explained thoroughly with examples. The chapter is completed with discussions on the termination of the algorithm, and problems initially expressed in nonstandard form, solved by the simplex method.

Chapter 4 discusses another essential concept in LP theory: duality. The presentation is consistent with the general linear algebra viewpoint of the book, emphasizing the dual representation of a matrix by row and column spaces. The duality and rank of linear systems are discussed first, and then the concept of duality in LP is presented theoretically and intuitively through interpretation of numerical examples. The preliminary theory leads to the description of the dual simplex method and its applications to LP problems.

Chapter 5 presents the revised simplex method, a procedure able to solve large linear problems. The chapter starts with the foundations, namely the basic feasible solutions and the basic matrices and their geometric interpretation, and continues with a description of the revised simplex method. The algorithm is given in MATLAB, and various aspects related to its application are presented in detail. A special section is devoted to the treatment of various network flow problems: minimum-cost network flow, shortest path, max flow, and transportation and assignment problems.

Chapter 6 examines the impact on its solution of changes to the data of an LP problem. The great practical importance of this aspect is accurately emphasized, and the changes are categorized into small and large. First, sensitivity analysis is examined for small changes in variables and constraints, and then the topic of parametric programming is discussed, concerning more extensive changes.

Chapter 7 considers extensions of LP problems to other mathematical optimization problems. Nonlinear programming, quadratic programming, linear complementarity problems, and bimatrix games including Nash equilibria are presented, along with their solution methods, always within the framework of MATLAB.

Chapter 8 is an introduction to an alternative class of methods, different from the simplex methodology and suitable for large problems. These are known under the general name of interior-point methods, and they are based on iterations staying in the interior of the feasible region. (This is unlike the simplex method, which moves from vertex to vertex.)

Chapter 9 discusses the applications of LP techniques to approximation, regression, and classification problems, so that the programming theory is wisely connected with statistics and machine learning. These applications involve minimax problems, least-squares approximation, robust estimation, and classification algorithms.

Finally, two appendices are provided. They introduce notions like convex sets and functions, vector norms, and quadratic functions. The second appendix provides a summary of the MATLAB commands used in the book.

Overall, I believe that the linear algebra perspective, under which the programming problems are presented, with the aid of MATLAB software, reveals the mathematical elegance behind methods that are often presented to students as strict algorithms, in a tedious manner, and drained from their mathematical reasoning. The last chapters will be useful for new researchers working on optimization in different scientific areas. The book is highly readable, and does not require advanced knowledge. It is therefore recommended for students, teachers, and researchers looking for a thorough introduction to the principles and methods of LP.