MAT 119 FALL 2001
MAT 119
FINITE MATHEMATICS
NOTES
PART 1 – LINEAR ALGEBRA
CHAPTER 3
LINEAR PROGRAMMING: GEOMETRIC APPROACH
3.1Linear Inequalities
Expressions involving the following symbols:<, >, ,
The first two – strict inequality
eg.2x + 3y < 4
3x – 5y > 6
The last two – nonstrict inequality
eg.2x + 3y 4
3x – 5y 6
The graph of an inequality includes all the points (x, y) that satisfy the inequality.
Steps for Graphing a Linear Inequality
1.Graph the corresponding linear equation, a line L. If the inequality is nonstrict, graph L with a solid line; in the inequality is strict, graph L with dotted (dashes) line. This divides the coordinate system into two regions.
2.Select a test point P not on the line L.
3.Substitute the coordinates of the test point P into the inequality.
If the point satisfy the inequality, shade the region that includes the point.
If not, shade the other side.
3.2A Geometric Approach to Linear Programming Problems
A Linear Programming Problem in two variables, x and y, involves maximizing or minimizing an objective function
z = Ax + By
where A and B are real numbers, subject to conditions/constraints expressible as a system of linear inequalities in x and y.
Feasible points – points (x, y) that obey all constraints and are potential solutions.
Solution to a linear programming problem
- feasible point (x, y) along with value of the objective function that either maximizes or minimizes the objective function
Existence of a Solution
Consider a linear programming problem with the set R of feasible points and objective function z = Ax + By.
1.If R is bounded, then z has both a maximum and a minimum value on R.
2.If R is unbounded and A 0, B 0, and the constraints include x 0 and y 0, then z has a minimum value on R but not a maximum value.
3.If R is the empty set, then the linear programming problem has no solution and z has neither a maximum nor a minimum value.
Fundamental Theorem of Linear Programming
If a linear programming problem has a solution, it is located at a corner point of the set of feasible points; if a linear programming problem has multiple solutions, at least one of them is located at a corner point of the set of feasible points. In either case the corresponding value of the objective function is unique.
Steps for solving a Linear Programming Problem
If a linear programming problem has a solution, follow these steps to find it:
1.Write an expression for the quantity that is to be maximized or minimized (objective function).
2.Determine all the constraints and graph the set of feasible points.
3.List the corner points of the set of feasible points.
4.Determine the value of the objective function at each corner point.
5.Select the optimal solution, ie, the maximum or minimum value of the objective function.
3.3Applications
Maximizing profit
Financial planning
Land reclamation
Pollution control model
1
DOUGLAS A. WILLIAMS, ARIZONA STATE UNIVERSITY, DEPARTMENT OF MATHEMATICS