Question

) Find the dual program of the following linear programming problem.

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑃 = 16𝑥 − 2𝑦 − 5𝑧

𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜

𝑥 + 4𝑦 − 𝑧 ≥ 120

𝑥 + 𝑦 + 3𝑧 ≤ 130

𝑥 ≥ 0, 𝑦 ≥ 0, 𝑧 𝑖𝑠 𝑢𝑛𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑒𝑑.

Answer 1

All constraints can be converted to $\geq$  by multiplying by -1. So we have;

$\text{Min} ~~p=16x-2y-5z\\ \text{subject to}\\ ~~~~~x+4y-z\geq120\\ ~-x-~~y+3z\geq-130\\ \text{and } x,y\geq 0; z \text{is unrestricted}.$

Since the primal has three variables and two constraints, then the dual will have two variables and three constraints. Also, the $z$ variable is unrestricted in the primal, therefore the third constraint in the dual shall be equality.

Dual program is;

$\text{Max } ~~p=1220a-130b\\ \text{subject to }\\ ~~~~~-a-b~~~\leq16\\ ~~~~~~~4a-b~~~\leq-2\\ ~~~~~-a-3b~=-5\\ \text{and } a,b\geq0.$