## 16.5 Outline

- Introduction
- linear programming
- simultaneous systems of inequalities

- System of inequalities
- Linear programming
- convex set
- objective function
- constraints
- feasible solution
- optimum solution
- linear programming theorem
- linear programming procedure
- superfluous constraint

## 16.5 Essential Ideas

This section is an extension of both systems and graphing linear inequalities.

A linear expression in two variables

*c*_{1}*x + c*_{2}*y*

defined over a convex set *S* whose sides are line segments takes on its maximum value at a corner point of *S* and its minimum value at a corner point of *S*. If *S* is unbounded, there may or may not bean optimum value, but if there is, then it must occur at a corner point.

*Procedure for solving a linear programming problem*:

To solve a linear programming problem, use the following procedure.

**Step 1:** Find the objective function (the quantity to be maximized or minimized).

**Step 2:** Graph the constraints defined by a system of linear inequalities; this graph is called the set *S*.

**Step 3:** Find the corners of *S*; for each corner, this may require the solution of a system of two equations with two unknowns.

**Step 4:** Find the value of the objective function for the coordinates of each corner point.

**The largest value is the maximum; the smallest value is the minimum.**