How do we prove that if a linear programming problem is unbounded, then its feasible region is necessarily an unbounded set as well? It kind of seems intuitive but how do I rigorously show this?
Feasible region unbounded
linear programming
linear programming
How do we prove that if a linear programming problem is unbounded, then its feasible region is necessarily an unbounded set as well? It kind of seems intuitive but how do I rigorously show this?
Best Answer
We prove the contrapositive. Suppose the feasible region is bounded. We already know it is closed, by assumption. The objective function is continuous (because it is linear). Therefore the extreme value theorem applies: it implies that the maximum (or minimum) of the objective function on the feasible region is attained at some point in the region. Thus the LP problem is bounded.