Duality 2 - Dual of Maximization LPP and Minimization LPP
VISIT My CHANNEL and SUBSCRIBE, there are so many PLAYLISTS on so many topics/chapters... Concept... Method... Calculations...
#operationsresearch #OR #dual #duality #simplexmethod #linearprogramming #LPP
Duality in Linear Programming
Every LPP called the primal is associated with another LPP called dual. Either of the problems is primal with the other one as dual. The optimal solution of either problem reveals the information about the optimal solution of the other.
Let the primal problem be
Max Zx = c1x1 + c2x2 + … +cnxn
Subject to restrictions
a11x1 + a12x2 + … + a1nxn ≤ b1
a21x1 + a22x2 + … + a2nxn ≤ b2
. . .
am1x1 + am2x2 + … + amnxn ≤ bn
and x1 ≥ 0, x2 ≥ 0,…, xn ≥ 0
The corresponding dual is defined as
Min Zy = b1y1 + b2y2 + … + bmym
Subject to restrictions
a11y1 + a21y2 + … + am1ym ≥ c1
a12y1 + a22y2 + … + am2ym ≥ c2
. . .
a1ny1 + a2ny2 + ……….+amnym ≥ cn
and y1, y2, …, ym ≥ 0
Important characteristics of Duality
1) Dual of dual is primal.
2) If either the primal or dual problem has a solution then the other also has a solution and their optimum values are equal.
3) If any of the two problems has an infeasible solution, then the value of the objective function of the other is unbounded.
4) The value of the objective function for any feasible solution of the primal is less than the value of the objective function for any feasible solution of the dual.
5) If either the primal or dual has an unbounded solution, then the solution to the other problem is infeasible.
6) If the primal has a feasible solution, but the dual does not have then the primal will not have a finite optimum solution and vice versa.
Steps for a Standard Primal Form
Step 1 – Change the objective function to Maximization form
Step 2 – If the constraints have an inequality sign ‘≥’ then multiply both sides by -1 and convert the inequality sign to ‘≤’.
Step 3 – If the constraint has an ‘=’ sign then replace it by two constraints involving the inequalities going in opposite directions. For example x1+ 2x2 = 4 is written as x1+2x2 ≤ 4 x1+2x2 ≥ 4 (using step2) → - x1-2x2 ≤ - 4
Step 4 – Every unrestricted variable is replaced by the difference of two non-negative variables.
Step5 – We get the standard primal form of the given LPP in which. 2o All constraints have ‘≤’ sign, where the objective function is of maximization form. o All constraints have ‘≥’ sign, where the objective function is of minimization from.
Rules for Converting any Primal into its Dual
1) Transpose the rows and columns of the constraint co-efficient.
2) Transpose the co-efficient (c1,c2,…cn) of the objective function and the right side constants (b1,b2,…bn)
3) Change the inequalities from ‘≤’ to ‘≥’ sign.
4) Minimize the objective function instead of maximizing it.
www.prashantpuaar.com
Watch video Duality 2 - Dual of Maximization LPP and Minimization LPP online, duration hours minute second in high quality that is uploaded to the channel PUAAR Academy 29 May 2016. Share the link to the video on social media so that your subscribers and friends will also watch this video. This video clip has been viewed 188,456 times and liked it 1.6 thousand visitors.
