 # Pricing

This is a tactic in the simplex method, by which each variable is evaluated for its potential to improve the value of the objective function. Let $LaTeX: \textstyle p = c_B[B^{-1}],$ where $LaTeX: B$ is a basis, and $LaTeX: c_B$ is a vector of costs associated with the basic variables. The vector $LaTeX: p$ is sometimes called a dual solution, though it is not feasible in the dual before termination. $LaTeX: p$ is also called a simplex multiplier or pricing vector. The price of the j-th variable is $LaTeX: \textstyle c_j - pA_j.$ The first term is its direct cost $LaTeX: (c_j)$ and the second term is an indirect cost, using the pricing vector to determine the cost of inputs and outputs in the activity's column $LaTeX: (A_j).$ The net result is called the reduced cost, and its value determines whether this activity could improve the objective value.
Other pricing vectors are possible to obtain information about the activity's rates of substitution without actually computing $LaTeX: \textstyle r = [B^{-1}]A_j.$ If $LaTeX: \textstyle p = v[B^{-1}],$ then $LaTeX: \textstyle pA_j = vr,$ and $LaTeX: v = c_B$ is the special case to get the reduced cost. Another special case is to obtain information about whether the (nonbasic) activity would need to perform a degenerate pivot. For LP in standard from, let $LaTeX: v_i=1$ if $LaTeX: x_i=0$ and $LaTeX: v_i=0$ if $LaTeX: x_i > 0.$ Then, $LaTeX: \textstyle vr = \sum_i \left \{r_i: x_i = 0 \right \}.$ Thus, if $LaTeX: pA_j > 0,$ activity $LaTeX: j$ must have a positive tableau value with respect to some basic variable whose level is zero, so the pivot would have to be degenerate.