Suppose I was given a linear program like
$$\max z = – x_1 + 2x_2 + x_3 $$
s.t. $$ 3x_1 + x_2 – 4x_3 \leq 4$$
$$x_1 – x_2 – x_3 \leq 10$$
$$x_1 – 2x_2 + 6x_3 \leq 9 $$
$$x_1, x_2, x_3 \geq 0 \ .$$
It's easy to verify geometrically that this problem is unbounded, but how can I use the simplex method to show that this problem has no finite optimal solution? I am also confused about what it really means to be a finite solution, because the unreadable, chaotic, confusing and contradictable literature of linear programming cannot give me another better definition than "$z$ can be as big as possible". I am not so much concerned about this particular example above more than understand how the simplex method could be used in this case.
Best Answer
When an LP is unbounded, the (primal) simplex method will terminate with a basic feasible solution (call it $x^{*}$ and a ray (call it $r$) such that along the path $x^{*}+\alpha r$, $\alpha > 0$, the points are all feasbile and the objective function is monotonically increasing (or decreasing if your problem is a minimization.)