Formulating the Dual of a linear program

Question

I have a linear program:

Maximize 18x + 12y 

subject to: x+y <= 20 x <= 12 y <= 16 x,y >=0

I have found that x = 12, y = 8, P = 316 using the simplex method, but how do I find the dual of the linear program?

Answer 1

Recall that each variable in the primal problem corresponds to a constraint in the dual problem, and vice versa. The primal has two variables, so the dual will have two constraints, and the primal has three constraints, so the dual will have three variables. The primal is a maximization problem, so the dual is a minimization problem, and the primal constraints are $\leqslant$, so the dual variables are nonnegative ($\geqslant 0$). The primal variables are nonnegative, so the dual constraints are $\geqslant$. The constraint matrix of the dual is the transpose of the constraint matrix of the primal, the RHS of the dual is the cost vector of the primal, and the cost vector of the dual is the RHS of the primal.

In other words, the primal is

\begin{align} \max\quad &\mathbf c^T\mathbf x\\ \mathrm{s.t.}\quad &A\mathbf x\leqslant\mathbf b&\\ &\mathbf x\geqslant 0 \end{align} and the dual is \begin{align} \min\quad & \mathbf b^T \mathbf w\\ \mathrm{s.t.}\quad & A^T\mathbf w\geqslant \mathbf c\\ &\mathbf w\geqslant 0, \end{align} where $$ \mathbf c = \begin{bmatrix}18\\12\end{bmatrix},\quad\mathbf b=\begin{bmatrix}20\\12\\16\end{bmatrix},\quad \mathbf x = \begin{bmatrix}x\\y\end{bmatrix},\quad\mathbf w = \begin{bmatrix}w_1\\w_2\\w_3\end{bmatrix}, \quad A = \begin{bmatrix}1&1\\1&0\\0&1 \end{bmatrix}. $$ Written explicitly, the dual is \begin{align} \min\quad& 20w_1 + 12w_2 + 16w_3\\ \mathrm{s.t.}\quad & w_1 + w_2 \geqslant 18\\ & w_1 + w_3 \geqslant 12\\ & w_1,w_2,w_3\geqslant0. \end{align} The third constraint in the primal is not binding, so by complementary slackness, the corresponding dual variable $w_3$ is zero at optimality. Therefore from the second constraint in the dual we see that $w_1=12$, and so from the first constraint $w_2=6$. This yields the objective value $$20\cdot12 + 12\cdot6=312. $$ This is equal to the objective value of the primal solution $(x,y)=(12,16)$, and so by strong duality is optimal.