# Can the dual of a problem has no solution if the primal has a solution?

I'm having a problem with linear programming, the primal function is given by:

$$\text{minimize }z = 5x_1 - 6x_2 - 7x_3$$ subject to \begin{align} x_1 + 5x_2 - 3x_3 &\ge 15 \\ 5x_1 -6x_2 +10x_3 &\le 20 \\ x_1 + x_2 + x_3 &\le 5 \\ x_i &\ge 0\hspace{1cm}(i=1,2,3) \end{align}

which has an optimal solution, although when I find the dual and solve it it has no solution at all:

$$\text{maximize }z = 15x_1 -20x_2 - 5x_3 + 5x_4$$ subject to \begin{align} x_1 - 5x_2 - x_3 + x_4 &\le 5 \\ 5x_1 + 6x_2 - x_3 + x_4 &\le -6 \\ -3x_1 - 10x_2 - x_3 + x_4 &\le -7 \\ x_i&\ge 0\hspace{1cm}(i=1,2,3,4) \end{align}

How is this even possible? Am I doing something wrong?

• I transcribed your images into MathJax so that readers won't have to click on a link to see your equations. Please check that I didn't make any transcription errors! – Joey Zou Oct 5 '16 at 2:14

## 1 Answer

Indeed, this is not possible. Your dual problem is wrong, which should explain why you do not find a solution. The dual should be $$\max\quad 15x_1+20x_2+5x_3$$ subject to \begin{align} x_1+5x_2+x_3 &\le 5\\ 5x_1-6x_2+x_3 &\le -6\\ -3x_1+10x_2+x_3 &\le -7\\ x_1 &\ge 0\\ x_2,x_3 &\in \mathbb{R} \end{align}