Année Académique2022-2023

EXPOSE
MODULE : RECHERCHE OPERATIONNELLE

THEME :

PROGRAMMATION

DYNAMIQUE

Niveau : licence 3
Filière : Génie industriel
Option : Tronc commun

Formateur : Alex MOUKANGALA

 LISTE DES PARTICIPANTS
KOUMBA IBOUANGA Julio S

2
 PLAN

INTRODUCTION ............................................................................................. 4
I. GENERALITES ............................................................................................... 5
A. DEFINITION DES CONCEPTS.................................................................. 5
B. PRINCIPE DE LA PROGRAMMATION DYNAMIQUE ......................... 5
II. OBJECTIF DE LA PROGRAMMATION DYNAMIQUE ......................... 5
III. TYPES DE PROGRAMMATION DYNAMIQUE ..................................... 5
1. LA PROGRAMMATION DYNAMIQUE DETERMINISTE ..................... 6
2. LA PROGRAMMATION DYNAMIQUE STOCHASTIQUE (ENCORE
APPELE PROGRAMMATION DYNAMIQUE PROBABILISTES) ............. 6
IV. Notation ......................................................................................................... 6
V. TRAVAIL A FAIRE ..................................................................................... 7
PRISE DE RECUL .......................................................................................... 15
CONCLUSION ................................................................................................ 15
BIBLIOGRAPHIE ........................................................................................... 16

3
 INTRODUCTION

La Recherche opérationnelle (R.O.) est une méthodologie quantitative d'aide à la

décision caractérisée par la modélisation, la simulation et l'optimisation. Parmi
les méthodes de la recherche opérationnelle on distingue la programmation
dynamique. Cette dernière est une méthode algorithmique pour résoudre des
problèmes d'optimisation. Ce concept a été introduit par Bellman, dans les années
50, pour résoudre typiquement des problèmes d’optimisation. Le but de cet
exposé est de permettre à un futur technicien de comprendre certaine base de la
Programmation Dynamique en R.O. et être capable de modéliser une question
industrielle en modèle mathématique en utilisant la programmation dynamique.
Dans la suite de travail, nous développerons les points suivants : Définition,
objectif, principe et différentes méthodes de la programmation dynamique.

4
 I. GENERALITES
A. DEFINITION DES CONCEPTS
Programmation : c’est l'ensemble des activités qui permettent l'écriture des
programmes. Dans le cadre de l’étude, il indique un plan d’action
Dynamique : se dit d’une variable dont le type est susceptible de changer au cours
de l’exécution, au gré du type des valeurs qui y sont rangées successivement. Ici
il s’étend comme le découpage en phases du problème.
Programmation dynamique : c’est une méthode algorithmique qui permet de
résoudre des problèmes d’optimisation dont les décisions doivent être prise de
manière séquentielle, ceci à l’aide du principe d’optimalité de Bellman.

B. PRINCIPE DE LA PROGRAMMATION DYNAMIQUE

La programmation dynamique s'appuie sur le principe d'optimalité de Bellman
qui est le suivant : « Une politique optimale est composée de sous-politiques
susceptibles de faire partie d’une politique optimale ». En d’autres termes, une
solution optimale d'un problème s'obtient en décomposant un problème en
plusieurs sous problèmes qui auront chacun une solution et dont la combinaison
des solutions optimales de ces sous problèmes constituent la solution optimale du
problème.

II. OBJECTIF DE LA PROGRAMMATION DYNAMIQUE

Son but étant de minimiser un coût (ou, de manière équivalente, maximiser un
profit), associée à la suite de décisions retenues et à leurs conséquences. La
programmation dynamique a pour objectif de trouver le meilleur compromis entre
ces objectifs en ordonnant à chaque étape les décisions selon la somme d’un coût
immédiat et de l’espérance des coûts avenir, supposant alors que les décisions
futures sont prises de manière optimale.

III. TYPES DE PROGRAMMATION DYNAMIQUE

