Question

Consider the following linear programming problem.

min −x1 + 4x2

subject to:

• x1 + x2 ≥ 1

• 3x1 + x2 ≤ .5

• x1, x2 ≥ 0

Formulate the dual of this problem.

Answer 1

In Linear programming problems the initial problem is known as Primal and the transpose problem obtained by transposing row with columns but having the same optimal solution is known as dual.

The Primal problem given is,

subject to:

Before finding the dual of this problem we have to check the sign of the constraints

Since this is a minimisation problem , all the constraints should be

But we find that the second constraint is having sign.

To change the sign we multiply the constraint by - sign on both sides

Then the constraint becomes,

Now all constraints have same sign.

The total number of variable in the primal is 2(x1 and x2), which will be the total number of constraints in its dual.

The total number of constraints in the primal is 2, so there will be two variables in its dual( y1 and y2)

So our dual will be formulated by changing minimisation to maximisation and by transposing rows and columns and changing the sign of the constraints of primal to get the dual.

Dual will be,

subject to: