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.

  • $\begingroup$ Hint: if $x,y \ge 0$ then it cannot be that $x+y \le -1$. $\endgroup$ – Yuval Filmus Apr 4 '19 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 Apr 4 '19 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 Apr 4 '19 at 17:04

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.


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.