ODDI_01-12-2024

Optimisation Dynamique et Décision dans l’Incertain
M1 ERO (2024=2025)
Plan du cours
Introduction
1 Exemples introductifs.
2 Les fondements théoriques de la programmation dynamique.
3 Exemple d’application de la programmation dynamique.
4 Programmation dynamique dans l’incertain.
5 Conclusion.
6 Annexes.
Références
[1] R. Faure, B. Lemaire, C. Picouleau. "Précis de recherche opérationnelle : Méthodes et exercices
d’application" - Masters, écoles d’ingénieurs. Editeur : Dunod, 08/07/2009 (6e édition).
[2] M. Goudran et M. Minoux, "Graphes et algorithmes", Ayrolles 95.
[3] J.L. Lauriere, "Eléments de programmation dynamique", Masson 82.
[4] Michel Minoux. "Programmation Mathématique, Théorie et algorithmes", volume 2, Collection

Technique et Scienti…que des Télécommunications. Bordas et CNET - ENST, Paris, France,
1983.
[5] M. Sakarovitch . "Optimisation combinatoire : Programmation discrète". Editeur : Broché,

21 octobre 1997.
[6] L.A. Wolsey, "Integer programming", Wiley interscience 98.

Optimisation Dynamique et Décision dans l’Incertain (ODDI) ERO (M1) (2024/2025)
Introduction.
La Recherche opérationnelle propose des méthodes scienti…ques pour l’application des méthodes
scienti…ques à la résolution des problèmes de gestion a…n d’aider à la prise de meilleures décisions.
L’idée est de développer et d’utiliser des outils mathématiques et informatiques pour maîtriser
les problèmes complexes. La recherche opérationnelle se présente comme une "boîte à outils",
un ensemble d’"objets" qu’il faut savoir combiner a…n de modéliser puis résoudre un problème
concret. Un de ses outils fondamentaux est la programmation dynamique.
En 1944, Pierre MASSÉ1 utilisait une méthode pour plani…er les investissements d’électricité de
France. Cette méthode n’a pas eu l’intérêt qu’elle méritait à cette époque, malgré son e¢ cacité en
optimisation, vue la relation étroite qu’elle présentait avec l’économie. Le célèbre mathématicien
américain Richard BELLMAN2 fût le premier, à formuler son principe d’optimalité le cœur de
cette méthode, à savoir
"dans une séquence optimale de décisions,

quelle que soit la première décision prise,
les décisions suséquentes forment une sous-séquence optimale,
Pierre MASSÉ compte tenu des résultats de la première décision". Richard Ernest BELLMAN
1898-1987
1920-1984
Il la désigna par la programmation dynamique 3 pour la première fois dans les années 1940.
Le terme programmation dynamique peut paraître un peu étrange et est maintenant parfois utilisé
dans un autre sens ; il repose sur le fait que les di¤érentes valeurs sont mises à jour dynamiquement.
La programmation dynamique n’est pas un algorithme, mais plutôt une technique algorithmique
exacte qui permet de résoudre une catégorie particulière de problèmes d’optimisation. Elle se
caractérise par une méthode de résolution, appliquant le principe d’optimalité, Aussi, l’adjectif
"dynamique", qui donne une image avantageuse de cette technique, s’explique par le fait qu’il
s’agit d’une méthode d’optimisation applicable pour des problèmes possédant une structure dite
de décomposabilité (somme de fonctions monotones non décroissantes) nécessitant une séquence
de décisions corrélées entre elles. Chaque décision transforme la situation actuelle en une nouvelle
situation. Une séquence de décisions, qui dans un ordre produit une séquence de situations, est à
établir pour optimiser une certaine valeur4 . Notons que l’algorithme de Bellman, appliqué pour
la recherche des chemins optimaux dans des graphes orientés sans circuit, est un de ses algorithmes.
La programmation dynamique est séduisante de son formalisme assez générique, ce qui laisse
libre cours à de multiples variantes et à la résolution de problèmes assez variés, qu’ils soient
déterministes ou non. Cependant, seuls les problèmes d’optimisations séquentielles sont concernées
et la véri…cation de l’applicabilité du principe d’optimalité est indispensable avant tout appel de
cette méthode. La di¢ culté réside dans la caractérisation des problèmes susceptibles d’être traités
par cette méthode. Aussi, la programmation dynamique s’applique pour certains problèmes, où
le temps n’intervient pas explicitement, mais il est nécessaire pour cela qu’on puisse - d’une manière
plus ou moins arti…cielle - les décomposer en étapes.
1
P. Massé. Le choix des investissements. Dunod, Paris, 1959.
2
J.C. Culioli (article dans la Recherche 2003), raconte que R. Bellman, alors chercheur à la Rand Corporation,
devait rendre des comptes au secrétaire à la Défense de l’époque qui ne supportait ni le mot “recherche”, ni le
mot “mathématiques”; Richard Bellmann a alors choisi ce nom dans un souci de “marketing”: il lui a semblé que
l’utilisation des termes “programmation” et “dynamique” donnait à son travail une apparence qui plairait à son
supérieur.
3
Le terme et le concept ont été introduits pour résoudre des problèmes d’a¤ectation et d’optimisation (recherche
opérationnelle) dans les années 50.
4
La valeur d’une séquence de décisions est généralement égale à la somme des valeurs des décisions et situations
séparément dans la séquence.
Equipe pédagogique : KAHOUL nawel 2

1 Exemples introductifs.
Nous commençons cette section par introduire, à travers des exemples, les idées essentielles de
la programmation dynamique (retrouvées sous une forme plus générale, dans la prochaine section).
1.1 Le triangle de Pascal.

n n!
On veut calculer les coe¢ cients binomiaux Cnk = = .
k k! (n k)!
Rappellons que
8
< n 1 n 1
n + pour 0 < k < n
Cnk = = k 1 k
k : si k = 0 ou k = n
1
La fonction ci-contre, est un algorithme Fonction cnk (n; k : naturel) : NaturelNonNul

n précondition(s) n > k
récursif qui permet de calculer .
k début
si k = 0 ou k = n alors retourner 1 ;
sinon retourner cnk(n 1; k 1) + cnk(n 1; k).
finsi
fin
Voyons l’exécution de cette fonction sur un exemple donné:
n = 5 et k = 3.
2
Remarquez, dans l’arbre ci-contre le nombre de fois, par exemple que le terme noté 2,1 ,
1
est calculé.

n
1.1.1 Résolution du problème du calcul de par la programmation dynamique.
k
La programmation dynamique est un paradigme de conception, qu’on peut voir comme étant
une adaptation ou une amélioration de la méthode diviser-régner, dans le sens où une solution
recherchée d’un problème dépend des solutions précédentes obtenues pour ses sous-problèmes.
C’est une méthode itérative qui calcule tout d’abord les résultats de base pour les assembler et ainsi
calculer le résultat recherché. Il faut (au moins tenter) d’utiliser la programmation dynamique
lorsque les sous-problèmes ne sont pas indépendants et/ou la complexité de l’algorithme naïf
est elevé (non polynomial). L’utilisation d’un tableau pour le stockage des valeurs calculées qui
pourront être réutilisées, est plus que souhaitée.
n
Pour notre problème "calcul du nombre binomial ", a…n d’éviter le calcul d’un nombre
k
plusieurs fois, l’idée est de créer un tableau où on calcule tous les nombres de petites tailles,
ensuite, déduire ceux de tailles de plus en plus grandes avant d’arriver au nombre désiré.
Pour ce faire, on procède comme suit :
Nouvelle_Fonction cnk (n; k : naturel) : NaturelNonNul
précondition(s) n > k et n 6 max _N et k 6 max _K
Déclaration i; j : Naturel
b : Tableau[0 : : : max _N ][0 : : : max _K] de
NaturelNonNul
début
pour i 0 à n faire
pour j 0 à min(i; k) faire
si i = j ou j = 0 alors
b[i; j] 1
sinon
b[i; j] b[i 1; j 1] + b[i 1; j]
finsi
finpour
finpour
retourner b[n; k]
fin
5
Pour le calcul de , on a le tableau suivant :
3 j
!
0 1 2 3 4 5
0 1
1 1 1
i# 2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
5
3
Remarque. Pour obtenir le triangle de Pascal, il su¢ t de remplacer l’expression min(i; k) par
min(i; n), dans l’algorithme Voir l’exemple ci-dessus.

1.2 Le problème de retour monnaie.

1.2.1 Position du problème.
On dispose de pièces de monnaies de valeurs v1 , v2 ,..., vn . On cherche à savoir le nombre minimal
de pièces à utiliser pour rendre une somme donnée M et la répartition des pièces correspondantes.
1.2.2 Formalisation mathématique.

Formalisons un peu ce problème avec quelques notations mathématiques :
Le système de pièces de monnaie peut être modélisé par un n-uplet d’entiers naturels S = (v1 ; v2 ; :::; vn ),
en supposant que v1 < v2 < < vn . Une somme à rendre est un entier naturel M .
Une répartition de pièces est un n-uplet d’entiers naturels x = (x1 ; x2 ; :::; xn ), où xj représente
le nombre de pièces de valeur vj .
8
Ceci revient à résoudre le programme linéaire en > P
n
>
< min xj
nombres entiers (PLNE) ci-contre : (P ) j=1
xj 2 N; 8j = 1; n
> Pn
>
: vj xj = M
j=1
En fait, la valeur de la solution optimale de (P ) sera ce nombre minimal de pièces et la solution

en elle-même la liste des pièces nous permettant de rendre la somme M .
Remarque. On peut ajouter l’hypothèse v1 = 1, pour garantir que le problème rendu monnaie
est toujours possible puisque la somme à rendre est entière, où la contrainte égalité signi…e juste
que l’on rend la bonne somme.
1.2.3 Résolution par la programmation dynamique.

Pour ce faire, pour k 2 [1; n] \ N et m 2 [0; M ] \ N, on dé…nit
C(k; m) : le nombre minimum de pièces pour produire exactement le montant m

