Complementary slackness and farkas lemmaa

to test the optimality of dual solutions: complementary slackness theorem
to test the feasibility : farkas' lemma

1. Complementary slackness & Farkas ’ lemma SHAMEER P H DEPT OF FUTURES STUDIES

2. STRONG DUALITY THEOREM If Z LP or W LP is finite, then both P and D have finite optimal value and Z LP = W LP COROLLARY: There are only four possibilities for a dual pair of problems P and D Z LP or W LP are finite and equal Z LP = ∞ and D is infeasible W LP = -∞ and P is infeasible both P and D are infeasible DEPT OF FUTURES STUDIES

3. Complementary Slackness PRIMAL: u = max{cx : Ax ≤ b, x≥ } DUAL: w = min{ by : Ay ≥ c, y ≥ } let ‘ s ’ be the vector of slack variables of the primal& ‘ t ’ is the vector of surplus variables of dual s = b-Ax≥0 and t= yA-c≥ DEPT OF FUTURES STUDIES

4. Principle If x * is an optimal solution of Primal (P) and y * is an optimal solution of Dual (D), then x j * t j * =0 for all j & y i * s i * =0 for all i ( The theorem identifies a relationship between variables in one problem and associated constraints in the other problem .) DEPT OF FUTURES STUDIES

5. proof Using the definitions of s and t cx* = (y*A-t*)x* = y* Ax *- t*x* = y*(b-s*)-t*x* (since Ax *+s=b) = y*b-y*s*-t*x* but by strong duality theorem, cx*=y*b ie ; cx* = cx*-(y*s*+t*x*) 0= y*s*+t*x* y*s*=0 and t*x*=0 ( Since, y*,x*,s*, t*≥ ) DEPT OF FUTURES STUDIES

6. In other words Given a dual pair of LPPs have optimal solutions , then if the k th constraint of one system holds inequality ( i.e , associated slack or surplus variable is positive) then the k th component of the optimal solution of its dual is zero OR If a variable is positive, then its dual constraint is tight . If a constraint is loose, then its dual variable is zero. DEPT OF FUTURES STUDIES

7. example PRIMAL: max z=6x 1 +5x 2 such that: x 1 +x 2 ≤5 3x 1 +2x 2 ≤12 x 1, x 2 ≥0 OR x 1 +x 2 +S 1 =5 3x 1 +2x 2 +S 2 =12 x 1 ,x 2 ,s 1 ,s 2 ≥0 Solution: x 1 =2, x 2 =3, z=27 S 1 =0, s 2 =0 DUAL: Min. W=5y 1 +12y 2 Such that y 1 +3y 2 ≥6 y 1 +2y 2 ≥5 y 1 ,y 2 ≥0 OR y 1 +3y 2 -t 1 =6 y 1 +2y 2 -t 2 =5 y 1 ,y 2, t 1, t 2 ≥0 Solution: y 1 =3, y 2 =1, w=27 t 1 =0, t 2 =0 DEPT OF FUTURES STUDIES

8. applications Used in finding an optimal primal solution from the given optimal dual solution and vice versa Used in finding a feasible solution is optimal for the primal problem DEPT OF FUTURES STUDIES

9. FARKAS’ LEMMA Proposed by Farkas in 1902. Used to check whether a system of linear inequalities is feasible or not Let A be an m × n matrix, b ∈ R n + . Then exact one of the below is true : There exists an x ∈ R n + such that Ax ≤ b ; or There exists a y ∈ R m + such that y ≥ 0 , y A = 0 and yb < 0 . OR Ax ≤ b, x ≥ 0 is infeasible iff yA ≥ 0, y b < 0 is feasible DEPT OF FUTURES STUDIES

10. Proof: Consider the LPP, Z LP =max{0x:Ax≤b, xԐR n + } and its dual W LP =min{yb:yA≥0,y Ԑ R m + } . A s y=0 is a feasible solution to the dual problem, the only possibilities to occur are i & iii of corollary of strong dual theorem . Z LP = W LP =0. hence { xԐR n + : Ax ≤ b}≠ф and Yb ≥0 for all yԐR m + with yA ≥ W LP = - ∞. hence { xԐR n + : Ax ≤ b}=ф and there exists yԐR m + with yA ≥ 0 and yb˂0. DEPT OF FUTURES STUDIES

11. Variants of Farkas ’ Lemma There are many variants of Farkas ’ Lemma. Some are: Either { xԐR n + : Ax =b }≠ ф, or { yԐR m : yA ≥0 , yb˂ 0} ≠ ф Either { xԐR n : Ax ≤b }≠ф, or { yԐR m + : yA =0 , yb˂0} ≠ф DEPT OF FUTURES STUDIES

12. THANK YOU…. DEPT OF FUTURES STUDIES