0
$\begingroup$

I have a problem in my book:

Maximize $ -x_1 + 2x_2$

Subject to

$3x_1 +4x_2 \leq 12$

$ 2x_1-x_2 \geq 2 $

$x_1, x_2 \geq 0$

The problem asks to find the values of all the primal variables from the optimal dual solution.

So I figured first step is to find the dual which is:

Minimize $12y_1 - 2y_2$

Subject to

$3y_1 - 2y_2 \geq -1$

$4y_1 + y_2 \geq 2$

I have confirmed this to be correct as solving both the primal and dual graphically produce the same result, that is $1.4545..$

I'm a bit confused what is being asked. Isn't the optimal dual solution the same as the optimal primal solution? We are also using different variables in the primal compared to the dual?

I'd much prefer an understanding of what is being asked in the question instead of a direct answer.

Thanks a lot.

$\endgroup$
1
$\begingroup$

If you know the optimal dual solution, and not just the optimal dual objective value - that is, if you know the values of $y_1$ and $y_2$ that achieve it - then you can use complementary slackness.

Complementary slackness tells us that if a dual variable is positive, then the corresponding primal constraint is tight. That is:

  • If $y_1 > 0$ in the optimal dual solution, then the constraint corresponding to $y_1$ is tight: $3x_1 + 4x_2 = 12$ in the optimal primal solution.
  • If $y_2 > 0$ in the optimal dual solution, then the constraint corresponding to $y_1$ is tight: $2x_1 - x_2 = 2$ in the optimal primal solution.

Plus, of course, if you know that $12y_1 - 2y_2 = \frac{16}{11}$ in the optimal dual solution, then $-x_1 + 2x_2 = \frac{16}{11}$ in the optimal primal solution.

All this means that instead of solving the primal LP, you can solve a system of linear equations instead. (Of course, in the simple $2$-variable case you're looking at, both are fairly easy tasks, but in general, just solving a system of linear equations is much easier.)

$\endgroup$
  • $\begingroup$ In my case I showed graphically that the optimal dual solutions were $\frac{3}{11}$ and $\frac{20}{22}$. Since they are positive it is as simple as solving the simultaneous equations (constraints) from the primal problem, right? $\endgroup$ – Gregory Peck Mar 24 '17 at 1:08
  • $\begingroup$ Right: both of the primal constraints have to be tight, giving you two equations to solve for $x_1$ and $x_2$. $\endgroup$ – Misha Lavrov Mar 24 '17 at 1:09
  • $\begingroup$ Just wondering, we can solve the primal in this case because there are 2 constraints and 2 variables. Suppose the dual has 4 constraints and 2 variables with positive solutions. We can say both constraints in the primal are tight. But since there are 4 variables we cannot solve the simulataneous equation. Does this mean there are free variables (i.e - infinite solutions?) $\endgroup$ – Gregory Peck Mar 25 '17 at 23:06
  • $\begingroup$ You could also use complementary slackness going the other way: if a dual constraint is not tight, the corresponding primal variable is $0$. You do get free variables when a "surprising number" of dual constraints are tight: e.g., with $2$ variables, we can generally only make $2$ constraints tight, and making $3$ constraints tight is a sign of degeneracy. $\endgroup$ – Misha Lavrov Mar 25 '17 at 23:14
  • $\begingroup$ If all corresponding constraints are tight, but there are more variables than constraints, you cannot solve the equations, right? Are there other theorems of duality to use in that case? $\endgroup$ – Gregory Peck Mar 25 '17 at 23:48

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.