en utilisant seulement des pièces de valeurs v1 ,..., vk .
8
> P
k
>
< min xj
j=1
En fait C(k; m) est la valeur optimale du PLNE (Pk;m ) xj 2 N; 8j = 1; k
>
> P
k
: vj xj = m
j=1
Ainsi, la réponse à notre problème est C(n; M ).
De plus, on montre aisément les formules récurrentes suivantes :
8
> C(k; 0) = 0; 8k[1; n] \ (
>
>
N
m m
>
> ; si 2N
>
< C(1; m) = min x1 =
m
v1 v1 8m 2 [0; M ] \ N
x1 = v +1; sinon
x 1
>
>
1
x1 2N
>
>
>
> C(k; m) = min
h i fxk + C(k 1; m vk xk )g ; 8k 2 [2; n] \ N; 8m 2 [0; M ] \ N
: x x 2 0; m \N
k k vk

1.2.4 Exemple numérique.

Supposons qu’on ait un montant de 8 et des pièces de valeurs : v1 = 1; v2 = 4 et v3 = 6.
m 0 1 2 3 4 5 6 7 8
v1 = 1 0 1 2 3 4 5 6 7 8
" " "
v2 = 4 0 1 2 3 1 2 3 4 2
v3 = 6 0 1 2 3 1 2 1 2 2
on rend deux pièces de valeur 4.
1.3 Le problème de la partition.

Dé…nition. On appelle problème de la partition le problème suivant :
Étant donnés n objets de poids entiers
p(a1 ); p(a2 ); :::; p(an );
est-il possible de les partager en deux ensembles de mêmes poids total ?

Sachant que les poids sont entiers, on voit immédiatement qu’une condition nécessaire pour que
ce soit possible est que la somme des poids des objets soit paire : 2P .
Remarque. Ce problème peut être considéré comme un cas particulier du problème de décision
associé au problème du sac à dos, dé…ni comme suit :
Étant donnés n objets, chaque objet i (1 i n) possédant un poids vi et une utilité ui , étant
donnés deux entiers K et M , est-il possible de trouver un sous-ensemble de ces objets dont le poids
total soit inférieur ou égal à M et la somme des utilités soit supérieure ou égale à K ?
En prenant vi = ui = p(ai ) pour tous les objets, avec
M = K = P = la demi-somme de tous les objets,
on reconnaît la forme générale du problème de la partition.
1.3.1 Résolution du problème de la partition par la programmation dynamique.

Nous allons plonger le problème dans une classe de problèmes dépendant de paramètres liés par
une relation de récurrence.
En premier, les objets de poids a1 ; :::; an sont classés.
On considère deux entiers i et j, avec 1 i n et 0 j P , et l’expression booléenne
T (i; j) : "étant donnés les i premiers objets, il existe un sous-ensemble de ces i éléments de poids j":
Ainsi, on remplit un tableau A ligne par ligne, qui contient les valeurs de T , dont les colonnes
(resp. les lignes) sont indexées par j (resp. i).
On représente la valeur "vrai" (resp. "faux ") par V (resp. F ).
Le problème de la partition admet une solution, si et seulement si A(n; p) vaut V .

Pour le remplissage de A :
- La première ligne de A (i = 1), correspondant à l’examen de a1 , est très facile à remplir.
En e¤et, les seuls éléments valant V correspondent à j = 0 et j = p(a1 ).
- Le passage d’une ligne à la suivante, se fait grâce aux formules récurrentes suivantes :
Si A(i 1; j) = V , alors A(i; j) = V ;

Si A(i 1; j p(ai )) = V , alors A(i; j) = V
En fait, nous avons énuméré tous les V de la ligne i. Autrement dit, on a les relations récurrentes:
A(i; j) = A(i 1; j) ou A(i 1; j p(ai )).
On considère le problème de partition pour les données suivantes :
n = 6; p(a1 ) = 5; p(a2 ) = 9; p(a3 ) = 3; p(a4 ) = 8; p(a5 ) = 2; p(a6 ) = 5.
Par conséquent, P vaut 16.

On applique la méthode de programmation dynamique dé…nie ci-dessus ; on obtient le tableau
suivant :
inj 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 V F F F F V F F F F F F F F F F F
2 V F F F F V F F F V F F F F V F F
3 V F F V F V F F V V F F V F V F F
4 V F F V F V F F V V F V V V V F V
5 V F V V F V F V V V V V V V V V V
6 V F V V F V F V V V V V V V V V V
À l’aide du tableau, on peut aussi reconstituer un choix possible pour la partition de l’ensemble
initial en deux sous-ensembles. En e¤et, on peut considérer que la valeur V de A(6; 16) provient de
celle de A(4; 16) (on ne prend donc ni l’objet 5 de poids 2, ni l’objet 6 de poids 5), qui provenait de
A(3; 8) (on prend l’objet 4 de poids 8), dont la valeur V provenait à son tour de A(2; 5) (on prend
l’objet 3 de poids 3), issue de A(1; 5) (ce qui amène à prendre en…n l’objet 1 de poids 5 mais
pas l’objet 2 de poids 9). La partition est donc possible avec les objets 1; 3 et 4, ou encore,
par complémentarité, à l’aide des objets 2; 5 et 6 (d’autres choix seraient aussi possible).

1.4 Le problème du sac à dos.

1.4.1 Résolution du problème du sac à dos généralisé.
Le problème du sac à dos étant une généralisation du problème de la partition, on peut s’inspirer
de ce qui a été fait plus haut.
Soit (P ) le problème du sac à dos généralisé suivant :
8 8
> Pn
> Pk
>
< max u j x j >
< max uj xj
j=1 j=1
(P ) P
n xj 2 N; 8j = 1; n (Pk;v ) xj 2 N; 8j = 1; k
>
> >
> Pk
: v x
j j M : vj xj v
j=1 j=1
On suppose que tous les coe¢ cients uj et vj sont des entiers strictement positifs.
En fait, on peut considérer (P ) comme étant un cas particulier de la famille des problèmes
(Pk;v ) 1 k n (notés ci-dessus), dé…nis pour 1 k n et 0 v M . On a en e¤et (P ) = (Pn;M ).
0 v M
Le plongement étant réalisé, il nous reste à trouver les relations de récurrence permettant de
résoudre les problèmes (Pk;v ) de proche en proche.
Notons par zk;v le maximum de (Pk;v ). En posant z0;v = 0, 0 v M , il vient :
v
zk;v = max fzk 1;v vk :xk + uk xk g ; où Xk = xk xk 2 N et 0 xk :
xk 2Xk vk
En e¤et, Xk contient toutes les valeurs possibles de xk . Une valeur de Xk étant attribuée à xk , on
peut considérer que zk;v est la somme de l’utilité associée en propre à xk , c’est-à-dire uk xk , et de
l’utilité maximum apportée par les k 1 autres variables pour un volume égal au volume laissé
libre par le choix de xk , à savoir v vk xk ; d’où le terme entre accolades dans l’expression de zk;v ,
v
0 xk . Ceci étant vrai pour toute valeur attribuée à xk , on prendra pour zk;v le maximum
vk
de ces termes quand xk décrit Xk .
1.4.2 Cas particulier de problèmes de "sac à dos".

Considérons le problème du sac à dos
8
> Pn
>
< max Z = cj xj
j=1
(KP ) Pn xj 2 f0; 1g; 8j = 1; n
>
> aj x j b
:
j=1
On suppose que tous les coe¢ cients aj (j = 1; n) sont entiers positifs et b un entier. Ainsi, le second
membre b doit être entier positif. Les coe¢ cients cj (j = 1; n) peuvent être des réels quelconques.
On notera, F la valeur optimale de (KP ), i.e
P
n
F =8 max 9 cj xj :
< P
n =j=1
x aj xj b et x2f0;1gn
: ;
j=1
L’idée de base de la programmation dynamique consiste à essayer de ramener la résolution du

problème (KP ), comportant n variables, à la résolution d’une suite de problèmes d’optimisation
à un nombre de variables inférieur (jusqu’à atteindre même une variable). Pour se faire, on va
e¤ectuer deux opérations:

1. On plonge le problème posé dans une famille de problèmes de même nature.

Le programme linéaire (KP ) peut être écrit (ce n’est pas l’unique possibilité) comme suit :
" #
Pn Pn
8 max 9 cj xj () 8 max 9 c1 x1 + cj xj
< P n = j=1 < Pn = j=2
x aj xj b et x2f0;1gn x a 1 x1 + aj xj b et x2f0;1gn
: ; : ;
j=1 j=2
2 3
6 !7
6 P
n 7
() max 6 max c1 x1 + cj xj 7
x1 2f0;1g 6 7
8 9
4< P
n = j=2 5
x0 a1 x1 + aj xj b et x0 2f0;1gn 1
: ;
j=2
2 3
6 !7
6 P
n 7
() max 6 c1 x1 + 8 max cj xj 7
x1 2f0;1g 6 7
9
4 < P n = j=2 5
0 x aj xj b a1 x1 et x0 2f0;1gn 1
: ;
j=2
Dans ce cas de (KP ), on considèrera, la famille des n(b + 1) problèmes

8 !
>
> Pn
>
< Fi (E) = max cj xj
j=i 1 i n
(KPi (E)) x j 2 f0; 1g; 8j = i; n
>
> Pn 0 E b
>
: aj x j b E
j=i
La valeur E, qui paramètre la famille de problèmes ci-dessus, est classiquement appelée

une variable d’états (lorsque cette quantité est vectorielle, elle est appelée vecteur d’états).
On remarque qu’il s’agit d’une quantité attachée aux contraintes du problème.
L’ensemble E = f0; 1; :::; bg des valeurs possibles de E est appelé l’espace d’états associé au
problème (on peut écrire E = fE=E = 0; 1; :::; bg).
Le problème (KP ) initial fait évidemment partie de la famille (prendre i = 1 et E = 0).
On a donc
F = F1 (0):
D’autre part, 8i = 1; 2; :::; n, on conviendra de noter :
8
< E<0
Fi (E) = 1 pour ou
:
E 0 lorsque (KPi (E)) n’a pas de solution (correspondant au cas E > b).

2. On cherche une relation de récurrence reliant entre les valeurs optimales de ces di¤érents problèmes.
Ceci revient à l’écriture de l’équation fonctionnelle reliant ces di¤érents problèmes. On a :
8 9
>
> >
>
> ( )>
>
>
P
n < P
n =
8 max 9 cj xj () max c1 x1 + 8 max 9 cj xj
< P n =j=1 x1 2f0;1g >
> < P n = j=2 >
>
x aj xj b et x2f0;1gn >
> x0 aj xj b a1 x1 et x0 2f0;1gn 1 >
>
: ; : : ; ;
j=1 j=2
P
n
Si on note F1 (0) = 8 max 9 cj xj , alors
< P
n =j=1
x aj xj b et x2f0;1gn
: ;
j=1
F1 (0) = max fc1 x1 + F2 (a1 x1 )g = max fF2 (0); c1 + F2 (a1 )g :

x1 2f0;1g
Ainsi, dans le cas de la famille (KPi (E))1 i n, on obtient aisément la relation de récurrence
Fi (E) = max fci xi + Fi+1 (E + ai xi )g
xi 2f0;1g
= maxfFi+1 (E); ci + Fi+1 (E + ai )g

Cette relation traduit simplement le fait que, dans une solution optimale (xi ; xi+1 ; :::; xn ) de
(KPi (E)), on doit avoir soit xi = 0, soit xi = 1, et que dans les deux cas, (xi+1 ; :::; xn ) doit
être solution optimale du problème restreint aux n i dernières variables.
Ainsi, pour toute valeur de E (0 E b), l’obtention de Fi (E) à partir des valeurs Fi+1 (E 0 )
(pour 0 E 0 b) se ramène à un problème d’optimisation élémentaire (la comparaison de
deux nombres).
La relation de récurrence obtenue permet alors de résoudre le problème posé par un algo-
rithme à n étapes.
Algorithme 1. (Résolution du problème du sac à dos par la programmation dynamique)

(a) Initialiser (étape n) ;
8E (0 E b) calculer 8 Fn (E) par :
< 0 pour E > b an ,
Fn (E) = cn pour E b an et cn 0,
:
0 pour E b an et cn < 0
(b) Pour i = n 1; n 2; :::; 2 successivement, calculer (étape i):
8E (0 E b) : Fi (E) = maxfFi+1 (E); ci + Fi+1 (E + ai )g,
(c) Etape 1 : Calculer F par :
F = F1 (0) = maxfF2 (0); c1 + F2 (a1 )g.
Notons que l’algorithme précédent permet, non seulement de résoudre le problème posé (KP ), mais
également, et moyennant très peu de calculs supplémentaires, tous les (KPi (E)) pour E = 0; 1; :::; b,
autrement dit, toute la famille de problèmes ne di¤èrant de (KP ) que par la valeur du second
membre de la contrainte. Il su¢ t de remplacer l’étape 1 par
(c) Etape 10 : Calculer pour E (0 E b) :
F1 (E) = maxfF2 (E); c1 + F2 (E + a1 )g.

1.4.3 Détermination d’une solution optimale x .

Algorithme 1 permet de déterminer la valeur optimale F de (KP ), mais malheureusement ne
fournit pas explicitement le vecteur x correspondant.
Néanmoins, pour obtenir x une première idée consiste simplement à dé…nir, à chaque étape i,
pour i = 1; 2; :::; n 1, de Algorithme 1, pour tout E (0 E b), les quantités xi (E) par
0 si Fi (E) = Fi+1 (E)

xi (E) =
1 si Fi (E) = ci + Fi+1 (E + ai )
et pour l’étape n
0 si Fn (E) = 0,
xn (E) =
1 si Fn (E) = cn
Une solution optimale x sera alors obtenue à la …n de Algorithme 1 par la procédure
Procédure 1.
(a) E 0,
(b) Pour i = 1; 2; :::; n successivement, faire
xi xi (E)
E E + ai x i
On voit que cette méthode nécessite le stockage d’un volume important d’informations, à savoir
les n(b + 1) quantités xi (E).
Exemple/Exercice.
8
> PN
>
< max Z = cj xj
j=1
On considère le problème de sac à dos (P ) xj 2 f0; 1g; 8j = 1; N
>
> PN
: aj x j b
j=1
(aj et b entiers (strictement) positifs).
1) Écrire l’équation fonctionnelle relative à la résolution de ce problème par la programmation
dynamique.
2) Résoudre l’exemple numérique suivant :
max Z = 2 x1 + x2 + 3 x3
(P ) xj 2 f0; 1g; 8j = 1; 3
2 x1 + 3 x2 + x3 5

Solution de l’Exemple/Exercice.
1) Pour k 2 [1; N ] \ N; E 2 [0; b] \ N, on considère la séquence de problèmes (Pk;E ) k2[1;N ]\N , où
E2[0;b]\N
8
>
> P
N
>
< max Z = cj xj
j=k
(Pk;E ) xj 2 f0; 1g; 8j = k; N
>
> PN
>
: aj x j b E
j=k
L’équation fonctionnelle :
Fk (E) = maxfFk+1 (E); ck + Fk+1 (E + ak )g; 8k; 1 k N 1; E 2 [0; b] \ N:

8
< 0 pour E > b aN ,
FN (E) = cN pour E b aN et cN 0,
:
0 pour E b aN et cN < 0.
2) Application numérique : appel à Algorithme 1

(a) Initialisation (étape n = 3) : calcul de F3 (E), 8E (0 E 5) par
8
< 0 pour E > b a3 ,
F3 (E) = c3 pour E b a3 et c3 0, E2N
:
0 pour E b a3 et c3 < 0.
On a b a3 = 5 1 = 4 et c3 = 3 > 0
3 pour E 2 [0; 4]
F3 (E) = E2N
0 pour E > 4
(b) Pour k = 2, calcul de Fi (E), 8E (0 E 5) par
Fk (E) = maxfFk+1 (E); ck + Fk+1 (E + ak )g;
F2 (E) = maxfF3 (E); c2 + F3 (E + a2 )g = maxfF3 (E); 1 + F3 (E + 3)g

