# How to find all solutions of a given LP problem

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?

• there's a typo for the third constraint. Nov 1, 2018 at 5:44
• @SiongThyeGoh fixed it. Can you help me out with the thought process Nov 1, 2018 at 6:10
• Is it common to see $0\cdot\text{something}$ in $z= 3x_1+x_2+0x_3$? Nov 1, 2018 at 6:24
• @manooooh I'm not sure, but on the worksheet i printed out has a $0$ in front of $x_3$. Nov 1, 2018 at 6:26

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$$.

• Thanks for the clarification. Does that mean any point $(5, 0, x_3); x_3 \geq 3$ is a solution to this problem Nov 1, 2018 at 6:59
• I think so unless I make a mistake. Nov 1, 2018 at 6:59