Programmation dynamique
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (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...) est très souvent applicable dans un cadre industriel pour deux raisons :

  • la nature additive de la monnaie (Le Théâtre de la Monnaie (De Munt en néerlandais) est la salle d'opéra de Bruxelles situé sur la place 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de consommateurs touchés par une campagne (La campagne, aussi appelée milieu rural désigne l'ensemble des espaces cultivés habités, elle s'oppose aux concepts de ville, d'agglomération ou...) publicitaire en répartissant le budget (Un budget est un document comptable prévisionnel distinguant les recettes et les dépenses.) sur différents médias (On nomme média un moyen impersonnel de diffusion d'informations (comme la presse, la radio, la télévision), utilisé pour communiquer. Les médias permettent...), ou au contraire en le concentrant (média-planning).

C'est la programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de...) dynamique (Le mot dynamique est souvent employé désigner ou qualifier ce qui est relatif au mouvement. Il peut être employé comme :) — et non des considérations de respect des riverains d'un aéroport (Un aéroport est l'ensemble des bâtiments et des installations d'un aérodrome qui servent au trafic aérien d'une ville ou d'une région. Ces...) — qui conduisit à faire monter les avions civils et militaires le plus rapidement possible jusqu'à leur altitude (L'altitude est l'élévation verticale d'un lieu ou d'un objet par rapport à un niveau de base. C'est une des composantes géographique et biogéographique...) de croisière. Cette technique montre en effet que c'est ce qui minimise tant la consommation générale de carburant (Un carburant est un combustible qui alimente un moteur thermique. Celui-ci transforme l'énergie chimique du carburant en énergie mécanique.) que la rentabilisation du capital de l'appareil.

Application algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus...)

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 (En anatomie, chez les animaux vertébrés parmi lesquels les humains, le dos est la partie du corps consistant en les vertèbres et les côtes. Les dorsaux étaient les muscles les plus sollicités par les singes...) (knapsack en anglais) est un problème classique de recherche opérationnelle (La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l'ensemble des méthodes et techniques rationnelles d'analyse et de synthèse des phénomènes d'organisation utilisables pour élaborer...) 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.

Page générée en 0.096 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique