Skip to Main content Skip to Navigation
Theses

Problèmes d'optimisation combinatoires probabilistes

Résumé : L'étude du domaine récent que constituent les problèmes d'optimisation combinatoires probabilistes (POCPs) forme le sujet de cette thèse. Les POCPs sont des généralisations des problèmes d'optimisation combinatoires classiques dont les formulations contiennent explicitement des éléments probabilistes. Plusieurs motivations ont provoqué cette étude. Deux d'entre elles sont particulièrement importantes. La première correspond au désir de formuler et d'analyser des modèles qui sont plus appropriés pour des problèmes pratiques pour lesquels l'aléatoire est une source constante de préoccupations, les modèles de nature probabiliste sont plus particulièrement attractifs comme abstraction mathématique des systèmes réels. La seconde motivation est d'analyser la stabilité des solutions optimales des problèmes déterministes lorsque les exemplaires sont perturbés : les perturbations sont simulées par la présence ou l'absence de sous-ensembles des données. Notre étude s'appuie sur certains de ces problèmes et en particulier : problème du voyageur de commerce; problème d'ordonnancement des travaux probabiliste et le problème du bin-packing probabiliste. Les questions soulevées et les résultats obtenus sont dans les domaines suivants : complexités des problèmes et analyse d'heuristiques pour les POCPs ; analyse du comportement asymptotique des problèmes lorsque les exemplaires correspondent à des problèmes de grandes tailles ; dégager une méthodologie générale d'étude de la stabilité des solutions des problèmes d'optimisation combinatoires classiques.
Document type :
Theses
Complete list of metadatas

Cited literature [60 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00568759
Contributor : Ecole Des Ponts Paristech <>
Submitted on : Wednesday, February 23, 2011 - 2:24:25 PM
Last modification on : Thursday, April 5, 2018 - 11:01:54 AM
Long-term archiving on: : Tuesday, May 24, 2011 - 4:08:43 AM

Identifiers

  • HAL Id : pastel-00568759, version 1

Collections

Citation

Monia Bellalouna. Problèmes d'optimisation combinatoires probabilistes. Optimisation et contrôle [math.OC]. Ecole Nationale des Ponts et Chaussées, 1993. Français. ⟨pastel-00568759⟩

Share

Metrics

Record views

1378

Files downloads

4415