What is the relation between dual variables and reduced costs?

Question

My background: Pure math current Undergrad, learned the theory of Operations Research, but pretty basic. All we covered have been dealing with problems that have only 1 constraint matrix. I have dealt with 2-dimensional variables, but not worked with it extensively (unless just setting up the variable and letting AMPL figure it out).

in the usual set-up with a single constraint matrix: $$ \min c^T \cdot x, \text{satisfying } Ax \leq b, x \geq 0 $$

In this case, we can then define the reduced cost of $x_j:=$

$$= c_j - c_B^T \cdot \bar{a_j}$$

Where $B$ is the set of basic indices (variables in the basis), and $\bar{a_j} = A_B^{-1}\cdot\bar{a_j}$ . I think it is more commonly defined as $:=$

$$ =c_j - \pi^T \cdot a_j, $$

where $\pi^T = c^T_B \cdot A_B^{-1}$, also known as the shadow price, the optimal solution of the dual problem. I usually think of the shadow price as the reduced cost of slack variables, or how much more profit we will gain if we have one more unit of each resource.

This is all fine and dandy, but what if we have multiple constraint matrices? I would assume that for each constraint matrix we will have a shadow price, which itself is an optimal solution of the dual problem of each constraint matrix. But how are the shadow prices related to the reduced cost now?

In fact, what is the reduced cost for a variable now? In a paper I'm reading, supposing we have constraint matrices $G, H$, the reduced cost for $x_j:=$ $$ c_j - \left( \pi^T \cdot g_j + \mu^T \cdot h_j \right) $$

where $\pi,\mu$ are the shadow prices for $G$ and $H$ respectively. Why? May I see a derivation?

Answer 1

First, as a note, your formulation (minimizing with $\le$ constraints) will produce nonpositive shadow prices. It might be easier to understand if you use $\ge$ constraints (nonnegative shadow prices). For clarity, I'll assume we are maximizing profit with $\le$ constraints, which results in nonnegative shadow prices.

Each shadow price represents the marginal rate at which profit increases (decreases) as the supply of a particular resource increases (decreases), assuming that the solution is adjusted optimally to the change. Now suppose that, rather than monkeying with the resources, we force the value of a variable $x_j$ to go (down) slightly, meaning we insist that the solution do a bit more (less) of that activity. Let $\delta$ be the change imposed. The direct impact on profit is to increase (decrease) by $c_j\cdot \delta$. The indirect effect is that we force a change of $-g_{ij}\cdot\delta$ in the availability of the $i$-th resource from the $G$ portion of the constraints and $-h_{ij}\cdot\delta$ in the availability of the $i$-th resource from the $H$ portion of the constraints. The "-" is because increasing (decreasing) the level of $x_j$ increases (decreases) consumption of the resources and thus decreases (increases) the availability of those resources for the rest of the solution. The expression you subtract from $c_j$ in the reduced cost is the marginal impact of those changes on the profit from the rest of the solution, again assuming that the remainder of the solution is adjusted optimally.

For cost minimization, or when you have constraints going in the "noncanonical" direction (such as profit maximization with a lower bound on some combination of activities that are for some reason less desirable to do), the logic is similar.

Answer 2

If you interpret $$A= \begin{pmatrix}G \\ H\end{pmatrix}$$ then $$\pi^TA_j = \mu^T G_j + \lambda^T H_j$$ (where $\pi,\mu,\lambda$ are the corresponding duals) is not a surprise.