Question

Find the dual program of the following linear programming problem.

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑧 = 5𝑥1 − 2𝑥2

𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜

3𝑥1 + 2𝑥2 ≥ 16

𝑥1 − 𝑥2 ≤ 4

𝑥1 ≥ 5

𝑥1 ≥0,𝑥2 𝑖𝑠 𝑢𝑛𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑒𝑑 

Answer 1

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

$\text{Max} ~~z=5x_1-2x_2\\ \text{subject to}\\ ~~~~~-3x_1-2x_2\leq-16\\ ~~~~~~~~~~~x_1-~~x_2\leq4\\ ~~~~~~~-x_1~~~~~~~~~~~\leq-5\\ \text{and } x_1\leq 0; x_2 \text{is unrestricted}.$

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

Dual program is;

$\text{Min } ~~z=-16y_1+4y_2-5y_3\\ \text{subject to }\\ ~~~~~-3y_1+y_2-y_3\geq5\\ ~~~~~-2y_1-y_2~~~~~~~~=-2\\ \text{and } y_1,y_2\geq0.$