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?

  • $\begingroup$ 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! $\endgroup$ – Joey Zou Oct 5 '16 at 2:14

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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.