Reduced cost (original) (raw)
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 minimization and positively maximization, is sometimes referred to as the steepest edge.
| Property | Value |
|---|---|
| dbo:abstract | Lorsqu'on résout des problèmes d'optimisation, on obtient une solution optimale (ou pas). Chacune des contraintes a une valeur précise. Le coût réduit est la perte d'argent si l'on baisse la contrainte. Ainsi, une contrainte non saturée a un coût réduit nul. Prenons un exemple : pour fabriquer des sacs à main, une compagnie utilise 2 usines, la première a une capacité de 50 heures par semaine, la deuxième de 35 h. Les usines sont utilisées 40 heures pour la première et 35 heures pour la deuxième. Le chiffre d'affaires est de 12 000 euros. Si, pour une raison quelconque, la capacité de la deuxième usine descend à 34 heures, alors le chiffre d'affaires baisse à 11 500 euros. Ainsi, le coût réduit est ici de 500 pour la deuxième usine (et 0 pour la première). (fr) 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 minimization and positively maximization, 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 minimization problem, any non- 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 maximization problem, the non-basic variables at their lower bounds that are eligible for entering the basis have a strictly positive reduced cost. (en) |
| dbo:wikiPageID | 16614405 (xsd:integer) |
| dbo:wikiPageLength | 4916 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1070084361 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Devex_algorithm dbr:Polyhedron dbr:Objective_function dbr:Linear_programming dbr:Shadow_price dbc:Linear_programming dbr:Basic_variable dbr:Pivot_strategy |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description dbt:Citations_missing |
| dcterms:subject | dbc:Linear_programming |
| rdfs:comment | 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 minimization and positively maximization, is sometimes referred to as the steepest edge. (en) Lorsqu'on résout des problèmes d'optimisation, on obtient une solution optimale (ou pas). Chacune des contraintes a une valeur précise. Le coût réduit est la perte d'argent si l'on baisse la contrainte. Ainsi, une contrainte non saturée a un coût réduit nul. (fr) |
| rdfs:label | Coût réduit (fr) Reduced cost (en) |
| owl:sameAs | freebase:Reduced cost wikidata:Reduced cost dbpedia-fr:Reduced cost https://global.dbpedia.org/id/4thP2 |
| prov:wasDerivedFrom | wikipedia-en:Reduced_cost?oldid=1070084361&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Reduced_cost |
| is dbo:wikiPageWikiLink of | dbr:List_of_numerical_analysis_topics dbr:Branch_and_price dbr:Shortest_path_problem dbr:Column_generation dbr:A*_search_algorithm dbr:Opportunity_cost dbr:Shadow_price dbr:Dijkstra's_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Reduced_cost |