Question

1. Consider the following linear program, where a and b are real-valued constants:

max: x + y;
ax + by ≤ 1;
x ≥ 0;
y ≥ 0;

A) Suppose a < 0 and b < 0. Which one of these statements is true?

Group of answer choices

i) The linear program has a finite feasible region

ii) The linear program has an empty feasible region

iii) The feasible region is infinite, but there is an optimal solution

iv) The feasible region is infinite, and there is no optimal solution

B) Suppose a < 0 and b > 0. Which one of these statements is true?

Group of answer choices

i) The linear program has a finite feasible region

ii) The linear program has an empty feasible region

iii) The feasible region is infinite, but there is an optimal solution

iv) The feasible region is infinite, and there is no optimal solution

C) Suppose the linear program has a finite feasible region. In which one of the following cases will it not have a unique optimal solution?

Group of answer choices

i) a = b

ii) a < b

iii) a > b

iv) a ≠ b

Answer 1

max : x + y

subject to ax + by <=1 , x , y >=0

• LP is never infeasible as the origin satisfies for any choice of a and b.
• If a<=0 or b<=0. If a<=0 then we can increase x(and the objective function) arbitarily without violating any constraint. The same argument works for b and y. conversely, suppose both a and b are positive. Let m= min {a,b} and notice m>0. Then, m(x+y)<=ax+by<=1 , so that x+y <=1/m. Hence, the LP cannot be unbounded.

(A) i) The linear program has a finite feasible region.

• the LP has a fnite optimal solution when a and b are positive. Suppose now a>b. Then, the optimal is clearly uniquely achieved at x=1/b.Similarly, if b>a, the unique optimum is x=1/a. However,if a==b, then any positive pair (x,y) such that x+y=1/a achieves the optimum. Hence,the optimum exists and is unique if and only if a,b are positive and a!=b.

(B) i) The linear program has a finite feasible region.

(c) iv)