Programme > Par auteur > Allamigeon Xavier

Jeudi 27
Graphes, flots, algorithmes combinatoires et approximation
Mariem Mekki
› 14:40 - 15:00 (20min)
› Bât B - TD 43
La méthode du simplexe tropical
Pascal Benchimol  1, 2@  , Xavier Allamigeon  1, 2  , Stéphane Gaubert  1, 2  , Michael Joswig  3  
1 : Centre de Mathématiques Appliquées - Ecole Polytechnique  (CMAP)  -  Site web
Polytechnique - X
CMAP UMR 7641 École Polytechnique CNRS Route de Saclay 91128 Palaiseau Cedex -  France
2 : MAXPLUS  (INRIA Saclay - Ile de France)
INRIA
3 : Technische Universität Berlin  (TUB)  -  Site web

Cet exposé présente un analogue de la méthode du simplexe pour la
programmation linéaire tropicale, c'est à dire les problèmes
d'optimisation décrits par des inégalités (max,+)-linéaires.
Tropicalement, les opérations de pivotage et de calcul des coûts réduits
sont purement combinatoires. Pivoter s'interprète comme une succession
de graphes acycliques. Le calcul des coûts réduits s'effectue via un
problème couplage de poids maximum et un problème de plus court chemin.
La séquence de bases obtenue par méthode du simplexe tropical
correspond exactement à la séquence de bases donnée par la méthode du
simplexe classique appliquée sur le corps des séries de Puiseux.


Personnes connectées : 1