In linear programming, reduced cost, or opportunity cost, is the amount by which an objective function coefficient would have to improve (so increase for maximization problem, decrease for minimization problem) before it would be possible for a corresponding variable to assume a positive value in the optimal solution. It is the cost for increasing a variable by a small amount, i.e., the first derivative from a certain point on the polyhedron that constrains the problem. When the point is a vertex in the polyhedron, the variable with the most extreme cost, negatively for minimisation and positively maximisation, is sometimes referred to as the steepest edge.
Given a system minimize subject to, the reduced cost vector can be computed as, where is the dual cost vector.
It follows directly that for a minimisation problem, any non-basic variables at their lower bounds with strictly negative reduced costs are eligible to enter that basis, while any basic variables must have a reduced cost that is exactly 0. For a maximisation problem, the non-basic variables at their lower bounds that are eligible for entering the basis have a strictly positive reduced cost.
Read more about Reduced Cost: Interpretation, Reduced Costs in Pivot Strategy, Reduced Cost in Linear Programming, See Also
Famous quotes containing the words reduced and/or cost:
“There surely is a being who presides over the universe; and who, with infinite wisdom and power, has reduced the jarring elements into just order and proportion. Let speculative reasoners dispute, how far this beneficent being extends his care, and whether he prolongs our existence beyond the grave, in order to bestow on virtue its just reward, and render it fully triumphant.”
—David Hume (1711–1776)
“If music in general is an imitation of history, opera in particular is an imitation of human willfulness; it is rooted in the fact that we not only have feelings but insist upon having them at whatever cost to ourselves.... The quality common to all the great operatic roles, e.g., Don Giovanni, Norma, Lucia, Tristan, Isolde, Brünnhilde, is that each of them is a passionate and willful state of being. In real life they would all be bores, even Don Giovanni.”
—W.H. (Wystan Hugh)