0
$\begingroup$

given the linear program:

minimize $x+y$

subject to,

$ax+by \leq 1$

$x,y \geq 0$

I need to find real numbers $a,b \in \mathbb{R}$ such that the program (a) is infeasible, (b) is unbounded, and (c) has a unique optimal solution.

Since we are asked to minimize the sum of two non-negative numbers the solution for all $a,b \in \mathbb{R}$ is $(x,y)=(0,0)$, right?

I cannot see any potential values of $a,b$ which would make the program infeasible or unbounded, because we are always looking to minimize the sum of non-negative numbers.

Improve this question
$\endgroup$
3
  • $\begingroup$ Hint: if $x,y \ge 0$ then it cannot be that $x+y \le -1$. $\endgroup$
    – Yuval Filmus
    Commented Apr 4, 2019 at 16:45
  • $\begingroup$ @YuvalFilmus What values of $a,b$ transform the constraint into the one you have shown? If we take $a,b < 0$ then the constraint is equivalent to $ax+by \geq -1$, but even for that (0,0) is an optimal solution. If we take $a > 0$ and $b < 0$, then the constraint is equivalent to $-ax+by \geq -1$ and again we have that (0,0) is the optimal solution. $\endgroup$
    – Matthew Riley
    Commented Apr 4, 2019 at 17:03
  • 1
    $\begingroup$ Well then, perhaps there is a mistake in the question. Perhaps you can prove that the program is feasible and bounded for all $a,b$. $\endgroup$
    – Yuval Filmus
    Commented Apr 4, 2019 at 17:04

1 Answer 1

Reset to default
1
$\begingroup$

I’d say the program is always feasible because x = y = 0 is a solution.

Most pairs a, b give a unique solution. Only certain pairs don’t.

Now it depends on the definition of “unbounded”. If we talk about the goal function, the minimum is always bounded by 0. If we talk about the points (x, y), they are unbounded if a <= 0 or b <= 0.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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