Quand une décision en entraîne d'autres, on peut résoudre le problème à reculons : d'abord la dernière étape, puis l'avant-dernière, jusqu'à la première. Une seule idée, celle de Richard Bellman (1957), suffit pour remplacer des milliards d'essais par quelques centaines de calculs.
L'idée en une phrase : la meilleure façon de finir le voyage ne dépend que de l'endroit où l'on se trouve, pas du chemin qui y a mené. On peut donc calculer, pour chaque endroit, la meilleure fin de parcours, une fois pour toutes, en partant de l'arrivée.
La vague de calcul remonte de l'arrivée vers le départ : chaque ville reçoit le coût du meilleur trajet qui la relie à l'arrivée. Puis le meilleur itinéraire se lit d'un seul coup, en avançant.
Les exemples sont inventés. Les résultats sont calculés sur place dans votre navigateur et confrontés à une seconde méthode : l'examen de toutes les possibilités, ou la simulation. La programmation dynamique est déjà apparue dans ce cahier (sac à dos, tarifs, ressources) ; cette page en présente la méthode elle-même.
Planche 1
Décomposer un problème en étapes
Un transporteur va de Départ à Arrivée en traversant quatre régions, avec trois villes-relais possibles dans chacune. Chaque tronçon a un coût. Il y a 3 × 3 × 3 × 3 = 81 itinéraires. Plutôt que de tous les essayer, on découpe le voyage en étapes : une étape = le passage d'une région à la suivante.
Le nombre dans chaque ville : le coût du meilleur trajet de cette ville jusqu'à l'arrivée, calculé en remontant. Trait vert : la meilleure décision depuis chaque ville. Rouge : le meilleur itinéraire complet.
–
Coût du meilleur itinéraire–
Contrôle : meilleur des itinéraires énumérés–
Itinéraires possibles–
Additions faites par la programmation dynamique–
Ce qu'il faut retenir. Avec n régions de 3 villes, il y a 3ⁿ itinéraires, mais seulement 9 tronçons par étape à examiner, soit environ 9n additions. À 12 régions : 531 441 itinéraires contre une centaine d'additions. Le travail n'explose plus, il croît comme le nombre d'étapes. C'est tout l'intérêt de la décomposition.
Planche 2
États, décisions et transitions
Pour écrire une programmation dynamique, il faut répondre à quatre questions. Cliquez sur une ville de la figure pour voir les réponses sur un cas concret.
Étape tLe moment où l'on décide : ici, la région où l'on se trouve.
État sCe qu'il faut savoir pour décider la suite : ici, la ville. Rien d'autre.
Décision dCe que l'on choisit : la ville suivante.
TransitionLe nouvel état après la décision : la ville choisie, et un coût c(s, d).
Valeur ft(s)Le meilleur coût restant, depuis l'état s à l'étape t.
Récurrenceft(s) = mind [ c(s, d) + ft+1(d) ], et f = 0 à l'arrivée.
Cliquez sur une ville (état). Ses décisions possibles sont en orange, avec le calcul de chaque option.
–
Problème
Étape
État
Décision
Transition
Itinéraire
Région
Ville
Ville suivante
On y est, on paie le tronçon
Renouvellement (planche 4)
Année
Âge de la machine
Garder ou remplacer
Âge + 1, ou 1 après remplacement
Budget (planche 5)
Projet examiné
Budget restant
Montant donné au projet
Budget restant diminué
Stock (planche 5)
Semaine
Stock en début de semaine
Quantité commandée
Stock + commande − demande (aléatoire)
Ce qu'il faut retenir. Le choix de l'état est le cœur de la méthode. Il doit résumer tout le passé utile : si deux histoires différentes mènent au même état, la suite optimale doit être la même. Trop pauvre, l'état fait échouer la méthode (planche 3) ; trop riche, il fait exploser le nombre de calculs.
Planche 3
Le principe d'optimalité de Bellman
« Une politique optimale a cette propriété que, quels que soient l'état initial et la première décision, les décisions restantes forment une politique optimale pour l'état qui en résulte. » Autrement dit : tout morceau de fin d'un trajet optimal est lui-même optimal. C'est ce qui autorise le calcul à reculons. Mais il ne vaut pas pour n'importe quel objectif.
Cliquez sur une ville du meilleur itinéraire (rouge). Tous les trajets de cette ville à l'arrivée sont essayés (gris) : le plus court est exactement la fin de l'itinéraire optimal (rouge épais).
Ville choisie : trajets jusqu'à l'arrivée–
Meilleur d'entre eux ; fin de l'itinéraire optimal–
Contrôle sur les 12 villes intermédiaires : écarts–
Changeons d'objectif. Chaque tronçon rapporte ou coûte (nombres signés), et le transporteur veut finir avec un solde le plus proche possible de zéro. La récurrence naïve garde, pour chaque ville, la fin de trajet dont le solde est le plus proche de 0. Mais une fin « mauvaise » peut compenser un début « mauvais » : le meilleur morceau n'est plus le bon morceau.
Orange : la solution de la récurrence naïve. Bleu : la vraie meilleure, obtenue en ajoutant à l'état le solde déjà accumulé. Les nombres sur les tronçons sont signés.
Récurrence naïve : |solde| final–
État enrichi (ville, solde) : |solde| final–
Contrôle : 81 itinéraires énumérés–
États enrichis créés–
Ce qu'il faut retenir. Le principe tient quand le coût s'additionne étape par étape et que l'avenir ne dépend que de l'état : c'est le cas des sommes, des produits de probabilités, des maxima. Avec |solde|, la valeur de la fin dépend du début : l'état « ville » ne suffit plus. Le remède est général : enrichir l'état avec ce qu'il manque, ici le solde déjà accumulé. On paie en nombre d'états (122 au lieu de 14), mais la méthode redevient exacte.
Planche 4
Calcul d'une politique optimale : le renouvellement d'équipements
Une entreprise possède une machine. Chaque année, elle peut la garder (l'entretien coûte de plus en plus cher avec l'âge) ou la remplacer (on paie une neuve, moins la revente de l'ancienne). Au bout de 8 ans, on revend ce qu'on a. La programmation dynamique ne donne pas seulement un plan : elle donne une politique, c'est-à-dire la bonne décision pour chaque âge possible à chaque année, même dans les situations que le plan n'atteint pas.
La politique : une case par année (colonne) et par âge de la machine (ligne). Vert : garder. Rouge : remplacer. Le nombre : le coût restant optimal ft(âge), en k€. Le chemin bleu suit la machine depuis l'âge initial. Cliquez sur une case pour y placer la machine.
Coûts annuels selon l'âge : entretien (orange), qui monte, et prix net d'un remplacement, neuf moins revente (bleu), qui baisse. Remplacer devient intéressant quand l'écart de l'avenir le justifie.
Remplacer seulement à 7 ans ; remplacer chaque année–
Ce qu'il faut retenir. Le tableau est calculé de droite à gauche : la dernière année d'abord, où l'on sait ce que vaut chaque âge à la revente, puis chaque année précédente grâce à la suivante. Une fois rempli, il répond à toutes les questions : si la machine tombe en panne et qu'on en achète une d'occasion de 3 ans, il suffit de lire la bonne case. Remarquez aussi l'effet d'horizon : la politique change à l'approche de la fin. En année 6, on remplace dès 3 ans, pour finir avec une machine jeune, qui se revend bien ; dans les deux dernières années, au contraire, on garde jusqu'à 5 ou 6 ans, car une machine neuve n'aurait plus le temps de servir.
Planche 5
Deux exemples : répartir un budget, gérer un stock
Le même schéma s'applique à des problèmes qui ne ressemblent pas à des trajets. Dans le premier, les étapes sont des projets ; dans le second, les semaines, et la demande est aléatoire.
Une collectivité répartit 10 tranches de 100 k€ entre quatre projets. Chaque projet rapporte selon ce qu'il reçoit (tableau). Certains rapportent vite puis plafonnent, d'autres demandent un gros effort avant de rapporter. Étape = projet, état = budget restant, décision = tranches données au projet.
Gain de chaque projet selon les tranches reçues. Points pleins : la répartition optimale. Points creux : la règle « donner chaque tranche au projet qui rapporte le plus tout de suite ».
Répartition optimale (projets 1 à 4)–
Gain optimal–
Règle « meilleur gain immédiat »–
Contrôle : répartitions énumérées–
Un magasin gère un article sur 12 semaines. Chaque lundi, il voit son stock et décide combien commander (livraison immédiate). La demande de la semaine est aléatoire, de moyenne 4. Commander coûte un forfait K plus 2 € par unité ; garder une unité coûte 1 € par semaine ; une vente manquée coûte 12 €. Étape = semaine, état = stock, décision = quantité, transition = stock + commande − demande. On minimise le coût moyen.
La politique optimale : pour chaque semaine (colonne) et chaque stock (ligne), le niveau atteint après commande. Blanc : on ne commande pas. Couleur : on commande jusqu'au niveau indiqué. Une forme apparaît, sans qu'on l'ait demandée.
Une saison simulée avec la politique optimale : stock au fil des semaines (bleu), commandes (flèches vertes), ventes manquées (rouge). Elle se renouvelle toute seule.
Semaine 1 : seuil s ; niveau S–
Coût moyen prévu sur 12 semaines (stock initial nul)–
Contrôle : 40 000 saisons simulées–
Règle simple « compléter à 4 chaque semaine »–
Semaines où la politique a la forme (s, S)–
Ce que montrent ces deux exemples. Pour le budget, la règle gloutonne rate l'optimum (38 contre 46) car elle ne voit pas que le projet 2 rapporte beaucoup une fois lancé ; la programmation dynamique, elle, regarde toutes les répartitions sans les énumérer. Pour le stock, le hasard ne gêne pas la méthode : on remplace le coût par sa moyenne, et la récurrence reste la même. Mieux, elle découvre une règle simple que personne ne lui a imposée : si le stock tombe à s ou moins, commander jusqu'à S ; sinon, ne rien faire. C'est la politique (s, S), dont Herbert Scarf a démontré l'optimalité en 1960. Le forfait K crée l'écart entre s et S : mettez-le à 0 : s et S se rapprochent (6 et 7), et l'on commande presque chaque semaine, juste ce qu'il faut.
Ce qu'il faut garder
Découper
Des étapes, des états, des décisions, des transitions. Le bon état résume tout le passé utile, et rien de plus.
Remonter
La valeur d'un état se calcule à partir des valeurs de l'étape suivante. Le principe de Bellman le permet quand le coût s'additionne ; sinon, on enrichit l'état.
Décider partout
Le résultat est une politique : la bonne décision dans chaque situation, y compris imprévue. Avec le hasard, elle reste calculable, et prend souvent une forme simple.
Pour aller plus loin
Dans ce cahier.Le problème du sac à dos (programmation dynamique sur la capacité), La gestion du rendement tarifaire (prix-plancher par programmation dynamique), Répartir une ressource entre plusieurs activités, Les stocks et la chaîne d'approvisionnement, Le voyageur de commerce (Held-Karp), Le plus court chemin (Bellman-Ford).
Sur les calculs. Itinéraire : coûts entiers tirés au hasard. Renouvellement : entretien 8 k€ la première année, multiplié chaque année par (1 + hausse) ; revente à 80 % du prix neuf, moins 25 % par an ; au plus 7 ans d'âge. Stock : demande de Poisson de moyenne 4, tronquée à 12 ; stock limité à 25 ; ventes manquées perdues ; aucune valeur au stock restant après 12 semaines. Le contrôle du stock rejoue la politique calculée sur 40 000 saisons tirées au hasard.