Unbounded 2-var LP's

In the LP's considered above, the feasible region (if not empty) was a bounded area of the -plane. For this kind of problems it is obvious that all values of the LP objective function (and therefore the optimal) are bounded. Consider however the following LP:

s.t.

The feasible region and the direction of improvement for the isoprofit lines for this problem are given in Figure 6.

  
Figure 6: An unbounded LP

It is easy to see that the feasible region of this problem is unbounded, and furthermore, the orientation of the isoprofit lines is such that no matter how far we ``slide'' these lines in the direction of increasing the objective function, they will always share some points with the feasible region. Therefore, this is an example of a (2-var) LP whose objective function can take arbitrarily large values. Such an LP is characterized as unbounded. Notice, however, that even though an unbounded feasible region is a necessary condition for an LP to be unbounded, it is not sufficient; to convince yourself, try to graphically identify the optimal solution for the above LP in the case that the objective function is changed to: .

Summarizing the above discussion, we have shown that a 2-var LP can either

• have a unique optimal solution which corresponds to a ``corner'' point of the feasible region, or
• have many optimal solutions that correspond to an entire ``edge'' of the feasible region, or
• be unbounded, or
• be infeasible.

In the next section, we generalize this geometrical description of the LP solution space for the n-var LP case, and we provide a brief (informal) derivation of the Fundamental Theorem of Linear Programming. The latter states that if an LP has a bounded optimal solution, then it must have one which is an extreme point of its feasible region. The Simplex algorithm to be discussed in the last section of this set of notes essentially exploits this fundamental result to reduce the space to be searched for an optimal solution.

Finally, you can actively try the graphical approach to the solution of 2-var LP's discussed above, by using the code developed by the group of Professors Ken Goldberg and Ilan Adler, at the University of Berkeley, Dept. of Industrial Engineering and Operations Research. Notice that the problem formulation uses a "minimization" objective, and all variables are considered to be "urs". Therefore, (i) any maximization problem must be turned into a minimization one (can you think of an easy way?), and (ii) all sign restrictions must be introduced in the formulation explicitly. Other than that, the software is self-explanatory.
Submit your examples