Cours de recherche opérationnelle I

Ce cours couvre les notions fondamentales de la recherche opérationnelle, destinées aux étudiants en mathématiques appliquées, informatique, gestion et ingénierie. Il présente les concepts clés, les applications industrielles, les outils mathématiques et informatiques, ainsi que la programmation linéaire avec un exemple concret et une introduction à l’algorithme du simplexe.

Introduction à la Recherche Opérationnelle

La recherche opérationnelle (RO), aussi appelée science de la décision, est une discipline qui vise à produire les meilleures décisions possibles dans des systèmes complexes. Elle utilise des modèles mathématiques, des statistiques et des algorithmes pour aider à la planification, à l’optimisation, à la simulation et à la rationalisation des systèmes industriels et économiques.

La RO se situe à l’intersection des mathématiques et de l’informatique, notamment en algorithmique avancée manipulant des structures comme les graphes et les polyèdres. Elle s’appuie aussi sur la théorie de la complexité algorithmique pour évaluer la faisabilité des solutions.

Les outils de la RO permettent de :

• trouver des solutions là où l’homme ne peut pas ou ne sait pas en trouver,
• juger la qualité des solutions,
• confirmer et justifier des décisions.

Applications de la Recherche Opérationnelle

La RO s’applique à de nombreux domaines :

• Conception, configuration et exploitation de systèmes techniques complexes (réseaux de communication, systèmes d’information).
• Gestion de la chaîne logistique : transports, production, stocks.
• Gestion stratégique d’investissements.
• Domaines variés tels que la santé, l’éducation, la voirie, la distribution de courrier, la production et le transport d’énergie, les télécommunications, les banques et les assurances.

Exemples concrets :

• Problème du voyageur de commerce (TSP) : trouver la tournée la plus courte pour visiter un ensemble de villes.
• Problèmes de transport : optimiser la distribution de marchandises entre entrepôts et clients en minimisant les coûts.
• Problèmes de mariages stables : affecter des candidats à des postes ou des étudiants à des écoles en respectant les préférences mutuelles et en assurant la stabilité des appariements.

Exemple : Mariages stables

Considérons trois femmes (Alice, Bénédicte, Camille) et trois hommes (Elie, François, Gondran) avec des préférences respectives :

Femmes	Préférences	Hommes	Préférences
Alice (A)	Gondran (G), Elie (E), François (F)	Elie (E)	Alice (A), Bénédicte (B), Camille (C)
Bénédicte (B)	François (F), Elie (E), Gondran (G)	François (F)	Bénédicte (B), Camille (C), Alice (A)
Camille (C)	Gondran (G), Elie (E), François (F)	Gondran (G)	Alice (A), Camille (C), Bénédicte (B)

Un couplage est instable s’il existe un couple (A, B) non marié ensemble qui se préfèrent mutuellement à leurs conjoints actuels. Par exemple :

• F est mariée avec G, G est marié avec F,
• F préfère G à son conjoint actuel g,
• G préfère F à son conjoint actuel f.

Questions clés :

• Comment vérifier qu’un couplage est stable ?
• Existe-t-il toujours un couplage stable ?
• Peut-on trouver un couplage stable lorsqu’il existe ?

Outils de la Recherche Opérationnelle

La recherche opérationnelle utilise plusieurs outils mathématiques et informatiques :

• Programmation linéaire (PL) : optimisation d’une fonction linéaire sous contraintes linéaires.
• Optimisation combinatoire (OC) : recherche de la meilleure solution parmi un ensemble fini mais très grand d’alternatives.
• Graphes : modélisation de réseaux, chemins, ordonnancement, compatibilité.
• Files d’attente, stochastique, simulation : modélisation de phénomènes aléatoires et dynamiques.

Programmation linéaire : définition et exemple

La programmation linéaire consiste à maximiser ou minimiser une fonction objectif linéaire :

max (ou min) z = c1x1 + c2x2 + ... + cnxn

soumise à des contraintes linéaires :

a11x1 + a12x2 + ... + a1nxn ≤ b1
a21x1 + a22x2 + ... + a2nxn ≤ b2
...
am1x1 + am2x2 + ... + amnxn ≤ bm

avec les variables xj ≥ 0.

Exemple : culture de courgettes et navets

Variables de décision :

