This HTML5 document contains 39 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n9http://g.co/kg/g/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n5http://fr.dbpedia.org/resource/Théorème_optimisation/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n12http://fr.dbpedia.org/resource/Modèle:
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
dbpedia-fr:Approche_polyédrique
rdfs:label
Approche polyédrique
rdfs:comment
En mathématiques, le problème fondamental de l'approche polyédrique est le suivant. Étant donné un ensemble X de points de l'espace euclidien, déterminer un système d'inégalités linéaires décrivant l'enveloppe convexe de X. Dans les faits, il existe un lien étroit entre la complexité algorithmique de l'optimisation sur X et la connaissance d'une description simple de l'enveloppe convexe de X. Pour beaucoup de problèmes polynomiaux, une telle description est connue. * Portail de la géométrie
owl:sameAs
n9:121kw95z wikidata:Q2858912
dbo:wikiPageID
2147247
dbo:wikiPageRevisionID
187314348
dbo:wikiPageWikiLink
dbpedia-fr:Jack_Edmonds dbpedia-fr:Linéarité n5:séparation category-fr:Algorithmique_et_convexité dbpedia-fr:Optimisation_(mathématiques) dbpedia-fr:Algorithmique dbpedia-fr:Mathématiques dbpedia-fr:Séparation_des_convexes dbpedia-fr:Inéquation_du_premier_degré dbpedia-fr:Enveloppe_convexe dbpedia-fr:Entier_relatif dbpedia-fr:Coordonnées_cartésiennes dbpedia-fr:Exponentiation_ensembliste dbpedia-fr:Polytope_des_stables dbpedia-fr:Théorème_de_Kőnig_(théorie_des_graphes) dbpedia-fr:Contrainte_(mathématiques) dbpedia-fr:Polytope dbpedia-fr:Complexité_algorithmique category-fr:Optimisation_combinatoire dbpedia-fr:Espace_euclidien dbpedia-fr:Optimisation_linéaire dbpedia-fr:Optimisation_linéaire_en_nombres_entiers dbpedia-fr:Théorie_des_graphes
dbo:wikiPageLength
2004
dct:subject
category-fr:Algorithmique_et_convexité category-fr:Optimisation_combinatoire
prop-fr:wikiPageUsesTemplate
n12:Portail n12:Énoncé n12:Exp n12:Palette
prov:wasDerivedFrom
wikipedia-fr:Approche_polyédrique?oldid=187314348&ns=0
foaf:isPrimaryTopicOf
wikipedia-fr:Approche_polyédrique
dbo:abstract
En mathématiques, le problème fondamental de l'approche polyédrique est le suivant. Étant donné un ensemble X de points de l'espace euclidien, déterminer un système d'inégalités linéaires décrivant l'enveloppe convexe de X. Parfois, X est un ensemble de points à coordonnées entières (voire de valeur 0 ou 1) qui représente les points admissibles d'un problème d'optimisation linéaire en nombres entiers. À l'origine, cette approche a été introduite par Jack Edmonds, qui donna la première caractérisation du polytope des couplages d'un graphe, c'est-à-dire de l'enveloppe convexe des vecteurs caractéristiques (dans {0, 1}E) des couplages d'un graphe (V, E). Le succès de l'opération a une conséquence algorithmique directe puisqu'elle réduit ainsi le problème d'optimisation sur X à un problème facile d'optimisation linéaire classique. Ceci est rendu possible à la condition toutefois de posséder un algorithme polynomial pour séparer les contraintes linéaires, c'est-à-dire pour décider si un point donné de l'espace appartient ou non au polyèdre défini par les contraintes, et sinon à trouver un hyperplan de séparation. Ce résultat fondamental est connu sous le nom de théorème optimisation/séparation. Dans les faits, il existe un lien étroit entre la complexité algorithmique de l'optimisation sur X et la connaissance d'une description simple de l'enveloppe convexe de X. Pour beaucoup de problèmes polynomiaux, une telle description est connue. * Portail de la géométrie