Complementary slackness

If the primal is feasible and the cost is bounded, then the dual is feasible and its cost is
also bounded. Moreover, their optimum values coincide. If the solution of primal and dual are equal, then they are optimum of their linear program. The theorem is as follows:

decision11

 

Process

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).

The complementary slackness is a method which, using both primal and dual program, provides useful guess to determine variables. The complementary slackness process is as follows:

  1. Begin with a guess for Primal
  2. Check feasibility. If not, Stop. It cannot be a solution.
  3. If so, note positive variables (implies binding dual constraints) and constraints with slack (implies zero dual values).
  4. Use non-zero dual variables to solve the equations in dual (typically equal number of equations and unknows).
  5. Check feasibility of this solution (are variables nonnegatives? are the dual constraints corresponding to zero primal variables satisfied?). If yes, then you have solutions to both Primal and Dual. If not, original guess is not a solution.

Example 1

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.

decision6

The dual model associated with the primal model is:

decision7

Then the Complementary Slackness Theorem shows us the following relationships:

decision8

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).

Example 2

Let’s take the following problem

decision9

The solution to this problem is {42, 0, 10.4, 0, 0.4}. The dual problem is as follows:

decision10

Step1: feasibility. First constraint is binding, no conclusion for y1. Second constraint is not binding, so y2=0. Third constraint is binding, nothing about y3.

Step2: positive variables. x1=0, nothing to do. x2>0, the second dual constraint binds. x3=0, nothing to do. x4>0, fourth dual constraint binds.

So solution to dual must satisfy: y2=0; y1 + y3=4; 4y1 + y3=1 with {1, 0, 3} as solution (no invalid constraint and equals optimal value).

Publicités