|
|
||||||||||
Duality & Sensitivity Testing |
||||||||||
Mixed Constraints
|
||||||||||
 |
The direction of a constraint can be reversed by multiplying both sides of that constraint with minus one (-1). |
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
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.
