Find the dual of the lp problem

Question

The problem given is and I need to find the dual:

Min $Z=x_1$

st. $x_1+x_2 \leq 4$

$x_2 \geq 0$

So this is what I did, I said:

Let $x_1=x_1'-x_1''$ where $x_1',x_1'' \geq 0$

So now the new lp problem will be:

Min $Z=x_1'-x_1''$

st. $x_1'-x_1''+x_2 \leq 4$

$x_1',x_1'',x_2 \geq 0$

I put it into standard form:

Min $Z=x_1'-x_1''$

st. $x_1'-x_1''+x_2+x_3 =4$

$x_1',x_1'',x_2,x_3 \geq 0$

Now the dual I got was:

Max $W=4 y_1$

s.t $y_1 \geq 1$

$-y_1 \geq -1$

$y_1 \geq 0$

$y_1 \geq 0$

However, my professor said the dual is:

Min $W=4 y_1$

s.t $y_1 \geq 1$

$-y_1 \geq 1$

$y_1 \geq 0$

$y_1 \geq 0$

I'm not sure what i did wrong

Answer 1

Your solution is not right. If you have a primal min-Problem and the variable is greater or equal to 0 ($\geq$) the corresponding inequality sign of the dual constraint is $\leq$.

Therefore the dual is

Max $W=4 y_1$

s.t $y_1 \leq 1 \quad \quad (1)$

$-y_1 \leq -1\quad \quad (2)$

$y_1 \leq 0\quad \quad (3)$

$y_1 \leq 0\quad \quad (4)$

Multipying the second constraint by (-1):

$y_1 \geq 1\quad \quad (2')$

In combination with the third and (redundant) forth constraint it is obvious that this problem has no solution.

Now a new variable can be defined. $-y_1=y_2$. The (dual) problem becomes

Max $W=-4 y_2$

s.t $-y_2 \leq 1 \quad \quad (1)$

$y_2 \leq -1\quad \quad (2)$

$-y_2 \leq 0\quad \quad (3)$

$-y_2 \leq 0\quad \quad (4)$

If you multiply all constraints by -1 you´ll get the constraints in the form of your professor-except the first constraint. Maybe a typo. The same can be done to the objective function. In this case the objective function has to be minimized.

Min $-W=4 y_2$

s.t $y_2 \geq -1 \quad \quad (1)$

$-y_2 \geq 1\quad \quad (2)$

$y_2 \geq 0\quad \quad (3)$

$y_2 \geq 0\quad \quad (4)$

Your dual problem has the solution $y_1=1$ and the primal problem is unbounded. This is a contradiction. If the primal (dual) problem is unbounded, then the dual (primal) Problem has no solution. Et vis versa. And if the primal (dual) problem has an optimal solution, the dual problem has also an optimal solution. The values of the objetctive function then are equal.

Answer 2

You haven't done anything wrong, the DP in standard form is a maximisation problem with "less than" inequalities. (but your inequalities are "more than" so everything has just been multiplied by negative 1)

Your standard form correct providing your x1 is a free variable, in which case you are free to use the substitution you have given. When you convert from LP to DP you quote a maximisation problem, transpose the coefficient matrix of your inequalities, and interchange X and Y.