This is probably a dumb question… but I'm trying to find how to calculate the reduced cost for a particular variable based on the information in a simplex tableau after I've minimized a linear programming problem. I've been googling like crazy and, while I can find a million sites that explain how to interpret reduced costs and how they are useful, I can't find a single resource that tells me how to calculate them.
How can this be done?
Best Answer
After you have minimized the LP, there are no more reduced costs, e.g. they are all zero. All that you have are the dual variables. You only do have nonzero reduced costs at a local minimum (=basis = edge of the feasible polyhedron).
Generally, the reduced cost is:
\begin{equation} d_j = c_j - \mu^\top A_j \end{equation}
Cost of increasing a nonbasic variable $x_j$. Nonbasic row of the coefficientmatrix $A$: $A_j$.
With dual variable $\mu$:
\begin{equation} \mu = c_B^\top B^{-1} \end{equation}
$B$ is the Basis of coefficient matrix $A$, sometimes $B$ is called $A_B$.
There is an example in Bertsimas - Introduction to Linear Optimization on p.84.