How obtain the dual variables' value given a primal solution 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?
 A: 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.
