# How to apply complementary slackness

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.

• You need optimal solution of the primal to obtain the optimal solution of the dual. Jan 21 at 16:04
• The optimal solution is $(10,0,0)$ which can be obtained by setting $x_2=x_3=0$ since they are nonbasic at optimality . Jan 21 at 16:06
• The optimal solution of the dual is $(5/2,0,0)$ using the complementary slackness condition. Jan 21 at 16:19
• @Manish Saini that is precisely the question, how? Jan 21 at 16:20
• @Upstart If you have no questions anymore feel free to accept the answer or even give a reply. Jan 21 at 16:41

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

• see the primal variables at the optimal are $x_1=10,x_2=0,x_3=0,s_2=16,s_3=30$ and the dual optimal is $y_1=5/2,y_2=,y_3=0,s_1'=13/2,s_2'=18$ so how is the CST verified? Jan 21 at 16:46
• @Upstart As I've written: At the optimal solution of the primal we have $s_2,s_3\neq 0$. So we have two equations: $y_2\cdot s_2=0$ and $y_3\cdot s_3=0$. $\textrm{A product is zero, if at least one factor is zero}$. Thus $y_2=y_3=0$ Jan 21 at 16:48

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