• xc : surface cultivée en courgettes (m²)
• xn : surface cultivée en navets (m²)

Objectif : maximiser la production totale en poids :

max z = 4xc + 5xn

Contraintes liées aux ressources :

• Engrais A disponible : 8 unités, avec 2 unités nécessaires par m² de courgettes, 1 unité par m² de navets
• Engrais B disponible : 7 unités, avec 1 unité nécessaire par m² de courgettes, 2 unités par m² de navets
• Anti-parasites disponible : 3 unités, 1 unité nécessaire par m² de navets

Formulation des contraintes :

2xc + xn ≤ 8
xc + 2xn ≤ 7
xn ≤ 3
xc ≥ 0, xn ≥ 0

Interprétation géométrique

Chaque contrainte définit un demi-plan dans R² :

• 2x + y ≤ 8
• x + 2y ≤ 7
• y ≤ 3
• x ≥ 0, y ≥ 0

L’ensemble des solutions réalisables est l’intersection de ces demi-plans, formant un polyèdre convexe.

Les lignes de niveau de la fonction objectif sont des droites parallèles définies par :

4x + 5y = constante

L’optimum, s’il existe, est atteint sur un sommet (point extrême) du polyèdre.

Bases et points extrêmes en programmation linéaire

Le domaine admissible est un polyèdre défini par les contraintes linéaires. La solution optimale se trouve toujours sur un sommet de ce polyèdre.

Pour manipuler algébriquement les contraintes, on passe souvent à la forme standard :

• Maximisation
• Variables non négatives
• Contraintes sous forme d’égalités en ajoutant des variables d’écart (slack variables)

Par exemple, les contraintes :

2x + y ≤ 8
x + 2y ≤ 7
y ≤ 3

deviennent :

2x + y + e1 = 8
x + 2y + e2 = 7
y + e3 = 3
x, y, e1, e2, e3 ≥ 0

où e1, e2, e3 sont des variables d’écart représentant la différence entre la contrainte et la limite.

L’algorithme du simplexe (aperçu)

L’algorithme du simplexe est une méthode efficace pour résoudre les problèmes de programmation linéaire. Il exploite le fait que l’optimum se trouve sur un sommet du polyèdre des solutions admissibles et explore ces sommets de manière systématique jusqu’à trouver la solution optimale.

Historique :

• Années 30-40 : Kantorovitch introduit les modèles linéaires pour la planification.
• Années 40-50 : Dantzig développe l’algorithme du simplexe.
• Application historique : ravitaillement de Berlin durant le blocus (1948-1949) avec des milliers de variables.
• Depuis, la programmation linéaire est largement utilisée dans l’industrie grâce à des logiciels performants (CPLEX, Excel, etc.).

Glossaire des termes clés

• Recherche Opérationnelle (RO) : discipline scientifique qui étudie la meilleure façon de résoudre des problèmes complexes de gestion et d’optimisation.
• Programmation Linéaire (PL) : méthode d’optimisation d’une fonction linéaire sous contraintes linéaires.
• Optimisation Combinatoire (OC) : recherche de la meilleure solution dans un ensemble fini mais très grand d’alternatives.
• Polyèdre : ensemble convexe défini par l’intersection de demi-espaces (contraintes linéaires).
• Variable d’écart (slack variable) : variable ajoutée pour transformer une inégalité en égalité dans la programmation linéaire.
• Simplexe : algorithme qui explore les sommets du polyèdre des solutions admissibles pour trouver l’optimum.
• Couplage stable : appariement entre deux ensembles (ex : hommes et femmes) où aucun couple non marié ne préfère mutuellement être ensemble plutôt qu’avec leur conjoint actuel.

Points clés à retenir

• La recherche opérationnelle aide à prendre des décisions optimales dans des systèmes complexes.
• Elle combine mathématiques, informatique et modélisation pour résoudre des problèmes industriels et économiques.
• La programmation linéaire est un outil fondamental, avec des méthodes efficaces comme l’algorithme du simplexe.
• Les solutions optimales de PL se trouvent toujours sur les sommets du polyèdre des contraintes.
• Les problèmes de mariages stables illustrent l’importance de la stabilité dans les appariements et ont des applications pratiques en économie et gestion.
• La RO est largement utilisée en France et dans le monde, avec des entreprises, laboratoires et logiciels dédiés.