Using the primal solution solve the dual sloution

202 Views Asked by At

For: $$\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:

$$\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?

1

There are 1 best solutions below

0
On

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.