In the optimal primal simplex tableau, if we have a non-basic variable with a reduced cost of zero, can we say for sure the primal has multiple optimal solutions? Or can the same thing also happen when we have a degenerate unique solution? Thanks.
[Math] Multiple optimal solutions / LP
linear programmingoptimizationsimplex
Related Solutions
You can find a proof of the statement in the table that you quote in the book
Linear and Integer Programming: Theory and Practice, Second Edition
pages 141-145, proof of Theorem 4.5.
However the exact statement is that existance of a degenerate and (additionally) unique solution of the primal implies multiple solutions to the dual.
Using the notation of the the above cited book, the proof of this statement proceeds as follows:
Let $x^*$ be a primal optimal basic feasible solution with basis variables $x_B^*$ (from this and due to the duality theorems you already know that the dual has a finite optimal solution). Since it is degenerate then there exists $$x_{i_0}^*=0, \qquad \text{ with } i_0 \in B$$ But the variable $y_{j_0}^*$ (that corresponds to $x_{i_0}$) of the corresponding dual basic feasible solution $y^*$ is nonbasic and therefore $$y_{j_0}^*=0 \tag1$$ On the other the Strong Complementary Slackness Theorem
(Theorem 3.6 of the book) implies that (given that primal in standard form has an optimal solution) there exists a pair of primal and dual optimal solutions $x^*$ and $y^*$ such that for each pair of complementary dual variables $(x_i^*,y_j^*)$ it holds that either $x_i^*>0$ or $y_j^*>0$ (or both).
Thus, due to uniqueness of the primal optimal solution (so this assumption is necessary for this proof) there is a dual optimal solution (not necessarily basic feasible) for which $$y_{j_0}^*> 0 \tag{2}$$
Relations $(1)$ and $(2)$ together imply that there exist multiple optimal dual solutions.
Edit 1: According to this question and answer you can see that it is impossible that both the primal and the dual have simultaneously multiple solutions. Together with the above proof this answers your question.
Note that the "unstable operation" above won't give you a different solution. You've just replaced the basic variable $x_1 = 0$ by a nonbasic variable $x_4 = 0$, but the solution shown in the above optimal simplex tableau is still $(x_1,x_2,x_3,x_4,x_5,x_6)^T = (0,2,3,0,0,0)^T$.
Therefore, only "stable operations" with a non-zero variable $x_r \ne 0$ to be replaced by $x_j$ will give you a different basic optimal feasible solution.
It's easy to verify that any convex combination of a set of basic optimal feasible solution(s) is still an optimal feasible solution (since the feasible region in a linear program in convex), so the set of optimal feasible solution is convex (i.e. path connected). Hence, the answer to your question is yes.
(Added in response to the edit of the question)
You may just think of the graph so as to visualize your problem. A basic solution corresponds to an extreme point in the feasible region. (If $\mathbf x$ is an extreme point, then there doesn't exists two different $\mathbf u$ and $\mathbf v$ such that $\mathbf x$ is a convex combination of $\mathbf u$ and $\mathbf v$.) Form the graph of the set of all optimal feasible solutions of the linear program, and note its convexity (so it's a convex polygon), then eliminate its relative interior point. Take any two vertices of the remaining boundary points to be $X_1$ and $X_2$ in (1). Clearly, we can see a path running from $X_1$ to $X_2$ through adjacent vertices. (Assume that you have $m$ constraints and $n$ decision varibles, and $m < n$. Choose $n$ vectors in the $m$-by-$m+n$ matrix $A$ to form a basis matrix $B$. This is similar to choosing hyperplanes (representing the constraints) in $\Bbb R^{m+n}$ and find its intersection.) This corresponds to a (finite) series of steps of replacing $x_r$ by $x_j$, which is feasible. Since that's feasible, there exists a pivot operation in one of the simplex tableaux $T_1$ for $X_1$.
Let $y_{00} = \bar c$ be the objective function value, $y_{0j}$ be the $j$-th column of the objective function row (i.e. the row of $\bar c$), $y_{r0} = x_r$ be the $r$-th component of the current solution, and $y_{rj}$ be the $r,j$-th entry in the coefficient matrix.
\begin{matrix} y_{0j}& y_{00}\\ y_{rj}& y_{r0} \end{matrix}
In order not to change the value of $y_{00}$ after a pivot operation $y_{00}-\dfrac{y_{r0} y_{0j}}{y_{rj}}$, i.e. $$y_{00}-\dfrac{y_{r0} y_{0j}}{y_{rj}} = y_{00},$$ we have $y_{r0} y_{0j} = 0$. Since we want to move to another point, we must have $y_{r0} \ne 0$, which implies $y_{0j} = 0$, so the operation must be stable. Hence (1) is proved.
Best Answer
I use "BV" as an abbreviation of "basic variable". In the following optimal simplex tableau, suppose that we are going to replace the basic variable $x_r$ by a non-basic variable $x_j$ to obtain an alternate optimal basic feasible solution to the LPP. Suppose that in the tableau, there're $m$ constraints and $n$ columns (excluding "BV" and "RHS").
\begin{align*} \begin{array}{c|ccc|c} \mbox{BV} & * & x_j & * & \mbox{RHS} \\ \hline * & * & * & * & * \\ x_r & * & y_{rj} & * & y_{r0} \\ * & * & * & * & * \\ \hline * & * & y_{0j} & * & y_{00} \end{array} \end{align*}
If $y_{r0} = 0$, then we are just replacing $x_r = 0$ by $x_j = 0$ on the LHS of the tableau, but the current optimal solution is not changed. Therefore, to find an alternate basic optimal feasible solution, we need to assume that $y_{r0} \ne 0$.
To perform a pivot operation on $y_{rj}$, we first need the condition that $y_{rj} > 0$. This gives us another (feasibility) condition: there exists $j \in \left\{ 1,\dots,n \right\}$ such that \begin{equation*} \begin{cases} x_j \mbox{ is a non-basic variable,} \\ y_{0j} = 0 \mbox{ and} \\ \exists r \in \left\{ 1,\dots m \right\} \mbox{ s.t. } y_{rj} > 0 \end{cases} \end{equation*}
After a pivot operation on $y_{rj}$, the objective function value $y_{00}$ will become $y_{00} - \dfrac{y_{r0} y_{0j}}{y_{rj}}$. If we want $y_{00}$ to be unchanged, we need $\dfrac{y_{r0} y_{0j}}{y_{rj}} = 0$. Since $y_{rj} > 0$ (feasibility) and $y_{r0} \ne 0$ (to get another solution), we have $y_{0j} = 0$. Therefore, the only way to determine whether there is an alternate basic optimal feasible solution from the optimal simplex tableau is to search for the zeros in the reduced cost coefficient of the non-basic variables.