Write the associated dual problem for the following primal LP:

Question

Write the associated dual problem for the following primal LP:

$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\text{Max }~~~~ 2x_1+4x_2+4x_3-3x_4$$ $$\text{subject to } x_1+x_2+x_3 =4$$ $$~~~~~~~~~~~~~~~~~~x_1+4x_2+x_4 = 8$$ $$x_i \geq 0 ~~~\forall i$$

Following closely using the universally accepted primal - duality table, my answer is as follows:

$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\text{Min }~~~~ 4p_1+8p_2$$ $$\text{subject to } p_1+p_2 \leq 2$$ $$~~~~~~~~~~~~~~~~~~p_1+4p_2 \leq 4$$ $$~~~~~~~p_1 \leq 4$$ $$~~~~~~~~~p_2 \leq -3$$ $$~~~~~~~~~~p_1,p_2 \text{ free}$$

But i got very confused when my prof's solution is as follows: $$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\text{Min }~~~~ 4p_1+8p_2$$ $$\text{subject to } p_1+p_2 \geq 2$$ $$~~~~~~~~~~~~~~~~~~p_1+4p_2 \geq 4$$ $$~~~~~~~p_1 \geq 4$$ $$~~~~~~~~~p_2 \geq -3$$ $$~~~~~~~~~~p_1,p_2 \text{ free}$$

There is no more further explanation. So where did i go wrong?

Answer 1

If the primal problem is a maximization problem the constraints in the dual which correspond to variables $\geq 0$ become constraints of the form $ax \geq b$ just as in your profs solution. If the primal is a minimization problem then the constraints will have the form $ax \leq b$ in the dual. My guess is that you looked at a duality table in which the primal problem is a minimization problem but you are dealing with a maximization problem in your example.