0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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}$ ? $\endgroup$ – callculus Nov 8 '16 at 7:44
  • $\begingroup$ My bad $x_1$, $x_2$, and $x_3$ are $\geq0$ $\endgroup$ – daultongray8 Nov 8 '16 at 18:28
  • $\begingroup$ Are $x_4,x_5,x_6\geq 0$ as well ? $\endgroup$ – callculus Nov 8 '16 at 18:34
  • $\begingroup$ yes they are. I am getting that the dual LP is infeasible, and if that is the case there is no y* right? $\endgroup$ – daultongray8 Nov 8 '16 at 19:16
  • $\begingroup$ No you have infinite many solution for the dual problem. The primal problem is not unbounded. $\endgroup$ – callculus Nov 8 '16 at 19:52
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.