| course |
course_year |
question_number |
tags |
title |
year |
Optimization |
IB |
73 |
|
3.II.20D |
2005 |
Consider the linear programming problem
$$\begin{aligned}
\operatorname{maximize} \quad 4 x_{1}+x_{2}-9 x_{3} & \\
\text { subject to } \quad x_{2}-11 x_{3} & \leqslant 11 \\
-3 x_{1}+2 x_{2}-7 x_{3} & \leqslant 16 \\
9 x_{1}-2 x_{2}+10 x_{3} & \leqslant 29, \quad x_{i} \geqslant 0, \quad i=1,2,3 .
\end{aligned}$$
(a) After adding slack variables $z_{1}, z_{2}$ and $z_{3}$ and performing one pivot in the simplex algorithm the following tableau is obtained:
\begin{tabular}{c|rrrrrr|r}
& $x_{1}$ & $x_{2}$ & $x_{3}$ & $z_{1}$ & $z_{2}$ & $z_{3}$ & \
\hline$z_{1}$ & 0 & 1 & $-11$ & 1 & 0 & 0 & 11 \
$z_{2}$ & 0 & $\frac{4}{3}$ & $-\frac{11}{3}$ & 0 & 1 & $\frac{1}{3}$ & $\frac{77}{3}$ \
$x_{1}$ & 1 & $-\frac{2}{9}$ & $\frac{10}{9}$ & 0 & 0 & $\frac{1}{9}$ & $\frac{29}{9}$ \
\hline Payoff & 0 & $\frac{17}{9}$ & $-\frac{121}{9}$ & 0 & 0 & $-\frac{4}{9}$ & $-\frac{116}{9}$
\end{tabular}
Complete the solution of the problem using the simplex algorithm.
(b) Obtain the dual problem and identify its optimal solution from the optimal tableau in (a).
(c) Suppose that the right-hand sides in the constraints to the original problem are changed from $(11,16,29)$ to $\left(11+\epsilon_{1}, 16+\epsilon_{2}, 29+\epsilon_{3}\right)$. Give necessary and sufficient conditions on $\left(\epsilon_{1}, \epsilon_{2}, \epsilon_{3}\right)$ which ensure that the optimal solution to the dual obtained in (b) remains optimal for the dual for the amended problem.