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

exampleExample: 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

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: Dualilty Concepts

exampleExample

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.

Share this article with your friends