8 8
< maxf3; 1 + 3g pour E 2 [0; 1] < 4 pour E 2 [0; 1]
= maxf 3 ; 1 + 0g pour E 2 [1; 4] E 2 N = 3 pour E 2 [1; 4] E2N
: :
maxf0; 1 + 0g pour E > 4 1 pour E > 4
(c) Etape 1: calcul de F par
F = F1 (0) = maxfF2 (0); c1 + F2 (a1 )g = maxf4; 2+ 3 g = 5
Procédure 1.
(a) E 0
(b) x1 = x1 (0) = 1; E 0 + a1 x 1 = 2
x2 = x2 (2) = 0; E 2 + a2 x 2 = 2
x3 = x3 (2) = 1.

2eme méthode. Considérons, l’équation fonctionnelle pour (Pk;E ) k2[1;N ]\N , où

E2[0;b]\N
8
> P
k
>
< max Z = cj xj
j=1
(Pk;E ) xj 2 f0; 1g; 8j = 1; k
>
> Pk
: aj x j E
j=1
8
< E
c1 si 1 (pour x1 = 1)
Pour i = 1 F1 (E) = a1 E2N
: 0 sinon
8
< Fk (E) = maxfF 1 (E); ci + Fk 1 (E ak )g; pour 0 < E b; E 2 N
| k {z } | {z }
Pour k 2 (2 k n) xk =0 xk =1
:
F3 (b) = F
Application numérique :
F3 (5) = maxfF2 (5); c3 + F2 (5 a3 )g = maxfF2 (5); 3 + F2 (4)g

F2 (5) = maxfF1 (5); c2 + F1 (5 a2 )g F2 (4) = maxfF1 (4); c2 + F1 (4 a2 )g
= maxfF1 (5); 1 + F1 (5 3)g = maxfF1 (4); 1 + F1 (4 3)g
= maxfF1 (5); 1 + F1 (2)g = maxfF1 (4); 1 + F1 (1)g
F1 (5) = 2 F1 (2) = 2 F1 (4) = 2 F1 (1) = 0
F2 (5) = maxf2; 1 + 2g = 3 F2 (4) = maxf2; 1 + 0g = 2

F3 (5) = maxf3; 3 + 2)g = 5
x = (1; 0; 1)t ; Z = 5.

1.5 Programmation dynamique et problèmes de plus courts (plus longs)

chemins dans le graphe.
1.5.1 Problème du plus court (plus long) chemin par la programmation dynamique.
L’Algorithme 1 décrit ci-dessus pour le problème du sac à dos peut être interprété (et ceci est
intéressant de le faire) comme la recherche d’un plus long chemin dans un graphe G = (V; E), dont
l’ensemble des sommets X et l’ensemble des arcs U sont construits de la façon suivante :
L’ensemble des sommets X est constitué par :
un sommet particulier, noté (0; 0) (sommet initial) ;
n(b + 1) sommets correspondant chacun à un couple (E; i), où 0 E b et 1 i n.
? D’autre part, à toute paire de sommets de la forme f(0; 0); (E; 1)g, on associe un arc [(0; 0); (E; 1)]
de longueur 0 si E = 0 ;
de longueur c1 si ((E = a1 ) et (0 a1 b)).
? En…n, pour i = 1; 2; :::; n 1, à toute paire de sommets de la forme: f(E; i); (E 0 ; i + 1)g,
on associe un arc [(E; i); (E 0 ; i + 1)]
de longueur 0 si E 0 = E ;
de longueur ci+1 si E 0 = E + ai+1 et que 0 E + ai+1 b;
Le sous-ensemble Xt des sommets de la forme (E; n), pour 0 E b, est appelé l’ensemble
des sommets (des états) terminaux.
Exemple. Soit le problème (KP ) dont la …gure ci-dessous illustre la conception de la solution.
8
< max Z = 2 x1 + 3 x2 + 6 x3
(KP ) 3 x1 + 2 x2 + 4 x3 5
:
xj 2 f0; 1g; 8j = 1; 3
Figure 1

Des graphes tels que celui de la Figure 2, où l’ensemble des sommets est partitionné en n + 1 sous-
ensembles, pour lesquels il n’existe d’arcs qu’entre deux sous-ensembles consécutifs sont appelés
des graphes sans circuit séquentiels. Le problème (KP ) est équivalent à la recherche d’un chemin
de longueur maximale entre le sommet (0; 0) et l’ensemble Xt des sommets terminaux. En e¤et,
chaque chemin de l’origine (0; 0) vers un sommet (E; n) de Xt correspond à une solution de (KP ),
et la longueur de ce chemin n’est autre que le coût de la solution associée. En fait, l’Algorithme
1 s’interprète comme l’algorithme Bellman connu en théorie de graphes. Remarquons en…n, que le
même graphe G permet de représenter toute la famille de problèmes (KP1 (E)) pour tout 0 E b.
En e¤et, pour 0 E b, il su¢ ra de choisir comme nouvel ensemble de sommets terminaux
l’ensemble des sommets de la forme (E 0 ; n) avec 0 E 0 b E.
1.5.2 Un simple problème de cheminement.

Supposons que nous vivions dans une ville dont les rues sont représentées sur le graphe ci-dessous
(Figure 2). Toutes les rues sont à sens unique, et les nombres indiqués sur les arcs représentent
l’e¤ort (temps de parcours, coût de transition ou distance entre deux points) nécessaire pour passer
d’un point à un autre voisin. On vit à A et on souhaite atteindre B avec un e¤ort total minimum.
Figure 2
On pourrait, naturellement, résoudre ce problème en énumérant tous les chemins possibles de A à

B et choisir par la suite le plus petit chemin en poids (somme des poids de ses arcs). Au lieu de
dresser la liste de tous les chemins (avec risque d’erreur élevé) et comparer leurs poids, on peut
résoudre ce problème plus e¢ cacement que par cette énumération brute, par une méthode plus
e¢ cace, c’est la progammation dynamique.
L’une des raisons du développement de l’approche par la programmation dynamique vient du
fait qu’on ne sait pas s’il faut aller en diagonale vers le haut ou vers la bas de A, mais si on
connait (d’une manière ou une autre) seulement deux valeurs supplémentaires, à savoir l’e¤ort
total nécessaire pour avancer de C à B par un meilleur chemin (minimum d’e¤ort) et l’e¤ort total
nécessaire pour aller de D à B par un meilleur chemin aussi, on peut déduire le meilleur choix en
A. En désignant l’e¤ort minimum de C à B par SC , et l’e¤ort minimum de D à B par SD , on
veut ajouter à SC , l’e¤ort nécessaire pour aller de A à C, pour l’obtention de l’e¤ort nécessaire
sur la meilleure voie de départ diagonalement vers le haut de A. On peut ensuite ajouter l’e¤ort
sur AD à SD , pour obtenir l’e¤ort sur le meilleur chemin commençant diagonalement descendant
de A, et on peut donc comparer ces deux premières sommes pour trouver l’e¤ort minimum global
et la meilleure première décision.

Bien sûr, tout cela est fondé sur la connaissance des deux nombres SC et SD qui, malheureusement
ne sont pas connus. Toutefois, l’une des deux principales idées de la programmation dynamique
a été déjà faite en ses ino¤ensives apparences. C’est le constat que seuls les meilleurs des e¤orts
le long des chemins de C et D à B doivent être calculés. C’est l’interprétation propre du principe
d’optimalité
Le meilleur chemin de A à B possède la propriété que,

quelque soit la décision initiale prise en A, le chemin restant vers B,
commençant en un point succédant A, doit être le meilleur de ce point vers B.
Ayant dé…ni SC et SD comme ci-dessus, on peut citer le principe d’optimalité comme preuve de
la formule suivante
1 + SC
SA = min ;
0 + SD
où SA est l’e¤ort minimum pour aller de A vers B. Maintenant pour la seconde principale idée
du choix de la programmation dynamique est qu’initialement les deux nombres SC et SD sont
inconnues. Nous pouvons calculer SC , si nous connaissions les deux nombres SE et SF (le minimum
d’e¤orts de E et F à B, respectivement), en invoquant le principe de l’optimalité
5 + SE
SC = min :
4 + SF
De même
7 + SF
SD = min :
3 + SG
SE , SF et SG sont initialement inconnus, mais peuvent être calculés si SH , SI , SJ et SK étaient
disponibles. Ces nombres à leur tour dépendent de SL , SM , et SN , qui dépendent aussi de SO
et SP . Ainsi, on utilise les formules ci-dessus pour calculer tous les S, si on connait SO et SP ,
les e¤orts minimum de O et P , respectivement, puisque il existe un seul arc de O et P vers B.
En procédant par une marche-arrière de O et P vers A, on obtient:
SO = 2 SP = 1
2 + SO
S L = 5 + SO = 7 SM = min =4 SN = 4 + SP = 5
8 + SP
3 + SL 2 + SM
SH = 3 + SL = 10 SI = min =8 SJ = min = 6 SK = 2 + SN = 7
4 + SM 2 + SN
2 + SH 1 + SI 5 + SJ
SE = min = 9 SF = min = 8 SG = min = 11
1 + SI 2 + SJ 4 + SK
5 + SE 7 + SF
SC = min = 12 SD = min = 14
4 + SF 3 + SG
1 + SC
SA = min = 13
0 + SD

1.5.3 Analyse de la complexité et limitations de la programmation dynamique.

Pour étudier l’e¢ cacité d’un algorithme, il est intéressant d’évaluer sa complexité5 . L’application
de la programmation dynamique au problème de la partition (un problème N P -complet, classe
de problèmes di¢ ciles) a fait de lui un problème pseudo-polynomial6 . En e¤et, on doit remplir
un tableau de dimensions n (le nombre d’éléments) et P (la demi-somme de leurs poids), où le
remplissage de chaque case se fait à l’aide de nP . Cependant, si l’algorithme proposé est non
polynomial, on procède au calcul de sa complexité pour un codage "raisonnable" des données
(le codage binaire). Le nombre P apparaît alors comme une fonction exponentielle de la place
mémoire prise pour coder P (plus précisément, pour coder les nombres qui permettent le calcul de
P ), à savoir blog2 P c + 1 bits. Si P est borné par une constante, alors l’appel à la programmation
dynamique est en O(n). Ainsi, si on accepte de coder P sur P symboles, l’algorithme issu de la
programmation dynamique est e¤ectivement de complexité polynomiale par rapport à ce nouveau
codage, ce qui fait du problème de la partition un problème pseudo-polynomial. En pratique, il
arrive souvent que P ne soit pas très grand et du coup l’algorithme soit très performant.
Pour le problème N P -complet du sac à dos, le même type d’analyse s’applique : un algorithme
pouvant être décrit consiste à remplir un tableau à n lignes et b colonnes, où une case nécessite
le calcul d’un maximum sur au plus b valeurs. D’où une complexité en O(nb), ce qui fait que
ce problème soit pseudo-polynomial. Aussi, dans l’Algorithme 1, chaque étape requiert, pour
chaque valeur de E (0 E b) : une addition et une comparaison ; répétés en n étapes ; le
nombre d’opérations élémentaires croit comme n(b+1). On dit que la complexité est en O(nb). Du
point de vue de l’encombrement mémoire, Algorithme 1 ne nécessite à tout instant que 2(b + 1)
places mémoires (les b + 1 valeurs Fi+1 (E) et les b + 1 valeurs Fi (E)). Si l’on utilise Procédure
1 pour expliciter x , le volume de mémoire nécessaire sera donc (n + 2)(b + 1).
En résumé, pour le problème du sac à dos, la complexité du calcul, aussi bien que l’encombrement
en mémoire d’un algorithme de programmation dynamique, dépendent directement du nombre de
valeurs de E , c’est-à-dire de la cardinalité de l’espace d’état associé au problème. C’est ce paramètre
qui constituera, en pratique, la limitation la plus sévère à l’application de la programmation
dynamique.
5
Le nombre d’opérations élémentaires (additions, comparaisons, ...) nécessaires, en fonction du volume de
mémoire exigé par la mise en œuvre sur calculateur
6
Un problème est dit pseudo-polynomial s’il existe un algorithme (dit aussi pseudo-polynomial ) dont la complexité
est bornée par un polynôme en fonction de la place mémoire occupée par les données, en acceptant cette fois-ci de
coder les quantités numériques en unaire (il faut autant de symboles que la valeur de l’entier à coder ; un codage
non raisonnable). Aussi, un problème N P -complet qui n’est pas pseudo-polynomial est dit fortement N P -complet
(un problème de décision associé au problème du voyageur de commerce).

2 Les fondements théoriques de la programmation

