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$ – Siong Thye Goh Nov 1 '18 at 5:44
  • $\begingroup$ @SiongThyeGoh fixed it. Can you help me out with the thought process $\endgroup$ – PiCubed Nov 1 '18 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 '18 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 '18 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$.

  • $\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 '18 at 6:59
  • $\begingroup$ I think so unless I make a mistake. $\endgroup$ – Siong Thye Goh Nov 1 '18 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.