R

MA205-Chapter4(4-4)

4.4 Complementary Slackness

Theorem (Complementary Slackness Theorem)

  • Definition: Necessary and sufficient conditions for simultaneous optimality of a primal feasible solution (x1,...,x*) and a dual feasible solution (y1,...,ym) involve:

    • m ( \sum a_{ij} y_j = c_i ) for all ( j = 1,...,n )

    • or ( x_j = 0 ) (or both)

    • n ( \sum a_{ij} x_i = b_j ) for all ( i = 1,...,m )

    • or ( y_i = 0 ) (or both)

  • Proof Requirements:

    • Feasibility of (y1,...,ym) implies ( \sum C_j x \leq \sum a_{ij} y_i )

    • Feasibility of (x1,...,xm) gives ( \sum a_{ij} x_i \leq b_i )

Consequence of the Duality Theorem

  • Equations (5) and (6) must hold as equalities.

    • This leads to conditions for both primal and dual optimality. Where:

      • ( C_j x - \sum a_{ij} y_i = 0 )

      • or ( \sum a_{ij} y_i = c_j ) or ( x_j = 0 ) (or both)

      • ( \sum a_{ij} x_i = b_i ) or ( y_i = 0 ) (or both)

Complementary Slackness in Practice

Conditions for Optimality

  • Theorem: A feasible solution ( (x_1,...,x_*) ) is optimal iff:

    • There exists ( (y_1,...,y_m) ) such that:

      • ( \sum a_{ij} y_i = c_j ) whenever ( x_j > 0 )

      • ( y_i = 0 ) whenever ( \sum a_{ij} x_j < b_i )

  • Completing the Method:

    1. Check feasibility of (x1,...,xn) for the primal.

    2. Set up an equation system for (y1,...,Ym) based on the conditions above.

    3. Check for dual feasibility: if feasible, (x1,...,xn) is optimal; otherwise, it is not.

    4. If the solution for (y1,...,Ym) is not unique, further exploration is needed.

Example: Applying Complementary Slackness

Problem Formulation

  • Given LP:

    • Maximize: 18x1 - 7x2 + 12x3 + 5x4 + 8x5

    • Subject to:

      • Constraints define the feasible region.

Step 1: Feasibility Check

  • Verify all constraints are satisfied with the candidate solution ( (x_1,...,x_6) = (2,4,0,0,7,0) ).

  • Ensure all variables ( x_i > 0 ) for those not equal to zero.

Step 2: Establish the Equation System

  • Define dual constraints that relate to primal variables being positive. This would yield:

    • Dual equations based on candidate variables.

Step 3: Dual Feasibility Check

  • Verify that the derived dual solution fulfills constraints:

    • Establish and verify conditions for each dual constraint against the respective relationships in the primal.

Conclusion

  • If every condition holds, confirm optimality of both solutions.

Additional Example

LP Definition & Feasibility Check

  • LP to maximize: 8x1 + 9x2 + 12x3 + 4x4 + 11x5

  • Conduct feasibility check on given candidate: ( (x_1,...,x_5) = (0,2,0,7,0) ).

Steps for Solver

  1. Confirm the candidate's feasibility against constraints.

  2. Set up the dual equations similarly as above.

  3. Check both candidates, looking for viability within constraints and conditions established.

Consequence of Solution Checks

  • Analyzing if optimal solutions exist for both primal and dual, identifying respective statuses and potential gaps.

Summary: Duality

  • Existence: Dual problems always exist; dual of a dual yields the primal.

  • Weak Duality: For feasible solutions, primal yields results that are bounded by dual results.

  • Optimal Solutions: If feasible solutions exist with stated optimalities, then both primal and dual solutions are optimal.

  • Duality Theorem: Offers conditions under which the established relationships affirm the optimality of variable regimes.

  • Importance of Complementary Slackness: A tool to check primal optimality and infer dual solutions.