Exercise 3.19

Question

While solving a standard form problem, we arrive at the following tableau, with $x_{3}, x_{4}$, and $x_{5}$ being the basic variables:
\begin{table}
\begin{tabular}{|r|rrrrr|}
\hline
$-10$ & $\delta$ & $-2$ & $0$ & $0$ & $0$ \
\hline
$4$ & $-1$ & $\eta$ & $1$ & $0$ & $0$ \
$1$ & $\alpha$ & $-4$ & $0$ & $1$ & $0$ \
$\beta$ & $\gamma$ & $3$ & $0$ & $0$ & $1$ \
\hline
\end{tabular}
\end{table}
The entries $\alpha, \beta, \gamma, \delta, \eta$ in the tableau are unknown parameters. For each one of the following statements, find some parameter values that will make the statement true.
\begin{enumerate}[label=(\alph*)]
\item The current solution is optimal and there are multiple optimal solutions.
\item The optimal cost is $-\infty$.
\item The current solution is feasible but not optimal.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)]

\item We take the following facts into account.
ewline

First, the current solution is optimal, yet the reduced cost $\bar{c}_2$ is negative. By Theorem 3.1(b), the current solution cannot be nondegenerate. In other words, $\beta = 0$ by Definition 2.11.
ewline

Secondly, in the next iteration, we can choose the second column to enter the basis. If we do so, we stay in the same basic feasible solution only have changed the basis as $	heta^*=\beta / 3 = 0$ (cf. page 92). We want, however, the new basis to be optimal; thus, we must impose $\delta + \frac{2}{3}\gamma \geq 0$ in the resulting tableau.
ewline

Finally, we do not want this solution to be unique, i.e., we fix $\delta = 0$ and $\alpha > 0$. Thus, we can move in a positive direction (since $\alpha > 0$ and $\gamma = 0$) without changing the optimal cost (since $\delta = 0$). 
ewline

A possible choice of values is represented through the following tableau:
  \begin{table}
    \begin{tabular}{|r|rrrrr|}
      \hline-10 & {\color{blue}0} & -2 & 0 & 0 & 0 \
      \hline 4 & -1 & {\color{blue}2} & 1 & 0 & 0 \
      1 & {\color{blue}1} & -4 & 0 & 1 & 0 \
      {\color{blue}0} & {\color{blue}0} & 3 & 0 & 0 & 1 \
      \hline
    \end{tabular}
  \end{table}

\item For the tableau to represent a feasible solution, we must demand $\beta \geq 0$. Furthermore, recall that the problem is declared unbounded if no components of an exiting column are positive; accordingly, set $\delta < 0$ for the first column to qualify as an exiting one, and set $\alpha, \gamma \leq 0$ for the values of $\mathbf{u}$ to result in nonpositive values. A possible example is:
  \begin{table}
    \begin{tabular}{|r|rrrrr|}
      \hline-10 & {\color{blue}-1} & -2 & 0 & 0 & 0 \
      \hline 4 & -1 & {\color{blue}-1} & 1 & 0 & 0 \
      1 & {\color{blue}-1} & -4 & 0 & 1 & 0 \
      {\color{blue}1} & {\color{blue}-1} & 3 & 0 & 0 & 1 \
      \hline
    \end{tabular}
  \end{table}

\item For the tableau to represent a feasible solution, we must demand $\beta \geq 0$. Since the second column has a negative reduced cost, moving in the direction of $x_2$ will result in a better result, i.e., the current cost is not optimal.
  \begin{table}
    \begin{tabular}{|r|rrrrr|}
      \hline-10 & {\color{blue}2} & -2 & 0 & 0 & 0 \
      \hline 4 & -1 & {\color{blue}1} & 1 & 0 & 0 \
      1 & {\color{blue}1} & -4 & 0 & 1 & 0 \
      {\color{blue}1} & {\color{blue}1} & 3 & 0 & 0 & 1 \
      \hline
    \end{tabular}
  \end{table}

\end{enumerate}

Exercise 3.19

Answers

Comments


$- 10$	$δ$	$- 2$	$0$	$0$	$0$

$4$	$- 1$	$η$	$1$	$0$	$0$
$1$	$α$	$- 4$	$0$	$1$	$0$
$β$	$γ$	$3$	$0$	$0$	$1$


-10	0	-2	0	0	0

4	-1	2	1	0	0
1	1	-4	0	1	0
0	0	3	0	0	1


-10	-1	-2	0	0	0

4	-1	-1	1	0	0
1	-1	-4	0	1	0
1	-1	3	0	0	1


-10	2	-2	0	0	0

4	-1	1	1	0	0
1	1	-4	0	1	0
1	1	3	0	0	1

Exercise 3.19

Answers

Comments

Add answer