How to use complementary slackness to find y*?

Question

My Primal LP is

Min -5x1   - x3
      x1+ x2+ x3+ x4        =1
     2x1+ x2        + x5    =2
      x1+2x2+3x3        + x6=3
      x1,x2,x3,x4,x5,x6 >=0

My dual LP is

Max y1+2y2+3y3
    y1+2y2+ y3<=-5
    y1+ y2+2y3<=0
    y1    +3y3<=-1
     y1,y2,y3<=0

x*=(1,0,0,0,0,2)

How do I find y* and z*?

Answer 1

First of all you have primal problem

Min $-5x_1 - x_3$

$x_1+ x_2+ x_3+ \leq 1$

$2x_1+ x_2 \ \ \quad \quad \leq 2$

$ x_1+2x_2+3x_3 \leq 3$

$x_1,x_2,x_3\geq 0$

The other variables are can be interpreted as slack variables: $s_1, s_2$ and $s_3$. I would even say that they are slack variables. The optimal solution is $(x_1,x_2,x_3,s_1,s_2,s_3)=(1,0,0,0,0,2)$

Then the dual problem is

$\text{Max} \ \ y_1+2y_2+3y_3$

$y_1+2y_2+y_3 \leq -5$

$y_1+y_2+2y_3\leq 0$

$y_1+3y_3\leq -1$

$y_1,y_2,y_3\leq 0$

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

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

---

We know that $x_1=1$. Thus $z_1=0$. And we get the equation

$y_1+2y_2+ y_3=-5$

And $y_3\cdot s_3=0\Rightarrow y_3=0 $

The equation above becomes $y_1+2y_2=-5$ Thus the solution is $y_1=-5-2y_2$.

Therefore you have infinitely many solutions like

$y_1^*=(-3,-1,0), y_2^*=(-1,-2,0), y_3^*=(-2, -1.5,0)$