Exercise 3.18

Question

Consider the simplex method applied to a standard form problem and assume that the rows of the matrix $\mathbf{A}$ are linearly independent. For each of the statements that follow, give either a proof or a counterexample.
\begin{enumerate}[label=(\alph*)]
\item An iteration of the simplex method may move the feasible solution by a positive distance while leaving the cost unchanged.
\item A variable that has just left the basis cannot reenter in the very next iteration.
\item A variable that has just entered the basis cannot leave in the very next iteration.
\item If there is a nondegenerate optimal basis, then there exists a unique optimal basis.
\item If $\mathbf{x}$ is an optimal solution, no more than $m$ of its components can be positive, where $m$ is the number of equality constraints.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)] \item \textit{An iteration of the simplex method may move the feasible solution by a positive distance while leaving the cost unchanged.}\newline \textbf{False.} From Step 2 of the simplex algorithm (cf. page 100), we know that the simplex method only moves when there is some index $j$ with the negative reduced cost $\bar{c}_j < 0$. The overall cost then changes by $\theta^*\bar{c}_j$ for some positive $\theta^*>0$; in other words, the cost cannot remain unchanged. \item \textit{A variable that has just left the basis cannot reenter in the very next iteration.}\newline \textbf{True.} Suppose that we are working with the following tableau. Here, $x_i$ denotes the exiting variable, $x_j$ the entering one and $l$ denotes the index of the basic variable for which $x_{B(l)}=x_i$. Since $x_i$ is basic, its reduced cost is zero. \begin{table} \begin{tabular}{|c|ccccc|} \hline & $\cdots$ & $\textcolor{red}{x_i}$ & $\cdots$ & $\textcolor{green}{x_j}$ & $\cdots $\ \hline & $\cdots$ & $\textcolor{red}{0}$ & $\cdots$ & $\textcolor{green}{\bar{c}_j}$ & $\cdots$ \ \hline $\vdots$ & $\vdots$ & $\textcolor{red}{\vdots}$ & $\vdots$ & $\textcolor{green}{\vdots}$ & $\vdots$\[5pt] ${x_{B(l)} = x_i}$ & $\vdots$ & $\textcolor{red}{1}$ & $\vdots$ & $\textcolor{green}{u_l}$ & $\vdots$ \[5pt] $\vdots$ & $\vdots$ & $\textcolor{red}{\vdots}$ & $\vdots$ & $\textcolor{green}{\vdots}$ & $\vdots$\[5pt] \hline \end{tabular} \end{table} Since $x_j$ is an exiting variable, it must be assumed that its reduced cost is negative $\bar{c}_j < 0$ while its pivot element is positive $u_l>0$. Compliant with Step 5 of the simplex algorithm, we must subtract $\frac{\bar{c}_j}{u_l}$ times the pivot row from the zeroth row and get the pivot element to be one. \begin{table} \begin{tabular}{|c|ccccc|} \hline & $\cdots$ & ${x_i}$ & $\cdots$ & ${x_j}$ & $\cdots$ \ \hline & $\cdots$ & ${-\frac{\bar{c}_j}{u_l}}$ & $\cdots$ & ${0}$ & $\cdots$ \[2.5pt] \hline $\vdots$ & $\vdots$ & ${\vdots}$ & $\vdots$ & ${\vdots}$ & $\vdots$\[5pt] ${x_{B(l)} = x_j}$ & $\vdots$ & ${\frac{1}{u_l}}$ & $\vdots$ & ${1}$ & $\vdots$ \[5pt] $\vdots$ & $\vdots$ & ${\vdots}$ & $\vdots$ & ${\vdots}$ & $\vdots$\[5pt] \hline \end{tabular} \end{table} But $-\frac{\bar{c}_j}{u_l}$ is positive; thus, $x_i$ cannot be a candidate for an entering variable. \item \textit{A variable that has just entered the basis cannot leave in the very next iteration.}\newline \textbf{False.} In Example 3.8 (pp. 114-115), $x_4$ enters the basis in the second tableau and immediately exits the basis in the third tableau. \item \textit{If there is a nondegenerate optimal basis, then there exists a unique optimal basis.}\newline \textbf{False.} To see why, consider the following nondegenerate problem with a nonunique optimal solution: \begin{equation*} \begin{array}{lll} \text { minimize } & x_{1}+ x_{2}+x_{3} \ \text { subject to } \quad &x_{1}+ x_{2}+x_{3}=1 \ & x_{1}, x_{2}, x_{3} \geq 0. \end{array} \end{equation*} Trivially, for the matrix $\mathbf{A} = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix}$, its components $\mathbf{A}_1,\mathbf{A}_2$ and $\mathbf{A}_3$ all constitute for optimal bases, yet $(1,0,0), (0,1,0)$ and $(0,0,1)$ are all optimal solutions to the problem. \item \textit{If $\mathbf{x}$ is an optimal solution, no more than $m$ of its components can be positive, where $m$ is the number of equality constraints.}\newline \textbf{True.} If $\mathbf{x}$ is an optimal solution found by the simplex method, then it must be a basic feasible solution (cf. Theorem 3.3). By Theorem 2.4, a basic feasible solution must have $x_i=0$ for all $i \neq B(1),\ldots,B(m)$. Thus, at most $m$ components of $\mathbf{x}$ can be positive. \end{enumerate}


	$\dots$	$x_{i}$	$\dots$	$x_{j}$	$\dots$

	$\dots$	$0$	$\dots$	${\bar{c}}_{j}$	$\dots$

$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$

$x_{B (l)} = x_{i}$	$⋮$	$1$	$⋮$	$u_{l}$	$⋮$

$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$


	$\dots$	$x_{i}$	$\dots$	$x_{j}$	$\dots$

	$\dots$	$- \frac{{\bar{c}}_{j}}{u_{l}}$	$\dots$	$0$	$\dots$


$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$

$x_{B (l)} = x_{j}$	$⋮$	$\frac{1}{u_{l}}$	$⋮$	$1$	$⋮$

$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$

Exercise 3.18

Answers

Comments

Exercise 3.18

Answers

Comments

Add answer