Exercise 3.20

Question

Consider a linear programming problem in standard form, described in terms of the following initial tableau:
\begin{table}
\begin{tabular}{|c|ccccccc|}
\hline 0 & 0 & 0 & 0 & $\delta$ & 3 & $\gamma$ & $\xi$ \
\hline $\beta$ & 0 & 1 & 0 & $\alpha$ & 1 & 0 & 3 \
2 & 0 & 0 & 1 & -2 & 2 & $\eta$ & -1 \
3 & 1 & 0 & 0 & 0 & -1 & 2 & 1 \
\hline
\end{tabular}
\end{table}
The entries $\alpha, \beta, \gamma, \delta, \eta, \xi$ in the tableau are unknown parameters. Furthermore, let $\mathbf{B}$ be the basis matrix corresponding to having $x_{2}, x_{3}$, and $x_{1}$ (in that order) be the basic variables. For each one of the following statements, find the ranges of values of the various parameters that will make the statement to be true.
\begin{enumerate}[label=(\alph*)]
\item Phase II of the simplex method can be applied using this as an initial tableau.
\item The first row in the present tableau indicates that the problem is infeasible.
\item The corresponding basic solution is feasible, but we do not have an optimal basis.
\item The corresponding basic solution is feasible and the first simplex iteration indicates that the optimal cost is $-\infty$.
\item The corresponding basic solution is feasible, $x_{6}$ is a candidate for entering the basis, and when $x_{6}$ is the entering variable, $x_{3}$ leaves the basis.
\item The corresponding basic solution is feasible, $x_{7}$ is a candidate for entering the basis, but if it does, the solution and the objective value remain unchanged.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)] \item extit{Phase II of the simplex method can be applied using this as an initial tableau.} ewline Since this tableau must represent a feasible solution, its entries must be nonnegative, i.e., $\beta \geq 0$. Other than that, the artificial variables have been driven out and there are no further restrictions. \item extit{The first row in the present tableau indicates that the problem is infeasible.} ewline We must check whether the first row \begin{table} \begin{tabular}{|c|ccccccc|} \hline 0 & 0 & 0 & 0 & $\delta$ & 3 & $\gamma$ & $\xi$ \ \hline $\beta$ & $ extcolor{blue}{0}$ & $ extcolor{blue}{1}$ & $ extcolor{blue}{0}$ & $ extcolor{blue}{\alpha}$ & $ extcolor{blue}{1}$ & $ extcolor{blue}{0}$ & $ extcolor{blue}{3}$ \ \hline \end{tabular} \end{table} can indicate infeasibility. Recall that the left-hand side of the tableau stands for $\mathbf{B}^{-1}\mathbf{b}$ whereas the rows are $\mathbf{B}^{-1}\mathbf{A}$; it must hold that $\mathbf{B}^{-1}\mathbf{b} = \mathbf{B}^{-1}\mathbf{A} \mathbf{x}^*$. In case of the first row, this translates to $\beta = x_2 + \alpha x_4 + x_5 + 3x_7$. Since $x_2 = \beta$ and since $x_4, x_5, x_7 = 0$ as they are non-basic, the equation holds no matter which value $\alpha$ and $\beta$ assume. \item extit{The corresponding basic solution is feasible, but we do not have an optimal basis.} ewline Since this tableau must represent a feasible solution, its entries must be nonnegative, i.e., $\beta \geq 0$. Since this solution is not optimal, we must be able to reduce cost by moving in some other direction, i.e., at least one of the conditions $\delta < 0$, $\gamma < 0$, or $\xi< 0$. \item extit{The corresponding basic solution is feasible and the first simplex iteration indicates that the optimal cost is $-\infty$.} ewline Since this tableau must represent a feasible solution, its entries must be nonnegative, i.e., $\beta \geq 0$. Since the optimal cost is $-\infty$, no component of the column entering the next step can be positive. Upon closer inspection, we see that the only candidate is $x_4$, and the condition is satisfied by setting $\alpha \leq 0$. To make sure that the simplex algorithm chooses $x_4$ to enter in the next step (and no other column), we set $\delta < 0$ and $\gamma > 0, \xi > 0$. \item extit{The corresponding basic solution is feasible, $x_{6}$ is a candidate for entering the basis, and when $x_{6}$ is the entering variable, $x_{3}$ leaves the basis.} ewline Since this tableau must represent a feasible solution, its entries must be nonnegative, i.e., $\beta \geq 0$. For $x_6$ to be a candidate for entering the basis, its reduced cost must be negative, i.e., $\gamma < 0$. For $x_3$ to exit the basis when $x_6$ enters, the ratio test must rule out in favour of the second row, i.e, we must have $ heta^* = \min\left\{\frac{2}{\eta},\frac{3}{2} ight\} = \frac{2}{\eta}$. In other words, we must have $\frac{2}{\eta} < \frac{3}{2}$ or, equivalently, $\eta > \frac{4}{3}$. \item extit{The corresponding basic solution is feasible, $x_{7}$ is a candidate for entering the basis, but if it does, the solution and the objective value remain unchanged.} ewline For $x_6$ to be a candidate for entering the basis, its reduced cost must be negative, i.e., $\xi < 0$. The only way that the overall objective value remains unchanged is when $x_1$ exits the basis without changing the cost, i.e, when we add the first row to the zeroth row with the parameter $\beta = 0$. \end{enumerate}


0	0	0	0	$δ$	3	$γ$	$ξ$

$β$	0	1	0	$α$	1	0	3
2	0	0	1	-2	2	$η$	-1
3	1	0	0	0	-1	2	1


0	0	0	0	$δ$	3	$γ$	$ξ$

$β$	$0$	$1$	$0$	$α$	$1$	$0$	$3$

Exercise 3.20

Answers

Comments

Exercise 3.20

Answers

Comments

Add answer