CODEWITHSUNDEEP
linear-programming
sap
sap

Reputation: 1141

Linear program question

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.

Upvotes: 5

Views: 5374

Answers (3)

kdebugging
kdebugging

Reputation: 337

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

Upvotes: 1

user2205837
user2205837

Reputation: 1

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

Upvotes: -1

Haluk
Haluk

Reputation: 2099

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

Upvotes: 4

Related Questions