Linear Inequalities in Two Variables and Systems of Inequalities
Math Models ] Up ] Bibliography ] Examples ] Notes on Linear Progarmming ] [ Linear Inequalities in Two Variables and Systems of Inequalities ] Homework 4 ] Problems ]


Graphing Linear Inequalities in Two Variables

A linear inequality in the two variables x and y looks like 

ax + by < c ax + by < c ax + by > c ax + by > c

where a, b, and c are constants. 

A solution to an inequality is any pair of numbers x and y that satisfy the inequality.

The rules for finding the solution set of a linear inequality are much the same as those for finding the solution to a linear equation. 

  1. Add or subtract the same expression to both sides. 
  2. Multiply or divide both sides by the same nonzero quantity; if that quantity is negative, then the inequality must be reversed. 

Example 1 Determine the solution set of 5x + 2y < 17. 

One solution to this is x = 2 and y = 3, because 5(2) + 2(3) = 16, which is indeed less than or equal to 17. 

A pair of numbers that does not form a solution is x = 3 and y = 2, because 5(3) + 2(2) = 19, which is not less than or equal to 17. The pair x = 2 and y = 3 isn't the only solution; as a matter of fact, there are infinitely many solutions. 

Since we can't write down all possible solutions to a linear inequality, a good way to describe the set of solutions to any linear inequality is by a graph. If the pair of numbers x and y is a solution, then think of this pair as a point in the plane, so the set of all solutions can be thought of as a region in the xy-plane. 

To illustrate how to determine this region; first, we solve the inequality for y in terms of x

5x + 2y  <  17 
 2y  <  ~5x+ 17
y  <  -(5/2) x + 17/2

Next, graph the line y = -(5/2) x + 17/2.

The set of points (x,y) that lie on this line is the set of all (x,y) such that y is exactly equal to -(5/2) x + 17/2. 

These points make up part of the set of solutions to the inequality, but not all. We see that y can also be less than -(5/2) x + 17/2, so all points below the line would also be solutions. The shaded region in Figure 1 shows the solution set. 


Figure 1

 

Example 2. Graph the solution set for the inequality 3x - 8y > 12. 

Solve for y: 

-8y  >  -3x + 12 
y  <  (3/8) x - 3/2

Do you notice that the inequality is reversed? That's because we divided by a negative number, any time you multiply or divide an inequality by a negative number, you must reverse the inequality

Next, graph the line

Points on this line are part of the solution set; the other part consists of all points below the line, shown if Figure 2.


Figure 2

 

Example 3. Graph the solution set for the inequality - 1Ox - 2y > 7.


Figure 3

 Solving for y gives 

-2y  >  10x + 7 
y  <  -5 x - 7/2  (Remember the minus?)

This example is a little different because there's no equals sign in the inequality. But you still graph the line 7 = -5x  -7/2, except draw it as a dashed lire

This indicates that the line itself is not part of the solution set. The actual solution set consists of all points below the dashed line. This is because y must be strictly less than -5x -  7/2.

 

Systems of Linear Inequalities in Two Variables

A system of linear inequalities is a set of one or more linear inequalities; a solution is a pair of numbers (x, y) that satisfies all of the inequalities. 

Example 4. Determine the solution set to the system of linear inequalities 

x + 5y  <  20 
3x +2y  <  21

The pair of numbers x = 1, y = 2 is one solution because 1 + 5(2) = 11 <  20 and  3(1)+2(2) = 7 < 21.

The pair x = 0, y = 5 is not a solution because it doesn't even satisfy the first inequality 0 + 5(5) = 25, which is not less than or equal to 20. Notice that it does satisfy the second inequality, but in order to be a solution, it must satisfy both

As before, a system can have an infinite number of solutions, so we present its solution set by a region in the plane. Solve each inequality for y: 

y  <  -(1/5)x + 4 
y  <  -(3/2)x + 21/2

Graph each of the lines on the same coordinate system. The solution set for the first inequality lies in the region below and on the line y = -(1/5)x + 4  and the solution set for the second inequality lies in the region on and below the line y = -(3/2)x + 21/2. 

The solution set for the system lies in the region common to both, and is the darker region shown in Figure 4.


Figure 4

