Reading the primal solution from dual simplex tableau

I was following ptrickJMT's video on how to solve a minimization linear programming problem and he did something that I did not understand why it works. He starts with the following minimization problem:

$$ \begin{matrix}\min & C = 3x_1 + 9x_2 \\ s.t: \\ & 2x_1 + x_2 \ge 8 \\ & x_1 + 2x_2 \ge 8 \\ &x_1, x_2 \ge 0 \end{matrix} $$

He proceeds to find the dual form of this example:

$$ \begin{matrix}\max & P = 8y_1 + 8y_2 \\ s.t: \\ & 2y_1 + y_2 \le 3 \\ & y_1 + 2y_2 \le 9 \end{matrix} $$

He proceeds to solve it using the regular simplex algorithm and arrives in the following matrix:

$$ \left[\begin{array}{ccccc|c} 2 & 1 & 1 & 0 & 0 & 3 \\ -3 & 0 & -2 & 1 & 0 & 3 \\ \hline 8 & 0 & 8 & 0 & 1 & 24 \end{array}\right] $$

Up to here, it's fine, I can see that the optimal solution is $C = P = 24$, and that $y_1 = 0$ and $y_2 = 3$. He also claimed that the optimal solution of the primal problem is $x_1 = 8$ and $x_2 = 0$, he did so by reading coefficients of the slack variables as seen below. I did not understand why this is true, can anyone clarify this to me?

$$ \left[\begin{array}{ccccc|c} 2 & 1 & 1 & 0 & 0 & 3 \\ -3 & 0 & -2 & 1 & 0 & 3 \\ \hline 8 & 0 & \color{red}{8} & \color{red}{0} & 1 & 24 \end{array}\right] $$

Thank you.

Solution 1:

He probably used the complementary slackness theorem. For this purpose I write the condition constraints with slack variables and therefore equalities.

$$ \begin{matrix}\min & C = 3x_1 + 9x_2 \\ s.t: \\ & 2x_1 + x_2 -s_1= 8 \\ & x_1 + 2x_2 -s_2= 8 \\ &x_1, x_2 \ge 0 \end{matrix}$$

$$\begin{matrix}\max & P = 8y_1 + 8y_2 \\ s.t: \\ & 2y_1 + y_2 +z_1= 3 \\ & y_1 + 2y_2 +z_2= 9 \end{matrix} $$

The complementary slackness theorem states:

$x_j^*\cdot z_j=0 \ \forall \ \ j=1,2, \ldots , n$

$y_i^*\cdot s_i=0 \ \forall \ \ i=1,2, \ldots , m$

$s_i \text{ are the slack variables of the primal problem.}$

$z_j \text{ are the slack variabales of the dual problem.}$

From the dual optimal solution we know that $y_2^*=3$. That means that $3\cdot s_2=0\Rightarrow s_2=0$. That again means the second constraint of the primal is

$$x_1+2x_2=8\quad (1)$$

And last but not least we know that the optimal primal value is equal to the optimal dual value (strong duality theorem). That means that $8\cdot y_1^*+8\cdot 0=y_1^*+8\cdot 3=24$. Therefore the equation for the optimal value of the primal is

$$3x_1 + 9x_2=24 \quad (2)$$

$$x_1 + 3x_2=8\quad (2a)$$

The solution follows straightforward if you subtract $(1)$ from $(2a)$. If you are more familiar with this theorems it is not very time-consuming. In this case more or less two minutes, I guess.