How to test if a feasible solution is optimal - Complementary Slackness Theorem - Linear Programming

Question

I have this linear program

$$\begin{cases} \text{max }z=&5x_1+7x_2-3x_3\\ &2x_1+4x_2-2x_3&\le8\\ &-x_1+x_2+2x_3&\le10\\ &x_1+2x_2-x_3&\le6\\ &x_1,\,x_2,\,x_3\ge0 \end{cases}$$

and a feasible solution of his dual $(D)$ is $y = {7/2,2,0}$.

I need to find an optimal basis of $(P)$ and an optimal basis of $(D)$ using the complementary slackness theorem.

I thought about assuming that $y$ is an optimal solution of $(D)$ and find the optimal solution of $(P)$ and after using the corollary of this theorem to prove that $y$ is an optimal solution (then $x$ also). Is that the method to use? Is there a more appropriate methodology to solve this problem?

The dual problem is

$$\begin{cases} \text{min }&8y_1+10y_2+6y_3\\ &2y_1-y_2+y_3&\ge5\\ &4y_1+y_2+2y_3&\ge7\\ &-2y_1+2y_2-y_3&\ge3\\ &y_1,y_2,y_3\ge0 \end{cases}$$

Answer 1

Your formulation of the dual Problem is right-you forgot the negative sign at the third constraint only. As I said, you can eleminate the third constraint (primal problem).In this case the dual problem is: $$ \text{min } 8y_1+10y_2\\ 2y_1-y_2\ge 5\\ 4y_1+y_2\ge 7\\ -2y_1+2y_2\ge -3\\ y_1,y_2\ge0 $$

The solution of this problem is $y^T=(y_1,y_2)=(3.5;2)$ Your solution is right. The solution is $y_3=0$, because the third constraint is not necessary.

The compementary slackness condition is $X^TC^*=b^TY^*$

This gives: $\begin{pmatrix}5 & 7 & -3\end{pmatrix}\cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=\begin{pmatrix} 8 & 10 \end{pmatrix} \cdot \begin{pmatrix} 3.5 \\ 2 \end{pmatrix} \Rightarrow \begin{pmatrix}5 & 7 & -3 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=48$

Additional

The following condition must hold $x_j \cdot z_j=0 \ \ \forall n$

$z_j$ are the slack variables of the dual problem. If you insert the solution for the dual problem, then you will see, that $z_1$ and $z_3$ are zero and $z_2$ is not zero. Thus the equations are (for all n):

$x_1\cdot 0=0 $

$x_2\cdot z_2=0$

$x_3\cdot 0=0$

Thus you know for sure, that $x_2=0$

And secondly this equation must hold: $s_i\cdot y_i=0 \ \ \forall m$

$s_i$ are the slack variables of the primal problem. Thus $s_1$ and $s_2$ are zero and so we have the equations:

$2x_1-2x_3=8$

$-x_1+2x_3=10 $

Remember, that $x_2=0$

This two equations you can solve.