Jagannath International Management School
From the practical and the theoretical point of view, the concept of duality is one of the most imperative topics of linear programming. The trivial idea behind the duality theory is that every linear program has an associated linear program called its dual such that a solution to one gives a solution to the other. There are a number of important relationships between the solution to the original problem (primal) and it’s dual. These are useful in investigating the general properties of the optimal solution to a linear program and in testing whether a feasible solution is optimal.
The significance of duality is twofold. Firstly, complete understanding of the shadow-value translation of the ideal simplex multipliers can beextremely helpful in understanding the ramifications of a specific direct programming problem. Second, it isn’t unexpected imaginable to address the connected direct program with the shadow costs as the factors instead of, or related to, the first direct program, accordingly exploiting of some computational efficiencies.
Formation of the dual problem:
Consider the Linear Programing Problem which is maximized in nature,
(PRIMAL)
Max Zy = d1y1 +d2y2 +……..+dnyn
s.t.
a11y1 +a12y2 +……..+a1nyn b1
a21y1 +a22y2 +……..+a2nyn b2
.
.
am1y1 +am2y2 +……..+amnynbm
and y1, y2, y3,…….yn0 and d1, d2,……dn, b1, b2,….., bm are constants.
Then its dual is
(DUAL)
Min Zw = b1w1 +b2w2 +……..+bmwm
s.t.
a11w1 +a21w2 +……..+am1 wmd1
a12w1 +a22w2 +……..+am2 wmd2
.
.
a1nw1 +a2nw2 +……..+amnwmdn
and w1, w2, w3,…….wm0
Some important Results and theorem
1.If we take the dual of the dual then it is primal.
2. If a particular constraint in the primal is perfect equality then the corresponding dual variable is unrestricted.
3. If any variable is unrestricted in sign in a primal then the corresponding constraint of the duality is a perfect equality.
Example 1
Primal
Max Z = x + y
s.t. x-y 20
2x +3y 4
5x – 2y 2
x, y 0
Solution
Max Z = x + y
s.t. x-y 20 …………w1
2x +3y 4 ……………w2
5x – 2y 2 ………….w3
Dual
Min Zw =20w1 + 4w2 + 2w3
S.t w1 +2w2 +5w3 1
-w1 + 3w2 -2w31
w1, w2, w30
Example 2
Primal is
Min Z = x1 +x2 +x3
s.t. 2x1 +3x2 +5x32
3x1 +x2 +7x3 =3
x1 +4x2 +6x3 5
x1, x2, x30
Dual is
Max Zw = 2x1 +3x2 +5x3
s.t. 2w1 +3w2 +w31
3w1 +w2 +4w31
5w1 +7w2 +6w3 1
w1, w30, w2 is unrestricted
Rules for the Solutions
When we obtain solution for one form of the LPP then depending on the nature of the solution for one we can conclude for the nature of the solution of the other as following:
1. If we obtain bounded optimal solution of Primal then the dual has bounded optimal solution.
2. If we obtain an unbounded solution of primal (dual) then the dual (primal) has no feasible solution.
3. If we obtain no feasible solution of Primal (dual) then the dual (primal) has either unbounded or no feasible solution.
Some useful properties
Even though we have studied how a dual of a primal can be evaluated, it becomes essential to understand the consequence of the same based on the type of solution we obtain.
1. Any feasible solution to the dual problem sets a bound on the optimal objective function value in the primal problem.
2. Understanding the dual problem leads to specialized method for some important classes of linear programming problems. Examples include the transportation simplex method, the Hungarian algorithm for the assignment problem, and the network simplex method.
3. The dual can be helpful for sensitivity analysis. Changing the primal’s right-hand side constraint or adding a new constraint to it can make the original primal optimal solution infeasible.
4. The variables we get in a dual LPP gives the shadow prices for the primal LPP’s constraints. For instance, suppose you have a profit maximization problem with a resource constraint say ‘j’. Then the valueyj of the corresponding dual variable in the optimal solution tells you that you get an increase of yj in the maximum profit for each unit increase in the amount of resource j.
5. Sometimes it is easier to solve the dual of a LPP. A primal problem that has many constraints and few variables can be converted into a dual problem with few constraints and many variables.
For more information visit: https://www.jagannath.org/
