1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Where is your objective function? $\endgroup$ – callculus May 7 at 13:57
  • $\begingroup$ @callculus the initial objective function is not given. Only consider unknown objective function C'X , and we should solve problems with the given result of the simplex method. $\endgroup$ – Yong Jin Shin May 8 at 6:03
1
$\begingroup$

Your answers are basically correct.

Even if the primal is not optimal, do we just adapt the (negative) coefficient of objective function from the primal.

Yes, the current dual solution can be always obtained in this way.

And how can I check the feasibility of dual solution?

The dual is feasible since all dual variables are non-negative.

[In item c)] how to analyze of dual problem with only this given information?

You can't continue since the dual is unbounded. Thus, by weak duality the primal is infeasible.

$\endgroup$
  • $\begingroup$ Thank you for replying. But the thing i still don't understand is how all dual variables are non-negative can guarantee the feasibility of dual. $\endgroup$ – Yong Jin Shin May 10 at 12:49
  • 1
    $\begingroup$ @YongJinShin By construction of the tableau. Maybe it helps to look first at the primal. The current basic feasible solution satisfies all equalities, so non-negativity is sufficient for feasibility. The same holds for the dual: the current solution satisfies all dual restriction, so non-negativity is sufficient for feasibility. $\endgroup$ – Marcus Ritt May 10 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.