- linear programming
- simultaneous systems of inequalities
- System of inequalities
- Linear programming
- convex set
- objective function
- 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
c1x + c2y
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.