The corner of this region is the intersection of the two lines, and corners will be very important in the next chapter. In order to find this point, return to the original system of inequalities and replace the inequality symbols with equal signs.  The resulting two equations are the equations of the two lines:

x + 5 y  = 20
3x + 2y 21

This is a system of two linear equations in two unknowns, and its solution is precisely the point of intersection of the two lines. You know how to solve this system by hand or using your calculator. 

The solution matrix is x = 5 and y = 3. The point of intersection, or corner of the region, is (5,3).

Example 5. Graph the solution set to the system 

7x - 5y  <  12 
2x + 3y  <  18
x > 0
y > 0

and find all corners. 

The last two inequalities in this system simply restrict the solution set to points in the first quadrant (that's the quadrant in which both coordinates are nonnegative). 

Solve the first two inequalities for y to get 

y  >  (7/5)x -12/5 
y  <  -(2/3)x + 6

The solution set to the first inequality lies in the region on and above the graph of the line y = (7/5)x -12/5, and the solution set to the second lies on and below the line y = -(2/3)x + 6. 

The common region which is in the first quadrant is the solution set to the original four inequalities.


Figure 5a


Figure 5b

Next we find corners of this region. There are four of them. One of them is really easy; that's the origin: x = 0 and y = 0. Two others are also easy; these are the ones on the axes. The one on the x-axis is the x-intercept of the line 7x - 5y = 12. To find this, take y = 0, and solve for x, x = 12/7  (= 1.71), so this corner is (12/7,0). 

On the y-axis, the corner is the y-intercept of the line 2x + 3y = 18; take x = 0 to get y = 6, so the corner is (0,6). 

The last point requires some work, but not much. You must find the intersection of the lines 7x - 5y = 12 and 2x + 3y = 18, which is the solution to the linear system 

7x - 5 y  = 12
2x + 3y 18

The solution is  x = 4.06 and y = 3.29, and the corner is (4.06, 3.29).

 

Example 6. Graph the solution set to the system

x + 4y  <  20 
3x + 4y  >  28
x - y  < 7

and find all corners. 

As before, graph each line and shade the appropriate region; the solution set to the entire system is the region common to all three, and is shown in the figure on the right, complete with corners. 


Figure 6

 

Linear Programming

The primary reason for studying systems of linear inequalities at this point is to determine solutions to mathematical problems that can be solved using linear programming methods. Specifically, one has a function that is to be maximized or minimized, but the solution is subject to certain restrictions. The function itself is called the objective function, and the restrictions are called constraints and usually appear in a system of inequalities. 

In order to solve a linear programming problem follow the steps below. 

  • Step 1. Graph the inequalities that express the constraints and determine the solutions set as a region in the plane; this region is called the feasible region. We will consider only bounded regions, which insures the existence of maximum and minimum values for the objective function. 
  • Step 2. Determine the corners of the feasible region. 
  • Step 3. The maximum or minimum of the objective function will occur at one of these corners. In order to find which one, evaluate the objective function at each corner; the maximum is the largest value and the minimum is the smallest. 

 

Example 7. Maximize the objective function A = 3x + 5y subject to the constraints 

2x +   <  16 
16 x + 3y  <  18
> 0
y > 0

First, graph each line and shade the appropriate region; then find the corners. 

Now evaluate the objective function at each corner.

Corner   

Functional Value 

(0, 0)   

 A = 3 (0) + 5 (0) = 0 

(0, 6)   

 A = 3(0) + 5(6) = 30 

(6, 4)   

 A = 3(6) + 5(4) = 38 

(8, 0)   

 A = 3(8) + 5(0) = 24 

Thus, the maximum is 38 and occurs at corner (6,4). 


Figure 7a

Here is a note on why you only need to look at the corners when you are finding the maximum or minimum value of the objective function. Of course, 3x + 5y can be as large as you want, but the problem is to stay inside the feasible region.

Figure 7b shows 3x + 5y = 50, 3x + 5y = 40, and the one that passes through the corner at which the solution occurs. The latter line is 3x + 5y = 38. None of the points on the line 3x + 5y = 50 are inside the feasible region, so none of these points are valid solutions. 

Notice that the line 3x + 5y = 40 is closer, and all the lines 3x + 5y = any number are parallel. Slide the highest line down staying parallel until you first hit a point in the feasible region. What point did you hit? A corner! So where is the maximum? At a corner!


Figure 7b

Example 8.  Maximize the objective function B = 8x + y subject to 

2x +   <  16 
16 x + 3y  <  18
> 0
y > 0

The feasible region with corners is shown in Figure 7b. Evaluate this objective function at the corners. 

Corner   

Functional Value

(0, 0)   

 B = 8(0) + 0 = 0 

(0, 6)   

 B = 8(0) + 6 = 6 

(6,4)   

 B=8(6) + 4=52 

(8,0)   

 B=8(8) + 0=64 

The maximum for the objective function B is 64, and occurs at corner (8, 0).

Example 9.  Minimize the objective function C = 11x +  10y subject to the constraints 

x +   >  15 
6x + 5y  >  80
4x + 3y < 60
> 0
y > 0

The graph of the feasible region with its corners is shown in Figure 9

Evaluate the objective function at the corners. 

Corner   

Functional Value

(5, 10)   

 C = 11(5) + 10(10) = 155

(0, 16)   

 C = 11(0) + 10(16) = 160 

(0, 20)   

 C = 11(0) + 10(20) = 200 

(15, 0)   

 C = 11(15) + 10(0) = 165 

The minimum value of the objective function is 155, which occurs at (5, 10).


Figure 9
 

The main deficiency of the graphical method is that it is limited to solving LP problems with 1 or 2 decision variables only. However, the main and useful conclusion we easily observe from the graphical methods, is as follow:

If a linear program has a non-empty, bounded feasible region, then the optimal solution is always one of the corner points.

The proof of this claim, follows from the results of the the following two facts:

Fact 1: The feasible region of any linear program is always a convex set.

Since all of the constraints are linear, the feasible region (F.R.) is a polygon. Moreover, this polygon is a convex set. In any higher than two-dimensional LP problem, the boundaries of F.R. are parts of the hyper-planes, and the F.R. in this case is called polyhedra that is also convex. A convex set is the one that if you choose two feasible points from it, then all the points on the straight line segment joining these two points are also feasible. The proof that the F.R. of linear programs are always convex sets follows by contradiction. The following figures depict examples for the two types of sets: A non-convex and a convex set.

The set of feasible region in any linear program is called a polyhedron, it is called a polytope if it is bounded.

Fact 2: The Iso-value of a linear program objective function is always a linear function.

This fact follows from the nature of the objective function in any LP problem. The following figures depict the two typical kinds of iso-valued objective functions.

Combining the above two facts, it follows that, if a linear program has a non-empty, bounded feasible region, then the optimal solution is always one of the corner points.

To overcome the deficiency of the graphical method, we will utilize this useful and practical conclusion in developing an algebraic method that is applicable to multi-dimensional LP problems.

The convexity of the feasible region for linear programs makes the LP problems easy to solve. Because of this property and linearity of the objective function, the solution is always one of the vertices. Moreover, since number of vertices are limited, one has to find all feasible vertices, and then evaluate the objective function at these vertices to seek the optimal point.

For nonlinear programs, the problem is much harder to solve, because the solution could be anywhere inside the feasible region on the boundary of the feasible region, or at a vertex.

Fortunately, most of the Business optimization problems are linear, which is why LP is so popular. There are well over 400 computer packages in the market today solving LP problems. Most of them are based on vertex searching, that is, jumping from one vertex to the neighboring one in search of an optimal point.

You have already noticed that, a graph of a system of inequalities and/or equalities is called the feasible region. These two representations, graphical, and algebraic are equivalent to each other, which means the coordinate of any point satisfying the constraints is located in the feasible region, and the coordinate of any point in the feasible region satisfies all the constraints.

A numerical Example: Find the system of constraints representing the following feasible region.

In the above Figure, the system of coordinate is shown in gray color at the background. By constructing the equations of the boundary lines of the feasible region, we can verify that the following system of inequalities indeed represents the above feasible region:

x1 -1
x2 1
x1 - x2 1


AnnouncementsAssignments | Bibliography | Grades | RequirementsResources | Home  
  Fall 2004 Marcelo Llarull | Department of Mathematics | William Paterson University