Linear Programming: Geometric Approach

MAT 119 FALL 2001

MAT 119

FINITE MATHEMATICS

NOTES

PART 1 – LINEAR ALGEBRA

CHAPTER 3

LINEAR PROGRAMMING: GEOMETRIC APPROACH

3.1 Linear 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.2 A 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.3 Applications

Maximizing profit

Financial planning

Land reclamation

Pollution control model

5

DOUGLAS A. WILLIAMS, ARIZONA STATE UNIVERSITY, DEPARTMENT OF MATHEMATICS