# How to use complementary slackness to find y*?

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*?

• Your primal LP is unbounded, A better value for the objective function is $−100$. And $x=(20,0,0,−19−38,−17)$. Or is $\color{red}{x_1,x_2,x_3\geq 0}$ ? – callculus Nov 8 '16 at 7:44
• My bad $x_1$, $x_2$, and $x_3$ are $\geq0$ – daultongray8 Nov 8 '16 at 18:28
• Are $x_4,x_5,x_6\geq 0$ as well ? – callculus Nov 8 '16 at 18:34
• yes they are. I am getting that the dual LP is infeasible, and if that is the case there is no y* right? – daultongray8 Nov 8 '16 at 19:16
• No you have infinite many solution for the dual problem. The primal problem is not unbounded. – callculus Nov 8 '16 at 19:52

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)$$