0
$\begingroup$

Please guide me on the following question.

Consider the LP problem

maximize $x_1+x_2$

subject to

$x_1-2x_2\le10$

$x_2-2x_1\le10$

$x_1,x_2\ge0$

Which of the following is true?

$1.$ The LP problem admits an optimal solution.

$2.$ The LP problem is unbounded.

$3.$ The LP problem admits no feasible solution.

$4.$ The LP problem admits a unique feasible solution.

The first line passes through $(0,-5)$ and $(10,0)$. The second line passes through $(0,10)$ and $(-5,0)$. They both intersect at (-10,-10). Thereby, I am getting that it would be an unbounded problem and won't have any feasible solution.

That is, according to me, $2nd$ and $3rd$ options are correct. But answer should be only one option. Please help.

$\endgroup$
  • 1
    $\begingroup$ It may be good for you to plot the feasible region - i.e. shade it. For e.g. check $(5, 5)$ - why would you think there is no feasible region? $\endgroup$ – Macavity Aug 16 '13 at 15:28
  • $\begingroup$ got it. I earlier thought only vertices can give us a feasible solution. But ur comment makes me think that a region can be feasible solution. that makes sense. so answer is 2. thanks! $\endgroup$ – Ramit Aug 16 '13 at 16:00
  • $\begingroup$ @Ramit: The intersection of the all areas left after the constraints give the feasible solutions. $\endgroup$ – Nick Jan 30 '15 at 15:14
1
$\begingroup$

Put $x_1 = x_2 \geq 0$ and check if this is a feasible solution. If so, then what happens to the objective function as $x_1 = x_2$ becomes larger and larger?

$\endgroup$
  • $\begingroup$ okay, understood. There are many feasible solutions, but it is an unbounded problem. $\endgroup$ – Ramit Aug 16 '13 at 15:58

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.