Solving a LP problem

Question

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

Answer 1

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.

Answer 2

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.