General strategy
To apply duality, use the SOB table.
In this case, we have
- primal equality constraints transformed to unrestricted dual variables, and
- positive primal variables transformed to $\ge$ constraints in the dual.
- Your mistake is wrong type of dual constraints.
You may want to see MIT's notes section 4.3 for the derivations of such transform.
Theoretical explanation for the mistake
Your attempt:
Transform
$$\max z=\sum_{j} c_jx_j \\ \text{s.t. } \sum_{j} a_{ij}x_j = b_j \quad (i=1,\dots,m) \\ x_j \ge 0 \quad (j=1,\dots,n)$$
into
$$\min v=\sum_{i} b_iy_i \\ \text{s.t. } \sum_{i} a_{ji}y_i = c_i \quad (j=1,\dots,n) \\ y_i \ge 0 \quad (i=1,\dots,m)$$
In fact, if you transform it into the standard form
$$\max z=\sum_{j} c_jx_j \\ \text{s.t. } \sum_{j} a_{ij}x_j \le b_j \quad (i=1,\dots,m)\\ \sum_{j} -a_{ij}x_j \le -b_j \\ x_j \ge 0 \quad (j=1,\dots,n)$$
you'll see the dual is
$$\min v=\sum_{i} b_iy_i^+ +\sum_{i} -b_iy_i^- \\ \text{s.t. } \sum_{i} a_{ji}y_i^+ \sum_{i} -a_{ji}y_i^- \ge c_i \quad (j=1,\dots,n) \\ y_i^+,y_i^- \ge 0 \quad (i=1,\dots,n)$$
Collecting $y_i^+-y_i^-$, we get the expected form.
$$\min v=\sum_{i} b_iy_i \\ \text{s.t. } \sum_{i} a_{ji}y_i \ge c_i \quad (j=1,\dots,n) \\ y_i \text{ unrestricted} \quad (i=1,\dots,n)$$
Additional response to updated question
So, either this version of the theorem is false, or it doesn't hold when all constrains are satisfied with equality in the primal problem, and that is my doubt.
My correction
- This version of the theorem is true.
- It does hold when all constraints are satisfied with equality in the primal problaem, and
- that is not my doubt. (Since this is the Strong Duality Theorem.)
Remarks:
After answering this linear-programming question, I'll change my old complementary slackness habits to solve problem faster using the SOB table.
I find it difficult to understand this in the question body.
by the version of the Complementary Slackness Theorem I am familiar with ... and in this case, ALL constraints are satisfied with equality.
It takes time to guess where the constraints are. (In the primal or dual?) To be concise and precise, I'll describe this as complementary slackness in words (to facilitate oral commumincation when there's no writing tool).
In the optimal feasible solution,
- A nonzero primal decision variable makes its corresponding dual slack/surplus variable zero.
- A nonzero primal slack/surplus variable makes its corresponding dual decision variable zero.
N.B.: The words "primal" and "dual" can be interchanged in the above sentences.
The advantage of using "primal/dual slack/surplus variable" variables over "the inequality constraints is satisfied with equality" is the conciseness and clearity. You won't confuse the given equality constraints with the ones found by complementary slackness.
Verification using your optimal solution
I suggest you to DIY, then check the solution.
Given optimal solution $\mathbf{x}^{\ast} = (7.25, 0 , 3.25 , 0.75)$. Apply complementary slackness. $$\begin{cases}x_1^*:& y_1+y_2+y_3 &= 1\\x_3^*:& -y_1\phantom{+y_2}-y_3 &= -2\\x_4^*:& -2y_1+y_2\phantom{+y_3} &= 2\end{cases}$$ Explanation: nonzero 1st, 3rd & 4th primal decision variables $\implies$ zero 1st, 3rd & 4th dual surplus variables. Solving this linear system gives $\mathbf{y}^*=(-1,-1.5,3.5)$. Check if 2nd dual constraint satisfied: $$-y_1^{\ast} + y_2^{\ast} + 2y_3^{\ast}=1.5 -1 + 2(3.5)=7.5 \ge 1,$$ then check optimality $$2.5y_1^*+8y_2^*+4y_3^*=2.5(-1.5)+8(-1)+4(3.5)=-3.75-8+14=2.25 \\ x_1^* + x_2^* - 2x_3^* + 2x_4^*=7.5+0-2(3.25)+2(0.75)=2.25.$$ So we can conclude the optimality from the weak duality theorem.
First of all the dual program is
\begin{align*}
\texttt{Max} \ 10y_1+8y_2 \\ \ \qquad \ y_1+2y_2\leq 5 \\ 2y_1-y_2\leq 12 \\ y_1+3y_2\leq 4
\end{align*}
Using the complementary slackness theorem:
$x_j^*\cdot z_j^*=0 \ \forall \ \ j=1,2, \ldots , n \quad\color{blue}{I}$
$y_i^*\cdot s_i^*=0 \ \forall \ \ i=1,2, \ldots , m \quad\color{blue}{II}$
$s_i \text{ are the slack variables of the primal problem.}$
$z_j \text{ are the slack variables of the dual problem.}$
We know that that $x_2^*>0$ and $x_3^*>0$. Thus $z_2^*= z_3^*=0$. See $\color{blue}{I}$. That means the constraints $2$ and $3$ are equalities at the dual program.
\begin{align*}
2y_1-y_2= 12 \\ y_1+3y_2= 4
\end{align*}
Solve this little equality system and find $y_1^*$ and $y_2^*$. The values can be insert into the objective function of the dual. This optimal value is equal to the optimal value of the primal problem (Strong duality theorem).
Best Answer
If there are multiple optimal solutions then some of them won't be basic. Instead, they will be strictly convex combinations of optimal solutions that are basic. (For example, an entire facet of a polytope could be optimal. The extreme points of the facet will be basic, but the interior points won't be.) For the nonbasic optimal solutions, complementary slackness will not be guaranteed to hold. (The complementary slackness theorem refers to basic solutions.) Thus the statements are true.
As far as your other question, yes, the complementary slackness conditions hold for the current basic feasible solution at every iteration of the primal - or dual - simplex method. The output of the simplex method will be an optimal basic feasible solution, and complementary slackness will hold for that solution. Again, though, if there are other optimal solutions, complementary slackness will not hold for the ones that aren't also basic.