Systems of linear inequalities

Many modern applications in optimization or economics or operations research lead to systems of several simultaneous inequalities, a topic that we examine now. We’re going to begin by defining the concept of half-space. Let me recall, once again, that a function is called affine if its defining formula is of the form mx plus b. I now ask the following question– which are the points (x, y) in the coordinate plane that satisfy the linear inequality y less than or equal mx plus b? The key to answering this question is to remember that the graph of an affine function is a line, a non-vertical line. Let’s call it capital L.

So here’s the Cartesian plane, and here’s the line L, the graph of the function y equals mx plus b. I give myself a point on the line. There it is. By definition of graph, the coordinates of this point are x, and then mx plus b. You’ll notice that this pair satisfies the linear inequality that we’re studying. In fact, equality holds at this pair. But we’re also interested in the points (x, y) for which the inequality holds. This means that y could be less than mx plus b. Geometrically this means that the point (x, y) would be lower down from the point we’re looking at.

In other words, it could be any point on the ray that starts at the point we’re looking at and goes vertically down from that point. It couldn’t be higher than our given point, though. But it could be any point that is lower. Similarly, if we take any other point on the line L, all the points below such a point will lie in the set satisfying our inequality. And when you fill up the set of all possible rays that you get this way, you get the solution set of our inequality– the set of points (x, y) for which y is less than or equal mx plus b. Now, that has a name. It’s called a half-space, this kind of set.

And it answers our question. The points we’re looking for are those in a certain half-space. What is a half-space? It’s the set of all points on a line or to one side of it. In this case, it’s the set of points that are below the line L, or on the line itself. And it’s called a lower half-space for that reason. Of course, given the line L in the plane, we could also just as well consider the set of points that are on the line or above the line. That is called an upper half-space. Now, we’ve seen all the possible half-spaces with the exception of those that correspond to a vertical line. Let’s examine that situation.

We give ourselves a value c on the real line, on the x-axis, and we consider the vertical line going through c. That means we’re looking at all the points (x, y) whose x-coordinate is c and whose y-coordinate is anything at all. If you look at all points to the left of this vertical line, then you get something called a left half-space. And similarly, if you looked at the points to the right of the line it would, of course, be a right half-space. Now that we understand half-spaces, let’s look at the following question. Suppose I have a system of two linear inequalities– ax plus by less than or equal p, that’s the first.

cx plus dy less than or equal q, that’s the second. Now, we’re going to assume that a and b are not both 0, so that the inequality 1 is really there, and similarly for c and d. What are the points in the plane that satisfy simultaneously these two linear inequalities? Well, now we know the answer to that question, to some extent. It will be an intersection of two half-spaces. Why? Because each of the inequalities 1 and 2 describes a half-space. It can be a lower half-space, an upper one. It can be a left or right. It depends on the specific coefficients a, b, c, and d. Now, here’s an important remark.

In the case of systems of equalities, it is not really of interest to consider a system of three or more equations in two variables. Why? Well, because, as we saw, when you have a system of two equations, then if it’s an interesting system, the two lines that lie behind the system will intersect at a unique point, and you have a unique solution. Now, if you add a third equation, well, either the new line will go through that same point and you’ll have the same solution, or it won’t go through that point, in which case you’ll have no solutions. You see, not very interesting.

Whereas in the case of inequalities, you can keep adding inequalities, and in general you will get a non-empty solution set which gets smaller and smaller as you add more inequalities, but which is of interest. Now, this solution set will usually contain an infinite number of points. And for that reason, it is often asked to represent it graphically. And here’s a typical problem of this sort. We want to sketch the solution set of the following system of four inequalities. To try and understand what it’s going to look like, consider each of these inequalities separately for a moment.

The first inequality, we see, will describe a lower half-space, because if you put the 2x over on the other side, it’s the set of points satisfying y less than or equal minus 2x plus 8. A lower half-space. Similarly, the second inequality describes a lower half-space. Now, the third and the fourth conditions are often called positivity constraints. They arise quite often in applications. We require that both x and y be positive. Another way to say that would be that the point (x, y) should lie in the first quadrant of the plane. And as we see, this corresponds to two further half-spaces. x being greater than 0 means you’re in the right half-space, x greater than 0.

And y greater than 0 means you’re in the upper half-space, y greater than 0. So in other words, our four inequalities each correspond to half-spaces, and our solution set will be the intersection of these four half-spaces. Now how do we sketch it? How do we find it? Well, we give ourselves coordinate axes– here they are– and we examine the line that corresponds to the first inequality. That is, I look at 2x plus y equals 8. Now, we want all the points that are on this line, but also the points that are below this line. That will be the lower half-space corresponding to the first inequality.

Similarly, the second inequality gives us another lower half-space, the points on or below the line x plus 2 equals 8. And then, as we’ve pointed out, we also want to restrict x and y to lie in the first quadrant. So the question now is, what are the points that are below both of those lines and which lie in the first quadrant? We find them. And there’s our solution set. In closing, I would like to wish you every success in finding your solution sets in future, both in mathematics and in your other endeavours.