Programmation Linaire, Complexit Sparation et Optimisation [Paperback]

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 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. 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.DE