Recherche opérationnelle
Le plus court chemin
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 11 : Le plus court chemin
Le principe d’optimalité
L’observation de Bellman
L’énoncé
Tout sous-chemin d’un plus court chemin est lui-même un plus court chemin.
Si le trajet optimal de A à F passe par E, alors sa portion de A à E est le trajet optimal de A à E.
La démonstration tient en une phrase
S’il existait un meilleur chemin de A à E, on l’utiliserait pour raccourcir le trajet complet — qui ne serait donc pas optimal.
C’est ce principe qui permet de construire la solution de proche en proche, au lieu d’énumérer tous les chemins.
L’algorithme de Dijkstra
Le déroulement
Les trois règles
- Attribuer une marque provisoire +\infty à tous les sommets, 0 à l’origine.
- Définitiver la plus petite marque provisoire.
- Depuis ce sommet, mettre à jour les marques de ses successeurs, et recommencer.
La mise à jour
d(j) \;\leftarrow\; \min\big(\,d(j),\ d(i) + \ell(i,j)\,\big)
On conserve aussi le prédécesseur retenu, pour pouvoir remonter le chemin à la fin.
Une condition à ne pas oublier
Dijkstra exige des longueurs positives ou nulles.
Avec une valeur négative — une subvention, un gain sur un trajet —, définitiver la plus petite marque n’est plus sûr : un détour pourrait faire mieux.
Le calcul sur le réseau
Étape par étape depuis A
| Étape | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Départ | \mathbf{0} | \infty | \infty | \infty | \infty | \infty |
| Depuis A | — | 4 | \mathbf{2} | \infty | \infty | \infty |
| Depuis C | — | \mathbf{4} | — | \infty | 5 | \infty |
| Depuis B | — | — | — | 14 | \mathbf{5} | \infty |
| Depuis E | — | — | — | \mathbf{9} | — | 14 |
| Depuis D | — | — | — | — | — | \mathbf{14} |
La lecture du résultat
Le chemin optimal
A \to C \to E \to F \qquad 2 + 3 + 9 = \mathbf{14 \text{ km}}
Les deux mises à jour instructives
Depuis B, D reçoit 4 + 10 = 14. Depuis E, il reçoit 5 + 4 = 9 : la marque s’améliore, et le prédécesseur de D devient E.
Depuis D, F recevrait 9 + 11 = 20, plus que les 14 déjà acquis : la marque ne bouge pas.
Ce que l’algorithme a évité
Il a définitivé six sommets en six étapes. L’énumération aurait exploré tous les chemins possibles.
Le gain est de l’ordre exponentiel contre quadratique : O(n^2) pour Dijkstra, contre un nombre de chemins qui explose avec la taille.
Les autres algorithmes
Bellman-Ford
Quand les longueurs peuvent être négatives
On relâche tous les arcs, n-1 fois de suite, sans se soucier de l’ordre.
Complexité O(n \times m) : plus lent que Dijkstra, mais il accepte les valeurs négatives.
Un bonus
Si une n-ième passe améliore encore une marque, c’est qu’il existe un circuit de longueur négative.
Le problème n’a alors pas de solution : on peut tourner indéfiniment en gagnant. L’algorithme détecte l’absurdité au lieu de boucler.
Le plus long chemin
Un changement de signe
Remplacer \min par \max dans la mise à jour.
Cela n’a de sens que sur un graphe sans circuit — sinon le plus long chemin est infini.
Pourquoi cela nous intéressera
La durée d’un projet est la longueur du plus long chemin dans le graphe des tâches : il faut attendre la plus lente des séquences.
C’est exactement le chemin critique du chapitre 13.
Les usages
Au-delà de la distance
Ce que la valuation d’un arc peut représenter
| Valuation | Le plus court chemin donne |
|---|---|
| Kilomètres | l’itinéraire le plus court |
| Minutes | l’itinéraire le plus rapide |
| Dirhams | le trajet le moins cher |
| -\log(\text{fiabilite}) | le trajet le plus sûr |
La dernière ligne mérite un mot
Le chemin le plus fiable maximise un produit de probabilités. Or maximiser un produit revient à minimiser la somme des -\log.
Un problème multiplicatif devient additif par changement d’échelle : c’est la même astuce que le passage aux rendements logarithmiques en finance.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Principe d’optimalité : tout sous-chemin d’un chemin optimal est optimal.
- Dijkstra définitive la plus petite marque, puis met à jour les successeurs.
- Il exige des longueurs positives ou nulles.
- Sur notre réseau : A \to C \to E \to F, soit 14 km.
- Bellman-Ford accepte les valeurs négatives et détecte les circuits absorbants.
- Le plus long chemin sur un graphe sans circuit donnera la durée d’un projet.
La suite
Le chapitre 12 change de question. On ne cherche plus le meilleur trajet d’une unité, mais combien d’unités le réseau peut absorber à la fois.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)