dynamique.
2.1 Le théorème d’optimalité - cas sans contraintes - .
L’idée de base de la programmation dynamique consiste à essayer de remplacer l’optimisation
d’une fonction de n variables par la résolution d’un certain nombre de problèmes d’optimisation,
plus simples à résoudre, par exemple des problèmes d’optimisation à une seule variable.
En ce sens, la méthode peut être considérée comme une méthode de décomposition. Pour illustrer
cette idée, considérons le problème d’optimisation sans contraintes
min f (x; y1 ; y2 ; :::; yk )
où f est une fonction réelle de la variable réelle x et des k variables réelles y1 ; y2 ; :::; yk .
Supposons que f est séparable en deux fonctions f1 et f2 , c’est-à-dire f s’écrit sous la forme
f (x; y) = f1 (x; f2 (y)), avec y = (y1 ; y2 ; :::; yk ):
Le problème posé s’énonce comme suit :
"est-il possible de ramener le problème initial à k + 1 variables

à des problèmes d’optimisation comportant un moins grand nombre de variables ? "
Autrement dit, quand pourra-t-on écrire
minf (x; y) = minff1 (x; minff2 (y)g)g. (1)

(x;y) x y
Une condition su¢ sante (mais cependant très générale) pour que la relation (1) soit véri…ée a été
donnée par Mitten (1964) et fait intervenir la notion de fonction décomposable.
Dé…nition. On dit que f est décomposable en f1 et f2 si f est séparable (f (x; y) = f1 (x; f2 (y))),
et si, de plus, la fonction f1 est monotone non décroissante par rapport à son deuxième argu-
ment.
On peut alors énoncer le résultat fondamental suivant :
Théorème (Théorème d’optimalité). Soit f une fonction réelle en x et y = (y1 ; y2 ; :::; yk ).
Si f est décomposable, avec f (x; y) = f1 (x; f2 (y)), alors on a :
Optf (x; y) = Optff1 (x; Optff2 (y)g)g (Opt = min ou max):

(x;y) x y

2.2 Extension du théorème d’optimalité au cas avec contraintes.

Le théorème d’optimalité se généralise immédiatement au cas (plus intéressant en pratique) de
l’optimisation avec contraintes. Considérons le problème
Opt f (x; y)
où Opt = min ou max ,
(x; y) 2
avec l’ensemble des solutions réalisables du problème ( Rk+1 et 6= ;).

Pour tout x réel, notons
k
x = fy=y 2 R ; (x; y) 2 g
(pour certaines valeurs x, on peut avoir x = ;). Alors en convenant de poser
+1 si x = ; et Opt = min
Opt ff2 (y)g =
y2 x
1 si x = ; et Opt = max
8x : f1 (x; +1) = +1 et f1 (x; 1) = 1
on peut énoncer :
Théorème 2 (Théorème d’optimalité: cas avec contraintes). Si f est décomposable avec
f (x; y) = f1 (x; f2 (y)), alors
Opt ff (x; y)g = Optff1 (x; Opt ff2 (y)g)g.

(x;y)2 x y2 x
2.3 La notion d’état en programmation dynamique.

Reprenons le dernier problème du paragraphe précédent, pour lequel on cherchait à résoudre
Opt f (x; y)
(x; y) 2
où f est décomposable et se met sous la forme
f (x; y) = f1 (x; f2 (y)). (2)
D’un point de vue pratique, si l’on suppose que l’ensemble des solutions est a priori quelconque,
la recherche de l’optimum de f sur par la formule de décomposition (2)
Optff1 (x; Opt ff2 (y)g)g. (2’)

x y2 x
est équivalente à :
- déterminer pour chaque x la valeur de la fonction ' :
'(x) = Opt ff2 (y)g;

y2 x
- puis déterminer l’optimum en x de la fonction :
(x) = f1 (x; '(x)).

Ainsi, on remarque que ceci est équivalent au calcul du minimum de f (x; y) par "énumération"
de tous les (x; y) 2 . La formule (2’) ne fait que préciser l’ordre dans lequel s’e¤ectue cette
"énumération". Il est claire qu’une telle procédure ne peut conduire à une méthode de résolution
e¢ cace en pratique.
En fait, l’intérêt du théorème d’optimalité (pour la conception des algorithmes de résolution)
dépend essentiellement de la forme du domaine des solutions et, plus précisément, de la possibilité
de le considérer comme un élément d’une famille plus vaste de domaines, i (E), paramétrée par
un vecteur E (vecteur d’états).
Considérons un problème d’optimisation, soumis à des contraintes, en variables (x; y) de la forme
générale
F = Opt f (x; y)
(P )
g(x; y) 2 Et
où g : Rk+1 ! Rm et Et Rm (lorsque Et est réduit à un seul point, on a un problème
d’optimisation avec contrainte d’égalité).
Supposons de plus que g soit séparable et puisse se mettre sous la forme
g(x; y) = h2 (y; h1 (x)) , où h1 : R ! Rm et h2 : Rk+m ! Rm .
On voit que, pour x et y donnés, g(x; y) peut être calculé par

8
< E1 = h1 (x)
E2 = h2 (y; E1 )
:
g(x; y) = E2 .
Soit E un sous-ensemble de Rm tel que
8x 2 fx=9y : (x; y) 2 g =) h1 (x) 2 E

8E 2 E; 8y 2 fy=9x : (x; y) 2 g =) h2 (y; E) 2 E.
E est appelé l’ensemble des états et un élément E 2 E est appelé un vecteur d’état. Les fonctions h1
et h2 sont appelées les fonctions de transition, Et est l’ensemble des états terminaux admissibles.
L’idée consiste à remplacer la résolution du problème (P ), qui comporte k + 1 variables, par
la résolution d’une famille de problèmes d’optimisation à k variables
F2 (E1 ) = Optff2 (y)g

(P2 (E1 )) pour Et parcourant E.
h2 (y; E1 ) 2 Et
Notons
2 (E1 ) = fy=h2 (y; E1 ) 2 Et g l’ensemble des solutions du problème (P2 (E1 )):
Remarquons que x = 2 (h1 (x)). Lorsque x = ;, convenons de poser
F2 (h1 (x)) = +1 (cas de minimisation) (resp. F2 (h1 (x)) = 1 (cas de maximisation))
La fonction f étant supposée décomposable, la formule (2’) s’écrit alors
F = Optff1 (x; Opt ff2 (y)g)g.

x y2 2 (h1 (x))

Mais par dé…nition

Opt ff2 (y)g = F2 (h1 (x)).
y2 2 (h1 (x))
Par suite, si l’on suppose que l’on a résolu tous les problèmes (P2 (E1 )) pour tous les E1 2 E, on
pourra résoudre le problème (P ) comme un problème d’optimisation d’une seule variable x par
F = Optff1 (x; F2 (h1 (x))g. (3)

x
Nous allons voir maintenant qu’en appliquant ce résultat de façon récursive, un problème d’optimisation
à n variables peut se résoudre en n étapes, chaque étape consistant à résoudre un certain nombre
de problèmes d’optimisation à une seule variable.
2.4 L’équation fonctionnelle de la programmation dynamique.

Considérons le problème d’optimisation à n variables
F = Optf (x1 ; x2 ; :::; xn )

(P )
g(x1 ; x2 ; :::; xn ) 2 Et Rm .
Supposons que f soit décomposable sous la forme
f (x1 ; x2 ; :::; xn ) = f1 (x1 ; f 2 (x2 ; :::; xn ))

f 2 (x2 ; :::; xn ) = f2 (x2 ; f 3 (x3 ; :::; xn ))
..
.
f n (xn ) = fn (xn ).
Supposons, d’autre part, qu’il existe un sous-ensemble E Rm (espace d’état) tel que g puisse
être calculé récursivement pour tout ensemble de valeurs x1 ; :::; xn par
8
>
> E1 = h1 (x1 ) 2 E
>
>
>
< E2 = h2 (x2 ; E1 ) 2 E
..
> .
>
> En = hn (xn ; En 1 ) 2 E
>
>
: g(x ; :::; x ) = E
1 n n
où les fonctions h1 , h2 , ..., hn sont appelées des fonctions de transition.

Pour tout i = 2; 3; :::; n notons hi (xi ; xi+1 ; :::; xn ; E) la fonction dé…nie récursivement par
8
>
> Ei = hi (xi ; E)
>
>
>
< Ei+1 = hi+1 (xi+1 ; Ei )
..
> .
>
> En = hn (xn ; En 1 )
>
>
: h (x ; x ; :::; x ; E) = E .
i i i+1 n n
Remarquons que l’on a, 8i = 1; n 1
hi (xi ; xi+1 ; :::; xn ; E) = hi+1 (xi+1 ; :::; xn ; hi (xi ; E)).

Considérons alors le problème (P ) qui peut se mettre sous la forme
F = Opt f1 (x1 ; f 2 (x2 ; :::; xn ))

h2 (x2 ; :::; xn ; h1 (x1 )) 2 Et
En identi…ant x à x1 , y à (x2 ; :::; xn ) et en faisant appel à (3), on obtient la relation
F = Optff1 (x1 ; F2 (h1 (x1 )))g

x1
où pour tout E1 2 E, F2 (E1 ) est la valeur optimale de
F2 (E1 ) = Opt f 2 (x2 ; :::; xn )

(P2 (E1 ))
h2 (x2 ; :::; xn ; E1 ) 2 Et
Considérons maintenant le problème (P2 (E1 )) pour E1 …xé. Ce problème se met lui-même sous
la forme
F2 (E1 ) = Opt f2 (x2 ; f 3 (x3 ; :::; xn ))
h3 (x3 ; :::; xn ; h2 (x2; E1 )) 2 Et
En identi…ant x à x2 , y à (x3 ; :::; xn ) et en appliquant la formule (3), on obtient la relation
F2 (E1 ) = Optff2 (x2 ; F3 (h2 (x2 ; E1 )))g

x2
où, pour tout E2 2 E, F3 (E2 ) est la valeur optimale de
F3 (E2 )) = Opt f 3 (x3 ; :::; xn )

(P3 (E2 ))
h3 (x3 ; :::; xn ; E2 ) 2 Et
En continuant de la sorte, les valeurs Fi (Ei 1 ) (pour 2 i n 1) peuvent être dé…nies, pour
tout Ei 1 2 E, par
Fi (Ei 1 ) = Optffi (xi ; Fi+1 (hi (xi ; Ei 1 )))g (4)
xi
et, pour i = n
Fn (En 1 ) = Opt ffn (xn )g (5)
xn ;
hn (xn ; En 1 ) 2 Et
où, pour i (2 i n), Fi (E) désigne la valeur optimale du problème
Opt f i (xi ; xi+1 ; :::; xn )

(Pi (E))
hi (xi ; xi+1 ; :::; xn ; E) 2 Et

Donc, on voit qu’il est possible de déterminer, de proche en proche, par récurrence les fonctions Fi ,
pour i = n; n 1; :::; 2, puis la valeur optimale F du problème (P ) à partir de F2 . L’équation (4)
est appelée l’équation fonctionnelle de la programmation dynamique. Sa résolution, par récurrence
à partir des conditions (5) conduit à la procédure algorithmique à n étapes suivante :
Algorithme 2 (Procédure « en arrière » )

