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
cz
x1x2x3 x4
x5 x6 x7
 b
x5
x6
x7
1 0 2 1
-2 1 0 -1
6 2 -30
1 0 0
0 10
0 0 1
20
15
54
C
-30 -6 5 -18
000
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		] [ 0
27
0
20		] = [ 20
7
54		] < [20
15
54		]
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 = 6
y1 - 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.