Chapter 16. Linear Programming

Formulating and solving optimisation problems with linear constraints.

Overview

This chapter introduces linear programming (LP) — the optimisation of a linear objective function subject to linear inequality constraints. Topics include the simplex method, LP duality, and applications to combinatorial optimisation. The chapter focuses on the theory and formulations rather than algorithmic implementations in the LLP framework; consequently, no companion programs are provided for this chapter.