Exercise 3.23

Question

While solving a linear programming problem by the simplex method, the following tableau is obtained at some iteration.
$$
\begin{array}{|c|cccc|}
\hline
 & 0 \quad \cdots \quad 0 & \bar{c}_{m+1} & \cdots & \bar{c}_n \
\hline
x_1 & 1 \quad \cdots \quad 0 & a_{1, m+1} & \cdots & a_{1, n} \
\vdots & \vdots \quad \ddots \quad \vdots & \vdots & \ddots & \vdots \
x_m & 0 \quad \cdots \quad 1 & a_{m, m+1} & \cdots & a_{m, n} \
\hline
\end{array}
$$
Assume that in this tableau we have $\bar{c}_j \geq 0$ for $j=m+1, \dots, n-1$, and $\bar{c}_n < 0$. In particular, $x_n$ is the only candidate for entering the basis.
\begin{itemize}
    \item[(a)] Suppose that $x_n$ indeed enters the basis and that this is a nondegenerate pivot (that is, $\theta^* \neq 0$). Prove that $x_n$ will remain basic in all subsequent iterations of the algorithm and that $x_n$ is a basic variable in any optimal basis.
    \item[(b)] Suppose that $x_n$ indeed enters the basis and that this is a degenerate pivot (that is, $\theta^*=0$). Show that $x_n$ need not be basic in an optimal basic feasible solution.
\end{itemize}

Ahmed · Accepted Answer

oindent (a) Let $z_0$ be the cost associated with the current tableau. Since all reduced costs are non-negative except for $\bar{c}_n$, this tableau represents the optimal solution to the problem restricted by the additional constraint $x_n=0$. Therefore, any feasible solution with $x_n=0$ must have a cost of at least $z_0$.
    
    When $x_n$ enters the basis with a nondegenerate pivot, we have $	heta^* > 0$. The cost changes by $	heta^* \bar{c}_n$, which is strictly negative. The new cost, $z_1 = z_0 + 	heta^* \bar{c}_n$, is strictly less than $z_0$.
    
    The simplex algorithm, when not cycling, ensures that the cost at any subsequent iteration, $z_k$, will be less than or equal to $z_1$ (i.e., $z_k \leq z_1 < z_0$).
    
    For $x_n$ to leave the basis in a future iteration, it would have to become nonbasic, meaning its value would be 0. Any such solution must have a cost greater than or equal to $z_0$. Since the algorithm's current cost is strictly less than $z_0$ and will never increase, it can never reach a state where $x_n=0$. Thus, $x_n$ can never leave the basis.
    
    \vspace{1em}

oindent (b) If $x_n$ enters the basis via a degenerate pivot ($	heta^*=0$), the basis changes, but the solution vector and the cost remain the same. This allows for the possibility that $x_n$ could leave the basis in a subsequent iteration without a change in cost.
    
    Consider the following sequence of events:
    \begin{enumerate}
        \item The algorithm is at a degenerate basic feasible solution $\mathbf{x}^*$.
        \item Variable $x_n$ enters the basis. Since the pivot is degenerate ($	heta^*=0$), the solution remains $\mathbf{x}^*$.
        \item In the new tableau, due to the basis change, another variable $x_k$ might now have a negative reduced cost, making it a candidate to enter.
        \item During the pivot for $x_k$, it is possible that the pivot row corresponds to the now-basic variable $x_n$. This pivot could also be degenerate.
        \item This would cause $x_n$ to leave the basis. The solution is still $\mathbf{x}^*$. If this new tableau is optimal (all reduced costs are non-negative), we have found an optimal basis that does not include $x_n$.
    \end{enumerate}
    This shows that after a degenerate entry, $x_n$ is not guaranteed to remain in the basis and therefore need not be basic in an optimal basic feasible solution. \qed

Exercise 3.23

Answers

Comments

Exercise 3.23

Answers

Comments

Add answer