Pour résoudre des problèmes d’optimisation, on tient compte du système du
problème. Les systèmes rencontrés en programmation dynamique sont : le
système stochastique et le système déterministe. Ainsi, selon le type de système,
on distingue deux types de programmation dynamique : La programmation
dynamique déterministe et la programmation dynamique stochastique. Les deux
types de programmation s’identifient au même principe (principe d’optimalité de
Bellman).

5
 1. LA PROGRAMMATION DYNAMIQUE DETERMINISTE
On parle de programmation dynamique déterministe lorsqu’il est question
d’appliquée la programmation dynamique sur les systèmes déterministes. Dans ce
type de problème, il n’existe pas de dépendances à des paramètres aléatoires. On
part d'un état initial à un seul état final.

2. LA PROGRAMMATION DYNAMIQUE STOCHASTIQUE

(ENCORE APPELE PROGRAMMATION DYNAMIQUE
PROBABILISTES)
La programmation dynamique stochastique est une programmation appliquée sur
les systèmes stochastiques. Dans la plupart des problèmes réels, on est amené à
prendre en compte l’incertain. Le processus fait intervenir non plus seulement les
choix du décideur mais également une part d’incertitude liée à des paramètres
extérieurs. Ici, on part d'un état initial pour plusieurs états finaux. Dans ce cadre,
une période se divise en deux phases successives : une décision, puis
l’intervention du hasard qui détermine l’état dans lequel on va se trouver à la fin
de cette période. Nous considérons que, étant donnés un état et une décision, le
hasard est la donnée d’un ensemble d’états susceptibles d’être atteints et d’une
probabilité pour chacun d’eux qu’ils soient effectivement atteints. Ainsi, cela
revient à considérer une fonction de transition non plus déterministe mais
aléatoire.

IV. Notation
La notation utilisée en programmation dynamique est la suivante :
• t= étape
• St= état de départ de l’étape t
• xt= décision stratégique pour passer à l’état t+1
• f*t(st)= valeur optimale pour les étapes ultérieures
• x*t = la politique optimale pour l’étape courante de sorte que l’on a que :

f*t (st)=ft(st,x*t)

6
 V. TRAVAIL A FAIRE

Observation : tout sous -sac d’un sac optimal est lui-même optimal
• Supposons une solution optimal S contenant l’objet k.
• Alors S contient aussi une solution optimal au problème de sac dos restreint
aux objets (1,…,k-1,k+1,…,n) .

Conclusion : Le sac à dos possède une propriété semblable au problème du plus

court chemin : une solution optimale est constituée avec les solutions optimales
de problèmes restreints.

7
Modèle de chemin : le sac à dos

8
9
10
 Problème du voyageur
Un voyageur traverse l’ouest de l’Amérique. Son point de départ et sa destination
sont connus. Il effectue son voyage en quatre étapes. A chaque étape, il a le choix
de se diriger vers plusieurs états. A la figure 1, on a représenté chaque état par un
cercle. Son état de départ est l’état 1 et son état d’arrivée est l’état 10. Le voyageur
souscrit à chaque étape une police d’assurance dont le coût reflète le degré
d’insécurité du voyage. Ceux-ci sont indiqués au-dessus des arcs à la figure 1. Il
va donc déterminer son itinéraire de manière à choisir la route la plus sûre en
minimisant la somme des polices d’assurance pour le passage d’état en état.
Notez d’abord que l’approche très simple qui consiste à choisir à chaque étape la
police là moins chère ne conduit pas à une solution globalement la moins chère.
Il existe une méthode permettant d’évaluer toutes les routes possibles. Cependant
sur ce petit exemple, elles sont déjà au nombre de 18 et lorsque le nombre d’étape
et/ou le nombre d’états croit, cela devient vite un travail prohibitif

Figure : Problème du voyageur

