Objectives
-
The definition of a feasible set.
-
How to graph a feasible set in the \(xy\)-plane.
-
The structure of a feasible set and how it helps solve LOPs
-
The convexity of feasible sets.
Section 2.3 Geometry of Feasible Sets
In the Section 2.1, we saw many different type of problems that fall into linear optimization. Many of these problems had a lot of variables and as we will see in this course is it easy to get tens or hundreds of variables.
Definition 2.3.1.
Consider a set of linear inequalities that arise from an Linear Optimization Problem in standard form:
\begin{align*}
a_{11} x_1 + a_{12} x_2 + \cdots a_{1n} x_n \amp \leq b_1 \\
a_{21} x_1 + a_{22} x_2 + \cdots a_{2n} x_n \amp \leq b_n \\
\vdots \; \amp \;\;\; \vdots\\
a_{m1} x_1 + a_{m2} x_2 + \cdots a_{mn} x_n \amp \leq b_m \\
x_1, x_2, \ldots, x_n \amp \geq 0.
\end{align*}
The feasible set for the set of inequalities is the set of all points \((x_1, x_2, \ldots, x_n)\) that satisfy all of the inequalities.
Note 2.3.2.
If there are no points in the feasible set, then the feasible set is empty.
Problem 2.3.3. Maximum Problem in \(\mathbb{R}^2\).
\begin{equation*}
\begin{aligned} \text{Maximize}\amp\amp \qquad z = 3x_1 + 2x_2, \amp \\ \text{subject to} \amp \amp x_1 + x_2 \amp \leq 7, \\ \amp \amp 2x_1+ 3x_2 \amp \leq 18, \\ \text{and} \amp \amp x_1, x_2 \amp \geq 0.
\end{aligned}
\end{equation*}
Example 2.3.4.
Graph the feasible set given by the inequalities in Problem 2.3.3.
Solution.
In this case, we use the techniques from Subsection 1.1.2 to graph each of the following inequalities. If we write the equation \(x_1 + x_2 = 7\) in intercept form as
\begin{equation*}
\frac{x_1}{7} + \frac{x_2}{7} = 1,
\end{equation*}
then the intercepts of these are \((7,0)\) and \((0,7)\text{.}\) The linear equation \(2x_1 + 3x_2 = 18\) can be written in intercept form as
\begin{equation*}
\frac{x_1}{6} + \frac{x_2}{9} = 1,
\end{equation*}
which has the intercepts \((6,0)\) and \((0,9)\text{.}\) Returning to the inequalities, the origin is within the feasible side of these lines so we cross out the other (northeast) side.
Additionally, the nonnegative inequalities have us cross out the region outside the first quadrant. The result of this is
The feasible set is the quadrilateral that is not shaded and labelled \(F\text{.}\)
Subsection 2.3.1 Geometry of 2D Feasible Sets
Examining the feasible set in Figure 2.3.5, notice that it is a polygon. The possible solutions to the problem is this set of points. So if we’re trying to find a solution, we limit the possible points to those in the feasible set. But that’s still a lot!!
One way to try to determine a solution, recall that we are trying to maximize the function \(z = 4x_1 + 5x_2\text{.}\) If we take any point in the feasible set, then increasing in the direction \(\langle 4, 5 \rangle\) will increase the most of any direction. A plot of the feasible set with the randomly selected point \((2,1)\) and a line going in the direction \(\langle 4, 5 \rangle\) can be seen in the following plot:
1
Recall that if there is a function \(f(x,y)\text{,}\) then the direction of increase in the most is \(\langle \partial f/\partial x, \partial f/\partial y \rangle\) and in the case of a linear function, this is the coefficients of the function.
The maximum that the function \(z=4x_1+5x_2\) within the feasible set reaches on this line would be where the line crosses the boundary (on the open circle). In the example above, repeating this argument, any random point selected, the line segment will be parallel to the one above and the maximum value will be on the north-east boundary of the feasible set.
A similar argument can be made with any point in \(F\text{.}\) If a line segment in the direction \(\langle 4, 5 \rangle\text{,}\) then it can be maximized along the upper right boundary of \(F\text{.}\)
Notice that in this case, since the coefficients of the variables in the objective function are both positive, the optimal function would be along the upper right side of the feasible set. Objective functions with other signs may result in the optimal point along other edges.
Note 2.3.7.
From a geometric argument, the optimal value of the objective function should be along the boundary of the feasible set.
Continuing along this rationale, let’s pick a point along the boundary of the feasible set. For example, \((6,1)\text{.}\) This boundary is the line \(x_1+x_2=7\) or if we solve for \(x_2\text{,}\) \(x_2 = 7 - x_1\text{.}\) The objective function along this line is \(z=4x_1 + 5x_2 = 4x_1 + 5(7-x_1) = 35-x_1\text{.}\) The objective function increases as \(x_1\) decreases. This is true up to the point on the boundary a the corner \((3,4)\text{.}\)
If we look at the other boundary side of the feasible set, the function is \(2x_1+3x_2=18\) or solving for \(x_2\text{,}\) \(x_2 = 6-2x_1/3\text{.}\) Substituting this into the objective:
\begin{equation*}
z = 4x_1+5x_2 = 4x_1 + 5 \left(6-\frac{2}{3} x_1\right) = 30 +\frac{2}{3} x_1
\end{equation*}
And on this side, the objective increases as \(x_1\) increases. This is true again up to the corner at \((3,4)\text{.}\)
Using this argument, it appears that the objective is optimal at corners or vertices of the feasible set.
Notice with this argument, we saw that along the two edges that we checked, the objective either increased or decreased along the edge. It might be the case that the objective is constant along the edge. Thus the two vertices of the side would have the same value of the objective.
Note 2.3.8.
From a further geometric argument, the optimal value of the objective function should be at a vertex of the feasible set.
Checkpoint 2.3.9.
Problem 2.2.4 is a minimum problem.
(a)
Sketch the feasible set for the problem.
Solution.
Using the techniques from Section 1.1, we put each line from the constraint in intercept form and plot the line, crossing out the
false side. The result is the feasible set in Figure 2.3.10.
(b)
Pick a random point in the feasible set and draw a directed line segment in the direction of the minimizing the objective.
Solution.
The direction of minimization is \(\langle 4, 3 \rangle \text{.}\) The point \((30,40)\) is shown with a directed line segment on Figure 2.3.10.
(c)
From the feasible set and the directed line segment, which sides of the feasible set does it appear the objective function is minimized?
(d)
Find the relevant vertices of the feasible set.
(e)
Evaluate the objective function at each of the vertices and find the smallest one.
Subsection 2.3.2 Solving LOPs — Possible Algorithm
So it seems that finding the optimal point of a linear optimization problem is straight forward. If we find all of the vertices of a feasible set, and evaluate the objective at these points, then we will find the optimal solution.
This would work, however, finding all of the vertices may be tricky, even if we have objectives and constraints of only two variables. With more variables, it is even more complex and many real-world problems may have hundreds or thousands of variables with hundreds or thousands of constraints. This would results in possibly millions of vertices.
We will see in the next chapter a more reasonable solution. This will start with a vertex (or possible vertex), and move to another vertex that increases (for a maximum problem) the objective and continue until the optimal value is reached.
Subsection 2.3.3 Feasible Sets are Convex
Consider a linear optimization problem with \(z=2x_1+5x_2\) to be maximizes and it has a feasible set with the following shape:
Let’s say that we have an algorithm that walks around vertices. Let’s say that the algorithm is at the point \((7,1)\) and it is noted that the objective at this point is \(z = 2(7) + 5(1) = 19\text{.}\) We also note that if we go the vertex at \((4,4)\text{,}\) then the objective is now \(z = 28\text{,}\) so it has increased. The algorithm now checks if any any adjacent vertices have a larger objective value. At the point \((2,2)\text{,}\) the objective is \(z=14\)therefore you may conclude that the maximum must be 28 at \((4,4)\) because it is larger than at any adjacent vertex.
However, note that at the vertex \((1,8)\text{,}\) the objective is \(z=42\text{,}\) so larger than \(z=14\) and this would in fact be maximum for this problem.
This situation cannot happen because feasible sets from Linear Optimization Problems are convex. As noted in Subsection 1.1.2, a single linear inequality cuts the \(xy\)-plane into two regions in the plane. As noted in Section 2.1, Linear Optimization Problems (LOPs) have a set of linear inequalities which lead to the following. In sort, any LOP has a convex feasible set and as we will see in Chapter 3 how this will be exploited.
