CHAPTER FOUR
DUALITY THEORY AND FURTHER VARIATIONS OF THE SIMPLEX METHOD
4.1 Dual Linear Programming
The term „dual „in a general sense implies two or more. The concept of duality is very
useful in mathematics, physics, statistics, engineering and managerial decision – making.
For example, in two – person game theory, one competitor‟s problem is the dual of the
opponent‟s problem.
In the context of linear programming, duality implies that each linear programming
problem can be analyzed in different ways but having equivalent solutions.
Formulation of Dual Linear programming problem.
Suppose the prime LP problem is given in the form:
Maximize Z x c1 x1 c2 x2 cn xn
Subject to the constraints:
a11 x1 a12 x2 a1n xn b1
a21 x1 a22 x2 a2n xn b2
a m 1 x1 a m2 x 2 a mn x n bm
and x1 x 2 , , x n 0.
Then the corresponding dual LP problem is defined as:
Minimize Z y b1 y1 b2 y2 bm ym
Subject to the constraints:
a11 y1 a 21 y 2 a m1 y m c1
a12 y1 a 22 y 2 a m 2 y m c 2
a1n y1 a 2 n y 2 a mn y m c n
and y1, y2 , , ym 0.
_____________________________________________________________________ 1
Duality LP problem
4.2 Primal-Dual Simplex Method
The rules for constructing the dual from the primal or primal from the dual when
using the symmetrical form are:
1. If the objective function of the primal is to be maximized, the objective function
of the dual becomes minimization and vice versa.
2. For a maximization prime with all " " type constraints, there exists a
minimization dual problem with all " " type constraints and vice versa. Thus the
inequality sign is reversed in all the constraints except the non-negativity
condition.
3. Each constraint in the primal corresponds to a dual variable in the dual and vice
versa. Thus, given a primal problem with m-constraints and n-variables, there
exists a dual problem with m-variables and n-constraints.
4. The RHS constants b1 b2 , , bm of the primal becomes the coefficients of the
dual variables y1 , y 2 ,, y m in the dual objective function Z y . Also the
coefficients c1 , c2 , , cn the primal variables x1 x 2 , , x n in the objective
function becomes the RHS constants in the dual.
5. The matrix of the coefficients of variables in the constraints of dual is the
transpose of the matrix of coefficients of variables in the constraints of primal and
vice versa. i.e. coefficients of the primal variables x1 , x 2 , , x n in the
coefficients of dual variables in 1st , 2nd , , n th constraints for the dual
problem respectively.
6. If the i th dual variable is unrestricted in sign, the j th primal constraint is equality
( ) type and vice versa.
_____________________________________________________________________ 2
Duality LP problem
The primal – dual relationships may also be remembered conveniently using the
following table
Primal variables
Dual Variables x1 x2 xn Maximize Z x
y1 a11 a12 a1n b1
y2 a 21 a 22 a2n b2
ym a m1 am2 a mn bm
Minimize Z y c1 c2 cn
The primal constraints should be read across the rows and dual constraints should be read
across the columns.
Example: 1 Write the dual of the following LP problem,
Maximize Z x x1 x 2 3x3
Subject to: x1 x 2 x3 10
2 x1 x3 2
2 x1 2 x 2 3x3 6
and x1 , x 2 , x3 0
Solution:
The dual have a minimizing objective function with all constraints “ ” type.
Let y1 , y 2 and y 3 are dual variable corresponding to three primal constraints in the given
order, therefore the dual of the given primal LP is:
Minimize Z y 10 y1 2 y2 6 y3
Subject to: y1 2 y 2 2 y3 1
y1 2 y3 1
y1 y 2 3 y3 3
and y1 , y 2 , y3 0
_____________________________________________________________________ 3
Duality LP problem
Example: 2 Write the dual of the following LP problem,
Minimize Z x 3x1 2 x 2 4 x3
Subject to: 3x1 5 x 2 4 x3 7
6 x1 x 2 3x3 4
7 x1 2 x 2 x3 10
x1 2 x 2 5 x3 3
4 x1 7 x2 2 x3 2
and x1 , x 2 , x3 0
Solution: Since the objective function of the given LP problem is of minimization, the
direction of each inequality has to be changed to “ ” type by multiplying on both sides
by (-1).
The standard LP problem so obtained is:
Minimize Z x 3x1 2 x 2 4 x3
Subject to: 3x1 5 x 2 4 x3 7
6 x1 x 2 3x3 4
7 x1 2 x 2 x3 10
x1 2 x 2 5 x3 3
4 x1 7 x2 2 x3 2
and x1 , x 2 , x3 0
Let y1 , y 2 , y 3 , y 4 and y 5 are dual variable corresponding to the five primal constraints in
the given order.
The dual of this primal LP problem is stated as:
Maximize Z y 7 y1 4 y2 10 y3 3 y4 2 y5
Subject to: 3 y1 6 y 2 7 y3 y 4 4 y5 3
5 y1 y 2 2 y3 2 y 4 7 y5 2
4 y1 3 y 2 y3 5 y 4 2 y5 4
And y1 , y 2 , y3 , y 4 , y5 0
_____________________________________________________________________ 4
Duality LP problem
Using principle of duality solve the following problem:
min
4.3 Duality Theorem
Theorem: 1 The dual of the dual is the primal.
Proof: Consider the primal problem is canonical form
Minimize Z x cx
Subject to: Ax b , x 0 where A is an mxn matrix, b T E m and c , x T E n (1)
Applying the transformation rules, the dual of this problem is:
Maximize Z y b T y
Subject to: AT y c T , y 0 ( 2)
This dual problem can also be written as:
Minimize Z *y (b) T y (3)
Subject to: ( A) T y (c) T , y 0 , where Z *y Z y
If we consider LP problem (3) as primal, then its dual can be constructed by considering
x as the dual variable. Thus, we have:
Maximize Z x* (cT )T x cx
Subject to: ( AT ) T x (b T ) T or ( A) x (b) and x 0 (4)
Theorem: 2 Let x be any feasible solution to the primal LP problem.
Maximize Z x cx
Subject to: Ax b , x 0
and y be any feasible solution to the dual LP problem
Minimize Z y b T y
Subject to: AT y c T , y 0 of the above primal problem. Then prove that
cx b T y , i.e. Z x Z y .
Proof: Since x and y are the feasible solutions to the primal and dual LP problem
respectively. Therefore, from the constraints in primal and dual, we have
Ax b , x 0 (5)
_____________________________________________________________________ 5
Duality LP problem
Ay c T , y 0 (6)
From inequality (6), we have c T AT y or c A( y ) T
Multiplying both sides by x , we get
cx ( Ay T ) x ( y ) T ( Ax ) ( y ) T b b T y (since y T b b T y )
This is completes the proof of the theorem.
Theorem: 3 If x is the feasible solution to the primal LP problem:
Maximize Z x cx
Subject to: Ax b , x 0
and y is the feasible solution to the dual problem:
Minimize Z y b T y
Subject to: AT y c T , y 0 of the above primal problem such that:
cx b T y , then x and y are the optimal solutions to their respective problems.
Proof: Let x 0 be any other feasible solution to the primal. Then from the above theorem
we have cxo bT yo or cxo bT x (since cx b T y ).
Hence x is an optimal solution to the given maximization primal LP problem.
Similarly, for any other feasible solution y o to the dual LP problem we have
cx bT yo or bT y bT yo (since cx b T y )
Hence, y is also an optimal solution to the given minimization dual problem.
4.4 Dual – simplex Algorithm
The simplex method is an algorithm that always deals with a basic feasible solution and
the algorithm is terminated as soon as an optimal solution is achieved. i.e. The procedure
should be stopped when all C j Z j 0 for maximization problem and C j Z j 0
for minimization problem. However , if one or more solution values (i.e X i ) are
negative and optimality condition C j Z j both for max and min is satisfied, then current
potential may not be feasible (because C j Z j = C j C B 1a j is completely
independent of the vector b). In such cases, it is possible to find a starting basic, but
_____________________________________________________________________ 6
Duality LP problem
feasible solution that is dual feasible. i.e all C j Z j 0 for a max – problem . In all
such cases a variant of the simplex method called the dual – simplex method would be
used.
The steps of a dual –simplex algorithm may be summarized as follows:
Step: 1. Determine an initial solution
Convert the given up problem into the standard form by adding slack, surplus and
artificial variables and obtain an initial B.F.S. Display this solution in the initial
dual-simplex table.
Step: 2 Test optimality of the solution
If all solution values are positive (i.e. x i 0 for all i) , then there is no need of
applying a dual-simplex method because improved solution can be obtained by
simplex method itself. Otherwise go to step 3.
Step: 3 Test feasibility of the solution
If there exists a row, say r, for which solution value is negative (i.e. X r 0) and all
elements in row r and column j are positive (i.e. r j 0 for all j), then the current
solution is infeasible, hence go to step 4.
Step: 4 Obtain improved solution
i) Select a basic variable associated with the row (called key row) having the
largest negative solution value.
i.e. X i min X i , X i 0
ii) Determine the minimum ratios only for those columns having a negative
element in row r. Then select a non-basic variable for entering into the basis
associated with the column for which
Ck Z k C j Z j
Min ; Yrj 0 for all j
yrk Yrj
The element (i.e. y rk ) at the intersection of key row and key column is called key
element. The improved solution can be obtained by making y rk is 1 and all other element
of the key column zero. Here, it may be noted that key element is always positive.
_____________________________________________________________________ 7
Duality LP problem
Step: 5 Revise the solution
Repeat step 2 to 4 until either an optimal solution is reached or there exists no feasible
solution.
Examples: Use the dual simplex method to solve the following LP problem:
a). Maximize Z 3x1 2 x2
Subject to: x1 x2 1
x1 x2 7
x1 2 x2 10
x2 3
and x1 , x2 0
b) Maximize Z 2 x1 x2
Subject to: x1 x 2 x3 5
x1 2 x 2 4 x3 8
and x1 , x 2 , x3 0
_____________________________________________________________________ 8
Duality LP problem