Une autre méthode serait d’évaluer toutes les routes possibles. Cependant sur ce petit exemple,
elles sont déjà au nombre de 3×3×2 = 18 et lorsque le nombre d’étapes et/ou le nombre d’états
croît, cela devient vite un travail prohibitif.
C’est ici qu’intervient la programmation dynamique qui permet de calculer la solution
optimale sans faire de l’énumération explicite. La programmation dynamique commence
avec une petite portion du problème original, trouve la solution optimale pour cette portion
du problème. Ensuite on élargit progressivement le problème, en déterminant la nouvelle
solution optimale à partir de la précédente. Pour le problème du voyageur, on considère le
problème de fin de voyage, lorsqu’il n’y a plus qu’une étape à faire. Pour ce problème la
solution optimale est évidente : le voyageur doit aller directement à sa destination, l’état 10. A
l’itération suivante, on élargit d’une unité le nombre d’étapes à effectuer. On peut ensuite
déduire la stratégie optimale pour la troisième étape en fonction de la stratégie optimale pour
la dernière étape.

11
En programmation dynamique, deux types de variables sont associées à chaque
étape. La variable st indique l’état du système au début de l’étape t. Cette variable
doit contenir toute l’information résultant des choix effectués aux étapes
précédentes. La variable xt indique la décision stratégique prise à l’étape t. Ainsi,
dans notre exemple, notons st l’état de départ de l’étape t tandis que x t note la
destination de l’étape t.
On note par ft (st, xt) le coût total de la meilleure stratégie pour les étapes restantes,
si l’on se trouve au début de l’étape t dans l’état du système st et que l’on prend
xt comme décision stratégique à l’étape t. Notons par x*t la valeur de xt qui
minimise ft (st, xt) et ft* (st) la valeur minimum correspondante. On a donc que :

f*t (st)= min ft(st, xt) = ft(st, x*t)

Ainsi, dans notre exemple, ft (st, xt) note le coût total de la meilleure stratégie pour
les étapes restantes si le voyageur est dans l’état st à l’étape t et sélectionne comme
état suivant l’état xt
La programmation dynamique va déterminer successivement f*4 (s4), f*3 (s3), f*2
(s2), f*1 (s1) pour chaque état possible st à l’étape t et utiliser par exemple f*2 (s2)
pour calculer f*1 (s1).
Nous allons maintenant appliquer ceci à l’exemple du voyageur. Pour t = 4, c’est-
`a-dire lorsque le voyageur n’a plus qu’une étape à effectuer pour rejoindre sa
destination, sa route est entièrement déterminée par son état courant s4 (ici s4 = 8
ou 9) et sa destination finale x4 = 10. Le tableau 1 reprend les coûts
minimaux de la dernière étape ainsi que la décision optimale en fonction de l’état
de départ.

Tableau : Coûts minimaux de la dernière étape

12
Lorsque le voyageur a encore deux étapes à effectuer (t = 3), la solution requière
un peu plus de calculs. Si, par exemple, le voyageur est dans l’état 5, il peut aller
à l’étape 3 vers l’état 8
ou 9 à un coût respectif de c5,8 = 1 ou c5,9 = 4. S’il choisit l’état 8, le coût
additionnel qu’il va encourir pour rejoindre sa destination à partir de l’état 8 es
t donné dans la table 10.1, il s’agit de f*4 (8) =3, de sorte que son coût total est de
1 + 3=4. Semblablement, s’il choisit l’état 9, il devra additionner 4 + 4=8. Et donc
l’´état qu’il va choisir comme destination est l’état 8, donc x*3 = 8, qui donne un
coût minimum pour le chemin qui reste à parcourir de f*3 (5) = 4. On procède de
même pour les autres états possibles à l’étape 3, c’est-`a-dire les états s3 = 6 et
s3 = 7 et on obtient les valeurs données dans le tableau 1.
La solution pour le problème où il reste trois étapes (t = 2) est obtenue de manière
similaire. Elle est illustrée à la table 10.3. Les états destination sont cette fois au
nombre de trois : il s’agit de x2 = 5, x2 = 6 ou x2 = 7 tandis que les états de départ
possibles sont s2 = 2, s2 = 3 ou s2 = 4. Pour les états de départ 2 ou 4, la
destination optimale peut être au choix 5 ou 6 puisque le coût total est le même.

