Higher Engineering Mathematics

Professor P. N. Agrawal
Department of Mathematics
Indian Institute of Technology Roorkee
Lecture - 50
Duality - I

(Refer Slide Time: 00:41)

Hello friends, welcome to my lecture on The Concept of Duality, one of the most important
and interesting concepts in linear programming is the Duality. Every linear programming
problem has associated with it, another linear programming problem which involves the same
data and is closely related to the optimal solutions, such two problems are said to be duals of
each other.

While one of these problems is called the primal problem, the other one is called the dual
problem. The importance of the duality concept is due to the two main reasons. Firstly, if the
primal contains a large number of constraints and a smaller number of variables then the
labour of computation can be considerably reduced by converting it into the dual problem and
then solving it, because if there are say m constraints and n variables and m is greater than n
then when we will consider the corresponding dual problem there the number of constraints
will become n and number of variables will become m, ok.

So, number of constraints will reduce when we consider the dual problem and therefore it
will be easier to solve the get the solution of the dual problem. So labour of computation can
be reduced by converting the problem into the corresponding dual problem and then solving
it. Secondly, the interpretation of the dual variables from the cost or economic point of view
proves extremely useful in making future decisions in the activities being programmed.

(Refer Slide Time: 02:05)

Now, let us consider the following L.P.P. maximize Z = c 1 x 1 + c 2 x2 and so on c n x n subject

to these m constraints a11 x 1 + a12 x2 and so on a1n x n≤ b1; a21 x 1+ a22 x2 and so on a2n x n≤ b2
and then the m at constraint am 1 x 1 + am 2 x2 and so on amn x n≤bm , x 1, x2 x nare all non-
negative.

(Refer Slide Time: 02:37)

Now, in order to construct the dual problem we adopt the following guidelines, the
maximization problem in the primal becomes the minimization problem in the dual and vice
versa. ≤ type of constraints in the primal become ≥ type of constraints in the dual and vice
versa.

The coefficients c 1, c 2,… c n in the objective function, the coefficients c 1, c 2, … cn in the

objective function of the primal become b1, b2,…. bm, ok so c 1, c 2,… c n will be replaced by b1
, b2,…. bm, ok these b1, b2, … . bm and x 1, x2 , … . x n will be replaced by new variables y 1, y 2,
… . ym, ok.

So, the dual problem in the dual problem maximization will be replaced by minimization and
we will have minimization of Z¿ where we will have Z¿ = b1 y 1 + b2 y 2 and so on bm y m, ok.

If the primal has n variables and m constants like here we have n variables x 1, x2 , … . x nand m
constraints given by these m an equalities, ok so then the dual will have m variables and n
constraints that is the transpose of the body matrix of the primal problem gives the body
matrix of the dual.

So, here the body matrix is this one, body matrix is a11, a12 and so on a1n , a21, a22,.. a2n and so
on a m 1, am 2 and so on a mn this is body matrix, ok of the primal problem.

In the dual problem this will be replaced with a11, a21 and so on a m 1, a12, a21, am 2, ok and then
lastly a1n , a2n and so on amn, ok so here we have here we have m rows and n columns, so this
is m by n matrix, here we have n rows and we can see we have m there are 1, 2 and so on m
columns and n rows, so n b y m, ok.

So, here the body matrix, it is m by n size, here it is of the size n by m, transpose of the body
matrix of the primal problem, ok. So transpose of the body matrix of the primal problem
gives the body matrix of the dual.

The variables in both the primal and dual are non-negative, ok. So, now the dual problem will
then be you see here, the dual problem will now be Z¿ minimization of Z¿ = b1 y 1 + b2 y 2 and
so on bm y m, subject to the constraints a11 y 1 + a21 y 2 and so on + am 1 y m ≥c 1, ok a12 y 1, a22 y 2
…..+ am 2 y m ≥c 2 and so on a1n y1+ a2n y 2 and so on a mn y m ≥ c n, ok.

(Refer Slide Time: 06:15)

So, we will have these equations a 1 Z minimization of Z = b1 y 1, b2 y 2, bm y m subject to the
constants a11 y 1 + a21 y 2,….+ amn y m ≥yeah ≤will be replaced with ≥ ok in the dual. So, we
will have ≥here, so ≥c 1, ≥c 2 and ≥c n and y 1, y 2, y m are non-negative variables, ok. ≤

(Refer Slide Time: 06:46)

Let us find the dual of the following L.P.P. So, we have Z = 3 x 1 - 2 x2 + 4 x3 subject to 3 x 1 + 5
x2 + 4x3 ≥ 7, since the problem is of minimization you can see here, since the problem is of
minimization all the constraints must be of ≥ type, all the constraints must be ≥ type, ok

so ≥ type.

So here what is happening in this constraint, this is ≤ type, so we have to convert it to ≥ type,
so when you convert it to ≥ type it will become - 7 x 1 + 2 x2 , ok + x 3 ≥ - 10, ok - 7 x 1 + 2 x2 + x 3
≥ - 10, ok.

