I don't understand how I can solve the dual of a linear programming model knowing the solution to the primal.

Question

If we know the optimal solution for a primal model how can I find the optimal solution for the dual of that primal model?

I heard about complementary slackness which to my understanding is that the slack variables from the primal model can be used in the dual. The example I've seen is when the slack variables are 0. What would happen if we have slack variables that are non-zero?

To give a primal model as an example: $$ \max Z = 0.56x_1 + 0.46x_2 $$ the constraints are

\begin{align} x_1 &\leq 110000 \\ x_1 + 2x_2 &\leq 240000 \\ 3/2x_1 + x_2 &\leq 180000 \end{align}

The optimal solution for this model is $x_1 = 60000$ and $x_2 = 90000$.

Now here is the dual model of this primal: $$ \min Z = 110000y_1 + 240000y_2 + 180000y_3 $$

The constraints are :

\begin{align} y_1 + y_2 + 1.5y_3 &\geq 0.56 \\ 2y_2 + y_3 &\geq 0.46 \end{align}

Assume constraints of non-negativity for both models.

Now I calculated the slack variables of the primal model.

\begin{align} x_{s1} &= 50000 \\ x_{s2} &= 0 \\ x_{s3} &= 0 \end{align}

The problem is I don't know what to do with them to get the solution of the dual model.

Answer 1

By complementary slackness:

• $x_1 < 110000$ (equivalently, $x_{s1}>0$) implies $y_1=0$
• $x_1 > 0$ implies that the first dual constraint is satisfied with equality
• $x_2 > 0$ implies that the second dual constraint is satisfied with equality

Now solve these two equations for $y_2$ and $y_3$.

Note: the second and third bullets use the fact that the primal variables are the dual variables of the dual constraints.