Programmation Linéaire, Complexité: Séparation Et Optimisation

ISBN-13: 9783540436713 / Francuski / Miękka / 2002 / 222 str.

Jean F. Maurras

Opis

Le but de cet ouvrage est de faire une presentation complete et auto contenue de l'equivalence entre les Oracles Separer, Optimiser et Appartenir en Optimisation Polyedrale. Dans ce but le livre commence par une presentation detaillee des problemes de Complexite des Algorithmes suivi d'une presentation de la methode du Simplexe. On decrit ensuite l'algorithme de Khachiyan sans eluder les problemes numeriques. Viennent alors une suite d'algorithmes polynomiaux pour Optimiser a partir de l'oracle Separer. Apres quelques transformations, on montre que, par polarite, on peut Separer a partir de l'oracle Optimiser. La premiere equivalence est revue apres avoir decrit l'algorithme LLL. L'ouvrage se termine par la reduction de Separer a Appartenir.

Spis treści

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.