PRICING

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 p = c_B[B^-1], where B is a basis , and c_B is a vector of costs associated with the basic variables. The vector p is sometimes called a dual solution, though it is not feasible in the dual before termination. p is also called a simplex multiplier or pricing vector. The price of the j-th variable is c_j - pA_j. The first term is its direct cost (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 (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 r = [B^-1]A_j. If p = v[B^-1], then pA_j = vr, and 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 v_i=1 if x_i=0 and v_i=0 if x_i > 0. Then, vr = Sum_i(r_i: x_i=0). Thus, if pA_j > 0, activity 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.