Now, so let us write the dual problem, so maximization of maximize Z will be replaced by
some W, W = now this is c 1, c 2, c 3 W replaced by with b1, b2,.. bm, so 7 y 1 + 4 y 2 - 10 y 3, ok
and then 3 y 4 , ok and then we will have so this is our objective function in the dual problem
and (corres subs) subject to the constraints, we will have now the (bod) the matrix here is
body this body matrix is 3, 5, 4, ok 6, 1, 3, ok then we have - 7, 2, 1, ok we have 1 - 2, 5 this
is body matrix in the primal problem.

So, in the dual problem we have to take transpose of this, so we will have subject to constants
3 y 1 + 6 y 2 - 7 y 3 + y 4 and ≤ we will have ≤c 1, c 1 is 3, ok then we have 5 y 1 + y 2 + 2 y 3 and we
get - 2 y 4 ≤ - 2, ok and then 4 y 1 + 3 y 2 + y 3 + 5 y 4 ≤ 4, ok so c 1, c 2, c 3, ok and y 1, y 2, y 3 ≥ 0, so
this is our dual problem, we replaced (mak) minimization by maximization, the variable Z
will be replaced by some other variable,

some other variable, so we can write it as W.

Then the c 1, c 2, c 3 are replaced with b1, b2, b 3, b4 , ok so b1 is 7, b2 is 4, b3 is - 10, b 4 is 3, ok

and we use new variables y 1, y 2, y 3, y 4 , so 7 y 1 + 4 y 2 - 10 y 3 + 3 y 4 , the body matrix here is 3,
5, 4, 6, 1, 3 - 7, 2, 1 and then 1 - 2, 5 we take transpose of this and then it becomes transpose
of this becomes 3, 6, - 7, 1, 5, 1, 2, - 2, 4, 3, 1, 5, ok.

So, we get the constraints as 3 y 1 + 6 y 2 - 7 y 3 + y 4 ≤c 1, 5 y 1 + y 2 + 2 y 3 - 2 y 4 ≤ - 2, 4 y 1 + 3 y 2 +

y 3 + 5 y 4 ≤ 4, so this and where y 1, y 2, y 3 are non-negative, so this is the dual problem, ok.
(Refer Slide Time: 12:17)

Now, let us consider the problem where we have to maximize Z = c 1 x 1 + c 2 x2 and what we
have we are have here the change here is that 1 constraint is an equality, ok there is a equality
constraints a11 x 1 + a12 x2 = b1, so how we will (siles) find the dual of this as L.P.P. ok. So,
what we will do is the equality constraint a11 x 1 + a12 x2 = b1 can be written as a11 x 1 + a12 x2
≤b1 and a11 x 1 + a12 x2 ≥b1, so in the problem is of maximization, ok all the constraints should
be of ≤ type, ok.

So, first constraint will be a11 x 1 + a12 x2 ≤b1, the second constraint this one will be converted
into ≤ type and we will write it as - a11 x 1 - a12 x2 ≤ - b1. So, now the problems will this be
replaced by a11 x 1 + a12 x2 ≤b1 , - a11 x 1 - a12 x2 ≤ - b1, ok and a21 x 1, a22 x2 ≤b2, ok.

Now, so when we write the dual problem here we write maximize maximization we replaced
by minimization minimize W = now here we have b1, - b1, b2, ok so we write b1, ok we can

write b1 y 1' , ok b1 c 1, c 2 will be replaced with b1, - b1 and b2, so b1 y 1' - b1 y 1' ' , let us take the

variables y 1' , y 1' ' and then b2 y 2, ok.

So, this and the in the body matrix is now a11, a12, ok - a11, - a12, a21, a22 this is 3 b y 2 matrix,
ok 3 rows and columns, so we take the transpose of this body matrix, so transpose of this will
be giving you a11, - a11, a21 and then a12, - a12 and then a22, ok so subject to constraints a11 y 1'

- a11 y 1' ' + a21 y 2 ≥ we will have because we have ≤ here, so ≥ c 1, ok then a12 y 1' - a we have

here a12 here we have - a12, ha - a12 y 1' ' + a22 y 2 ≥c 2, so where y 1' y 1' ' and y 2 are all ≥0.
Now, let us define y 1 = y 1' - y 1' ' , since y 1' and y 1' ' are greater than both non-negative y 1 is
unrestricted in sign, ok it is not restricted in sign, so y 1 then y 1 is unrestricted in sign and we
will get this problem as minimization of, so this will then change to minimization of W = b1
' '' ' ''
y 1 - y 1 will be replaced by y 1, so b1 y 1 + b2 y 2, ok subject to a11 into y 1 - y 1 .

