Currently I am preparing the Linear Programming exam and I've got some issue to solve these problems. Shortly, suppose some linear program: max $C^{T}X$ s.t. $AX \leq b$, where $A$ is $2 \times 3$ matrix. After adding slack variables $x_4$and $x_5$ to the first and second constraints respective, we have got following tableau.
Current basis: $x_1, x_3$
\begin{array}{rrr}
-z & -4x_2 -x_4 -x_5 =& -12\\
& -x_1 -3x_2 + 11x_4 – x_5 =& -4\\
& 6x_2 + x_3 -3x_4 +2x_5 =& 3\\
& x_j \geq 0 \quad \forall j
\end{array}
(a) Identify the dual solution $y_1, y_2$ corresponding to the current
basis. Is the solution feasible to the dual problem?
My answer>>
I guess (1, 1) may be the solution of dual. However, even if the primal is not optimal, do we just adapt the (negative) coefficient of objective function from the primal (in this problem, negative of $x_4$ and $x_5$ are (1, 1)). And how can I check the feasibility of dual solution?
(b) Perform one iteration of the dual simplex method on this tableau.
My answer>>
\begin{array}{rrrrrr|r}
& x_1 & x_2 & x_3 & x_4 & \color{red}{x_5} \\ \hline
\color{red}{x_1} & 1 & -3 & 0 & 11 & \color{red}{-1}& -4\\
x_3 & 0 & 6 & 1 & -3 & 2 & 3\\ \hline
& 0 & -4 & 0 & -1 & -1 & -12\\
\text{ratio} & & 1.33 & & & 1 & 0 &
\end{array}
Leaving variable: $x_1$, entering variable: $x_5$
Current basis: $x_5, x_3$
\begin{array}{rrrrrr|r}
& x_1 & x_2 & x_3 & x_4 & x_5 \\ \hline
x_5 & -1 & 3 & 0 & -11 & 1& 4\\
x_3 & 2 & 0 & 1 & 19 & 0 & -5\\ \hline
& -1 & -1 & 0 & -12 & 0 & -8\\
\end{array}
(c) Can you perform the next dual simplex iteration on the tableau
obtained in (b)? What can be said about the status of the primal LP?
(e.g. finite optimal, unbounded, or infeasible) What about the status
of the dual of the problem?
My answer>>
We could not proceed the dual simplex method anymore. Maybe the status of the primal LP is also infeasible. However, like the problem (a), I don't know how to analyze a dual problem with only this given information.
Best Answer
Your answers are basically correct.
Yes, the current dual solution can be always obtained in this way.
The dual is feasible since all dual variables are non-negative.
You can't continue since the dual is unbounded. Thus, by weak duality the primal is infeasible.