1

I am trying to see if [3,-1,0,2] is an optimal solution to the following LP using complementary slackness:

maximize $6x_1 + x_2 -x_3 - x_4 $ s.t. $x_1 + 2x_2 + x_3 + x_4 \leq 5 $ $3x_1 + x_2 -x_3 \leq 8 $ $x_2 + x_3 + x_4 = 1 ,$ $x_3, x_4 \geq 0 $, $x_1, x_2 $ are unrestricted

I found the dual : minimize $5y_1 + 8y_2+ y_3$ s.t. $y_1 + 3y_2 =6$, $2y_1 + y_2 - y_3 =1$, $y_1 -y_2 + y_3 \leq -1$, $y_1+y_3 \leq -1$, $y_3$ unrestricted. I found $y_1=0, y_2 =2, y_3 =-1$ which implies the optimality of the primal solution. But the answer says NOT optimal. please suggest

user55531
  • 309

1 Answers1

0

The dual problem is:

$\texttt{min} \ \ 5y_1+8y_2+y_3$

$y_1+3y_2=0$

$2y_1+y_2+y_3=1$

$y_1-y_2+y_3 \geq -1$

$y_1+y_3 \geq -1$

$y_1,y_2 \geq 0;\ y_3 \texttt{is unrestricted}$

If the variable of the primal max-problem is $\geq 0$, then the inequality sign of the corresponding constraint of the dual problem is $\geq $.

callculus42
  • 30,550