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.
| Attributes | Values |
|---|
| rdfs:label
| - Coût réduit (fr)
- Reduced cost (en)
|
| 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)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has 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)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)