Programmation linéaire, complexité : séparation et optimisation / Jean François Maurras [ Livre]

Auteur principal: Maurras, Jean-FrançoisLangue: Français.Publication : Paris : Springer, cop. 2002Description : XIV-221p. ; 24 cmISBN: 3540436715.Collection: Mathematiques & Applications, 38Classification: 518 Analyse numérique, modélisation et calcul scientifiqueRésumé: Le but de cet ouvrage est de faire une présentation complète et auto contenue de l'équivalence entre les Oracles "Séparer", "Optimiser" et "Appartenir" en Optimisation Polyédrale. Le livre commence par une présentation détaillée des problèmes de Complexité des Algorithmes suivi d'une présentation de la méthode du Simplexe. On décrit ensuite l'algorithme de Khachiyan sans éluder les problèmes numériques. Viennent alors une suite d'algorithmes polynomiaux pour Optimiser à partir de l'oracle Séparer. Après quelques transformations, on montre que, par polarité, on peut Séparer à partir de l'oracle Optimiser. La première équivalence est revue après avoir décrit l'algorithme LLL. L'ouvrage se termine par la réduction de Séparer à Appartenir. Sommaire Notations et rappels Complexité des Algorithmes Quelques problèmes NP-Complets Algorithme de Gauss et modification d'Edmonds Programmes linéaires et la méthode du Simplexe Implémentations pratiques Polyèdres et Polytopes Polyèdres Combinatoires Les méthodes intérieures Optimisation par séparation Séparer en optimisant Les oracles polyédraux, et les autres Optimisation par séparation L'oracle appartenir.Sujet - Nom commun: Simplexes (mathématiques) | Programmation linéaire | Optimisation mathématique | Algorithmes
Current location Call number Status Notes Date due Barcode
ENS Rennes - Bibliothèque
Mathématiques
518 MAU (Browse shelf) Available 518 Analyse numérique, modélisation et calcul scientifique 00010637

Bibliogr. p. [213]-217. Index

Bibliogr. Index

Le but de cet ouvrage est de faire une présentation complète et auto contenue de l'équivalence entre les Oracles "Séparer", "Optimiser" et "Appartenir" en Optimisation Polyédrale. Le livre commence par une présentation détaillée des problèmes de Complexité des Algorithmes suivi d'une présentation de la méthode du Simplexe. On décrit ensuite l'algorithme de Khachiyan sans éluder les problèmes numériques. Viennent alors une suite d'algorithmes polynomiaux pour Optimiser à partir de l'oracle Séparer. Après quelques transformations, on montre que, par polarité, on peut Séparer à partir de l'oracle Optimiser. La première équivalence est revue après avoir décrit l'algorithme LLL. L'ouvrage se termine par la réduction de Séparer à Appartenir.
Sommaire
Notations et rappels
Complexité des Algorithmes
Quelques problèmes NP-Complets
Algorithme de Gauss et modification d'Edmonds
Programmes linéaires et la méthode du Simplexe
Implémentations pratiques
Polyèdres et Polytopes
Polyèdres Combinatoires
Les méthodes intérieures
Optimisation par séparation
Séparer en optimisant
Les oracles polyédraux, et les autres
Optimisation par séparation
L'oracle appartenir

Powered by Koha