(a) Initialisation (Etape n)
8E 2 E, calculer : Fn (E) = Opt ffn (xn )g
xn ;
hn (xn ; E) 2 Et
(s’il n’existe pas xn tel que hn (xn ; E) 2 Et , alors

Fn (E) = +1 si Opt = min, Fn (E) = 1 si Opt = max).
(b) Pour i = n 1; n 2; :::; 2 successivement, calculer (Etape i)
8E 2 E : Fi (E) = Optffi (xi ; Fi+1 (hi (xi ; E)))g
xi
(c) Etape 1:
Calculer F par
F = Optff1 (x1 ; F2 (h1 (x1 ))g
x1
Cet algorithme n’est autre qu’un calcul par récurrence e¤ectué dans l’ordre décroissants des indices
des variables et est appelé procédure « en arrière » par opposition à la procédure « en avant »
qui sera exposée ci-dessous.
Ainsi, de même que dans le problème du sac à dos (voir 2.2), l’algorithme consiste à :
- plonger le problème posé dans une famille de problèmes de même nature ;
- relier par une relation de récurrence les valeurs optimales de ces problèmes ;
- résoudre l’équation de récurrence obtenue (équation fonctionnelle) pour déterminer l’optimum
du problème posé.
Comme le nombre de sous-problèmes d’optimisation élémentaires (à une variable) à résoudre croît
comme le produit n p (où p est le nombre d’états qui doivent être considérés à chaque étape),
on ne pourra appliquer l’Algorithme 2 que dans des situations assez restrictives telles que :
- lorsque l’ensemble E des états est …ni et de cardinalité assez faible (on parle alors de program-
mation dynamique à nombre …ni d’états) ;
- lorsque l’ensemble E est un sous-ensemble de Rm comportant un nombre in…ni d’éléments (par
exemple un sous-ensemble compact de Rm ), mais que m (la dimension des vecteurs d’état) est
su¢ samment faible pour que l’on puisse approximer les fonctions Fi (E) sur E par discrétisation en
un nombre …ni (et si possible pas trop grand) de points E 1 , E 2 , ..., E q . Le calcul de Fi (E) pour
les autres états E se fait alors par interpolation linéaire ou polynomial.
Dans les autres cas, des techniques particulières devrons être mis en œuvre pour améliorer l’e¢ cacité
des algorithmes de programmation dynamique et seront exposées dans la prochaine section.

2.5 Le principe d’optimalité.

L’Algorithme 2, dont la validité découle du théorème d’optimalité, peut s’interpréter comme la
construction d’une solution optimale du problème (P ) à partir de solutions partielles optimales.
Ainsi, parmi toutes les solutions possibles (xi ; xi+1 ; :::; xn ) pour aller de l’état E (à l’étape i 1)
au sous-ensemble d’états Et (à l’étape n) (c’est-à-dire telles que hi (xi ; xi+1 ; :::; xn ; E) 2 Et ), on ne
conservera que l’information relative à une solution optimale (de valeur Fi (E)): toutes les autres
solutions se trouveront ainsi « oubliées » dans les étapes ultérieures de la résolution.
La solution optimale obtenue est alors conforme au principe d’optimalité énoncé par R. Bellman
(1957): Une politique optimale a la propriété que, quels que soient l’état initial et la décision
initiale, les décisions restantes doivent constituer une politique optimale vis-à-vis de l’état résultant
de la première décision.
Ce principe peut être résumé par, "Toute solution optimale ne peut être formée que par des solutions
partielles optimales".
Cependant, Porteus (1975) et Morin (1977) ont fait remarqué qu’il n’y a pas toujours équivalence
entre le principe d’optimalité et l’équation fonctionnelle de la programmation dynamique (4).
En e¤et, les conditions qui permettent d’établir la validité de l’équation (4) (essentiellement
l’hypothèse de décomposabilité de la fonction de coût, c’est-à-dire : séparabilité et monotonie)
ne sont pas su¢ santes pour obtenir la validité du principe d’optimalité.
Morin (1977) proposa un exemple pour illustrer ce point. Considérons le graphe de la …gure 3 dans
lequel on recherche un chemin de coût minimal entre les sommets 1 et 4, le coût d’un chemin étant le
produit des nombres associés à chacun des arcs (L est une constante positive choisie arbitrairement
grande). L’hypothèse de séparabilité et de monotonie est véri…ée pour cette fonction de coût et
pourtant le chemin f1; 3; 4g qui est optimal (de coût 0) entre 1 et 4 contient le chemin partiel
f1; 3g qui n’est pas optimale entre 1 et 3.
Figure 3
Pour assurer la validité du principe d’optimalité, il faut alors remplacer l’hypothèse de monotonie
au sens large intervenant dans la démonstration du théorème d’optimalité (Théorème 1) par
une hypothèse de monotonie au sens strict.
Nous dirons que f est décomposable au sens stricte si f est séparable sous la forme
f (x; y) = f1 (x; f2 (y))
et si f1 est une fonction strictement monotone de son deuxième argument c’est-à-dire
8x : z1 < z2 =) f1 (x; z1 ) < f1 (x; z2 )
z1 = z2 =) f1 (x; z1 ) = f1 (x; z2 )
Morin (1977) montra que si l’hypothèse de décomposabilité au sens strict est satisfaite, toute
solution optimale satisfait le principe d’optimalité et correspond donc à une solution de l’équation
fonctionnelle. De plus, il est facile de démontrer, que dans ces conditions, l’Algorithme 2 permet
de déterminer toutes les solutions optimales d’un problème.

2.6 Exemples de fonctions décomposables.

La principale classe générale de fonctions décomposables utilisée en pratique est constituée de
fonctions de la forme
f (x1 ; x2 ; :::; xn ) = f1 (x1 ) f2 (x2 ) fn (xn )
où est un opérateur de décomposition (la notion ci-dessus suppose l’associativité de mais cette
propriété n’est pas indispensable). Comme la séparabilité de telles fonctions est évidente, il su¢ t
de véri…er que l’opérateur de composition satisfait la propriété de monotonie.
Dans ce qui suit, nous exposons les cas les plus fréquement rencontrés dans les applications.
(a) Cas de fonctions additives.

On a alors = addition des réels. De telles fonctions sont évidemment décomposables et également
décomposables au sens strict.
(b) Produit de fonctions réelles positives ou nulles.

On a alors = multiplication des réels. Dans ce cas, pour obtenir la propriété de monotonie, il
faut supposer que les fonctions élémentaires qui composent la fonction f sont positives ou nulles.
La propriété de monotonie au sens strict est obtenue en excluant l’élément 0, autrement dit
supposer que les fonctions élémentaires f1 ; :::; fn sont toutes strictement positives.
Remarquons que le cas d’un produit de fonctions réelles toutes strictement positives se ramène
immédiatement à une fonction additive en prennant le logarithme de la fonction (sachant que
le logarithme est une fonction monotone croissante, il est équivalent d’optimiser f ou log(f )).
(c) Minimum (resp. maximum) de n fonctions réelles.

Dans le cas où = minimum (resp. maximum) de n nombres réels, la fonction f est de la forme
f (x1 ; x2 ; :::; xn ) = Optff1 (x1 ); f2 (x2 ); :::; fn (xn )g (avec Opt = min ou max )
et peut s’écrire
f (x1 ; x2 ; :::; xn ) = Optff1 (x1 ); zg = f 0 (x1 ; z) avec z = Optff2 (x2 ); :::; fn (xn )g
La fonction f 0 satisfait l’hypothèse de monotonie car
z0 z 00 =) f 0 (x1 ; z 0 ) = Optff1 (x1 ); z 0 g Optff1 (x1 ); z 00 g = f 0 (x1 ; z 00 )
On en déduit que f est décomposable. Cependant, on remarque que f 0 n’est pas strictement
monotone et que, par suite, le principe d’optimalité peut ne pas être satisfait par toutes les solutions
optimales.

2.7 Programmation dynamique à nombre …ni d’états et recherche

d’un plus court (ou d’un plus long) chemin dans un graphe.
Cette partie est consacrée à la généralisation de la construction présentée dans x2:3:2.
On se place dans un cas où l’ensemble des états E est de cardinalité jEj …nie.
Supposons de plus que f est décomposable sous la forme
f (x1 ; x2 ; :::; xn ) = f1 (x1 ) + f2 (x2 ) + + fn (xn ).
Considérons alors le graphe G = (X; U ) dont l’ensemble des sommets X et l’ensemble des arcs U
sont construits de la façon suivante :
~ L’ensemble X est constitué par :
(a) un sommet particulier que nous noterons I (sommet initial) ;
(b) np sommets correspondant chacun à un couple (E; i), où E 2 E et 1 i n.
~ L’ensemble U comporte :
(a) l’ensemble des arcs de la forme (I; (E; 1)), où E = h1 (x1 ) pour toutes les valeurs possibles
de x1 (i.e telles que h1 (x1 ) 2 E).
"On attribue à l’arc (I; (E; 1)) une longueur égale à f1 (x1 )"
(b) Pour i = 2; 3; :::; n et pour tout E 2 E l’ensemble des arcs de la forme ((E; i 1); (E 0 ; i))
où E 0 = hi (xi ; E) pour toutes les valeurs possibles de xi (i.e telles que hi (xi ; E) 2 E).
"On attribue à l’arc ((E; i 1); (E 0 ; i)) une longueur égale à fi (xi )"
Le sous-ensemble des sommets terminaux Xt est constitué par tous les sommets de la forme (E; n),
avec E 2 Et (ensemble des états terminaux). On remarque alors que :
- tout chemin entre I et Et est une solution du problème (i.e satisfait les contraintes g(x1 ; x2 ; :::; xn ) 2
Et );
- la longueur d’un tel chemin est
f1 (x1 ) + f2 (x2 ) + + fn (xn ):
Il en résulte que
la résolution du problème par programmation dynamique
équivaut à
la recherche d’un plus court (ou plus long) chemin entre I et Xt dans le graphe G.
2.8 Second algorithme de programmation dynamique.

Procédure « en avant » .
On peut utiliser le principe de la résolution d’un problème de plus court (plus long) chemin, pour
dé…nir un second algorithme, baptisé Algorithme 3 de programmation dynamique, où les calculs
s’e¤ectueront, cette fois, selon l’ordre des indices croissant des variables (d’où le nom procédure
« en avant » ). Cet algorithme di¤ère de l’Algorithme 2 en ce sens qu’il ne s’en déduit pas par
une simple inversion de l’ordre des variables.
Ainsi, plaçons nous dans le cas de la programmation dynamique à nombre …ni d’états et considérons
le graphe du x3:7. Comme la plupart des algorithmes de plus court (plus long) chemin, l’algorithme
suivant est un algorithme de marquage :
à chaque sommet du type (E; i) est associé un nombre (une marque) (E; i).

À la …n de l’étape i 1, (E; i 1) représente e¤ectivement la longueur d’un chemin optimal entre

I (sommet initial) et (E; i 1).
Au début de l’étape i, on a 8E :
8
< +1 (cas du plus court chemin)
(E; i) = ou
:
1 (cas du plus long chemin).
Algorithme 3 (Procédure « en avant » )

+1 (cas où Opt = min )
(a) Étape i = 1 : 8E 2 E, faire (E; 1) :=
1 (cas où Opt = max ).
Puis pour toutes les valeurs de x1 possibles (où h1 (x1 ) 2 E) déterminer E = h1 (x1 )
et faire (E; 1) f1 (x1 ).
(b) Pour i = 2; 3; :::; n : (Étape i )
+1 (cas où Opt = min )
Faire 8 E 2 E : (E; i) =
1 (cas où Opt = max ).
Pour tout E tel que : j (E; i 1)j < +1 et pour toutes les valeurs possibles de xi
(telles que E 0 = hi (xi ; E) 2 E) ;
- calculer E 0 = hi (xi ; E) ;
- faire (E 0 ; i) Optf (E; i 1) + fi (xi )g.
(c) Calculer F par F = Opt f (E; n)g.
E2Et
L’étape i consiste à modi…er ces marques, à partir des valeurs optimales (E; i 1), de telle sorte
qu’à la …n de l’étape i, (E; i) représente e¤ectivement la longueur du plus court (plus long) chemin
joignant le sommet initial à ce sommet.
Si l’on veut obtenir, non seulement la valeur optimale de F , mais une solution optimale x , on
dé…nira, pour chaque i = 1; :::; n et pour chaque E 2 E, les quantités xi (E) donnant la valeur de
la variable xi ayant permis l’obtention de la valeur optimale (E; i).
A l’étape 1, on posera x1 (E) = x1 (où E = h1 (x1 )) et à l’étape i (2 i n), chaque fois
0
qu’une marque (E ; i) est améliorée et remplacée par (E; i 1) + fi (xi ), on posera xi (E) = xi .
Ceci permet, à la …n de l’Algorithme 3, d’expliciter une solution optimale x = (x1 ; :::; xn ) par :
(a) E = E , où E est tel que :

F = Opt f (E; n)g = (E ; n).
E2Et
(b) pour i = n; n 1; :::; 1, successivement faire :
xi xi (E)
E E 0 où E 0 est telle que : E = hi (xi ; E 0 ).
Rappelons que, dans certains cas, la reconstruction d’une solution optimale x peut nécessiter
une moins grande quantité d’informations.

3 Exemple d’application de la programmation dynamique:

Un problème de gestion de stock.
(a) Enoncé du problème. Le tableau donné ci-dessous résume pour cinq périodes, qui font l’objet
d’une étude, les quantités demandées (resp. leurs prix d’achat unitaire) d’une marchandise qu’un
commerçant aurait à acheter avant de revendre :
Période j 1 2 3 4 5
Demande dj 2 3 4 3 2
Prix pj 13 15 20 11 12
Sachant que le commerçant dispose d’une capacité de stockage de 5 unités (le coût de stockage est
nul), le problème consiste à déterminer la politique d’achat optimal, c’est-à-dire qu’on cherche à
trouver les quantités à acheter à chaque période de manière à minimiser le coût total d’achat sur
les 5 périodes. On sait de plus que :
1. les achats se font en début de période ;
2. on doit stocker les ventes de la périodes en cours ;
3. on commence et on …nit avec un stock nul ;
4. les quantités sont nécessairement entières.
(b)Modélisation.
Les étapes du problème : les périodes 1, 2, 3, 4 et 5.
L’état du système : la quantité sj de la marchandise restante en stock à la …n de la période j.
Les variables de décision : les quantités xj de la
8marchandise achetées en début de période j.
< dj sj 1 + xj 5 pour 1 j 5
Le système est régi par les relations suivantes : sj = sj 1 + xj dj pour 1 j 4
:
s0 = s5 = 0:
En e¤et,
dj sj 1 + xj 5 pour 1 j 5
les inégalités de cette première série de relations traduisent le fait que la quantité achetée au début
de la période j plus celle héritée de la période précédente
X d’une part doivent être su¢ santes, pour pourvoir à la demande de la période,
X mais d’autre part ne doivent pas excéder la capacité de stockage.
sj = sj 1 + xj dj pour 1 j 4
Alors que cette seconde série correspond au fait que la quantité disponible en début de période j
est utilisée pour satisfaire la demande ou se retrouve en stock pour la période suivante.
Les égalités s0 = s5 = 0 signi…ent que les stocks initial et …nal sont nuls.
P
5
Quant à la fonction objectif, que l’on veut minimiser, il s’agit de pj xj
j=1
Nous devons donc résoudre un problème de 8

