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?

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

1 Answer 1


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.