Having the following linear program:

\begin{cases} \max & -x_1 & -2 x_2&+x_3\\ & -3 x_1 &+x_2 & &\le -1\\ & x_1 &-x_2 & &\ge 1\\ &-2x_1 & +7 x_2 & & \le 6\\ & -5x_1& &+2x_3 &=-3\\ & 7x_1 &-3x_2 &&\le6\\ &x_1\ge0\\ &x_3\le0 \end{cases}

Why do we have:

\begin{cases} \min &-y_1 &-y_2 &+6y_3 & +6y_4& &-3y_6\\ &-3y_1&-y_2 & -2y_3& +7y_4 & & -5y_6&\ge-1\\ &y_1 &+y_2 &+y_3 &-3y_4&&&=-1\\ &&&&&y_5&+2y_6&=1\\ \forall i\in[[1,5]],y_i\ge0 \end{cases}

And not

\begin{cases} \min &-y_1 &-y_2 &+6y_3 & -3y_4& &+6y_5\\ &-3y_1&-y_2 & -2y_3& +7y_4 & & -5y_6&\ge-1\\ &y_1 &+y_2 &+y_3 &-3y_4&&&=-1\\ &&&&&y_5&+2y_6&=1\\ \forall i\in[[1,5]],y_i\ge0 \end{cases}

I just read the $b_i$ in the vertical way and put them at the place of the $c_i$ in the dual problem.


They changed the order of the inequalities:

\begin{cases} \max & -x_1 & -2 x_2&+x_3\\ & -3 x_1 &+x_2 & &\le -1 \color{blue}{\qquad (y_1)}\\ & x_1 &-x_2 & &\ge 1 \color{blue}{ \qquad (y_2)}\\ &-2x_1 & +7 x_2 & & \le 6\qquad \color{blue}{ (y_3)}\\ & 7x_1 &-3x_2 &&\le6\qquad \color{blue}{(y_4)}\\ & x_3\leq 0 \qquad \qquad \color{blue}{(y_5)}\\ & -5x_1& &+2x_3 &=-3\qquad \color{blue}{(y_6)}\\ &x_1\geq 0\\ \end{cases}

The second constraint has to be multiplied by 1.

Note that the second constraint of the dual program has to be

$y_1+y_2+7y_3-3y_4+2y_6=\color{red}{-2} \quad (x_2)$

The corresponding coefficient in the objective function is -2 ($-2x_2$).

The others constraints are:

$-3y_1-y_2-2y_3+7y_4-5y_6\geq -1 \quad (x_1)$

$y_5+2y_6=1 \quad (x_3)$


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.