Taking Dual of a Linear Program

100 Views Asked by At

Take the dual of the following LP:

min $x_1 + x_2 + 4$ such that $$\begin{bmatrix} 1 & 3 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\x_2 \end{bmatrix} \leq \begin{bmatrix} 10 \\ 21 \end{bmatrix}$$ where $x_1,x_2 \geq 0$

I rewrote the objective function as $\begin{bmatrix} 1 & 1 \end{bmatrix} $ $\begin{bmatrix} x_1 \\ x_2+4 \end{bmatrix} $

I then get the following: min $10y_1 + 21y_2$ such that $$\begin{bmatrix} 1 & 2 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} y_1 \\y_2 \end{bmatrix} \leq \begin{bmatrix} 1 \\ 1 \end{bmatrix}$$ $y_1,y_2 \geq 0$

Can someone tell me if this is correct?

1

There are 1 best solutions below

0
On BEST ANSWER

You're almost there, but there's a minus sign missing on the RHS of the dual constraints.

As David M. points out, the dual of a max LPP should be a min LPP. It can be observed that you've replaced the dual variables in

\begin{align} \max 10 y_1 + 21 y_2 & \\ \begin{bmatrix} 1 & 2 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} y_1 \\y_2 \end{bmatrix} &\leq \begin{bmatrix} 1 \\ 1 \end{bmatrix} \\ \bbox[yellow,5px]{y_1, y_2 \le 0} & \end{align}

by their additive inverses

\begin{align} \max - 10 y_1 - 21 y_2 & \\ \begin{bmatrix} 1 & 2 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} -y_1 \\ -y_2 \end{bmatrix} &\leq \begin{bmatrix} 1 \\ 1 \end{bmatrix} \\ \bbox[yellow,5px]{y_1, y_2 \ge 0.} & \end{align}

Then you replaced "$\max- 10 y_1 - 21 y_2$" with "$\min 10 y_1 + 21 y_2$". However, the negative signs remain in the dual constraints, and you can't get rid of them by multiplication with any scalar. Therefore, a correct equivalent LP would be

\begin{align} \min 10 y_1 + 21 y_2 & \\ \begin{bmatrix} 1 & 2 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} &\bbox[yellow,5px]{\geq \begin{bmatrix} -1 \\ -1 \end{bmatrix}} \\ \bbox[yellow,5px]{y_1, y_2 \ge 0.} & \end{align}