Linear program question

4
votes

I'm trying to prepare for my midterm and I was going over some problems out of my algorithm book but can't seem to figure out the following problem:

Find necessary and sufficient conditions on the reals a and b under which the linear program 

max: x+y
ax + by <=1
x, y =>0

(a) is infeasible. (b) is unbounded. (c) has a finite and unique optimal solution.

here is what I've come up with: for (a), we can add another constraint: ax+by=>5

I'm not sure what to do about b and c.I'm not sure If I'm allowed to change the constraints I'm already given or add new ones.

Any help will be appreciated. Thanks so much advance.

3
linear-programming
This problem sounds to me like you are allowed to choose a and b, but may not add or otherwise modify any constraints of the program. Except the part about "necessary and sufficient" means you need to describe a way to determine which of the three cases (if any) applies no matter what a and b you're given. – aschepler
Just curious: is that a "linear program" or a "linear programming model"? You know correct nomenclature is key in this field. – R. Martinho Fernandes
Should be linear programming model but that's how it is written in my book. – sap

3 Answers

3
votes

a) I'm not sure if this is possible unless you add a constraint just like you did.
b) if a and b are both less than or equal to zero your problem will be unbounded
c) if a and b are both larger than zero, and they are not equal to each other you will have a unique optimal solution

0
votes

a. This linear program never infeasible. No matter what value of a and b, there is always a feasible solution to satisfy ax + by <= 1

b. This linear program is unbounded when either a <= 0 or b <= 0.

c. Finite and unique optimal solution exist when a != b and both a > 0 and b > 0

-1
votes

For part (a): it is infeasible when either a=0 and b<0 OR a<0 and b=0