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?
Best Answer
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$