2
$\begingroup$

Prove that $(2,0,0)$ is the optimal solution to this problem.

P) Minimize $2x_1+5x_2+7x_3$ subject to constraints:
$7x_1+6x_2+3x_3-s_1=14$
$2x_1+4x_2+5x_3+s_2=4$
Where: $x_1,x_2,x_3 \ge 0$

This question asked me to prove me that $(2,0,0)$ is the optimal solution for the primal problem Without using simplex.(using complementary slackness conditions)

The dual is: Maximize $14y_1+4y_2$
$7y_1+2y_2+t_1=2$
$6y_1+4y_2+t_2=5$
$3y_1+5y_2+t_3=7$
Where: $y_1 \ge 0,y_2 \le 0$

Now if we use complementary slackness theorem: $x_1>0$ then $t_1=0 $
The equation will be: $7y_1+2y_2=2$

Then:

$x_2=0 , x_3=0$ then $t_2,t_3=?$
(We cannot determine $t_2, t_3$)

If we substitute $(2,0,0)$ in the primal we see $s_1,s_2=0$
And we cannot determine $y_1$ and $y_2$

So we only get one equation $7y_1+2y_2=2$.

Now should i say we can't prove that $(2,0,0)$ is the optimal answer for the problem? Or am i wrong?

$\endgroup$
3
  • $\begingroup$ Note that you should check that $x=(2,0,0)$ is primal feasible. $y$ must also satisfy the dual constraints. If you can find any vector $y$ with $7y_{1}-3y_{2}=0$ that also satisfies the other dual constraints then you will have shown that $x=(2,0,0)$ is optimal. There's no reason to expect the optimal dual solution $y$ to be unique. $\endgroup$ Jan 1, 2022 at 0:56
  • 1
    $\begingroup$ Setting $t_1=0$ yields $7y_1+2y_2=2$. $\endgroup$
    – RobPratt
    Jan 1, 2022 at 3:30
  • $\begingroup$ Thanks i edited the question $\endgroup$ Jan 1, 2022 at 5:18

1 Answer 1

2
$\begingroup$

You are right so far. Here you have the case with a multiple optimal solution:

$$(y_1^*,y_2^*)=\left(y_1,1-\frac72y_1\right)$$

with the constraint $1-\frac72y_1\leq 0$. It comes out that $y_1\geq \frac27$.

So one possible optimal solution is $(y_1^*,y_2^*)=\left(\frac47,-1\right)$

Remark

Your dual is almost right. If the variables of a min primal problem are non-negative, then the corresponding constraints are $\leq$-constraints. So the $t_j$'s are added and not subtracted.

Maximize $14y_1+4y_2$
$7y_1+2y_2+t_1=2$
$6y_1+4y_2+t_2=5$
$3y_1+5y_2+t_3=7$
Where: $y_1,t_1,t_2,t_3 \ge 0,y_2 \le 0$

$\endgroup$
2
  • $\begingroup$ Thank you for your answer It's right $\endgroup$ Jan 2, 2022 at 9:16
  • $\begingroup$ @You´re welcome. $\endgroup$ Jan 2, 2022 at 12:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .