Pricing

From Glossary

Jump to: navigation, search

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.


Views
Personal tools