I read this problem in CLRST :
Show that a linear program can have finite optimal objective value even if the feasible region is not bounded.
Now all the cases I could think of where such a thing could happen were these :
Among these only b seems to satisfy what the problem asks me to prove. Please note that in b I am not assuming non negativity constraints on both the variables.
Can some one point out if this is right/wrong ? And any other example to prove the same ? or any other more elegant way to do the same ?
Best Answer
Turning my comment into an answer.
Example a) looks like a fine example to me as well. Maximize $−x$ with respect to $x+2y\ge3,x−2y\ge−1,x,y\ge0$. In that case, the optimal value is the vertex to the left, even though the feasible region extends to infinity towards the right. And you also have those non-negativity constraints on the variables which were absent in b) but are suggested by your drawing for a).
So your thinking about b) being an example was right, but your thinking about it being the only possible one was wrong.
Your idea behind the enumeration of these four cases is something I cannot follow without further explanation, so I simply considered each as a single problem, although your statement suggests that you have some partitioning of all problems in mind, and each example should represent one of these partitions. I don't see any kind of completeness here, but the examples should still be sufficient to illustrate the essential ideas.