How to treat new variables in the dual of a Linear Program

118 Views Asked by At

I am attempting to find the dual of the following linear program

Max $2x_1+x_2$, subject to:

$12x_1+3x_2\leq60$,

$3x_1-x_2\geq -7$,

$x_2\leq 10$,

$x_1\geq 0$,

$x_2$ free.

To do this I took the transpose of

$\begin{bmatrix} 12&3&60\\ 3&-1&-7\\ 0&1&10\\ 2&1 \end{bmatrix}$

and got

$\begin{bmatrix} 12&3&0&2\\ 3&-1&1&1\\ 60&-7&10 \end{bmatrix}$

which gives me the linear program

min $60v_1-7v_2+10v_3$ subject to:

$12v_1+3v_2\geq 2$,

$3v_1-v_2+v_3\leq1$

Now I am unsure as to the nonegitivity constraints because I have one more variable $v_3$ and because $x_2$ was a free variable. Any help would be appreciated.

1

There are 1 best solutions below

2
On BEST ANSWER

The constraint of a primal problem actually corresponds to the variable to the dual problem.

Your primal problem is a maximization problem.

The first constraint of your primal problem is $$12x_1 + 3x_2 \leq 60$$

Let's associate a variable $v_1$ to it. When we go from a primal maximization constraint to a dual minimization variable, $\leq$ in the constraint, corresponds to $\geq$ in the variable. Hence $\color{blue}{v_1 \geq 0}$.

I will leave the sign of $v_2$ and $v_3$ as an exercise.

When we go from a primal maximization variable to a dual minimization constraint, the sign is preserved.

Hence $x_1 \geq 0$ corresponds to $$12v_1+3v_2 \geq 2.$$

$x_2$ being free corresponds to $$3v_1-v_2+v_3\color{red}=1$$