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?

a) The linear program has a finite feasible region

b) The linear program has an empty feasible region

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

d) 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?

a) The linear program has a finite feasible region

b) The linear program has an empty feasible region

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

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

Answer 1

A) The answer is option (a).

To see that the feasible region is non-empty, note that satisfies all the inequalities when . To prove that the region is finite, note that for any , there is no such that . SImilarly, for , there is no such that   holds. Therefore the region is bounded within .

Therefore the feasible region is finite.

B) The answer is option (d).

To see why, note that the condition can be rewritten as . For a particular value , the value of x is bounded by . But as the value gets larger, the range for x keeps getting larger. Therefore the region is unbouded.

To see that there is no optimal solution, note that as the value of gets larger, larger value of x can be picked in the region. Therefore even larger values of x+y can be obtained by choosing larger y, and then it enables picking larger x. Hence there is no optimal solution.

The graph of this looks like the following, where the shaded region is bounded. It can be seen that there is no maximum to how large x+y can be:

Comment in case of any doubts.