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.
On
The prime has infinite many optimal solution as long as x1 belongs to [8/5,8]. However, the dual solution is unique.
Note that the third constraint of the prime problem has to be tight to achieve the optimal value of -8 (dividing it by 3 and you obtain the objective function). Thus, y3 must not equal to 0. The first and the second constraints of the prime problem are equivalent, and cannot be tight. Thus, y1=y2=0.
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.