-1

I'm having the following linear programming problem: $$\begin{align} \max \quad & 2x_{1}+6x_{2}+3x_{3}, & \\ \text{s.t.} \quad & -3x_{2}+a x_{3} \geq2, \\ & x_{1}+5x_{2}+2x_{3} =2, \\ & x_{1},x_{2},x_{3} \geq 0 \end{align}$$

for which value of $a$ do we have an optimal solution?

TMM
  • 9,976
Mary Star
  • 13,956
  • As a start, you could try eliminating $x_3$ from the system using the second equation. (Or $x_1$ or $x_2$.) – TMM Dec 06 '13 at 20:20
  • Couldn't we solve this using methods like Simplex, M-method, dual Simplex,...? – Mary Star Dec 07 '13 at 01:20
  • @MaryStar Can you look at this little problem here? I will vote your answer as the best. https://math.stackexchange.com/questions/4558186/linear-program-problem-optimal-solution-p-l-1-bigg-dfrac21-alpha – user253963 Oct 21 '22 at 12:53

1 Answers1

2

Using the second equation with $x_1 = 2 - 5x_2 - 2x_3$ we can eliminate $x_1$ to get $$\begin{align} \max \quad & 2(2 - 5x_2 - 2x_3) + 6x_2 + 3x_3, \\ \text{s.t.} \quad & -3x_2 + ax_3 \geq 2, \\ & 2 - 5x_2 - 2x_3 ,x_2, x_3 \geq 0 \end{align}$$ Rewriting this a bit, this is the same as $$\begin{align} 4 \quad + \quad \max \quad & -4x_2 - x_3, \\ \text{s.t.} \quad & -3x_2 + ax_3 \geq 2, \\ & -5x_2 - 2x_3 \geq -2, \\ & x_2, x_3 \geq 0 \end{align}$$ Or, in matrix/vector form, $$\begin{align} 4 \quad + \quad \max \quad & \left(\begin{matrix}-4 & -1\end{matrix}\right) \left(\begin{matrix} x_2 \\ x_3 \end{matrix}\right), \\ \text{s.t.} \quad & \left(\begin{matrix} -3 & a \\ -5 & -2 \end{matrix}\right) \left(\begin{matrix} x_2 \\ x_3 \end{matrix}\right) \geq \left(\begin{matrix} 2 \\ -2 \end{matrix}\right), \\ & x_2, x_3 \geq 0 \end{align}$$ Can you take it from here?

Apparently not. Consider the two inequalities. If $a \leq 0$ then $-3x_2 + ax_3 \leq 0$ (since $x_2, x_3 \geq 0$) which leads to a contradiction. For $a > 0$, recall that the two inequalities are given by $$\begin{align} -3 x_2 + a x_3 &\geq 2 \\ -5 x_2 - 2 x_3 &\geq -2\end{align}$$ Let us multiply the second inequality by $3/5$, and move the $x_2$-terms to one side in each equation, to get $$\begin{align} -3 x_2 &\geq 2 + ax_3 \\ -3 x_2 &\geq -\frac{6}{5} - \frac{6}{5} x_3\end{align}$$ Now $2$ and $a$ are both positive (and $x_3$ is nonnegative), so we know that $$2 + ax_3 > 0 > -\frac{6}{5} - \frac{6}{5} x_3$$ In other words, both inequalities are satisfied iff the following inequality is satisfied: $$-3 x_2 \geq 2 + ax_3$$ So for $a > 0$ the whole system can be reduced to the simpler system $$\begin{align} 4 \quad + \quad \max \quad & -4x_2 - x_3, \\ \text{s.t.} \quad & -3x_2 + ax_3 \geq 2, \\ & x_2, x_3 \geq 0 \end{align}$$ Rewriting this a bit more, we get $$\begin{align} 4 \quad - \quad \min \quad & 4x_2 + x_3, \\ \text{s.t.} \quad & ax_3 \geq 2 + 3x_2, \\ & x_2, x_3 \geq 0 \end{align}$$ The main inequality tells us that if we increase $x_2$, then the inequality only becomes harder to satisfy and the target value goes up. So the optimum for $x_2$ is $0$, after which we get $x_3 = 2/a$ as the optimum with target value $2/a$.

So to get back to the original system: for $a \leq 0$ there are no solutions, and for $a > 0$ the optimum is $(x_1,x_2,x_3) = (2 - \frac{4}{a}, 0, \frac{2}{a})$ with target value $4 - \frac{2}{a}$.

TMM
  • 9,976