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$ Commented Jan 1, 2022 at 0:56
  • 1
    $\begingroup$ Setting $t_1=0$ yields $7y_1+2y_2=2$. $\endgroup$ Commented Jan 1, 2022 at 3:30
  • $\begingroup$ Thanks i edited the question $\endgroup$ Commented Jan 1, 2022 at 5:18

1 Answer 1

Reset to default
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$ Commented Jan 2, 2022 at 9:16
  • $\begingroup$ @You´re welcome. $\endgroup$ Commented Jan 2, 2022 at 12:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.