Tableau : Coûts minimaux de la troisième étape

Tableau : Coût minimaux de la deuxième étape

Enfin, pour terminer, le problème de première étape (t = 1), le coût minimum de la police
optimale est à nouveau donné en fonction de l’état destination de l’étape comme la somme du
coût de première étape plus le coût minimum des étapes ultérieures. On obtient les résultats de
la table 10.4.

13
 Tableau : Coût minimaux de la première étape
On peut maintenant identifier une politique optimale. Pour t = 1, le voyageur doit donc se
diriger initialement vers l’état 3 ou 4. Supposons qu’il choisisse x*1 = 3. Pour t = 2, la stratégie
optimale pour s2 = 3 est x*2 = 5 (voir tableau 10.3), ce qui dans l’étape t = 3 conduit à l’état
s3= 5. La stratégie optimale pour s3 = 5 consiste à choisir x*3 = 8 (voir tableau 10.2). On se
retrouve en s4 = 8 et on choisit x*4 = 10 à l’étape 4 (voir tableau 10.1). Une des routes optimales
est donc 1 → 3 → 5 → 8 → 10 donnant un coût total minimum de f*1 (1) = 11.
On peut résumer la solution dans le tableau suivant :

Tableau : Solution finale

14
 PRISE DE RECUL

Nous avons appris :

➢ une nouvelle methodes de la recherche operationnelle
➢ à resoudre un probleme de programmation dynamique
Comme difficulté :
➢ Pas d’unité au sein du groupe, il y a diversité de filières et les emploies du
temps ne nous permettaient pas de tous se retrouver.
➢ Problème de salle
➢ Apres les cours nous ne pouvions travailler suite à la fermeture des classes et
de l’école
➢ Enfin, la dernière difficulté rencontrée était sur la compréhension de
Résolution d’un problème de programmation dynamique car celle-ci est
différente de la programmation linéaire apprise en classe et fait appel à des
connaissances en mathématiques mais avec de nombreux efforts, de la
motivation nous avons fini par comprendre comment résoudre un problème
de programmation dynamique.

CONCLUSION
Nous voici au terme de notre exposé qui a porté essentiellement sur la
programmation dynamique. Outre l’introduction et la conclusion, il s’est articulé
en deux (2) grands points : GENERALITES et RESOLUTION DES
EXERCICES. Nous avons retenu que la programmation dynamique est l’une des
méthodes les plus utilisées en recherche opérationnelles, son objectif est de
résoudre des problèmes d'optimisation, son principe consiste à diviser le
problème en sous problème. La difficulté est d’interpréter le problème ensuite
affecter aux variables propres à la programmation dynamique. Aux vues des deux
(2) exercices précédemment traités, Il se trouve qu’une classe générale de
problèmes d’optimisation satisfait le principe d’optimalité de Bellman.
Nous pouvons dire que la programmation dynamique est efficace car son
formalisme est assez générique ce qui laisse libre cours à des multiples variantes
et à la résolution des problèmes assez divers.

15
 BIBLIOGRAPHIE
(1) RECHERCHE OPERATIONNELLE ET ORGANISATION
SCIENTIFIQUE DU TRAVAIL
(2) Programmation dynamique Wikipédia
(3) Cours 5 : algorithmique programmation dynamique
(4) UNIVERSITE DU LITTORAL/ Maîtrise AES / Recherche opérationnelle
/ Daniel DE WOLF / Dunkerque, Septembre 2003
(5) RECHERCHE OPERATIONNELLE : Programmation dynamique,
chaines de Markov/ Ecole des Mines de Nancy 2013-2014

16