Additional deviations

Additional deviations

The complementary deviations are usable if the primal is realizable and the solution is bounded, the dual is realizable and its solution is also bounded. If the values of the primal and dual solutions are equal, they are optimal for their linear program, we speak of strong duality. Sometimes it is not possible to find a solution, or not useful to calculate it. The primal and dual program being linked, it is possible to deduce a solution of the reciprocal program using the complementary deviations.

Process

One of the main theorems of the theory of duality in linear programming is the theorem of complementary deviations. 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 the constraints (primal and dual model).

The importance of this theorem is that it makes it easier to solve linear optimization models, allowing you to find the easiest model to deal with (from the point of view algorithmic). The process is as follows:

1. Find a workable solution on the primal.
2. If this is the case, note the non-zero variables (this implies that the constraint of the dual is saturated) and the constraints with play (which implies that the variable of the dual is zero).
3. Solve the system of equations
4. Check the strong duality, ie the solution of the primal is identical to that of the dual. In this case the feasible solution is an optimum.

Version I. Let x * and y * be the solutions of the primal and the dual. These two solutions are optimal if and only if:

• for any j from 1 to n
  • either the constraint j of the dual is saturated
  • or x *_j=0
  • or both
• for all i from 1 to m
  • either the constraint i of the primal is saturated
  • or y *_i=0
  • or both

The second version of the complementary deviations makes it possible to better understand how to find a solution in the reciprocal program. For this it must be assumed that the two conditions of version I are always true.

Version II. A solution x of the primal is optimal if and only if there exists a vector y * such that:

• y * is eligible
• if x_j> 0 then the j-th constraint of the dual is saturated
• if the i-th constraint of the primal is not saturated then y *_i=0.
• and conversely between the dual and the primal.

Thus, once a solution is found in the reciprocal program, all that remains is to verify the strong duality of the system.

Example 1

Consider the following linear programming model with 2 variables whose optimal solution is X = 14/5 and Y = 8/5 with the optimal value V = 20.8.

The dual model associated with the primal model is:

Then, the theorem of complementary deviations shows the following relations:

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 equations (because both constraints of the primal are saturated and we cannot conclude anything about equations 1 and 2), we generate a system of equations in terms of A and of B whose solution corresponds to A = 6/5 and B = 2/5. If we then evaluate the objective function in the dual problem of this solution, we get: V = 12 (6/5) +16 (2/5) = 20.8, which is similar to the optimal value of the primal problem ( strong duality).

Example 2

Consider the following problem:

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

Feasibility test. The first constraint is saturated, no conclusion for y1. The second constraint is not saturated, so y2 = 0. The third constraint is saturated, nothing on y3.

Positive variables. x1 = 0, nothing to conclude. x2> 0, the second constraint of the dual is saturated. x3 = 0, nothing to conclude. x4> 0, the fourth constraint of the dual is saturated.

So, the solution to dual must satisfy: y2 = 0; y1 + y3 = 4; 4y1 + y3 = 1 with {1, 0, 3} as the solution. The values of the primal and dual are equivalent so we have the optimum.