Complementary Slackness Theorem (Duality Theory in Linear Programming)

One of the major theorems in the theory of duality in Linear Programming is the Complementary Slackness Theorem. This theorem allows us to find the optimal solution of the dual problem when we know the optimal solution of the primal problem (and vice versa) by solving a system of equations formed by the decision variables (primal and dual) and constraints (primal and dual model).

The importance of this theorem is that it facilitates the resolution of the models of linear optimization, allowing you to find the simplest model to address (from the algorithmic point of view) because either way you will get the results of the associated equivalence model (may it be a primal or dual model).

Let us consider the following Linear Programming model (here in after primal) in 2 variables whose optimal solution is X=14/5 and Y=8/5 with optimal value V(P)=20.8.

primal-model

The dual model associated with the primal model is:

dual-model

Then the Complementary Slackness Theorem shows us the following relationships:

complementary-slackness-the

As we know X=14/5 and Y=8/5 (primal optimal solution). If we replace these values of X and Y in the third and fourth equation we generate a 2×2 system of equations in terms of A and B whose solution corresponds to A=6/5 and B=2/5 (a feasible and optimal solution of the dual model). If we subsequently evaluate the objective function in the dual problem of this solution we obtain: V(D)=12(6/5)+16(2/5)=20.8 which is similar to the primal problem’s optimum value (satisfy the Strong Duality Theorem).

Notes: Note that the 1 and 2 constraints of the primal problem are active at the optimum, i.e. equality is met.

Rating: 3.0/5. From 18 votes.
Please wait...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.