Mixed & Unrestricted Constraints: Duality
First we will take an example of Mixed Constraints and after that we will take one example of Unrestricted Constraints in duality.
Mixed Constraints: Duality
Example: Linear Programming
Maximize z = x1 + 5x2
subject to
3x1 + 4x2 ≤
6
x1 + 3x2 ≥ 2
x1, x2 ≥ 0
Solution.
The above problem can be written as
Maximize z = x1 + 5x2
3x1 + 4x2 ≤ 6
-x1 - 3x2 ≤ -2
Now, the dual model of the problem can be formulated as follows:
Minimize z = 6w1 - 2w2
subject to
3w1 - w2 ≥
1
4w1 - 3w2 ≥ 5
w1, w2 ≥ 0
Unrestricted Constraints: Dualilty Concepts
Example
Maximize z = 2x1 + 3x2 + x3
subject to
4x1+ 3x2 + x3 = 6
x1 + 2x2 + 5x3 = 4
x1, x2, x3 ≥ 0
Solution.
Converting equalities to inequalities
Any linear equality can be written as a set of like-directioned linear inequalities by imposing one additional constraint. The equation may be replaced by two weak inequalities. For instance, x = 10 can be written as x ≤ 10 and x ≥ 10, which in turn can be written as x ≤ 10 and -x ≤ -10.
So the constraints can be written as
4x1 + 3x2 + x3 ≥
6
4x1 + 3x2 + x3 ≤
6
x1 + 2x2 + 5x3 ≥
4
x1 + 2x2 + 5x3 ≤
4
Further, the above constraints can be written as
-4x1- 3x2 - x3 ≤
-6
4x1 + 3x2 + x3 ≤
6
-x1 -2x2 - 5x3 ≤
-4
x1 + 2x2 + 5x3 ≤
4
Now, the dual model of the problem can be formulated as follows:
Minimize z = -6w1 + 6w2 - 4w3 + 4w4
-4w1+ 4w2 - w3 + w4 ≥
2
-3w1 + 3w2 - 2w3 + 2w4 ≥
3
-w1+ w2 - 5w3 + 5w4 ≥
1
w1, w2, w3, w4 ≥ 0.
Simplifying the problem
Let y1 = w2 - w1 , y2 = w4 - w3
Minimize z = 6y1 + 4y2
subject to
4y1 + y2 ≥ 2
3y1 + 2y2 ≥ 3
y1 + 5y2 ≥ 1
y1, y2 are unrestricted.
The above problem can be directly solved by using the following rules:
| Primal | Dual |
|---|---|
| ith relation an equality | ith variable unrestricted in sign |
| jth variable unrestricted in sign | jth relation an equality |
Minimize z = 6w1 + 4w2
subject to
4w1 + w2 ≥ 2
3w1 + 2w2 ≥ 3
w1 + 5w2 ≥ 1
w1, w2 are unrestricted.
