Problèmes d'optimisation combinatoires probabilistes - PASTEL - Thèses en ligne de ParisTech Accéder directement au contenu
Thèse Année : 1993

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.
Fichier principal
Vignette du fichier
1993TH_BELLALOUNA_M_NS16942.pdf (8.57 Mo) Télécharger le fichier
Loading...

Dates et versions

pastel-00568759 , version 1 (23-02-2011)

Identifiants

  • HAL Id : pastel-00568759 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More