Just started learning Linear Programming, and was given this question as a weekly exercice question from my professor
$$ \text{Min } z=-x_{1}$$
$$
\begin{aligned}
-\mathrm{x}_{1}+\mathrm{x}_{2} & \leq 2 \\
\mathrm{x}_{1}+\mathrm{x}_{2} & \leq 8 \\
-\mathrm{x}_{1}+\mathrm{x}_{2} & \geq-4 \\
\mathrm{x}_{1}, \mathrm{x}_{2} & \geq 0
\end{aligned}
$$
I was asked to solve this question graphically first (The solution is therefore $x_1=6, x_2 = 2, z = -6)$. However, the second part of the question is what I am unable to think of an idea how to solve it.
With the help of the graph, suppose now the objective function becomes $z=-x1+ax_2$ where $a$ is a constant. Determine the interval of $a$ for which the new objective function will still have the same optimal solution
I am not exactly sure how to solve it using the graph? What are some characteristics or properties I have to use in order to find the answer?
Best Answer
The optimal solution will be at one of the vertices of the polygon described by the 5 inequality constraints. The vertices are $(0,0)$, $(0,2)$, $(3,5)$, $(4,0)$ and $(6,2)$. We want to determine the interval of $a$ for which the optimal solution remains at $(6,2)$. In this regard, when we evaluate $z = -x_{1} + ax_{2}$ at each vertex, $-6 + a2$ must be the lowest.
The following inequalities must hold:
$-6 + a2 \leq -0+a0$
$-6 + a2 \leq -0+a2$
$-6 + a2 \leq -3+a5$
$-6 + a2 \leq -4+a0$
which gives you the interval $-1 \leq a \leq 1$.