5

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.

Improve this question
3
  • 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. Commented Nov 15, 2010 at 22:24
  • Just curious: is that a "linear program" or a "linear programming model"? You know correct nomenclature is key in this field. Commented Nov 15, 2010 at 22:25
  • Should be linear programming model but that's how it is written in my book. Commented Nov 15, 2010 at 22:27

3 Answers 3

Reset to default
4

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

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

More precisely: (a) is never possible without additional constraint, since (0, 0) is always feasible. (b) the problem is unbounded if and only if either a<=0 or b<=0 (whatever the value of the second coefficient is)
1

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

Improve this answer

Comments

-1

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

Improve this answer

2 Comments

I'll leave it as an exercise to @sap to figure out why this answer is wrong.
a=0, b<0, say -1-> 0*x-1*y <=1 x= 0, y = 1 = -1 <1 ->feasible.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.