I’m guessing that if you are reading this book (either you picked it up or have been assigned it) that you have a fair bit of mathematical background. That being said, I’m guessing that you are quite familiar with lines—you may even be embarrassed if you are seen reading a section on lines. However, review is nearly always good and seeing the context of old material in a new way expands your thinking. In short, it will be worth your while to read through this chapter.
When most mathematics students are asked about lines, the response is \(y=mx+b\text{,}\) the slope-intercept form of the line. This is often presented in a Precalculus class in which linear functions fall from this naturally. However, not all lines can be written in this form. The exception is vertical lines, like \(x=1\text{.}\)
This form is quite nice in that if \(a\) is zero, then the line is horizontal, if \(b\) is zero, then the line is vertical and if both are non-zero then the line is oblique with \(x\)-intercept of \(c/a\text{,}\)\(y\)-intercept of \(c/b\) and slope of \(-a/b\text{.}\) If we take the line in (1.1.1) with \(ab \neq 0\) and divide through by \(c\text{,}\) this can take on the intercept form of the line:
Plot the following lines: \(x=3\text{,}\)\(y= 4\text{,}\)\(2x+ 3y = 24\) and \(-3x+4y = 12\) on the same axes. Note: do this by hand instead of graphing calculator/website/software.
Related to lines is that of linear inequalities. Consider the inequality \(3x+ 4y \leq 12\) and let \(S\) be the set of all points that satisfy the inequality. The line \(3x+4y=12\) cuts the \(xy\)-plane into two regions and in this case, the line is included in the set \(S\text{.}\)
Which side of the line satisfies the inequality? Since every point that is not on the line either satisfies the inequality or not, we can pick any point to determine this. For example in the line \(3x+4y=12\) above, an easy point to pick is \((0,0)\) and since \(3(0)+4(0) \leq 12\) is true, then the side of the line containing the origin is in the set. The following is plot:
The set that satisfies the inequality we have labelled \(F\) and shaded in light gray. When combined with other inequalities, we often call the set a feasible set, hence labelling it as \(F\text{.}\)
As we will see throughout this book, it is common that there are multiple inequalities. For example, let’s add the inequality \(y \geq x+1\) to the inequality above and determine the set of points that satisfy both inequalities. There are two techniques that can be used.
Technique 1: Graph and Choose. First, let’s plot the two lines (ignoring the inequality) \(y=x+1\) and \(3x+4y=12\text{.}\) The first line is in slope-intercept form and the second was plotted above. A plot with both graphs is
The 2 lines split the plane into four regions and only one of these satisfies both inequalities. If we pick four points (one for each region), we can determine the feasible set. The following table does this formally.
This technique will work however, as the number of lines increases it become increasingly difficult to plot and determine all of th inequalities. The next technique is often more desirable.
Technique #2: Cross Out Regions Instead, we start with one line and then cross out the region not in the feasible set. Each subsequent inequality, we repeat. After all inequalities are examined, the region (if one exists) that is not crossed out is the feasible set. Performing this technique with the same pair of equalities, we’ll start with the inequality \(3x+4y \leq 12\text{.}\) We’ve already seen this and will cross out the region in the northeast part.
Now we will add the second inequality, \(y \geq x+1\text{.}\) Graph the line and then cross out the region that does not satisfy the inequality. Note that this is the southeast side of the line.
Figure1.1.8.A graph of the lines \(3x+4y=12\) and \(y=x+1\) with the corresponding inequalities crossed out. The feasible set is labelled \(\boldsymbol{F}\)
From Figure 1.1.8, the region not crossed out is the feasible set and is the same that was found with Technique #1 as shown in Figure 1.1.5. Although either technique will result in the correct answer, this one is generally faster to perform with a large number of inequalities.
In this case, we’ll graph and cross out the false side of each line. The first two lines are the coordinate axes. The 3rd and 4th lines can be written in intercept form as
Figure1.1.10.The feasible set of the given inequalities. The side of the line not in the feasible set is crossed out and the remaining region is the feasible set and labelled \(\boldsymbol{F}.\)
Note: as we will see throughout this book, it is common that we have a nonnegative constraint, like \(x \geq 0\) and \(y \geq 0\text{.}\) With only two variables, this means outside the first quadrant is crossed out.
Subsection1.1.3Bounded and Unbounded Feasible Sets
Another feature of feasible sets is that of being bounded. For feasible sets in the plane, a feasible set that is a polygon (interior as well as its boundary), is bounded. For example, in Section 2.3, we will see the feasible set \(F\) be set defined by
Figure1.1.11.A graph of the feasible set of the above problem. For each inequality, the side of the line not in the feasible set is crossed out. The set of points left is the feasible set for the inequalities and labelled \(\boldsymbol{F}\text{.}\)
The feasible set is the interior of the polygon together with its boundary and appears to be bounded. In contrast, the feasible set in Checkpoint 1.1.9 is not a polygon and the feasible set extends without bound. The definition below is more general for a feasible set in any dimension.
A feasible set, \(F\) in \(\mathbb{R}^n\) is bounded, if there exists a ball centered at the origin, \(B\) such that \(F \subset B\text{.}\) If no ball exists, the set \(F\) is unbounded.
The feasible set in Figure 1.1.11 is bounded because the ball with radius 8 would encompass the feasible set. The feasible set in Checkpoint 1.1.9 has no ball that encompasses it, so is unbounded.
A linear equation in three variables is a plane. For example the equation \(x+2y-3z = 12\) describes points in \(\mathbb{R}^3\text{,}\) the set of all three-dimensional space. Like a line in \(\mathbb{R}^2\text{,}\) it extends indefinitely and is flat. The following shows a plot of the plane \(2x+3y + 4z = 24\text{.}\)
Figure1.1.14.A plot of the plane \(2x+3y + 4z = 24\) in \(\mathbb{R}^3\text{.}\) If reading on the web, this figure is interactive and the orientation can be changed.
We will encounter inequalities involving three variables. As seen in two dimensions, the feasible set will be the set of all points satisfying all of inequalities. It is difficult to graph this, but one can imagine that in three dimensions, the same ideas hold as those above. For example, one can cross out the side of the plane that is not in the feasible set and then the region in \(\mathbb{R}^3\) is the region not crossed out.
Figure1.1.15.A plot of a feasible set of in \(\mathbb{R}^3\text{.}\) If this is being viewed in a web browser, the graph should be interactive in that it can be rotated.
Linear equations with more than 3 variables are often called hyperplanes. Although impossible to graph, these work the same ways as lines and planes in that the cut the Euclidean space in half.
As we will see later, a convex feasible set is key to the simplex method working. What does convex mean? We will explore this and show that a feasible set constructed of linear inequalities is always convex.
A set \(S\) in \(\mathbb{R}^n\) is convex if for any two points \(\boldsymbol{x}\) and \(\boldsymbol{y}\) in \(S\) that all points in the line segment connecting \(\boldsymbol{x}\) and \(\boldsymbol{y}\) is in \(S\)
In two dimensions, a convex set is a set in \(\mathbb{R}^2\) such that its boundary is convex in the standard sense. Sets like the interior of circles, rectangles and the “inside” of parabolas are examples. To get a sense of this, the sets consisting of the interior of the following objects are convex:
Although example line segments are shown drawn within the figures in Figure 1.1.18, recall that in order to be convex, all line segments need to be within the set, not just an example line segment.
Some examples of sets that are not convex are shown in Figure 1.1.19. A line is shown in blue with point endpoints that are in the set, but the are parts of the line that are not in the set. Recall that a set that is not convex just needs a single line segment with endpoints in the set and some part of the line segment passes outside the set.
\begin{align*}
a (x_1 (1-t) + x_2 t) + b(y_1 (1-t) + y_2 t) \amp = (a x_1 + b y_1) (1-t) + (a x_2 + b y_2) t\\
\amp \leq (1-t) c + t c \\
\amp = c-tc+ct = c
\end{align*}
And since the both points \((x_1,y_1)\) and \((x_2, y_2)\) are in \(S\text{,}\) then \(a (x_1 (1-t) + x_2 t) + b(y_1 (1-t) + y_2 t) \leq c\text{,}\) the line segment is in \(S\text{,}\) therefore the set is convex.
