[Math] Find the Dual of a Linear Programming Problem

duality-theoremslinear programmingoptimization

I have a very simple linear programming problem with the following constraints:

Minimize $3x_1 + 2x_2 – 33x_3$

subject to

$x_1 – 4x_2 + x_3 \leq 15$

$9x_1 + 6x_3 \leq 12$

$5x_1 + 9x_2 \geq 3$

$x1,\ x2,\ x3 \geq 0$

Simple enough. When I optimize using GAMS I get a minimum optimal solution of $-65.33$. I know the dual of this problem must have the same optimal solution. I got the dual by putting the above constraints into a matrix and taking the transpose of the matrix to get the new constraints as follows:

maximize $15y_1 + 12y_2 + 3y_3$

subject to

$y_1 + 9y_2 + 5y_3 \geq 3$

$-4y1 + 9y3 \geq 2$

$y1 + 6y2 \leq -33$

$y1,y2,y3 \geq 0$

When I run this optimization problem using GAMS I get an infeasible solution. Am I taking the dual of the original problem correctly? What am I missing in these new constraints?

Thanks in advance.

Best Answer

There are some errors in your dual form. It should be:

\begin{align} -\textrm{minimize } 15y_1 + 12y_2 - 3y_3\\ \textrm{s.t. } y_1 + 9y_2 - 5y_3 &\geq{-3}\\ -4y_1 -9y_3 &\geq{-2}\\ y_1 + 6y_2 &\geq{33}\\ y_1, y_2, y_3 &\geq{0} \end{align}

or

\begin{align} \textrm{maximize } -15y_1 - 12y_2 + 3y_3\\ \textrm{s.t. } y_1 + 9y_2 - 5y_3 &\geq{-3}\\ -4y_1 -9y_3 &\geq{-2}\\ y_1 + 6y_2 &\geq{33}\\ y_1, y_2, y_3 &\geq{0} \end{align}

Notice that the sign of the third constraint is different from the first two. You can transform your primal problem to the standard form and then do the dual transform, which will make it easier.


P.S.

  • About the dual objective function, it doesn't matter if it is a maximize or a minimize problem since we can always transform one into the other.

  • By standard form, I mean the form in the book linear programming by Vanderbei[1].

[1] Vanderbei, Robert J., Linear programming. Foundations and extensions., International Series in Operations Research & Management Science 114. New York, NY: Springer (ISBN 978-0-387-74387-5/hbk). xix, 464 p. (2008). ZBL1139.90002.