Lecture Note Linear Programming (LP)
Graph the feasibility region for the following system of inequalities
32 xy
xy 6
− ≤
+ ≥
Corner Point
A corner point of a particular feasibility region R is a point in R where two of
the boudary lines of R intersect.
Example 6
Graph the feasibility region for the following system of inequalities:
25
30
4
xy
xy
x
− ≥
+ >
<
Answer: the corner points (1, 3−−)(4 , 3) (4 , 1 2)
Example 7
Graph the feasibility region and find the corner points for the following system of
inequalities:
10 12 1, 920
5 3 780
,0
HL
HL
HL
+ ≤
+≤
≥
Answer: the corner points (156, 0) (120, 60) (0,160)( )0, 0
2 Geometric Linear Programming
In general, a linear program in two variables x and y consists of a linear function
f =+ax bycalled the objective function that is to be optimized (maximized or
minimized) subject to a system of linear constraint inequalities. The variables x and y
are called decision variables, and the solution set of the system of inequality
constraints is called the feasibility region.
The Corner Point Theorem
If a linear program has an optimal solution (maximum or minimum), it must
occur at a corner point of the feasibility region.
Geometric Method for Solving a Linear Program with Two Decision
Variables
- Graph the feasiblity region R and find the coordinates of all corner points
of R. - Make a table evaluating the objective function F at each corner point.
- If R can be contained in a circle it is bounded. In this case, the largest
(smallest) value of F on R is its largest (smallest) value at a corner point. - If R cannot be contained in a circle, it is unbounded, and an optimum
soluion may not exist. However, if it does, it must occur at a corner point.
Example 1
From the example 1 in section 1, how many bags of each grade should be made up
from available supplies to generate the largest possible profit?
Solution
To maximize