2.6. Canonical Form and Standard Form

So far, we have focused on discussing how to model some optimization problems using LPs. More examples will follow in subsequent chapters: Linear programming will be used as a tool to express optimization problems throughout this book. Chapter 3 is concerned with discussing the most widely used algorithm for solving LPs, the Simplex Algorithm. This algorithm assumes that its input is in a particular form. This section introduces two standard representations of linear programs, the canonical form and the standard form; the latter, sometimes also called slack form, is the one the Simplex Algorithm works with.¹ Canonical form is important as the basis for the theory of LP duality, which will be the basis for a number of algorithms discussed in these notes.