15.053 Lecture Notes - Lecture 2: Linear Programming, Maxima And Minima, Alsn
Document Summary
Lecture 2: geometry and visualizations of linear programs. Recall that a single linear inequality determines a unique half-plane. A constraint is called redundant if the constrain does not decrease the size of the feasible region. The feasible region illustrates a bounded feasible region. The geometrical method for maximizing 3x + 5y. Find the maximum p such that there is a feasible solution to 3x + 5y = p. The optimal solution occurs at an extreme point often called a corner point. A feasible point is called an extreme point if it is not the midpoint of two other feasible points. In two-variable linear programs, an extreme point will be at the intersection of two binding constraints. Theorem: for a bounded linear program, there is always an optimum solution that occurs at an extreme point. This is true, but there may be other optimal solutions as well.
