1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ that's good. You have to get the system into more standard notation. max c'*x s.t. Ax <= b, so what's c, A and b? $\endgroup$ – tschm Mar 17 '16 at 13:24
  • $\begingroup$ I'm not sure what that means @tschm $\endgroup$ – Barney Chambers Mar 17 '16 at 13:24
  • $\begingroup$ @tschm The problem is already in that form. $\endgroup$ – Math1000 Mar 17 '16 at 13:34
  • $\begingroup$ Note that you could add x, y >= 0 without any harm to the problem $\endgroup$ – tschm Mar 17 '16 at 13:42
  • $\begingroup$ That is right @tschm, but how do I solve it? $\endgroup$ – Barney Chambers Mar 17 '16 at 13:44
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This answer is unclear to me $\endgroup$ – Barney Chambers Mar 17 '16 at 14:25
  • $\begingroup$ what does it mean "The third constraint in the primal is not binding"? $\endgroup$ – Mona Jalal Mar 6 '19 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.