Titre :	Optimisation combinatoire : graphes et programmation lineaire
Type de document :	texte imprimé
Auteurs :	Michel Sakarovitch, Auteur
Editeur :	Hermann
Année de publication :	1984
Importance :	249p
Présentation :	ill.
Format :	24x16.5cm
ISBN/ISSN/EAN :	97812705659745
Langues :	Français (fre)
Catégories :	AUTOMATISME
Mots-clés :	optimisation combinatoire .graphes et programmation lineaire
Index. décimale :	logique combinatoire et sequentiel
Résumé :	L'optimisation combinatoire traite des problèmes- apparemment dépourvus de mystère - dans lesquels on a à extraire un "meilleur" élément (de coût minimum, par exemple) d'un ensemble fini. Un instant de réflexion montre que la plupart des problèmes concrets d'optimisation appartiennent effectivement à cette classe ou peuvent se formuler de cette manière. Quoique fini, l'ensemble objet de l'étude comporte en général un grand nombre d'éléments (par rapport au nombre de données du problème). C'est ce phénomène qui, en interdisant la solution par énumération de toutes les solutions possibles, rend la problématique de l'optimisation combinatoire non triviale : on est amené à mettre en évidence certaines structures du modèle étudiées et à élaborer différentes méthodes de solution. Cet ouvrage présente l'ensemble de ces techniques très diverses dont l'unité profonde commence seulement à émerger. Après un rappel des principaux concepts et résultats du volume "Graphes et programmation linéaire", cet ouvrage commence par une présentation de la théorie de la complexité des algorithmes. La suite est consacrée à l'étude des problèmes de cheminement, d'ordonnancement et de flot. Puis on décrit les méthodes de solution des problèmes d'optimisation combinatoire réputés "difficiles": procédures par séparation et évaluation ("branch and bound"), méthodes de coupes, programmation dynamique et enfin méthodes approximatives ou heuristiques. On peut considérer qu'il s'agit d'autant de monographies qui peuvent être lues indépendamment et constituent des manuels de référence dans ces domaines. L'ouvrage pourra être utilisé comme tel par les étudiants en mathématiques appliquées et en informatique ou les élèves des grandes écoles d'ingénieurs. Il pourra également être consulté par tous ceux qui, ayant achevé leurs études depuis quelques années, souhaitent s'initier à des disciplines qui n'étaient pas enseignées au moment de leur formation initiale.
Note de contenu :	notions fondamentales de la theorie des graphes.arbres des graphes .representation des graphes.cycles et cocycles ;flots et tensions;cycles euleriens et hamiltoniens .graphes bipartis ;couplage et recouvrement graphes planaires ;graphes parfaitsss.programmes lineaires;programmes lineaires duaux.resolution des systemes lineaires;bases et solutions...la methode du simplexe .complement sur la dualite ..mise en oeuvre de la methode du simplexe ;algorithme revise...le probleme de transport

Optimisation combinatoire : graphes et programmation lineaire [texte imprimé] / Michel Sakarovitch, Auteur . - Hermann, 1984 . - 249p : ill. ; 24x16.5cm.
ISSN : 97812705659745
Langues : Français (fre)

Catégories :	AUTOMATISME
Mots-clés :	optimisation combinatoire .graphes et programmation lineaire
Index. décimale :	logique combinatoire et sequentiel
Résumé :	L'optimisation combinatoire traite des problèmes- apparemment dépourvus de mystère - dans lesquels on a à extraire un "meilleur" élément (de coût minimum, par exemple) d'un ensemble fini. Un instant de réflexion montre que la plupart des problèmes concrets d'optimisation appartiennent effectivement à cette classe ou peuvent se formuler de cette manière. Quoique fini, l'ensemble objet de l'étude comporte en général un grand nombre d'éléments (par rapport au nombre de données du problème). C'est ce phénomène qui, en interdisant la solution par énumération de toutes les solutions possibles, rend la problématique de l'optimisation combinatoire non triviale : on est amené à mettre en évidence certaines structures du modèle étudiées et à élaborer différentes méthodes de solution. Cet ouvrage présente l'ensemble de ces techniques très diverses dont l'unité profonde commence seulement à émerger. Après un rappel des principaux concepts et résultats du volume "Graphes et programmation linéaire", cet ouvrage commence par une présentation de la théorie de la complexité des algorithmes. La suite est consacrée à l'étude des problèmes de cheminement, d'ordonnancement et de flot. Puis on décrit les méthodes de solution des problèmes d'optimisation combinatoire réputés "difficiles": procédures par séparation et évaluation ("branch and bound"), méthodes de coupes, programmation dynamique et enfin méthodes approximatives ou heuristiques. On peut considérer qu'il s'agit d'autant de monographies qui peuvent être lues indépendamment et constituent des manuels de référence dans ces domaines. L'ouvrage pourra être utilisé comme tel par les étudiants en mathématiques appliquées et en informatique ou les élèves des grandes écoles d'ingénieurs. Il pourra également être consulté par tous ceux qui, ayant achevé leurs études depuis quelques années, souhaitent s'initier à des disciplines qui n'étaient pas enseignées au moment de leur formation initiale.
Note de contenu :	notions fondamentales de la theorie des graphes.arbres des graphes .representation des graphes.cycles et cocycles ;flots et tensions;cycles euleriens et hamiltoniens .graphes bipartis ;couplage et recouvrement graphes planaires ;graphes parfaitsss.programmes lineaires;programmes lineaires duaux.resolution des systemes lineaires;bases et solutions...la methode du simplexe .complement sur la dualite ..mise en oeuvre de la methode du simplexe ;algorithme revise...le probleme de transport