1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ When I use your constraints, I get positive 65.33. Shouldn't the answer be -65.33 like the original problem? $\endgroup$ – user3554599 Feb 23 at 23:27
  • $\begingroup$ Yeah, there should be a negative sign in my objective function. I will correct it. $\endgroup$ – Snjór Feb 23 at 23:45
  • $\begingroup$ My previous answer yields 65.33 because when I transformed your primal problem to the standard form, I added a negative sign to the primal objective function to make it a maximize. So a negative sign should be added back after the dual transform is finished. $\endgroup$ – Snjór Feb 23 at 23:50
  • $\begingroup$ When I put maximize instead of minimize I get infeasible. I thought the dual had to have the opposite kind of objective function (maximize if the original had minimize and vice versa). $\endgroup$ – user3554599 Feb 24 at 1:28
  • $\begingroup$ See the maximize program in the update. It is not origo feasible. Since if the primal dictionary is feasible, the corresponding dual dictionary is infeasible. But it doesn't mean the dual problem is infeasible. If we plug in the optimal solution of $y = (0, 5.5, 0.22)$, we can see it is feasible. $\endgroup$ – Snjór Feb 24 at 7:33
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ My original problem is a minimization problem. Doesn't it then convert to maximizing after i take the dual? $\endgroup$ – user3554599 Feb 23 at 23:29
  • $\begingroup$ Thanks for catching that. Fixed by negating $c$. $\endgroup$ – parsiad Feb 23 at 23:30

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.