Chapitre 2

Programmation dynamique
Introduction
La programmation dynamique est applicable à de nombreux problèmes d’optimisation avec
contraintes linéaires ou non linéaires, en variables continues ou discrètes, possédant une certaine
propriété dite de décomposablité. Le terme « Programmation dynamique » provient du fait que la
méthode a d’abord été appliquée à l’optimisation des systèmes dynamiques c.à.d. évoluant au
cours du temps. Cependant le principe de la PD est plus général et peut s’appliquer à des
problèmes d’optimisation où le temps n’intervient pas, comme pour la PLNE.
L’idée de base de la PD consiste à essayer de remplacer l’optimisation d’une fonction à n
variables par la résolution d’un certain nombre de problèmes d’optimisation, plus simple à
résoudre (par exemple l’optimisation d’un problème à une seule variable). En ce sens la méthode
peut être reconsidérée comme une méthode de décomposition.
La PD est dû à Bellman qui fait premier à formuler le principe d’optimalité : « Dans une
séquence optimale de décisions quel que soit la première décision prise, les décisions
subséquentes forment une sous-séquence optimale, compte tenu des résultats de la première
décision »
Avant de présenter le formalisme de la programmation dynamique, nous présentons dans ce qui
suit un exemple illustratif expliquant le principe du raisonnement de la programmation
dynamique.
Exemple illustratif : Problème de gestion de stocks
Le tableau suivant donne, pour les 5 périodes qui font l’objet de l’étude, les quantités d’un
certain bien qu’un marchant veut revendre, ainsi que les prix d’achat unitaires.

Période i 1 2 3 4 5
Demande 2 3 4 3 2
Prix 13 15 20 11 12

Sachant que ce marchant dispose d’une capacité de stockage de 5 unité ( le coût de stockage est
nul), le problème consiste à déterminer la politique d’achat optimal, c’est-à-dire qu’on cherche à
déterminer les quantités à acheter à chaque période de manière à minimiser le coût total d’achat
sur les 5 périodes. De plus on a :
1. Les achats se font en début de chaque période
2. On doit stocker les ventes de la période en cours
3. On commence et on finit avec un stock nul
4. Les quantités achetées sont nécessairement entières
Posons : = quantité achetée à la période ( j ∈ N, j = 1,5)

= quantité restant en stock à la fin de la période

 est appelée variable d’état. Elle décrit l’état du système à la fin de la période

est appelé variable de décision. Les variables et doivent donc satisfaite :

i. 0≤ ≤ 5 - j=1,2,…,5 (1) et (2)

ii. = =0
iii. = + -

Le problème précédent peut donc être formulé comme un PLNE :

( ) ∑

(P)

