I am learning optimization and I came across this exercise to solve the following problem:

$$\min 2x_1+3x_2$$

$$x_1+x_2\geq 5$$

$$x_1\geq 1$$

$$x_2\geq 2$$

This exercise has been introduced just after the definition of the standard LP and the corresponding dual problem. The question is to prove that $x^*=(3,2)$ is the optimal solution by showing that the objective value of any feasible solution is at least 12.

I have tried to convert the problem to the dual form.

First I convert my LP problem to a standard LP problem by introducing the surplus variables $x_3,x_4,x_5:$

$$\min 2x_1+3x_2$$

$$x_1+x_2-x_3 = 5$$

$$x_1-x_4 = 1$$

$$x_2 - x_5 = 2$$

with all $x_i \geq 0$.

Then I convert the problem to the corresponding standard dual:

$$\max 5y_1+y_2+2y_3$$

$$y_1+y_2\leq 2$$

$$y_3\leq 3$$

$$y_i \geq 0, i \in \{1,2,3\}$$

But then I am stuck...

  • 1
    $\begingroup$ How can $x^*=(3,2)$ if $x_1\geq5$? Did you mean to write $x_1\geq3$? $\endgroup$ – Thoth Jan 17 '19 at 6:00
  • $\begingroup$ You are right, sorry for the typo. I have corrected it. Thanks $\endgroup$ – JejeBelfort Jan 17 '19 at 6:12
  • $\begingroup$ @JejeBelfort Note the constraints at the dual are $$y_1+y_2\color{red}= 2$$ $$y_3\color{red}= 3$$ $\endgroup$ – callculus Jan 17 '19 at 6:40
  • $\begingroup$ Assuming that you're thinking of your primal as including the implicit (but redundant) constraints $\ x_1 \ge 0\ ,$ and $\ x_2\ge 0\ $ , then the second inequality in your dual, corresponding to the variable $\ x_2\ $ of the primal, should be $y_1 + y_3 \le 3\ $, because the coefficient of $\ x_2\ $ in the first inequality of the primal, corresponding to the variable $\ y_1\ $ of the dual, is $\ 1\ $. $\endgroup$ – lonza leggiera Jan 17 '19 at 6:52
  • $\begingroup$ @JejeBelfort Your dual is still wrong. Didn´t you get my comment? $\endgroup$ – callculus Jan 17 '19 at 7:02

Edited hint: Since a reformulation of the original problem into standard form has now been added, my original answer is no longer very comprehensible. The dual of the problem, as originally formulated is:

$ \begin{eqnarray} \max 5y_1\ + &y_2&+\ 2y_3\\ \ \ \ \ \ \ \ \ \mbox{ subject to:} & &\\ y_1+y_2\ \ \ &=& 2\\ y_1 + \ \ \ y_3&=&3\ \mbox{, and}\\ y_1\ge0, y_2&\ge0,& y_3\ge 0 \end{eqnarray} $

As callculus has pointed out, in the absence of any explicit sign restrictions on the variabes $x_1, \mbox{and } x_2\ $, the constraints in the dual should be equations rather than inequalities. However, since the second and third constraints of the primal imply that $\ x_1\ge0, \mbox{and } x_2\ge0\ $, these implied constraints could have been made explicit in the original formulation—as you have now so made them in your reformulation into standard form—, and then the dual constraints would have been $y_1+y_2 \le 2\ $ and $y_1 + y_3\le3\ $, as they are, in fact, for the standard form, whose dual is:

$ \begin{eqnarray} \max 5y_1\ + &y_2&+\ 2y_3\\ \ \ \ \ \ \mbox{ subject to:}& &\\ y_1+y_2\ \ \ &\le& 2\\ y_1 + \ \ \ y_3&\le&3\ \mbox{, and}\\ y_1\ge0, y_2&\ge0,& y_3\ge 0\ \ . \end{eqnarray} $

Now if $\ x^* = \left(3, 2\right)\ $ is an optimal solution for the primal, then because the non-negativity conditions, $\ x_1 \ge 0\ \mbox{ and } x_2 \ge0$, of your primal (in standard form) are both slack for those values (i.e. $\ 3\, {\color{red} >}\, 0\ \mbox{ and }\ 2\, {\color{red} >}\, 0 $), the complementary slackness conditions imply that the corresponding constraints, $\ y_1+y_2\le 2\ \mbox{ and } y_1 + y_3\le3\ $, must be tight for an optimal solution, $\ \left(y_1^*, y_2^*, y_3^*\right)\ $, of the dual—that is, $\ y_1^*+y_2^*= 2\ \mbox{ and } y_1^* + y_3^*=3\ $. Similarly, because the non-negativity condition $x_4 \ge 0$ is also slack (since $\ x_4 = x_1^* - 1 = 2\, {\color{red} >}\, 0\ $), then the corresponding constraint, $\ y_2 \ge 0\ $, should be tight for the optimal solution of the dual. That is, $\ y_2^* = 0\ $. These conditions are sufficient to determine uniquely what the optimal solution of the dual would have to be—namely, $\ y_1^* = 2, y_2^* = 0,\ $ and $\ y_3^* = 1\ $. To verify that these purported optimal solutions really are optimal, all you have to do is check that the values of their respective objective functions are the same for both of them, which is, in fact, the case.

  • $\begingroup$ You haven´t mentioned that the dual is still wrong. $\endgroup$ – callculus Jan 17 '19 at 7:19
  • $\begingroup$ I was assuming that the primal constraints implicitly included the redundant inequalities $x_1\ge 0\ $ and $\ x_2\ge 0\ $, in which case the dual constraints can be inequalites rather than equations. $\endgroup$ – lonza leggiera Jan 17 '19 at 7:51
  • 1
    $\begingroup$ I´ve change my downvote into an upvote. $\endgroup$ – callculus Jan 18 '19 at 20:57
  • $\begingroup$ --------Thank you. $\endgroup$ – lonza leggiera Jan 18 '19 at 22:19

Let's use a graphical solution. Taking $x_1$ on x axis and latter on y axis. We get $$x+y≥5$$ $$x≥1$$ $$y≥2$$ And we need to find the minimum value of c In $$2x+3y= c$$image of graphical rendering by desmos By slowly increasing c we can easily see that it first intersects the red area (possible values of X and y) first at (2,3) and is the unique solution to c= 12 I have used a graphing calculator for this but it can be easily drawn on paper.

  • $\begingroup$ Agreed for the graphical solution, thanks! However, I don't think this is the philosophy of the exercise, which is to play around with the dual problem. $\endgroup$ – JejeBelfort Jan 17 '19 at 7:11
  • $\begingroup$ Welcome to MSE: It should be clear from the question that the person who asked it is not after a solution that uses computers. $\endgroup$ – José Carlos Santos Jan 17 '19 at 7:12
  • $\begingroup$ As I mentioned a computer wasn't necessary. $\endgroup$ – Karthik Jan 17 '19 at 7:13
  • $\begingroup$ As I mentioned a computer isn't necessary. It can be easily hand drawn and the solution could be obtained just using a rough graph. I used the computer just so that it looks good. $\endgroup$ – Karthik Jan 17 '19 at 7:15

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.