Jtdylktuy

Let "stable operation" be an operation on a simplex tableau such that the entering variable has a reduced cost of 0. Recall that a pivoting operation will not change the objective value if either the reduced cost (i.e. in the $bar c$ row shown below) is 0, or if the leaving variable has value 0 already.

Example of stable operation (which preserves objective value):
$$
begin{array}{c|cccccc|c}
text{Basis} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & text{Sol.} \
hline
bar c & 0 & 0 & 0 & 0 & -1 & -1 & 1 \
x_1 & 1 & 0 & 0 & 1 & 1 & 1 & 4 \
x_2 & 0 & 1 & 0 & -1 & 1 & 1 & 2\
x_3 & 0 & 0 & 1 & -1 & 1 & 1 & 3\
end{array}
$$
$$LARGEpmbdownarrow$$
$$
begin{array}{c|cccccc|c}
text{Basis} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & text{Sol.} \
hline
bar c & 0 & 0 & 0 & 0 & -1 & -1 & 1 \
x_4 & 1 & 0 & 0 & 1 & 1 & 1 & 4 \
x_2 & 1 & 1 & 0 & 0 & 2 & 2 & 6 \
x_3 & 1 & 0 & 1 & 0 & 2 & 2 & 7 \
end{array}
$$

Example of an operation which is not stable but also preserves objective value:
$$
begin{array}{c|cccccc|c}
text{Basis} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & text{Sol.} \
hline
bar c & 0 & 0 & 0 & -1 & -1 & -1 & 1 \
x_1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \
x_2 & 0 & 1 & 0 & -1 & 1 & 1 & 2\
x_3 & 0 & 0 & 1 & -1 & 1 & 1 & 3\
end{array}
$$
$$LARGEpmbdownarrow$$
$$
begin{array}{c|cccccc|c}
text{Basis} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & text{Sol.} \
hline
bar c & 1 & 0 & 0 & 0 & 0 & 0 & 1 \
x_4 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \
x_2 & 1 & 1 & 0 & 0 & 2 & 2 & 2 \
x_3 & 1 & 0 & 1 & 0 & 2 & 2 & 3 \
end{array}
$$

However, in the second case, the solution does not change.

Is there always a path of stable operations from a tableau for an optimal basic feasible solution (BFS) to a tableau for all other optimal BFS? Which of the following are true:

1. For all optimal BFS $X_1$, for all tableaus $T_1$ for $X_1$, for all optimal BFS $X_2$, for all tableaus $T_2$ for $X_2$, there is a path of stable operations from $T_1$ to $T_2$. (I think the answer for this is false.)


2. For all optimal BFS $X_1$, for all tableaus $T_1$ for $X_1$, for all optimal BFS $X_2$, there is a tableau $T_2$ for $X_2$ such that there is a path of stable operations from $T_1$ to $T_2$.


3. For all optimal BFS $X_1$, there is a tableau $T_1$ for $X_1$ such that for all optimal BFS $X_2$, there is a tableau $T_2$ for $X_2$ such that there is a path of stable operations from $T_1$ to $T_2$.

The motivation for this problem is so that we decide when we have exhausted all optimal solutions when searching for them; can we limit our procedure to search only with stable operations on the tableau?

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.