{ ∈

Dans ce qui suit, nous résolvons (P) en décomposant le problème séquentiellement en plusieurs sous-
problèmes de la manière suivante ; Nous nous intéressons dans un premier lieu à la première période
seulement, puis nous cherchons une politique optimale d’achat sur les deux premières périodes, et ainsi de
suite. A l’étape k de la résolution, nous nous intéressons au sous problème restreint aux k premières
périodes. En d’autres termes, à l‘étape k de résolution, le problèmes est restreint aux k premières variables
seulement, jusqu’à arriver au problème initiale.
1ière période :
En vertu de (i), la 1ière période peut être terminée soit avec 0,1,2 ou 3 unités en stock (ie = 0,1,2 ou 3).
Les coûts correspondants sont respectivement 26, 39, 52 et 65 (exemple si =0, = 2 et =2)
2ième période :
Si on veut terminer la deuxième période avec 0 unité en stock :
=0 : on distingue alors 4 cas :

 =5 =0( ) c= 65+0= 65
 =4 =1( ) c= 52+15= 67
 =3 =2( ) c= 39+30= 69
 =2 =3( ) c= 26+45= 71
On voit bien que la meilleure décision à prendre si on veut terminer la 2ième période avec stock nul est
d’acheter 5 unités à la 1ière période et 0 unité à la seconde.
De même, si on veut terminer la seconde période ace 1 unité , la meilleure stratégie à prendre est
la suivante : =5 ( ), =1 de coût c= 65+15=80
On obtient ainsi la sous-politique optimale à choisir dans la 2ième période est la suivante :
Si =0 ( ) ( ) c=65
Si =1 ( ) ( ) c=80
 Si =2 ( ) ( ) c=95
De la même façon on déduit la sous politique optimale à entreprendre lors de la 3ième période (0≤ ≤ 1) :

 Si =0 ( , , )= (5,2,2) c=95+40=135
 Si =1 ( , , )= (5,2,3) c=95+60=155
Le tableau suivant résume les 5 sous-politiques optimales pour les 5 périodes. La politique optimale est
bien sûr celle correspondante à la 5ième période (avec un stock nul bien-sûr)
Période Coûts
cumulés
1ière 2 0 2 / / / / 26
période 1 3 / / / / 39
2 4 / / / / 52
3 5 / / / / 65
2ième 3 0 5 2 / / / 65+0=65
période 1 5 1 / / / 65+15=80
2 5 2 / / / 65+30=95
3ième 4 0 5 2 2 / / 95+40=135
période 1 5 2 3 / / 95+60=155
4ième 3 0 5 2 2 3 / 135+33=168
période 1 5 2 2 4 / 135+44=179
2 5 2 2 5 / 135+55=190
5ième 2 0 5 2 2 5 0 190+0=190
période

La politique optimale est donc : =5, =2, =2, =5, =0

Le coût total= 190
Rappelons que problème précédent peut être formulé comme un PLNE :

( ) ∑

(P)

{ ∈

Le dernier peut être décomposé (sur les 5 périodes) en cinq sous-problèmes ( )

( ) ∑

(α)

{ ∈
Notons que la résolution de ( ) revient à chercher une sous-politique optimale sur les k premières
périodes sachant qu’on veut terminer la kième période avec un stock de α unités. ((P) ( )). Nous
fixons donc d’abord la valeur de puis nous résolvons (α) pous chaque valeur fixée de
Pour k=1 par exemple, en posant ( )= valeur de la fonction objectif de ( ), on a , nous
avons donc quatre sous problèmes :
( ) ( )
( ){ avec

Notons que la méthode de résolution précédente est basée sur la relation de récurrence qui existe entre
ces sous problèmes.

Résolution du problème de gestion de stock en utilisant les graphes : Algorithme de Bellman

Le problème de gestion de stock précédent peut être modélisé par un graphe orienté pondéré :
G= (V,E) tel que : V ={(i, ) i=1,5 et ∈ {0,1,2,3}} avec et 0

((i, ) ( )) ∈ ssi j=i+1 et

Nous associons à chaque arc ((i, ) ( )) un poids ( ).

Il s’agit bien sûr de trouver un plus cours chemin du sommet initial (0.0) vers le sommet final (5,0), qui
correspond au problème initial.
Le graphe est sans circuit, nous appliquons l’algorithme de Bellman :
Nous rappelons dans ce qui suit le principe de cet algorithme :
Algorithme de Bellman : (graphe sans circuit)
Soit G=(V,E) un graphe orienté sans circuit pondéré muni d’une distance

(où , poids associé à l’arête e )

Soit s un sommet source sans prédécesseur.
( ) Représente (la plus courte) distance de s à x

Algorithme de Bellman
Début
Marquer le sommet : ( )
Tant qu’il des sommets non marqués, dont tous les prédécesseurs ont été marqués faire :
o Marquer un tel sommet « le noter y »
o ( ) ∈ ( )* + = Min { ( )+ d(x,y)}
Fin Tant que
Fin

Dans notre cas : ( ) , ( ) ( )-

Le chemin optimal est : (0,0)-(1,3)-(2,2)-(3,0)-(4,2)-(5,0)

Qui correspond à la politique optimale :
Remarques :
1. Le premier exemple de ce chapitre montre clairement que toute solution du problème posé est une
suite de 5 décisions ( ), où chaque décision représente l’achet pour la période i.
Par ailleurs, il est aussi clair que chaque décision prise à la période i ne dépend au fait que de l’état du
stock à la fin de la période i-1. Donc on a ici un processus de décision séquentiel (PDS), où le futur ne
dépend que du présent et non pas du passé, schématisé comme suit :
Fin de période1 Fin de période2 Fin de période3 Fin de période4 Fin de période5

Etat Etat du Etat du Etat du Etat du Etat

initial du stock stock stock stock final du
stock stock
0 1 23 0 1 2 0 1 0 1 2
0 0
étape1 étape2 étape3 étape4
2. Nous supposons que dans toute la suite de ce chapitre on ne s’intéressera qu’aux problèmes
d’optimisation combinatoire, dont la modélisation sous la forme d’un PDS est faisable, donc
justifiable par la programmation dynamique.

Fonctionnement de la programmation dynamique

Quelques notions fondamentales associées à un PDS (systèmes évolutifs)

Considérons un PDS en n étapes modélisant un certain problème d’optimisation combinatoire dont le
critère (objectif) est une minimalisation et évoluant d’un état initial vers un état final
Pour chaque étape , on définit deux ensemble et , ainsi que deux application et où :
: ensemble des décisions que l’on peut prendre à l’étape k
: ensemble des états dans lesquels le système se trouve à la fin de l’étape k
:
( ) ( )
( ) coût associé à la prise de décision quand le système se trouve dans l’état à la
fin l’étape k-1.
:
( ) ( )

: étant la fonction de transition qui assure le passage du système d’un état à un autre quand une
décision est prise
 Application au problème de gestion de stock
Ces différentes notions appliquées à l’exemple introductif sont :
n=5 (cinq étapes : une pour chaque période d’achat)
Pour la période k :
achats possibles pour la période k
états possible du stock à la fin de la période k
Posons : * +

:
( )

:
( ( )

Représentation d’un PDS par schéma

Entrées

Etape 1 sorties sortiesk-1

Etape sorties Etape k so

Coût : ( ) Coût : ( )

Le but rechercher dans PDS est l’établissement d’une stratégie, basée sur une séquence de
décision
{ + tel que ∑ ( ) soit minimale avec :

{
( )
Théorème
Toute sous-politique d’une séquence optimale est aussi optimale
Preuve
On utilise le raisonnement par l’absurde. Supposons le contraire (ie. Il existe une sous-politique
d’une politique optimale, mais qui n’est pas optimale).
Soit ( ) * + une politique optimale d’un PDS à n étapes (problème de
minimisation dans notre cas), et

( ) * + { + une sous-politique optimale de ( )

Supposons maintenant qu’il existe une sous-politique non optimale

( ) { } { + de ( )

Notons par ( ( )) d’une politique non optimale d’un état , et

par ( ( )), le cout d’une politique optimale d’un état . Alors an a :

C( ( ) C( ( ) ( ( )) ( ( )) ( ( ) ( ( ))
( ( ))

Impossible ( ( )) ( ( )).

Remarque :
Un PDS est donc caractérisé par l’hypothèse de Markov (le futur ne dépend que du présent) et
par la propriété de Markov, appelée aussi principe de l’optimalité (théorème précèdent).
Ces 2 caractéristiques facilitent le calcul du coût de la politique optimale par le biais de relations
de récurrence dites : récurrence avant ou récurrence arrière.
Relations de récurrences :
Récurrence avant :
Notons par ( ) le coût d’une politique optimale d’un état vers un état , qui est aussi
le coût du plus court chemin d’un graphe approprié d’un nœud vers un nœud .
( )= C ( ( )) où
( ) * + et ( )
Le calcul de ( ) se fera de façon récursive en utilisant la relation suivante dont la validité
est due au principe d’optimalité d’un PDS
( ) *( ) ( )* ( ) ( +
{
( )

( ) : coût d’une politique optimale d’un état vers un état

= solution optimale de la restriction du problème posé aux k premières étapes =
solution optimale du sous-problème du problème initial.
Exemple :
Reprenons le premier exemple de ce chapitre, ainsi que son modèle linéaire.