Find all the solutions of the following LP problem
maximize $z= 3x_1+x_2+0x_3$
subject to
$x_1+2x_2 \leq 5$
$x_1+x_2-x_3 \leq 2$
$7x_1 + 3x_2 -5x_3 \leq 20$
and $x_1, x_2, x_3 \geq 0$
my final LP is:
$x_3 = 3-x_2-x_4+x_5$
$x_1 = 5 - 2x_2 -x_4$
$x_6 = 0 + 6x_2+2x_4+9x_5$
$z = 15-5x_2-3x_4$
I have found a solution of this LP $(5, 0, 3, 0, 0, 0)$, but I'm not sure what it means by finding 'all the solutions', can someone give me a hint?
You have found a solution, but could there be another one? can you describe all of them?
Properties of this particular question, $x_1$ and $x_2$ are bounded. $x_3$ is unbounded from above.
Also notice that $(5,0)$ is the unique solution to
$$\max 3x_1+x_2$$
subject to $$x_1+2x_2 \le 5$$
$$x_1, x_2 \ge 0$$
If we have $x_3 < 3$, then our original problem would exclude the point $(5,0,x_3)$.
Observe that the only way to attain maximum value of $15$ is to set $x_1=5, x_2=0$. We need $x_3 \ge 3$ to make it attain the value of $15$.