Prove a feasible point is optimal for an LP using complementary slackness

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?

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

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

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