Section 16.5: Modeling with Linear Programming

by

16.5 Outline

  1. Introduction
    1. linear programming
    2. simultaneous systems of inequalities
  2. System of inequalities
  3. 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

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.