Applied Mathematics for Business and Economics

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

1. Graph the feasiblity region R and find the coordinates of all corner points
   of R.


2. Make a table evaluating the objective function F at each corner point.


3. 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.


4. 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