Duality
Duality
The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way:
- Each variable in the primal LP becomes a constraint in the dual LP;
- Each constraint in the primal LP becomes a variable in the dual LP;
- The objective direction is inversed – maximum in the primal becomes minimum in the dual and vice versa.
The weak duality theorem states that the objective value of the dual LP at any feasible solution is always a bound on the objective of the primal LP at any feasible solution (upper or lower bound, depending of whether it is a maximization or minimization problem). In fact, this bounding property holds for the optimal values of the dual and primal LPs.
The strong duality theorem states that, moreover, if the primal has an optimal solution then the dual has an optimal solution too, and the two optima are equal.
PYQs
Duality
1) Consider the following LPP
Maximize \(Z=2x_1+4x_2+4x_3-3x_4\) subject to \(x_1+x_2+x_3=4\), \(x_1+4x_2+x_4=8\) and \(x_1,x_2,x_3,x_4\geq 0\)
Use the dual problem to verify that the basic solution $(x_1,x_2)$ is not optimal.
[2019, 10M]
2) Write down the dual of the following LP problem and hence solve it by graphical method.
Minimize \(Z=6 x_{1}+4 x_{2}\),
subject to constraints:
\(2 x_{1}+x_{2} \geq 1\)
\(3 x_{1}+4 x_{2} \geq 1.5\)
\(x_{1}, x_{2} \geq 0\)
[2011, 20M]
3) Construct the dual of the primal problem.
Maximize \(Z=2 x_{1}+x_{2}+x_{3}\), subject to the constraints:
\(x_{1}+x_{2}+x_{3} \geq 6\)
\(3 x_{1}-2 x_{2}+3 x_{3}=3\)
\(-4 x_{1}+3 x_{2}-6 x_{3}=3\)
\(x_{1}, x_{2}, x_{3} \geq 0\)
[2010, 12M]
4) Find the dual of the following linear programming problem.
Maximize \(Z=2 x_{1}-x_{2}+x_{3}\), subject to:
\(x_{1}+x_{2}-3 x_{3} \leq 8\)
\(4 x_{1}-x_{2}+x_{3} \geq 5\)
\(2 x_{1}+3 x_{2}-x_{3} \geq 5\)
\(x_{1}, x_{2}, x_{3} \geq 0\)
[2008, 12M]
5) Given the programme
Maximize \(u=5x+2y\), subject to:
\(x+3y \leq 12\)
\(3 x-4 y \leq 9\)
\(7x+8y \leq 20\)
\(x, y \geq 0\)
]Write its dual in the standard form.
[2006, 12M]
6) Using duality or otherwise solve the linear programming problem. Minimize \(Z=18 x_{1}+12 x_{2}\), subject to:
\(2 x_{1}-2 x_{2} \geq-3\)
\(3 x_{1}+2 x_{2} \geq 3\)
\(x_{1}, x_{2} \geq 0\)
[2001, 12M]