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


$ 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


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

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

2 Answers 2


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

  • $\begingroup$ 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? $\endgroup$
    – Upstart
    Jan 21 at 16:46
  • $\begingroup$ @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$ $\endgroup$ 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).$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .