Maximize $Z=-x+2y$ given $x\geq 3,\ x+y\geq 5,\ x+2y\geq 6,\ y\geq 0$

Question

I am a highschool senior that's new to this topic. So, apologies for my lack of knowledge and misconceptions. The proof of the theory of this chapter is beyond the scope of my textbook, so that may be reason why I feel it difficult to do the following question.

Q) Maximize the function $Z=-x+2y$ which is subject to the following constraints:

$$ \begin{align} x\geq 3\\ x+y\geq 5\\ x+2y\geq 6\\ y\geq 0 \end{align} $$

My attempt::
>> Plotting the corresponding lines I get:

>> The intersection of the areas bounded by the inequalities is as shown below.
It can be seen that the feasible region is unbounded:

The corner points that I've found and their corresponding $Z$ values are: $$\begin{array}{|c|c|} \hline \text{Corner Points} & Z=-x+2y\\ \hline A\Big(6,0\Big) & -6 + 0 = -6 \\ \hline B\Big(4,1\Big) & -4 + 2 = -2 \\ \hline C\Big(3,2\Big) & -3 + 4 = 1 \\ \hline D\Big(\infty, \infty\Big) & \text{undefined}\\ \hline \end{array}$$

Obviously, the minimum $Z=-6$ is at $A(6,0)$ but I'm not sure about the maximum. My gut tells me it's $Z=1$ at $C(3,2)$ but I don't know how to prove it to myself. Am I right?

Please guide me in the right direction. How do I answer questions of this nature?

Answer 1

You need to consider "points at infinity": or more rigorously, points on the boundary as they approach an infinite distance from the origin.

Your graph shows that the point $(x,0)$ is in the feasible region if $x\ge 6$. As $x$ approaches $+\infty$ your function $-x+2y$ approaches $-\infty$. Therefore, there is no minimum.

Your graph also shows that the point $(3,y)$ is in the feasible region if $y\ge 2$. As $y$ approaches $+\infty$ your function $-x+2y$ approaches $\infty$. Therefore, there is no maximum.

---

Here is a graphical way to see the same thing.

I have added three lines $Z_A$, $Z_B$, and $Z_C$ to the graph. They take your function $Z=-x+2y$ and set that equal to the value of $Z$ at each boundary vertex. I.e. $Z_A$ is the line $-x+2y=-6$ since the value of $Z$ at the point $A$ is $-6$.

You see that the lines are parallel, since they have the same slope. For any of those lines, a point above the line has a larger value of $Z$ and any point below the line has a smaller value of $Z$. Of the vertices, $A$ has the lowest line so it has the smallest value of $Z$. That's why you thought the minimum of $Z$ is at point $A$ and likewise that the maximum is at point $C$.

However, you see that each of those lines cuts into the feasible region. In fact, any point on the boundary ray $x=3,\ y\ge 2$ also cuts into the region. For any point on the boundary, there is another boundary point above the line, so there is no maximum for $Z$. The ray $y=0,\ x\ge 6$ similarly shows that there is no minimum.

---

Is it all clear now?