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 Q5. A work shop contains four persons available for work on the four jobs. Only one person can work on any one job. The following table shows the cost of assigning each person to each job. The objective is to assign person to jobs such that the total assignment cost is a minimum. Jobs 1 2 3 4 A 20 25 22 28 Persons B 15 18 23 17 C 19 17 21 24 D 25 23 24 24

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.