programmation linéaire en variables entières, > P5
>
> min pj xj
moyennant la programmation dynamique. >
< j=1
dj sj 1 + xj 5 pour 1 j 5 xj 2 N
>
>
>
> s = sj 1 + x j dj pour 1 j 4
: j
s0 = s5 = 0

(c) Résolution.
1ere méthode. On dé…nit
Vj (sj ; xj ) : le coût d’une politique entre la période initiale et la période j, si on achète xj au début
de la période j et le stock en …n de cette période j est sj .
Vj (sj ) : le coût de la politique optimale entre la période initiale et la période j, si le stock en …n
de cette période j est sj .
xj #
Vj (sj ) = minVj (sj ; xj ) sj 1 sj
xj ! période j !
Vj (sj ; xj ) = pj xj + Vj 1 (sj 1 ) = pj xj + Vj 1 (sj + dj xj ) #dj
1ere période. Compte tenu de la demande de

la période 1, on voit que l’on peut …nir cette d1 s1 x1 V1 (s1 ; x1 ) V1 (s1 )
période avec 0, 1, 2 ou 3 unités en stocks. 2 0 2 2 13 = 26 26
Étant donné que s0 = 0, chacune des valeurs de 1 3 3 13 = 39 39
s1 parvient d’une seule décision possible. 2 4 4 13 = 52 52
Les coûts respectifs étant alors 26, 39, 52 ou 65. 3 5 5 13 = 65 65
2eme période. On peut de même terminer d2 s2 x2 V2 (s2 ; x2 ) V2 (s2 )

la période 2 avec 0 ou 1 ou 2. 3 0 0 0 + 65 = 65 65
Mais cette fois chacune de ces possiblités peut 1 15 + 52 = 67
parvenir de décisions di¤érentes : 2 30 + 39 = 69
3 45 + 26 = 71
1 1 15 + 65 = 80 80
2 30 + 52 = 82
3 45 + 39 = 84
4 60 + 26 = 86
2 2 30 + 65 = 95 95
3 45 + 52 = 97
4 60 + 39 = 99
5 75 + 26 = 101
3eme période. 4eme période.
d3 s3 x3 V3 (s3 ; x3 ) V3 (s3 ) d4 s4 x4 V4 (s4 ; x4 ) V4 (s4 )

4 0 2 40 + 95 = 135 135 3 0 2 22 + 155 = 177 168
3 60 + 80 = 140 3 33 + 135 = 168
4 80 + 65 = 145 1 3 33 + 155 = 188 179
1 3 60 + 95 = 155 155 4 44 + 135 = 179
4 80 + 80 = 160 2 4 44 + 155 = 199 190
5 100 + 65 = 165 5 55 + 135 = 190
5eme période.
d5 s5 x5 V5 (s5 ; x5 ) V5 (s5 )
La solution optimale est donnée par
2 0 0 0 + 190 = 190 190 x5 = 0; x4 = 5; x3 = 2; x2 = 2; x1 = 5
1 12 + 179 = 191 Coût V (0) = 190
2 24 + 168 = 192

Résolution du problème de gestion de stock en utilisant les réseaux.

Nous allons montrer dans ce paragraphe que le problème de gestion de stock que nous venons de
résoudre peut se formuler comme un problème de recheche de plus court chemin dans un réseau.
Ainsi, on peut associer au problème le réseau R dé…ni comme suit :
Les états du stock étant caractérisé par deux paramètres (j; sj ) où :
j : est la période ;
sj : le niveau du stock à la …n de la période j.
R = (X; U; c) avec :
X = f(j; sj ) jj = 0; 5, s0 = s5 = 0; 0 sj 5 dj ; j = 1; 2; 3; 4g ;
U = f((i; si ); (j; sj )) jj = i + 1 et il existe une décision pour passer de (i; si ) à (j; sj )g ;
c((i; si ); (j; sj )) = pj :(sj + dj si ) = pi+1 :(si+1 + di+1 si ).
Figure 4
Le problème de la recherche d’une politique optimale d’achat est ramené donc à la détermination
d’un chemin de longueur minimum entre (0; 0) et (5; 0).
Le réseau ne comporte pas de cicuit puisque chaque arc conduit d’un état correspondant à la …n
de la période j 1 à un état de la …n de la période j. Il est donc justi…able d’utiliser amgorithme
de Bellman. Si on utilise l’algorithme de Bellman, on trouve les (j; sj ) les plus courtes distances
de (0; 0) à (j; sj ) et une arboescence A de racine (0; 0).

Généralisation.
En résumé, on peut considérer que l’on a plongé notre poroblème initial (P ) qui est un problème
de programmation linéaire en nombres entiers dans une classe de problèmes Pk (s) qui peuvent être
décrits comme suit :
il s’agit de déterminer une politique d’achats optimale sur les k premières périodes
sachant que nous voulons terminer la k eme période avec un stock de s unités.
Le problème (P ) peut être considéré comme P5 (0).

Il peut sembler pour le moins curieux de remplacer la résolution d’un seul problème par celle de
toute une famille. E fait, l’e¢ cacité de la méthode tient à la relation de récurrence existant entre
ces problèmes : on les résout en séquence. Ainsi, l’intérêt de ce plongement est qu’il nous permet
de mettre en évidence une relation de récurrence entre ces di¤érents problèmes et de les résoudre
d’une façon plus économique en place et en temps que dans la méthode expliquée dans le chapitre
précédent.
Appelons zk (s) la valeur à l’optimum de la fonction objectif du problème Pk (s).
On a alors la relation
zk (s) = min fpk :xk + zk 1 (s + dk xk )g:
xk 2Xk (s)
où
Xk (s) = fxk jdk + dk 1 +s 5 xk s + dk g;
cet encadrement résultant de l’égalité
sk 1 + xk = dk + s
(le stock au début de la dernière période plus la quantité achetée
servent à satisfaire la demande et à constituer le stock …nal)
et du fait que
8 p
< p d’une part 0
sk 1 peut varier entre et d’autre part la capacité totale de stockage (5) diminuée par
:
la demande dk 1 de la période k 1.

4 Programmation dynamique dans l’incertain.

La programmation dynamique déterministe traite des problèmes, où l’état à la prochaine étape est
entièrement déterminé par l’état et la décision de la politique à l’étape actuelle.
Elle peut être schématisée comme suit :
Ainsi, à l’étape n, le processus se trouvera dans un certain état sn . En prenant la décision de

politique xn , le processus se déplace ensuite vers un certain état sn+1 à l’étape n+1. La contribution
ultérieure à la fonction objectif sous une politique optimale a été précédemment calculée comme
étant fn+1 (sn+1 ). La décision de politique xn contribue également à la fonction objectif.
Ainsi en combinant ces deux quantités de manière appropriée, on obtient fn (sn ; xn ) la contribution
des étapes n en avant à la fonction objectif. L’optimisation par rapport à xn donne alors la valeur
fn (sn ) = fn (sn ; xn ). Après avoir trouvé xn et fn (sn ) pour chaque valeur possible de sn , la procédure
de solution est prête à revenir d’une étape en arrière.
Le cas probabiliste, où il existe une distribution de probabilité pour le prochain état, est discuté
dans cette section. La programmation dynamique probabiliste, ou le cas incertain, di¤ère de
la programmation dynamique déterministe en ce que la détermination de l’état de la prochaine
étape n’est pas complète par l’état et la décision de politique à l’étape actuelle. Au lieu de
cela, il existe une distribution de probabilité pour déterminer le prochain état. Cependant, cette
distribution de probabilité est toujours entièrement déterminée par l’état et la décision de politique
à l’étape actuelle. La structure de base résultante pour la programmation dynamique probabiliste
est décrite de la manière suivante
Ici S représente le nombre d’états possibles à l’étape n + 1 et les étiquetes des états du côté droit
comme 1; 2; :::; S. Le système passe à l’état i avec une probabilité pi (i = 1; 2; : : : ; S) étant donné
l’état Sn et la décision xn à l’étape n. Lorsque le schéma ci-dessus est étendue pour inclure tous
les états et décisions possibles à toutes les étapes, elle est parfois appelée un arbre de décision.
Si l’arbre de décision n’est pas trop grand, il fournit un moyen utile de résumer les di¤érentes
possibilités.

En raison de la structure probabiliste, la relation entre fn (sn ; xn ) et fn+1 (sn+1 ) est nécessairement
un peu plus compliquée que celle pour la programmation dynamique déterministe. La forme précise
de cette relation dépendra de la forme de la fonction objectif globale.
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 : on doit alors modi…er le cadre déterministe étudié jusqu’à présent.
Dans un problème de gestion de stocks par exemple, il est rare que la demande soit déterministe.
Des données statistiques permettent néanmoins généralement de modéliser l’incertain sous forme
d’une variable aléatoire correspondant à la demande. On évalue alors la séquence de choix au
regard d’un critère de décision donné (par exemple l’espérance de la valeur de la solution).
4.1 Processus décision-hasard.

Dans ce nouveau 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 …n 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 e¤ectivement atteints.
Ainsi, cela revient à considérer une fonction de transition non plus déterministe mais aléatoire.
Une politique ne consiste plus ici en une séquence de décisions, car une telle séquence n’aurait
pas de sens en présence du hasard. Il s’agit maintenant de
donner pour chaque état s 2 S, la décision x(s) que l’on prendrait

(si les décisions précédentes et le hasard nous y conduisaient).
Il est commode de représenter le processus décision-hasard par un graphe d’états particulier, appelé
arbre décision-hasard, où l’on distingue :
~ deux types de sommets :
des sommets si 2 Si correspondant aux di¤érents états,
des sommets hi 2 Hi correspondant à l’intervention du hasard.
~ les arcs sont de deux types :
un arc (si ; hi ) correspond à une décision,
l’ensemble des arcs f(hi ; si+1 ) : si+1 2 + (hi )g correspond aux di¤érentes transitions
aléatoires possibles.
De plus, une probabilité de transition P (hi ; si+1 ) est associée à chaque arc (hi ; si+1 ).
Dans un tel contexte, l’état …nal possible n’est bien souvent pas unique :
on dispose d’un ensemble d’états …naux Sn qu’on est susceptible d’atteindre.
En outre, on attribue une valeur scalaire v(sn ) à chaque état …nal sn 2 Sn (les feuilles de l’arbre
décision-hasard).

La valeur d’une politique correspond alors à l’espérance :

X
E( ) = P (sn ) v(sn )
sn 2Sn
où P (sn ) désigne la probabilité que l’on aboutisse à l’état sn en menant la politique .

Selon que les valeurs associées aux états …naux représentent des coûts ou des pro…ts, on recherche
une politique minimisant ou maximisant l’espérance.
4.2 Résolution.
La valeur d’une politique optimale est l’espérance de la politique optimale et est obtenue en remontant
à partir des états …naux vers l’état initial selon les relations de récurrence suivantes :
v(si ) = minfv(hi ) : hi 2 + (si )g

X
v(hi ) = P (hi ; si+1 ) v(si+1 )
si+1 2 + (h
i)
On associe une étiquette à chaque sommet de l’arbre décision-hasard correspondant à la valeur

d’une politique optimale de ce sommet à un état …nal.
Une décision optimale x (si ) en un état si correspond à un arc (si ; hi ) pour lequel l’étiquette
associée au sommet hi est minimale.
L’ensemble de ces décisions optimales constituent une politique optimale.
4.3 Exemples.
Exemple 1. Considérons un contrat d’assurance auquel on peut décider de
souscrire pour une année 1 et/ou une année 2.
Bien évidemment, on ne sait pas si on sera amené ou non à le faire valoir à la suite d’un sinistre.
De plus, la probabilité d’avoir un sinistre durant l’année 2 est conditionnée au fait qu’on ait déjà
subi ou non un sinistre durant l’année 1.
L’arbre décision-hasard correspondant à ce problème est représenté sur la …gure 5.
X Le sommet d1 (état) concerne le choix de souscrire (branche 1) ou non (branche 0) au contrat
lors de la première année.
X Les sommets h1 ou h2 (intervention du hasard) concernent l’occurrence (branche 1) ou non
(branche 0) d’un événement nécessitant de faire jouer ce contrat , où P (0) = 2=5 et P (1) = 3=5
sont données.
X Les sommets d2 , d3 , d4 et d5 concernent le choix de souscrire ou non au contrat lors de l’année
2.
X En…n, les sommets h3 , h4 , h5 , h6 , h7 , h8 , h9 et h10 concernent l’occurrence d’un événement
nécessitant de faire jouer le contrat lors de la deuxième année. Si on a déjà connu un sinistre lors
de l’année 1, la probabilité d’occurrence d’un tel événement est P (0) = 3=4 (et donc P (1) = 1=4).
Par contre, si on n’a pas connu de sinistre lors de l’année 1, les probabilités demeurent P (0) = 2=5
et P (1) = 3=5.
En chaque feuille de l’arbre décision-hasard …gure le coût total engendré (la valeur d’un état …nal).

