I was given the following linear programming problem and have been asked to find all optimal solutions graphically. I am quite new to the subject, so please forgive my naivety.
$$\min\quad z = x - y$$ $$\text{subject to: }\qquad\qquad\qquad\qquad\qquad\qquad$$ $$x + y \le 6$$ $$x - y \ge 0$$ $$y - x \ge 3$$ $$x, y \ge 0$$
I've graphed the constraints as shown below:
To me, it seems like there are no optimal solutions because there is no feasible region (that is, a region where all constraints are satisfied and therefore all three shaded colors would overlap). Is my assumption correct or is there an optimal solution(s) to this problem, and how could I go about finding it (them) graphically?
You are correct in your observation as there exists no optimal solutions. Here is what the following model looks like in Desmos:
From here, we can observe that the constraints $y-x\ge3$ and $x-y\ge0$ conflict with one another in such a way that they do not overlap. Thus, there will never exist a point that will concurrently satisfy all three constraints.
Suppose we are not satisfied with the graphical representation with the model, or we did not consider a graphical approach, and we wanted to proceed via the Simplex method. Thus, using the Big-M approach we would standardize our model as such:
$$\min z -x+y-M(a_2+a_3)$$ Subject to, $$x+y+s_1=6$$ $$x-y-e_2+a_2=0$$ $$y-x-e_3+a_3=3$$ $$x,y,e_2,e_3,a_2,a_3\ge0$$
Where $M$ is the "largest" number in $\Bbb R$.
Our initial tableau setup would look like:
\begin{array} {|c|c|} \hline BV & z & x & y & e_2 & e_3 & s_1 & a_2 & a_3 & RHS & RT \\ \hline z & 1 & -1 & 1 & 0 & 0 & 0 & -M & -M & 0 & - \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 6 & - \\ ? & 0 & 1 & -1 & -1 & 0 & 0 & 1 & 0 & 0 & - \\ ? & 0 & -1 & 1 & 0 & -1 & 0 & 0 & 1 & 3 & - \\ \hline \end{array}
After solving for our missing basic variables: \begin{array} {|c|c|} \hline BV & z & x & y & e_2 & e_3 & s_1 & a_2 & a_3 & RHS & RT \\ \hline z & 1 & -1 & 1 & -M & -M & 0 & 0 & 0 & 3M & - \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 6 & 6 \\ a_2 & 0 & 1 & -1 & -1 & 0 & 0 & 1 & 0 & 0 & \infty \\ a_3 & 0 & -1 & 1 & 0 & -1 & 0 & 0 & 1 & 3 & 3 \\ \hline \end{array}
From here, would pivot the $y$ column with the $a_3$ row (for this we are assuming $\frac{0}{-\delta}=-0=\infty$ to follow the traditional pivoting rule of ignoring negative numbers in the minimum-ratio-test) to get the following tableau:
\begin{array} {|c|c|} \hline BV & z & x & y & e_2 & e_3 & s_1 & a_2 & a_3 & RHS & RT \\ \hline z & 1 & 0 & 0 & -M & -M+1 & 0 & 0 & -1 & 3M -3 & - \\ \hline s_1 & 0 & 2 & 0 & 0 & 1 & 1 & 0 & -1 & 3 & - \\ a_2 & 0 & 0 & 0 & -1 & -1 & 0 & 1 & 1 & 3 & - \\ y & 0 & -1 & 1 & 0 & -1 & 0 & 0 & 1 & 3 & - \\ \hline \end{array}
Notice that we are unable to pivot anymore and $a_2$ is still a basic variables such that our right-hand-side of our objective function is $3M-3$. Thus, this model is infeasible.
Graphically where this basis is located in the model can be shown in the red circle within the following image:
However, notice that there exists another point that shares the same objective function value as this point, as the reduced-cost-coefficient of $x$ is zero and $x=0$ since it is a non-basic variable. We'll leave that to the reader to figure out where that point is.