How to apply complementary slackness

Question

Given the primal $$\max z= 5x_1-4x_2+3x_3$$ subject to

$2x_1+x_2-6x_3=20$

$ 6x_1+5x_2+10x_3\leq 76$

$8x_1-3x_2+6x_3\geq 50$

with $x_1\in \mathbb{R}, x_2\geq 0,x_3\leq 0$.

The question is to construct the dual and find the dual solution using complementary slackness theorem if at the primal's optimal table the basic variables are $s_3$ (slack in the 3rd constarint),$s_2$ (slack in the 2nd constarint), $x_1$.

My attempt is since $x_2,x_3$ are not in the optimal table this implies $x_2=x_3=0$ at the optimal. So this also should satisfy the constraints. This gives $x_1=10$ and hence the optimum value as $z=50$. Now the dual constructed is $$\min w=20y_1+76y_2+50y_3$$ subject to

$2y_1+6y_2+8y_3=5$

$y_1+5y_2-3y_3\geq -4$

$6y_1-10y_2-6y_3\geq -3$ with $y_1\in \mathbb{R}, y_2\geq 0, y_3\leq 0$

Now I know since the first constraint is an equation in the primal$\implies~y_1=0$, after that I am stuck. can somebody help.

Answer 1

Your dual problem is right. Then the conditions for complementary slackness theorem are

---

$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 slack variables of the primal problem.}$

$z_j \text{ are the slack variables of the dual problem.}$

---

For $x_1=10, x_2=x_3=0$ we see that the constraints 2 and 3 are not fulfilled as equalities. Thus $s_2, s_3\neq 0$. And therefore $y_2=0, y_3=0$. From the first constraint of the dual problem we can calculate that $y_1=\frac52$.

Answer 2

Let $u_i$ be the slack variables of the primal and $v_i$ are the slack variables of the dual, where $i=1,2,3$

$x_i$ and $y_i$ are optimal variables for primal and dual respectively.

using Complementary slackness condition $x_1v_1+x_2v_2+x_3v_3+y_1u_1+y_2u_2+y_3u_3=0$, and $(10,0,0)$ is optimal to the primal which implies that $v_1=y_2=y_3=0$ implies $(5/2,0,0)$ is optimal to the dual with slack variables $(0,13/2,18).$