Programmation dynamique


Programmation dynamique

La programmation dynamique est une technique algorithmique pour optimiser des sommes de fonctions monotones croissantes sous contrainte.

Elle a été désignée par ce terme pour la première fois dans les années 1940 par Richard Bellman. Elle s'applique à des problèmes d'optimisation dont la fonction objectif se décrit comme « la somme de fonctions monotones croissantes des ressources ».

Elle a d'emblée connu un grand succès, car la plupart des fonctions économiques de l'industrie étaient de ce type : maximisation du tonnage de charbon (ou de barils de pétrole) produit à partir de plusieurs puits à budget donné, par exemple.

Sommaire

Principe

La programmation dynamique s'appuie sur un principe simple : toute solution optimale s'appuie elle-même sur des sous-problèmes résolus localement de façon optimale[1]. Concrètement, cela signifie que l'on va pouvoir déduire la solution optimale d'un problème en combinant des solutions optimales d'une série de sous problèmes. Les solutions des problèmes sont étudiées 'de bas en haut', c'est-à-dire qu'on calcule les solutions des sous-problèmes les plus petits pour ensuite déduire petit à petit les solutions de l'ensemble.

Par exemple pour optimiser la production de 30 puits à budget donné, on optimise la gestion de 2 puits pour tout budget inférieur ou égal[2], puis on considère l'ensemble comme un puits unique et on ajoute les puits suivants un par un.

Un autre exemple est le problème du sac à dos.

Utilisation

La programmation dynamique est très souvent applicable dans un cadre industriel pour deux raisons :

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-difficile, mais qui est résolu de manière pseudo-polynomiale à l'aide d'un algorithme de programmation dynamique.

le Problème du rendu de monnaie dans le cas général

il permet aussi de calculer la plus longue sous-suite commune entre deux chaines

Un autre exemple est le calcul de la distance de Levenshtein.

Articles connexes

La programmation dynamique a, compte-tenu de ses nombreux succès, fait disparaître du programme de la plupart des écoles d'ingénieurs une partie des mathématiques qui visait au même résultat par d'autres moyens : le calcul des variations.

Le temps d'exécution d'un algorithme de programmation dynamique peut être calculé grâce au théorème fondamental.

Martelli a démontré en 1976 que tout algorithme de programmation dynamique pouvait se ramener à la recherche du plus court chemin dans un graphe (A. Martelli. An application of heuristic search methods to edge and contour detection. Comm. ACM, 19(2):73--83, February 1976). Or, les techniques de recherche heuristique basées sur l'algorithme A* permettent d'exploiter les propriétés spécifiques d'un problème pour gagner en temps de calcul. Autrement dit, il est souvent plus avantageux d'exploiter un A* que d'utiliser la programmation dynamique.

Notes et références

  1. Attention : l'inverse n'est pas vrai en général et un ensemble de sous-solutions chacune optimale ne garantit pas un résultat général lui-même optimal
  2. par valeurs discrètes pour des raisons pratiques, mais un millier de valeurs sont en général suffisantes

Voir aussi

Articles connexes

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Programmation dynamique de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Programmation dynamique — ● Programmation dynamique méthode d optimisation due au mathématicien américain Richard Bellman. (Un programme optimal de décisions séquentielles est tel que, quels que soient l état initial et la décision initiale, les décisions suivantes… …   Encyclopédie Universelle

  • programmation dynamique — dinaminis programavimas statusas T sritis automatika atitikmenys: angl. dynamic programming vok. dynamische Programmierung, f rus. динамическое программирование, n pranc. programmation dynamique, f …   Automatikos terminų žodynas

  • Langage de programmation dynamique — Cet article traite d une classe des langages de programmation. Pour la méthode consistant en la réduction du temps d exécution d un algorithme, voir programmation dynamique On utilise le terme langage de programmation dynamique en informatique… …   Wikipédia en Français

  • PROGRAMMATION — Un ordinateur est une machine universelle pour le traitement de l’information. Il doit pouvoir être utilisé aussi bien pour des calculs numériques que pour la gestion d’un stock de pièces détachées ou des travaux de secrétariat. Il est donc… …   Encyclopédie Universelle

  • PROGRAMMATION MATHÉMATIQUE — La programmation mathématique consiste à chercher, parmi tous les points x vérifiant certaines conditions du type: celui ou ceux qui rendent minimal (ou maximal, suivant le cas) un certain critère f (x ), qui sera interprété comme un gain dans le …   Encyclopédie Universelle

  • Programmation mathématique — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour …   Wikipédia en Français

  • Programmation non linéaire — Optimisation (mathématiques) En mathématiques, l optimisation est l’étude des problèmes qui sont de la forme : Étant donné : une fonction d’un ensemble A dans l ensemble des nombre réels Rechercher : un élément x0 de A tel que pour …   Wikipédia en Français

  • Programmation (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Informatique La programmation informatique est l ensemble des activités qui permettent l écriture des programmes informatiques. On distingue… …   Wikipédia en Français

  • Dynamique — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Dynamique », sur le Wiktionnaire (dictionnaire universel) Le mot dynamique est souvent employé pour… …   Wikipédia en Français

  • Programmation Web — Wikibooks propose un ouvrage abordant ce sujet : Programmation Web …   Wikipédia en Français