Programmation dynamique

Infos
Inventée par le professeur Richard Bellman, la programmation dynamique permet de résoudre au moyen d'un ordinateur tout problème d'optimisation dont la fonction objectif se décrit comme la somme de fonctions monotones non-décroissantes des ressources. Concrètement, cela signifie que l'on va pouvoir déduire la solution optimale d'un problème à partir d'une solution optimale d'un sous problème.
Programmation dynamique

Inventée par le professeur Richard Bellman, la programmation dynamique permet de résoudre au moyen d'un ordinateur tout problème d'optimisation dont la fonction objectif se décrit comme la somme de fonctions monotones non-décroissantes des ressources. Concrètement, cela signifie que l'on va pouvoir déduire la solution optimale d'un problème à partir d'une solution optimale d'un sous problème.

Utilisation

La programmation dynamique est très souvent applicable dans un cadre industriel pour deux raisons :
- la nature additive de la monnaie
- la loi des rendements décroissants sur la plupart des postes de production Quelques exemples concrets :
- Optimiser la production d'un bassin minier en fonction des ressources sur chaque puits
- Optimiser le nombre de consommateurs touchés par une campagne publicitaire en répartissant le budget sur différents médias, ou au contraire en le concentrant (média-planning). C'est la programmation dynamique — et non des considérations de respect des riverains d'un aéroport — qui conduisit à faire monter les avions civils et militaires le plus rapidement possible jusqu'à leur altitude de croisière. Cette technique montre en effet que c'est ce qui minimise tant la consommation générale de carburant que la rentabilisation du capital de l'appareil.

Application algorithmique

Le problème des skieurs constitue une application : il s'agit de distribuer m skis à n skieurs (m>n) en minimisant les écarts de taille entre les skis et les skieurs. La propriété d'optimalité des sous-structures (si une distribution est optimale, alors toute sous partie des skis et des skieurs est optimale) le rend traitable par programmation dynamique. Le problème du sac à dos (knapsack en anglais) est un problème classique de recherche opérationnelle qui est NP-complet, mais qui est résolu de manière pseudo-polynomiale à l'aide d'un algorithme de programmation dynamique. Un autre exemple est le calcul de la distance de Levenshtein. ==
Sujets connexes
Algorithme de Viterbi   Calcul des variations   Distance de Levenshtein   Invariant   Loi des rendements décroissants   Monnaie   Problème du sac à dos   Recherche opérationnelle   Richard Bellman   Théorie de la complexité   Théorème fondamental  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^