0
$\begingroup$

For: $$\text{Max } z=2x_1+2x_2$$ $$\text{ s.t } 2x_1+x_2\leq 16$$ $$3x_1+2x_2\leq 25$$ $$2x_1+3x_2\leq 25$$ $$x_1+x_2\leq 16$$ $$x_1,x_2\geq 0$$

Solve the primal, and solve the dual using the primal solution.

So the dual is:

$$\text{Min } z=16y_1+25y_2+25y_3+16y_4$$ $$\text{ s.t } 2y_1+3y_2+2y_3+y_4\geq 2$$ $$y_1+2y_2+3y_3+y_4\geq2$$ $$y_1,y_2,y_3,y_4\geq0$$

Now I solve the primal and got: $$x_1=5, x_2=5, z=20$

How can this be useful to solve the dual?

$\endgroup$
  • $\begingroup$ I think you have an error in the statement of the primal. The third constraint should be $2x_1+3x_2\leq 25$. $\endgroup$ – Math1000 May 27 at 22:28
  • $\begingroup$ @Math1000 correct, edited $\endgroup$ – newhere May 27 at 22:30
2
$\begingroup$

The first and fourth constraints in the primal are not binding at the optimal solution to the primal, so the corresponding dual variables are zero by complementary slackness. Similarly, $x_1$ and $x_2$ are nonzero in the optimal solution to the primal, so the corresponding dual constraints are binding. Therefore we solve the system of equations \begin{align} 2y_2+3y_3 &= 2\\ 3y_2+2y_2 &= 2 \end{align} to yield $y_2=y_3=2/5$ and objective value $25\cdot2/5+25\cdot2/5=20$. Note that this is indeed equal to the optimal objective value of the primal, as would be expected from strong duality.

$\endgroup$

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.