Linear Programming and  Systems of Inequalities
Topic Index | Algebra Index | Regents Exam Prep Center

Linear Programming
Download worksheet for classroom use.

The worksheet contains 5 problems where the inequalities are given and students are asked to find the feasible regions and label the coordinates of the vertices of the polygons representing the feasible regions.  The worksheet is appropriate for use with, or without, the graphing calculator.

Discussion of Linear Programming to precede worksheet:

Linear Programming ("Planning") is an application of mathematics to such fields as business, industry, social science, economics, and engineering.  The process is used to establish feasible regions and locate maximum and minimum values which can take place under certain given conditions.

Linear programming was developed as a discipline in the 1940's by George Dantzig, John von Neumann, and Leonid Kantorovich.

Let's start our investigation into Linear Programming by establishing feasible regions.  These feasible regions are simply the solutions to systems of inequalities, such as those we have been studying.  Feasible regions are all locations that represent "feasible" (viable, possible, correct) solutions to the set of inequalities.

Example 1:

Establish a feasible region for the following set of inequalities:

Determine the coordinates of the vertices of the polygon formed by the feasible region.

 


The feasible region is shaded in yellow.  The coordinates of the polygon are (0,8), (0,1), (7,1).

Once the feasible region has been established, linear programming then examines the function which is to be maximized or minimized within this feasible region.
Let's assume that the function to be examined for Example 1 will be

Each vertex of the polygon is tested in the function.
2(0) + 3(8) = 0 + 24 = 24

2(0) + 3(1) = 0 + 3 = 3

2(7) + 3(1) = 14 + 3 = 17

A maximum value is at (0,8) and a minimum is at (0,1).

 

For our study of Linear Programming, we will be limiting our investigation to the locations of feasible regions and the vertices of the polygons formed.

Example 2:  Find a feasible region to represent this situation.

Student Council is making colored armbands for the football team for an upcoming game.  The school's colors are orange and black.  After meeting with students and teachers, the following conditions were established: 
1.  The Council must make at least one black armband but not more than 4 black armbands since the black armbands might be seen as representing defeat.

2.  The Council must make no more than 8 orange armbands.

3.  Also, the number of black armbands should not exceed the number of orange armbands.

Let x = black armbands
      y = orange armbands

1.  x > 1   and   x < 4
2.  y < 8
3.  x < y
It will be assumed that these numbers are not negative at any time.

 


The feasible region is shaded in yellow.
  The coordinates of the polygon are (1,8), (1,1), (4,4) and (4,8).