Using simplex method to show that a linear program has no finite optimal solution

1.5k Views Asked by At

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.

1

There are 1 best solutions below

0
On

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.)