La souscription à un contrat coûte 1, alors que faire face à un sinistre non couvert coûte 2 (contre
0 si l’on est assuré). On a
P2
v (f euille) = c (ai ) ,
8 i=1
>
> 0 si on ne souscrit pas à un contrat
>
>
>
> et on ne fait pas face à un sinistre
<
1 si on souscrit à un contrat
où c (ai ) = "si on fait face ou non à un sinistre couvert"
>
>
>
>
>
> 2 si on ne souscrit pas à un contrat
: "si on fait face à un sinistre non couvert"
et on fait face à un sinistre
Figure 5. Arbre décision-hasard pour le problème des contrats d’assurance
On véri…era sans peine que de telles paramètres conduisent à associer la valeur minf6=5; 1g = 1 au
sommet d2 , 5=2 au sommet d3 , 2 au sommet d4 et 3=2 au sommet d5 . Par conséquent, l’étiquette
du sommet h1 vaut (1 2=5) + (5=2 3=5) = 19=10, et l’étiquette du sommet h2 vaut 17=10.
La politique optimale consiste donc à souscrire au contrat la première année, et à ne souscrire au
contrat la deuxième année que si l’on n’a pas subi de sinistre lors de la première année.

Exemple 2. Dans une entreprise, on doit commander et stocker un produit sur deux périodes, de
telle sorte à maximiser l’espérance mathématique du béné…ce. Au départ, le stock est au niveau
s0 = 2. Au début de chaque période i (i = 1; 2), on peut décider de l’achat de xi (1 xi 2)
unités au prix ai . Durant cette période i, une demande de yi unités (1 yi 2) au prix de vente
unitaire vi , s’e¤ectue avec la probabilité pi (vi ). À la …n de la 2eme période, les invendus éventuels
sont soldés au personnel de l’entreprise à un prix unitaire 20 DA. Les valeurs de ai , vi et pi (vi )
sont données comme suit :
Période i 1 2
Prix d’achat ai 10 20
Prix de vente vi 30 50
Probabilité pi (1) 0:5 0:4
On note :
~ S1 et S2 les quantités en stock à la …n des périodes 1 et 2 (après vente) respectivement.
~ H1 et H2 les quantités en stock pendant les périodes 1 et 2, respectivement (après achat et
avant vente).
En utilisant ces notations et à la lumière des données du tableau ci-dessus, on a obtenu l’arbre
décision-hasard ci-dessous, où en chaque feuille on trouve le béné…ce total engendré en chaque
processus achat-vente. Autrement dit, si s2;` 2 S2 , est l’extrémité terminal du chemin s0 ; h1;k ; s1;k ; h2;` ; s2;` ,
alors la valeur de la feuille s2;` est v (s2;` ), où
v (s2;` ) = a1 (h1;k s0 ) + v1 (h1;k s1;k ) a2 (h2;` s1;k ) + v2 (h2;` s2;` ) + 20 s2;` ,8s2;` 2 S2 .

Partant des valeurs v(s2;k ) apportées aux sommets S2 , on dé…nit pour les sommets S1 , H1 et H2
les étiquettes suivantes :
P
v(h2;` ) = p2 (h2;` s2;` ):v(s2;k ); 8h2;` 2 H2
s2;` 2 + (h
2;` )
v(s1;k ) = max v(h2;` ); 8s1;k 2 S1

