Linear Programming

The simplest type of constrained optimization problem is realized when the functions f(x), g(x), and h(x) in (3.1.1) are all linear in x. The resulting formulation is known as a linear programming (LP) problem and plays a central role in virtually every branch of optimization. Many real situations can be formulated or approximated as LPs, optimal solutions are relatively easy to calculate, and computer codes for solving very large instances consisting of millions of variables and hundreds of thousands of constraints are commercially available. Another attractive feature of linear programs is that various subsidiary questions related, for example, to the sensitivity of the optimal solution to changes in the data and the inclusion of additional variables and constraints can be analyzed with little effort.