How obtain the dual variables' value given a primal solution

Question

I am currently studying duality theory (for linear programming) and stumbled upon some confusion. Duality theory provides a useful tool to check if a given primal solution is optimal. A given primal solution is optimum iff the corresponding dual solution is feasible. Now, I want to check whether my solution for my primal is optimal without having to solve it using the simplex method. I can write the corresponding dual formulation, but I don't see how to obtain the corresponding dual variables from a primal solution to check for a violated dual constraint?

Answer 1

Given the primal: \begin{equation*} \begin{array}{lll} \textrm{maximize } & \sum\limits_{j=1}^n c_j x_j&\\ \textrm{subject to} & \sum\limits_{j=1}^n a_{ij} x_j \leq b_i & \textrm{ for } i=1,2\ldots,m\\ & x_j \geq 0 & \textrm{ for } j=1,2\ldots,n \end{array} \end{equation*}

The dual is: \begin{equation*} \begin{array}{lll} \textrm{minimize } & \sum\limits_{i=1}^m b_i y_i&\\ \textrm{subject to} & \sum\limits_{i=1}^m a_{ij} y_i \geq c_j & \textrm{ for } j=1,2\ldots,n\\ & y_i \geq 0 & \textrm{ for } i=1,2\ldots,m \end{array} \end{equation*}

Now given a solution $x^*$, use the complementary slackness theorem!

Either the primal variable is zero, or the associated dual constraint is tight: \begin{equation} {x^*_j = 0 \textrm{ or } \sum_{i=1}^m a_{ij}y^*_i = c_j \textrm{ (or both) for } j=1,2,\ldots,n} \end{equation} Either the primal constraint is tight, or the associated dual variable is zero: \begin{equation} \label{eq:CSC:2} {\sum_{j=1}^n a_{ij}x^*_j = b_i \textrm{ or } y^*_i = 0 \textrm{ (or both) for } i=1,2,\ldots,m} \end{equation}

If your solution $x^*$ is basic, you should find yourself with a system of equations with $n$ equations and $n$ unknowns. Solving it will give you a dual solution. If it is feasible on the dual, $x^*$ is optimal.