So, a11 y 1 + a21 y 2 ≥c 1 and then a12 multiplied by y 1' - y 1' ' that is y 1, so a12 y 1 + a22 y 2 ≥c 2
where y 2 ≥0 and y 1 is unrestricted in sign, so y 1 can be negative as well as positive, so this is
the dual of the given problem when the primal has equality constraints we will do this, ok.

(Refer Slide Time: 18:02)

So, this what we have then, this is maximize Z = this, subject to this, ok this constraints x 1, x2

≥ 0 then we use the variables y 1' , y 1' ' , y 2, ok and we get W, W = this, subject to this, ok and
which gives us this problem, ok.
(Refer Slide Time: 18:19)

The term y 1' - y 1' ' appears both in the objective function and all the constraints of the dual.
This will always happen whenever there is an equality constraint in the primal. The new
variable this becomes unrestricted in sign, ok because of the difference of two non-negative
variables, so the above dual problem then takes this form, ok which we have just now seen,
ok.

(Refer Slide Time: 18:46)

Now, let us consider in general if the primal problem is Z = c 1 x 1 + c 2 x2 and so on c n x n

subject to this constraints, this is the = b1, this is the = b2, this is the = bm, ok then it will be
replaced with the it is dual of this will be minimize W, W = b1 y 1+ b2 y 2 and so on bm y m, ok
bm y m subject to the constraints a11, yeah a11 y 1+ a21 y 2 and so on a m 1 y m, ok.

We will have because it is maximization problems, so we will have ≤ here we will have ≥ c 1,
ok then a12 y 1+ a22 y 2 and so on am 2 y m ≥c 2 and so on, we shall have a1n y 1, a2n y 2 and so on
a mn y m≥ c m, ok c n sorry c n where y 1, y 2,.. y m are all unrestricted in sign, so this is the dual,
ok.

(Refer Slide Time: 21:01)

So, the dual will be W = b1 y 1 + b2 y 2 and so on bm y m subject to this constraints, ok where

these are all unrestricted in sign, thus the dual variables corresponding to the equality
constraints are unrestricted in sign. Conversely, when the primal variables are unrestricted in
sign corresponding to dual constraints are equalities, ok so if so when the when we have
equality constraints the dual variables are unrestricted in sign and if the primal variables
unrestricted in sign then the corresponding dual constraints are equalities, ok.
(Refer Slide Time: 21:40)

Now, let us construct the dual of the L.P.P. Z = (mik) 4 x 1 + 9 x2 + 2 x 3 subject to 2 x 1 + 3 x2 + 2

x 3 ≤ 7 and 3x 1 - 2x2 , so there is a 1 equality constraints here, so we have here we can write it
as 3 x 1 - 2 x2 + 4 x3 or ≤5, ok and 3 x 1 - 2 x2 + 4 x 3 ≥ 5, we will have to convert to ≤ because the
problem is of maximization, so - 3 x 1 + 2 x2 - 4 x 3 ≤ - 5, ok.

So, we have the three constraints one is this one, ok 2 x 1 + 3 x2 + 2 x 3 ≤ 7 and other one 3 x 1 - 2
x2 + 4x 3 ≤5 and third one is - 3x 1 + 2x2 - 4x3 ≤ 5, so ≤ - 5, so the dual problem will be

minimization of W = 7 y 1, ok 7 y 1 + 5 y 2' - 5 y 2' ' , ok and then we shall have the body matrix
is what here? 2, 3, 2, ok 3, - 2, 4, ok and then we have - 3, 2, - 4, so this is body matrix, ok we
have to take the corresponding transpose for the body matrix of the dual problems.

So, we get 2, 3, - 3, so 2 y 1 + 3 y 1' - 3 y 1' ' , ok and we will have to put ≥ 4, ok and then we

have 3 y 1 - 2, so this should be written as y 2 and y 2' ' not y sorry, this should be, ok so, ok. So,

3 y 1 - 2 y 2' + 2 y 2' ' ≥ 9 and then we have 2 y 1 + 4 y 2' - 4 y 2' ' ≥ 2, ok or we can write it as where

y 1, y 2' , y 2' ' they are all non-negative, ok.

Now, we can write the this problem also in the form minimize W = 7 y 1 + 5 y 2, we will write
y 2 = y 2' - y 2' ' , ok and then subject to 2 y 1 + 3 y 2 ≥4, 3 y 1 - 2 y 2 ≥ 9 and 2 y 1 + 4 y 2 ≥ 2 where y 2

= y 2' - y 2' ' , ok and so y 2 is unrestricted in sign, ok.

So, the dual problem is minimize W = 7 y 1 + 5 y 2 subject to the constraints 2 y 1 + 3 y 2 ≥ 4, 3 y 1
- 2 y 2 ≥ 9, 2 y 1 + 4 y 2 ≥ 2, y 2 is unrestricted in sign, y 1 ≥ 0. So, this is how we write the dual of
this L.P.P. where 1 constraint is of equality type. So that is all in this lecture, thank you very
much for your attention.