La méthode du simplexe tropical

Xavier Allamigeon 1, 2 Pascal Benchimol 1, 2 Stephane Gaubert 1, 2 Michael Joswig 3
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Résumé : 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.
Type de document :
Communication dans un congrès
ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision, Feb 2014, Bordeaux, France
Liste complète des métadonnées

https://hal.inria.fr/hal-01097726
Contributeur : Pascal Benchimol <>
Soumis le : dimanche 21 décembre 2014 - 16:33:53
Dernière modification le : jeudi 10 mai 2018 - 02:04:00

Identifiants

  • HAL Id : hal-01097726, version 1

Citation

Xavier Allamigeon, Pascal Benchimol, Stephane Gaubert, Michael Joswig. La méthode du simplexe tropical. ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision, Feb 2014, Bordeaux, France. 〈hal-01097726〉

Partager

Métriques

Consultations de la notice

409