Complementary slackness Theorem

Consider the following linear Linear Programming Problems

Primal:
Maximize z = ctX
subject to A X < = b, X > = 0.

Maximize z = 30 x1 + 6 x2 - 5 x3 + 18 x4
subject to:
 x1 + 2 x3 + x4 < = 20 - 2 x1 +   x2 - x4 < = 15 6 x1 + 2 x2 - 3 x3 < = 54
x1, x2, x3, x4 > = 0

Dual:
Minimize w = btY
subject to At Y > = c, Y > = 0.

Minimize w = 20 y1 + 15 y2+ 54 y3
subject to:
 y1 - 2 y2 + 6 y3 > = 30 y2 + 2 y3 > =   6 2 y1 - 3 y3 > = - 5 y1 -  y2 > = 18
y1, y2, y3 > = 0

The initial and final tableaux of the Primal problem are as follows:

 A b c z
 x1 x2 x3 x4
 x5 x6 x7
b
 x5 x6 x7
 1 0 2 1 -2 1 0 -1 6 2 -3 0
 1 0 0 0 1 0 0 0 1
 20 15 54
C
 -30 -6 5 -18
 0 0 0
0
 A* b* c* z*
 x1 x2 x3 x4
 x5 x6 x7
b*
 x4* x6* x2*
 1 0 2 1 -4 0 7/2 0 3 1 -3/2 0
 1 0 0 1 1 -1/2 0 0 1/2
 20 8 27
C*
 6 0 32 0
 18 0 3
522
Inititial Tableau Final Tableau
Note that the optimal solution to the primal proplem is X* = ( x1* , x2* , x3* , x4*)t = ( 0 , 27 , 0 , 20 )t .
Next we shall explain that given an optimal solution X*, one may obtain a solution to the dual problem.

Step 1

 [ 1    0      2      1-2     1     0     -1 6     2     3      0 ] [ 027020 ] = [ 20754 ] < [ 201554 ]
Let Y* = ( y1* , y2* , y2* )t be a solution to the dual, since 7 < 15, it follows that the slack variable x6* in the second row of the primal tableau is not zero. Thus y2* must be zero.

Step 2
Since x2* = 27 and x4* = 20, we conclude that the inequalities in the second and forth rows of the dual system must be equalities. By replacing y2 with zero in

 { y2 + 2 y3 = 6y1 - y2            = 18
we obtain
y1 = 18 and y3 = 3 .
Step 3
Since the vector Y = ( 18 , 0 , 3 )t is a solution to the dual system (i.e., At Y > = c ), then according to the duality theorem, we conclude that Y* = ( 18 , 0 , 3 )t is an optimal solution to the dual problem.