Programmation Linéaire, Complexité - Séparation et Optimisation

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. Dans ce but 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.

List of contents

I. Introduction.- II. Notation et rappels.- III. Complexité des Algorithmes.- IV. Quelques problèmes NP-Complets.- V. Algorithme de Gauss et modification d'Edmonds.- VI. Programmes linéaires et la méthode du Simplexe.- VII. Implémentations pratiques.- VIII. Polyèdres et Polytopes.- IX. Polyèdres Combinatoires.- X. Les méthodes intérieures.- XI. Optimisation par séparation: 1.- XII. Séparer en optimisant.- XIII. Les oracles polyédraux, et les autres.- XIV. Optimisation par séparation: 2.- XV. L'oracle appartenir.- XVI. Épilogue.

Summary

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. Dans ce but 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.

Product details

• Authors: Jean F. Maurras
• Publisher: Springer, Berlin
• Languages: French
• Product format: Paperback / Softback
• Released: 27.07.2002
• EAN: 9783540436713
• ISBN: 978-3-540-43671-3
• No. of pages: 222
• Weight: 396 g
• Illustrations: XIV, 222 p.
• Series: Mathématiques et Applications
• Subjects: Natural sciences, medicine, IT, technology > Mathematics > Miscellaneous; Operations Research, C, Algorithms, Mathematics and Statistics, Management & management techniques, Operations Research, Management Science, Mathematics of Computing, Algebraic Geometry, Discrete Mathematics, Number Theory, Management science, Algorithms & data structures, Discrete geometry, Convex and Discrete Geometry, Convex geometry, Numerical analysis, Mathematical theory of computation, Computer science—Mathematics, Maths for computer scientists, Algorithm Analysis and Problem Complexity, Complexite;Programmation Lineaire;Separation