[Math] Finding the values of all primal variables – Linear Programming

Question

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.

Answer 1

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.)