Résumé en français

L'optimisation combinatoire probabiliste est un nouveau domaine de recherche; elle permet de mieux appréhender les problèmes concrets souvent soumis à des phénomènes aléatoires. Nous proposons dans cette Note des résultats relatifs au problème du stable probabiliste. Nous étudions deux stratégies de modification; nous montrons que la fonctionnelle associée à l'une se calcule en temps polynomial et trouvons alors la solution a priori la maximisant; après avoir donné plusieurs expressions de la fonctionnelle associée à l'autre, nous montrons que cette fonctionnelle ne peut pas être calculée en temps polynomial et en donnons un encadrement.