2
$\begingroup$

Suppose I've a linear programming problem:

Maximize $2x_1 +x_2 - x_3$ s.t

$ x_1 +2x_2 +x_3 \leq 8 $

$ -x_1 +x_2 -2x_3 \leq 4 $

$ x_1,x_2,x_2 \geq 0 $

and a final tableau:

enter image description here

How could I find the optimal dual variables from this tableau?

I was thinking it could have something to do with complementary slackness, since the first constraint is tight we can know that the the corresponding dual variable is greater than 0.

This is not enough information however, I'm wondering is there any other tricks.

I'm studying for an exam right now so much more interested in a method rather than an answer, maybe some references to text if there's too much to type here.

Thanks a lot.

$\endgroup$
  • $\begingroup$ The second constraint is incomplete. Please check it. $\endgroup$ – callculus May 5 '17 at 13:36
  • $\begingroup$ My apologies.. fixed it. $\endgroup$ – Gregory Peck May 5 '17 at 16:30
1
$\begingroup$

First you should write down the dual pogram:

$\texttt{min}\ \quad 8y_1+4y_2$

$y_1-y_2\geq 2$

$2y_1+y_2\geq 1$

$y_1-2y_2\geq -1$


With slack variables $z_i$ we get equalities.

$\texttt{min}\ \quad 8y_1+4y_2$

$y_1-y_2-z_1= 2$

$2y_1+y_2-z_2= 1$

$y_1-2y_2-z_3= -1$

$y_1,y_2\geq 0$


Now you apply the complementary slackness theorem:

$x_j^*\cdot z_j^*=0 \ \forall \ \ j=1,2, \ldots , n$

$y_i^*\cdot s_i^*=0 \ \forall \ \ i=1,2, \ldots , m$

$s_i^* \text{ are the optimal values of the slack variables of the primal problem.}$

$z_j^* \text{ are the optimal values of the slack variabales of the dual problem.}$


With the dual program, the optimal values of the primal program and the complementary slackness theorem you can find the optimal dual variables. I hope it is now clear how such exercises can be answered.

$\endgroup$
  • $\begingroup$ Thanks for the answer!! I'm slightly confused. For your first statement on complementary slackness there are only 2 slack variables. But n = 5. And is $x_j=s_j$ and $y_i=z_i$ ? $\endgroup$ – Gregory Peck May 5 '17 at 18:29
  • $\begingroup$ The primal problem has 3 decision variables $(x_1,x_2,x_3)$. The results are $(x_1^*,x_2^*,x_3^*)=(8,0,0)$. The (corresponding) slack variables of the dual are $z_1,,z_2$ and $z_3$. One slack variable for every constraint. Since $x_1^*=8\neq 0$ the equation is $x_1^*\cdot z_1^*=8\cdot z_1^*=0$. Thus $z_1$ must be $0$. Consequently the first constraint of the dual is an equality: $y_1-y_2=2 \quad (1)$. We also can see from the first constraint of the primal that $s_2\neq 0$. Therefore $y_2=0 \quad (2)$. With $(1)$ and $(2)$ the values of $y_1$ and $y_2$ can be evaluated. $\endgroup$ – callculus May 5 '17 at 19:55
  • $\begingroup$ Have a look to the dual program with the slack variables in my answer. $\endgroup$ – callculus May 5 '17 at 19:58
  • $\begingroup$ Oh I got it now. I just never observed complementary slackness in that form. Thanks a lot! $\endgroup$ – Gregory Peck May 5 '17 at 20:52
  • $\begingroup$ I know this is only mildly related to the OP, but if I change the coefficient of $x_2$ in the objective function from 1 to 5, or the coefficient of $x_3$ in the second constraint from -2 to 1, how might this alter the solution? I know it has something to do with sensitivity analysis but all resources online are either too high-level or in way too much depth. $\endgroup$ – Gregory Peck May 5 '17 at 21:58

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.