16.5 Outline

A.  Introduction
     1. linear programming
     2. simultaneous systems of inequalities
B. System of inequalities
C. Linear programming
     1. convex set
     2. objective function
     3. constraints
     4. feasible solution
     5. optimum solution
     6. linear programming theorem
     7. linear programming procedure
     8. 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₁x + c₂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.