[Math] Finding optimal dual variables from primal tableau – Linear Programming

Question

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:

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.

Answer 1

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.