Existence of multiple optimal solutions in Linear Programming simplex method

Question

Let us suppose the final iteration of the simplex tableau indicates nondegeneracy (no basic variable is at zero level) and the reduced cost of one of the non-basic variables is zero. Are we always guaranteed to have another optimal solution that is distinct from the current optimal solution in this case?

Answer 1

Yes, just as long as the initial optimal point is basic feasible, as this is because the optimal solution for that type of model doesn't exist on just a singular point, but on a line with an infinitely amount of points. Let's consider the model:

$$\max\quad z=2000x_1+3000x_2$$ Subject to: $$6x_1+9x_2\le100$$ $$2x_1+x_2\le20$$ $$x_1,x_2\ge0$$

Now let's graphically depict this without the objective function as such:

What we'll find is that when we solve this is that the objective function will envelop the entire line like so:

Simplex is landing at either upper-corner, optimal extreme points in the model, and the non-basic variable that would produce the other optimal solution is the variable that correlates with the opposite optimal point that lives on the optimal line (the non-basic variable with a reduced cost coefficient of zero). In actuality, all points that exist on this line are optimal to this model, thus we can represent optimal lines as such:

$$\lambda(x_1,y_1)+(1-\lambda)(x_2,y_2),\quad\lambda\in[0,1]$$ where points $(x_1,y_1)$ and $(x_2,y_2)$ are unique extreme points on either end of the line. Thus, this is why we are always guaranteed to have another optimal feasible point if we pivot in the multi-solution situation if we start pivoting from an already feasible optimal point.