Question

Q4. Convert the following linear programming problem into dual

problem.

Maximise

Z = 22x1 + 25x2 +19x3

Subject to:

18x1 + 26x2 + 22x3 ≤ 350

14x1 + 18x2 + 20x3 ≥180

17x1 + 19x2 + 18x3 = 205

x1, x2, x3 ≥ 0

Answer 1

The primal linear programming problem is

$\text{Maximise~} Z = 22 x_{1} + 25 x_{2} + 19 x_{3}\\ \text{subject to}\\ \begin{aligned} &18 x_{1}+26 x_{2}+22 x_{3} \leq 350 \\ &14 x_{1}+18 x_{2}+20 x_{3} \geq 180 \\ &17 x_{1}+19 x_{2}+18 x_{3}=205 \\ &\text { and } x_{1}, x_{2}, x_{3} \geq 0 \end{aligned}$

Since the second constraint is of $``\ge"$ type, we convert it into $``\le"$ by multiplying it by -1.

$\text{Maximise~} Z = 22 x_{1}+25 x_{2}+19 x_{3}\\ \text { subject to } \\ \begin{aligned} 18 x_{1}+26 x_{2}+22 x_{3} &\leq 350\\ -14 x_{1}-18 x_{2}-20 x_{3} &\leq-180 \\ 17 x_{1}+19 x_{2}+18 x_{3} &=205\\ \end{aligned}\\ \text{and~} x_{1}, x_{2}, x_{3} \geq 0$

The dual of the given linear programming problem is

$\text{Minimise } Z^*= 350 y_{1}-180 y_{2}+205 y_{3}\\ \text{subject to}\\ \begin{aligned} 18 y_{1}-14 y_{2}+17 y_{3} &\geq 22 \\ 26 y_{1}-18 y_{2}+19 y_{3} &\geq 25 \\ 22 y_{1}-20 y_{2}+18 y_{3} &\geq 19 \\ \text { and } y_{1}, y_{2} &\geq 0, y_{3} \text { unrestricted in sign } \end{aligned}$

Since the third constraint in the primal is equality, the corresponding dual variable $y_{3}$ will be unrestricted in sign.