[Math] Write the dual LP of the primal LP problem

duality-theoremslinear programming

I have to find the dual of the lp problem given below
Minimise $$z=-x_1+\frac43 x_2$$
subject to∶
$$\begin{array}[t]{l}
2x_1+4x_2\le16\\
-\frac{1}2 x_1-x_2\le4\\
-3x_1+4x_2\ge-24\\
x_1≥0,x_2≤0
\end{array}
$$

Also find the solution to the dual problem without solving it.

Best Answer

By evaluating the objective function at each BFS of the primal, we see that $(x_1^\star,x_2^\star)=\left(\frac85,-\frac{24}5\right)$ is an optimal solution, with objective value $-8$. Consider the dual problem: \begin{align} \max & \quad 16y_1 +4y_2-24y_3\\ \mathrm{s.t.} &\quad 2y_1-\frac12 y_2-3y_3\geqslant -1\\ &\quad 4y_1 -y_2 +4y_3\leqslant \frac43\\ &\quad y_1,y_2,y_3\geqslant 0 \end{align} At optimality, $x_1$ and $x_2$ are nonzero, so by complementary slackness, the corresponding constraints in the dual are binding. Also, the constraint in the primal corresponding to the variable $y_1$ in the dual is not binding, so $y_1=0$ at optimality. It follows that $(y_2, y_3)$ is an optimal basis for the dual, with $y_2^\star = 0$, $y_3^\star = \frac13$, and objective value $8$. This is a feasible solution for the dual with the same objective value as an optimal solution for the primal, and therefore is an optimal solution for the dual.