How to find the optimal value of $z$?

Question

Consider the linear programming Problem : Maximize $ z=5x +7y$ such that

$x-y \le 1$

$2x+y \ge 2$

$x+ 2y \le 4$

$x \ge 0,$$ y \ge 0$

what is the optimal value of $z$ ?

My attempt : From $x-y \le 1$ and $2x+y \ge 2$ we have $x=0,y=-1$

From $x-y \le 1$ and $x+ 2y \le 4$ we have $x=1, y=0$

From $2x+y \ge 2$ and $x+ 2y \le 4$, we have $x=0, y=2$

Now im confused that what i have to do and im not able to proceed further

Answer 1

You don't mention anything about $x$ and $y$ being integers, so you can't assume much about what their specific values are from inequalities. I assume they can be real numbers. If so, then your first line's attempt of

My attempt : From $x-y \le 1$ and $2x+y \ge 2$ we have $x=0,y=-1$

as well as the next $2$ lines, aren't necessarily true. Also, note having $y = -1$ doesn't satisfy that $y \ge 0$.

Instead, consider the $2$ conditions of

$$x-y \le 1 \tag{1}\label{eq1A}$$

$$x+ 2y \le 4 \tag{2}\label{eq2A}$$

Note \eqref{eq1A} plus $4$ times \eqref{eq2A} gives

$$z = 5x + 7y \le 17 \tag{3}\label{eq3A}$$

Thus, the largest potential maximum value is $17$. To confirm this is the actual maximum, you just need to find one set of values of $x$ and $y$ which satisfy \eqref{eq3A} and all of the other conditions. You can confirm that $x = 2$ and $y = 1$ work, so integral values do suffice in this case. Thus, the maximum value for $z = 5x + 7y$ is $17$.

Answer 2

Since there are only two variables and three constraints, we can solve this LP by enumerating the basic feasible solutions and evaluating the objective function at each of them. Add slack and surplus variables to make the constraints of equality form: \begin{align} x-y + s_1 &= 1\\ 2x+y - s_2 &= 2\\ x+2y + s_3&=4\\ s_1,s_2,s_3&\geqslant 0. \end{align} Because there are three constraints, a BFS consists of three basic variables. With a total of five variables, this gives $\binom 53 = 10$ candidates.

• $B = (x,y,s_1) \implies (x,y,s_1) = (0,2,3)$ which is feasible, and has objective value $14$.

• $B = (x,y,s_2) \implies (x,y,s_2) = (2,1,3)$ which is feasible, and has objective value $17$.

• $B = (x,y,s_3) \implies (x,y,s_3) = (1,0,3)$ which is feasible, and has objective value $5$
• $B = (y,s_1,s_2) \implies (y,s_1,s_2) = (2,-1,0)$ which is infeasible.
• $B = (y,s_1,s_3) \implies (y,s_1,s_2) = (2,-1,0)$ which is infeasible.
• $B = (y,s_2,s_3) \implies (y,s_2,s_3) = (1,-1,2)$ which is infeasible.
• $B = (x,s_1,s_2) \implies (x,s_1,s_2) = (4,-3,6)$ which is infeasible.
• $B = (x,s_1,s_3) \implies (x,s_1,s_3) = (1,0,3)$ which is feasible, and has objective value $5$.
• $B = (x,s_2,s_3) \implies (x,s_2,s_3) = (1,0,3)$ which is feasible, and has objective value $5$.
• $B = (s_1,s_2,s_3) \implies (s_1,s_2,s_3) = (1,-2,4)$ which is infeasible.

We conclude that the LP has optimal solution $(x,y)=(2,1)$ with objective value $17$.