h2;` 2 + (s1;k )
P
v(h1;k ) = p1 (h1;k s1;k ):v(s1;k ); 8h2;` 2 H1
s1;k 2 + (h
1;k )
v(s0 ) = max
+
v(h1;k )
h2;` 2 (s1;k )
Le tableau suivant résume les valeurs des nœus de l’arbre :

v (s0 ) v(h1;k ) v (s1;k ) v(h2;` ) v (s2;` ) Chemins
max f113; 123g (0:5 108) max f108; 108g (0:4 90) 50 + 40 s0 ; h1;1 ; s1;1 ; h2;1 ; s2;1
+ (0:5 118) + (0:6 120) 100 + 20 s0 ; h1;1 ; s1;1 ; h2;1 ; s2;2
(0:4 90) 30 + 60 s0 ; h1;1 ; s1;1 ; h2;2 ; s2;3
+ (0:6 120) 80 + 40 s0 ; h1;1 ; s1;1 ; h2;2 ; s2;4
max f118; 118g (0:4 100) 80 + 20 s0 ; h1;1 ; s1;2 ; h2;3 ; s2;5
+ (0:6 130) 130 + 0 s0 ; h1;1 ; s1;2 ; h2;3 ; s2;6
(0:4 100) 60 + 40 s0 ; h1;1 ; s1;2 ; h2;4 ; s2;7
+ (0:6 130) 110 + 20 s0 ; h1;1 ; s1;2 ; h2;4 ; s2;8
(0:5 118) max f118; 118g (0:4 100) 40 + 60 s0 ; h1;2 ; s1;3 ; h2;5 ; s2;9
+ (0:5 128) + (0:6 130) 90 + 40 s0 ; h1;2 ; s1;3 ; h2;5 ; s2;10
(0:4 100) 20 + 80 s0 ; h1;2 ; s1;3 ; h2;6 ; s2;11
+ (0:6 130) 70 + 60 s0 ; h1;2 ; s1;3 ; h2;6 ; s2;12
max f128; 128g (0:4 110) 70 + 40 s0 ; h1;2 ; s1;4 ; h2;7 ; s2;13
+ (0:6 140) 120 + 20 s0 ; h1;2 ; s1;4 ; h2;7 ; s2;14
(0:4 110) 50 + 60 s0 ; h1;2 ; s1;4 ; h2;8 ; s2;15
+ (0:6 140) 100 + 40 s0 ; h1;2 ; s1;4 ; h2;8 ; s2;16
Ainsi, l’espérance mathématique du béné…ce optimal est 123 unités monétaires.
Remarque. L’utilisation de l’arbre de décision pour le poblème de l’exercice 20 de la série st
impensable, car il aura 216 feuilles, donc un nombre important de valeurs à calculer. L’étudiant
est invité à consulter l’annexe A3 pour le calcul de l’espérance du béné…ce de la politique optimale
de l’exemple 2 selon la méthode expliquée dans l’exercice 20
5 Conclusion.
Dans ce polycope, nous avons présenté un cadre formel pour la programmation dynamique, qui
est connue d’être une méthode d’énumération implicite des solutions et couramment utilisée en
optimisation combinatoire. Cette approche présente l’intérêt de pouvoir s’appliquer à une large
variété de problèmes, dont l’aspect séquentiel n’est pas forcément immédiat.
Deux procédures de résolution ont été données, une procédure "en avant" et une autre "en arrière",
pour lesquelles nous avons donné des conditions su¢ santes de validité (monotonie). Nous avons
aussi illustré ces procédures sur des exemples typiques en programmation dynamique (sac à dos,
plus court chemin, gestion de stocks).
En…n, une extensions classique de notre cadre d’étude (décision dans l’incertain) a été étudiée dans
une dernière partie.

6 Annexes.
A.1 Optimisation des systèmes dynamiques.
C’est l’optimisation de systèmes à évolution régie par une équation d’état (fonctionnelle) au cours
du temps et dont le comportement peut être modi…é par l’intermédiaire de variables de décision
(encore appelées de contrôle ou de commande). Ce problème apparaît dans de nombreux domaines
(plani…cation en économie, commande optimale en automatique, etc.) et a donné lieu à de très
nombreuses applications. Le modèle général lui correspondant est formellement identique à celui
étudié dans x2:4, où seule une interprétation dans le langage de la théorie des systèmes sera donnée.
On suppose que le système étudié peut être caractérisé à tout instant t par la donnée d’un vecteur
d’état E de dimension m (pour le contrôle de la trajectoire d’un mobile dans l’espace, l’état du
système à chaque instant t sera dé…ni par le couple position-vitesse).
De plus, on suppose que l’on peut agir sur le système par l’intermédiaire de variables (ou vecteurs)
de décision x1 ; x2 ; :::; xn , seulement à certains instants t0 ; t1 ; t2 ; :::; tn (pour le véhicule spatial à
un instant donné, les composantes du vecteur de décision correspondent aux poussées des di¤érents
réacteurs agissant sur la position du véhicule). Le comportement du système est alors dé…ni par
la donnée des fonctions de transition h1 ; h2 ; :::; hn où, pour tout i = 1; 2; :::; n
hi (xi ; Ei 1 )
donne l’état d’arrivée Ei du système à l’instant ti , en partant de l’état Ei 1 à l’instant ti 1 et en

appliquant la valeur xi à la variable (ou au vecteur) de décision xi .
D’autre part, à chaque décision xi prise à l’instant ti 1 , lorsque le système est dans l’état Ei 1 ,
est associée un coût ci (xi ; Ei 1 ) (pour le véhicule spatial, ci (xi ; Ei 1 ) sera la quantité de carburant
dépensée entre les instants ti 1 et ti lorsque la décision xi est prise à l’instant ti 1 ).
8
Partant de l’état E0 à l’instant t0 , on veut >
> E1 = h1 (x1 ; E0 )
>
>
amener le système dans un sous-ensemble d’états >
< E2 = h2 (x2 ; E1 )
Et (cible) à l’instant tn , tout en minimisant ..
> .
le coût total. Pour un ensemble de décisions >
> En = hn (xn ; En 1 )
>
>
x1 , x2 , :::, xn donné, l’état …nal du système sera : g(x ; x ; :::; x ) = E
1 2 n n
g(x1 ; x2 ; :::; xn ) (donné ci-contre).
de coût total f (x1 ; x2 ; :::; xn ) = c1 (x1 ; E0 ) + c2 (x2 ; E1 ) + + cn (xn ; En 1 ):
Une telle fonction étant décomposable, on pourra donc appliquer un algorithme de programmation
dynamique au problème
F = min f (x1 ; :::; xn )
g(x1 ; :::; xn ) 2 Et
L’équation de récurrence de la programmation dynamique s’écrit alors :
8E : Fn (E) = min
xn
fcn (xn ; E)g
hn (xn ;E)2Et
puis pour 1 i n 1
8E : Fi (E) = minfci (xi ; E) + Fi+1 (hi (xi ; E)g
xi
F = F1 (E0 ):

A.2 La suite de Fibonacci. 8

< u0 = 0
La suite de Fibonacci est la suite d’entier (un )n 0 dé…nie récursivement par : u1 = 1
:
un = un 1 + u n 2 ; 8 n 2
8
>
> Algorithm Fibonacci F1
>
>
> procédure Fibonacci(n)
>
>
>
>
> if n 1 then
On peut traduire directement <
return n
cette dé…nition en un algorithme
> else
récursif de complexité exponentielle7 : > >
>
>
> return Fibonacci(n 1) + Fibonacci(n 2)
>
>
>
> end if
:
end procedure
Pour améliorer la performance de l’algorithme, on peut stocker les résultats intermédiaires obtenus
et les réutiliser directement en cas de besoin au lieu de les recalculer. Cela donne :
Algorithm Fibonacci F2
procédure Fibonacci(n) C’est l’idée de la programmation dynamique.
if n 1 then La complexité devient alors linéaire :
return n on ne remplit la case T [n] qu’une fois,
end if donc le nombre d’appels à Fibonacci(i),
if T [n] n’est pas défini then pour chaque valeur i n est d’au plus 3 ;
Fibonacci(n 1) + Fibonacci(n 2) une fois pour le calculer,
end if une fois quand on calcule Fibonacci(i + 1)
return T [n] et une fois quand on calcule Fibonacci(i + 2).
end procedure
On peut dé-récursiver l’algorithme. Il s’agit de remplir le tableau T directement case par case8 .
Algorithm Fibonacci F4
Algorithm Fibonacci F3 procédure Fibonacci(n)
procédure Fibonacci(n) Allouer T avec n + 1 cases
Allouer T avec n + 1 cases a=0
T [0] = 0 b=1
T [1] = 1 for i de 2 à n 1 do
for i de 2 à n 1 do c=b
T [i] = T [i 1] + T [i 2] b=a+b
end for a=b
return T [n] end for
end procedure return b
Il est immédiat que l’algorithme est bien linéaire. end procedure
Il prend aussi une quantité de mémoire linéaire. Pour notre exemple, il su¢ t de se rappeler
La dernière étape consiste à essayer de gagner des deux derniers termes pour calculer le nouveau.
en mémoire en ne mémorisant que le nécessaire. On peut donc n’utiliser qu’un espace mémoire
constant (Voir l’algorithme F4 ci-dessus).
8
On s’aperçoit qu’il faut faire le contraire de ce que fait l’algorithme récursif : commencer par les petites valeurs.

A.3 Pogrammation dynamique dans l’incertain - Exemple 2.

Exemple 2. Dans une entreprise, on doit commander et stocker un produit sur deux périodes, de
telle sorte à maximiser l’espérance mathématique du béné…ce. Au départ, le stock est au niveau
s0 = 2. Au début de chaque période i (i = 1; 2), on peut décider de l’achat de xi (1 xi 2)
unités au prix ai . Durant cette période i, une demande de yi unités (1 yi 2) au prix de vente
unitaire vi , s’e¤ectue avec la probabilité pi (vi ). À la …n de la 2eme période, les invendus éventuels
sont soldés au personnel de l’entreprise à un prix unitaire 20 DA. Les valeurs de ai , vi et pi (vi )
sont données comme suit :
Période i 1 2
Prix d’achat ai 10 20
Prix de vente vi 30 50
On dé…nit, pour chaque période i, i = 1; 2 :
Ci (si ): l’espérance mathématique optimale du béné…ce si on rentre en i avec un stock si
Ci (si ; xi ): l’espérance mathématique du béné…ce si on rentre en i avec un stock si et on achète xi
On a l’équation fonctionnele relative à la programmation dynamique : :
Ci (si ) = max Ci (si ; xi ); 8i = 1; 2

0 xi 2
où : Ci (si ; xi ) = c(xi ) + Ci (si ; xi ; Pi (1)) + Ci (si ; xi ; Pi (2)); 8i = 1; 2
8
> c(xi ) = ai xi ; 8i = 1; 2
>
>
>
< C1 (s1 ; x1 ; P1 (1)) = P1 (1)(v1 + C2 (s1 + x1 1))
avec : C2 (s2 ; x2 ; P2 (1)) = P2 (1)(v2 + 20(s2 + x2 1))
>
>
>
> C (s ; x ; P (2)) = P1 (2)(2v1 + C2 (s1 + x1 2))
: 1 1 1 1
C2 (s2 ; x2 ; P2 (2)) = P2 (2)(2v2 + 20(s2 + x2 2))
Réponse à notre problème est C1 (2). Les calculs sont résumés dans le tableau ci-dessous :
i si xi c(xi ) Ci (si ; xi ; P i (1)) Ci (si ; xi ; P i (2)) Ci (si ; xi ) Ci (si )
2 1 1 20 0:4 (50 + 20) 0:6 (100 + 0) 68 68
2 40 0:4 (50 + 40) 0:6 (100 + 20) 68
2 1 20 0:4 (50 + 40) 0:6 (100 + 20) 88 88
2 40 0:4 (50 + 60) 0:6 (100 + 40) 88
3 1 20 0:4 (50 + 60) 0:6 (100 + 40) 108 108
2 40 0:4 (50 + 80) 0:6 (100 + 60) 108
1 2 1 10 0:5 (30 + 88) 0:5 (60 + 68) 113 123
2 20 0:5 (30 + 108) 0:5 (60 + 88) 123

A.4 Programmation dynamique généralisée.

On s’intéresse ici à une problématique similaire à celle évoquée dans un article de [SNI 81]9 ,
concernant la procédure de [KAO 78]10 pour un problème de voyageur de commerce avec des coûts
stochastiques. Nous étudions dans cette optique un problème de plus court chemin stochastique où
une probabilité de retard est associée à chaque arc. Considérons le graphe de la …gure 6. On part
du sommet s à 12H00 et on suppose qu’on prend des bus en chaque sommet du graphe, a…n de se
rendre au sommet t où l’on a un train à prendre qui part à 16H00. En chaque sommet du graphe
et à chaque heure pile part un bus pour se rendre au sommet suivant en un temps de parcours
normalement inférieur à une heure. Néanmoins, les aléas du tra…c peuvent allonger le temps de
parcours au-delà de l’heure, et sont modélisés par une probabilité d’occurrence de cet événement.
Figure A.4.1
On recherche le chemin le plus adéquat pour arriver à destination avant 16H00. Remarquons que
cet horaire est respecté si et seulement si un bus au plus est en retard. Soit R(P ) la variable
aléatoire représentant le nombre de bus en retard sur le chemin P . On cherche donc à maximiser
la probabilité P (R(P ) 1).
Au sommet t, on a P (R(s; 1; 3; t) 1) < P (R(s; 2; 3; t) 1). En e¤et, en additionnant la
probabilité que tous les bus soient à l’heure, avec les probabilités qu’un seul bus soit en retard, on
obtient :
8
>
> P (R(s; 1; 3; t) 1) = 0:009 + 0:9 0:09 + 0:1 0:01 + 0:9 0:09
<
= 0:172
>
> P (R(s; 2; 3; t) 1) = 0:016 + 0:6 0:04 + 0:6 0:04 + 0:9 0:16
:
= 0:208
et donc la solution optimale est le chemin (s; 2; 3; t). Malheureusement, si l’on prend comme
valeur du chemin P la probabilité P (R(P ) 1), l’application de la méthode de programmation
dynamique conduit à une erreur car le critère n’est pas monotone. En e¤et, au sommet 3 on a :
P (R(s; 1; 3) 1) = 1 0:09 = 0:91

P (R(s; 2; 3) 1) = 1 0:36 = 0:64
En conséquence, le chemin (s; 2; 3) serait coupé lors de l’exécution de la méthode.

9
[SNI 81] SNIEDOVICH M., « Analysis of a preference order traveling salesman problem » ,
Operations Research, vol. 29, n 6, p. 1234-1237, 1981.
10
[KAO 78] KAO E., « A preference order dynamic program for a stochastic traveling salesman problem » ,
Operations Research, vol. 26, n 6, p. 1033-1045, 1978.

La programmation dynamique généralisée a été développée par [CAR 89, CAR 90]11 pour faire
face à ce type de situation. Elle est basée sur un principe faible d’optimalité qui s’énonce comme
suit :
Une politique optimale est composée de sous-politiques susceptibles de faire

partie d’une politique optimale.
Plus précisément, il s’agit d’adapter le principe d’optimalité au cas où la fonction de valuation des
politiques n’est pas monotone, en élimininant les politiques partielles dont on sait qu’il n’est pas
possible de les compléter en une politique optimale.Pour cela, nous utilisons pour chaque état s le
préordre partiel 4s tel que pour tout ( 1 ; 2 ) 2 (s0 ; s)2 :
1 4s 2 ,9 02 (s; sn ) : 8 2 (s; sn ); v( 1 ; 0 ) v( 2 ; 0 )
La méthode de la programmation dynamique généralisée consiste alors à ne retenir, pour chaque

état s, que les politique 2 (s0 ; s) pour lesquelles il n’existe pas de politique 0 réalisable de s0 à
s telle que 0 s . 1En procédant ainsi, nous aboutissons pour la dernière période à un ensemble
de politiques réalisables de s0 à sn contenant toutes les politiques optimales.
Dans la pratique, il peut être di¢ cile de construire dans son intégralité le préordre 4s ; il est
0
néanmoins souvent possible de déterminer une condition su¢ sante pour que s . Cela permet
d’e¤ectuer des coupes et de gagner ainsi sensiblement en e¢ cacité par rapport à une méthode
exhaustive.
Dans l’exemple du plus court chemin stochastique, une telle approche consisterait à remarquer
qu’un chemin partiel P1 ne peut conduire à un chemin optimal dès lors qu’il est strictement
dominé par un autre chemin P2 au même sommet, au sens de la dominance stochastique 4s dé…nie
comme suit :
P2 4s P1 () 8k 2 f0; 1; 2; 3g; P (R(P2 ) k) P (R(P1 ) k)
Dès lors, un chemin n’est coupé par l’algorithme que s’il remplit cette condition. Sur le graphe de la
…gure 6, le chemin (s; 2; 3) n’est pas coupé au sommet 3 car P (R(s; 2; 3) 0) > P (R(s; 1; 3) 0).
En évaluant des politiques partielles vis-à-vis de leur impact sur le problème global, les errements
potentiels liés à la vision locale de la programmation dynamique traditionnelle sont évités. Ainsi,
l’exactitude de la procédure de résolution est assurée.
11
[CAR 89] CARRAWAY R., MORIN T., , MOSKOWITZ H., « Generalized dynamic programming for stochastic
combinatorial optimization » , Operations Research, vol. 37, n 5, p. 819-829, 1989.
[CAR 90] CARRAWAY R., MORIN T., MOSKOWITZ H., « Generalized dynamic programming for multicriteria
optimization » , European Journal of Operational Research, vol. 44, p. 95-104, 1990.

ODDI_01-12-2024

Transféré par

Droits d'auteur :

Formats disponibles

ODDI_01-12-2024

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

ODDI_01-12-2024

Transféré par

Droits d'auteur :

Formats disponibles

Optimisation Dynamique et Décision dans l’Incertain

2 Les fondements théoriques de la programmation dynamique.

3 Exemple d’application de la programmation dynamique.

4 Programmation dynamique dans l’incertain.

[2] M. Goudran et M. Minoux, "Graphes et algorithmes", Ayrolles 95.

[3] J.L. Lauriere, "Eléments de programmation dynamique", Masson 82.

[4] Michel Minoux. "Programmation Mathématique, Théorie et algorithmes", volume 2, Collection

[5] M. Sakarovitch . "Optimisation combinatoire : Programmation discrète". Editeur : Broché,

[6] L.A. Wolsey, "Integer programming", Wiley interscience 98.

"dans une séquence optimale de décisions,

Equipe pédagogique : KAHOUL nawel 2

1.1 Le triangle de Pascal.

La fonction ci-contre, est un algorithme Fonction cnk (n; k : naturel) : NaturelNonNul

Voyons l’exécution de cette fonction sur un exemple donné:

Equipe pédagogique : KAHOUL nawel 3

Equipe pédagogique : KAHOUL nawel 4

1.2 Le problème de retour monnaie.

1.2.2 Formalisation mathématique.

En fait, la valeur de la solution optimale de (P ) sera ce nombre minimal de pièces et la solution

1.2.3 Résolution par la programmation dynamique.

C(k; m) : le nombre minimum de pièces pour produire exactement le montant m

Equipe pédagogique : KAHOUL nawel 5

1.2.4 Exemple numérique.

on rend deux pièces de valeur 4.

1.3 Le problème de la partition.

p(a1 ); p(a2 ); :::; p(an );

est-il possible de les partager en deux ensembles de mêmes poids total ?

M = K = P = la demi-somme de tous les objets,

on reconnaît la forme générale du problème de la partition.

1.3.1 Résolution du problème de la partition par la programmation dynamique.

Equipe pédagogique : KAHOUL nawel 6

Si A(i 1; j) = V , alors A(i; j) = V ;

A(i; j) = A(i 1; j) ou A(i 1; j p(ai )).

On considère le problème de partition pour les données suivantes :

n = 6; p(a1 ) = 5; p(a2 ) = 9; p(a3 ) = 3; p(a4 ) = 8; p(a5 ) = 2; p(a6 ) = 5.

Par conséquent, P vaut 16.

Equipe pédagogique : KAHOUL nawel 7

1.4 Le problème du sac à dos.

1.4.2 Cas particulier de problèmes de "sac à dos".

L’idée de base de la programmation dynamique consiste à essayer de ramener la résolution du

Equipe pédagogique : KAHOUL nawel 8

1. On plonge le problème posé dans une famille de problèmes de même nature.

Dans ce cas de (KP ), on considèrera, la famille des n(b + 1) problèmes

La valeur E, qui paramètre la famille de problèmes ci-dessus, est classiquement appelée

Equipe pédagogique : KAHOUL nawel 9

F1 (0) = max fc1 x1 + F2 (a1 x1 )g = max fF2 (0); c1 + F2 (a1 )g :

= maxfFi+1 (E); ci + Fi+1 (E + ai )g

Algorithme 1. (Résolution du problème du sac à dos par la programmation dynamique)

Equipe pédagogique : KAHOUL nawel 10

1.4.3 Détermination d’une solution optimale x .

0 si Fi (E) = Fi+1 (E)

Equipe pédagogique : KAHOUL nawel 11

Fk (E) = maxfFk+1 (E); ck + Fk+1 (E + ak )g; 8k; 1 k N 1; E 2 [0; b] \ N:

2) Application numérique : appel à Algorithme 1

(b) Pour k = 2, calcul de Fi (E), 8E (0 E 5) par

Fk (E) = maxfFk+1 (E); ck + Fk+1 (E + ak )g;

F2 (E) = maxfF3 (E); c2 + F3 (E + a2 )g = maxfF3 (E); 1 + F3 (E + 3)g

(c) Etape 1: calcul de F par

F = F1 (0) = maxfF2 (0); c1 + F2 (a1 )g = maxf4; 2+ 3 g = 5

Equipe pédagogique : KAHOUL nawel 12