Find the Dual of a Linear Programming Problem

Question

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.

Answer 1

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.

Answer 2

The original linear program is $\max c^{\intercal}x$ with respect to $Ax\leq b$ and $x\geq0$ where $$ c^{\intercal}=\begin{pmatrix}-3 & -2 & 33\end{pmatrix}\text{, }A=\begin{pmatrix}1 & -4 & 1\\ 9 & 0 & 6\\ -5 & -9 & 0 \end{pmatrix}\text{, and }b=\begin{pmatrix}15\\ 12\\ -3 \end{pmatrix}. $$ The dual is $\min b^{\intercal}y$ subject to $A^{\intercal}y\geq c$ and $y\geq0$. It looks like you messed up some of your signs (i.e., $3$ instead of $-3$ in the objective function and $9$ instead of $-9$ in the second constraint).