Revue économique

Introduction à la programmation dynamique

Monsieur Pierre Duharcourt

Citer ce document / Cite this document :

Duharcourt Pierre. Introduction à la programmation dynamique. In: Revue économique, volume 20, n°2, 1969. pp. 182-
234;

doi : https://doi.org/10.3406/reco.1969.407859

https://www.persee.fr/doc/reco_0035-2764_1969_num_20_2_407859

Fichier pdf généré le 27/03/2018

Résumé
La programmation dynamique est une méthode d'optimisation des processus de décisions
séquentielles. Elle s'appuie sur l'algorithme de Bellman dont la traduction sur le graphe associé au
processus supposé discret permet de rechercher le chemin de valeur optimale partie. Les
programmes les plus simples sont ceux où l'avenir est déterminé intérêt de l'algorithme est évident
quand le caractère combinatoire du problème amène à comparer un très grand nombre de
politiques (2e partie). Mais dans beaucoup de cas concrets l'avenir est incertain. Dans le cas où il
est probabilisable il est possible de comparer les stratégies en les évaluant après leur espérance
mathématique. Ce critère est cependant pas suffisant où les distributions de probabilité sont trop
dispersées. Il est inapplicable dans le cas d'un avenir non probabilisable: les différents critères de
choix qu'on peut alors utiliser sont parfois contradictoires donc peu satisfaisants (3e partie).

Abstract
Dynamic programming is a means of optimising sequential decision processes. It is based on
Bellman's algorithm, which when expressed on the process graph (taken as discrete), makes it
possible to fincl the path of optimal value (lst part). The simplest programmes are those which
have a determinate future : the value of the algorithm is clear where the combinative character of
the problem entails comparison of a large number of policies (2nd part). But the future is uncertain
in a large number of cases. Where it can be probabilised we may compare strategies by assessing
them on their inathematical expectancy. But this criterion is inadequate where probability
distributions are too wiclely dispersed. It is inapplicable in cases where there is no probabilisable
future : the various criteria that can then be employee! in selection are sometimes contraclictory
and therefore unsatisfactory (3rd part).
jo ->
Aï —

INTRODUCTION A LA
PROGRAMMATION DYNAMIQUE

RESUME La programmation dynamique est une méthode d'optimisation

des processus de décisions séquentielles. Elle s'appuie sur l'algorithme de Bellman,
dont la traduction sur le graphe associé au processus (supposé discret) permet
de rechercher le chemin de valeur optimale (lro partie). Les programmes les
plus simples sont ceux où l'avenir est déterminé : l'intérêt de l'algorithme est
évident quand le caractère combinatoire du problème amène à comparer un
très grand nombre de politiques (2e partie). Mais dans beaucoup de cas concrets
l'avenir est incertain. Dans le cas où il est probabilisable, il est possible de
comparer les stratégies en les évaluant d'après leur espérance mathématique. Ce
critère n'est cependant pas suffisant où les distributions de probabilité sont trop
dispersées. Il est inapplicable dans le cas d'un avenir non probabilisable : les
différents critères de choix qu'on peut alors utiliser sont parfois contradictoires,
donc peu satisfaisants (3e partie).

ABSTRACT Dynamic programming is a means of optimising sequential

decision processes. It is based on Bellman's algorithm, which when expressed
on the process graph (taken as discrete), makes it possible to find the path of
optimal value (1st part). The simplest programmes are those which have a
determinate future : the value of the algorithm is clear where the combinative
character of the problem entails comparison of a large number of policies
(2nd part). But the future is uncertain in a large number of cases. Where it
can be probabilised we may compare strategies by assessing them on their
mathematical expectancy. But this criterion is inadequate where probability
distributions are too widely dispersed. It is inapplicable in cases where there
is no probabilisable future : the various criteria that can then be employed in
selection are sometimes contradictory and therefore unsatisfactory (3rd part).
 INTRODUCTION

La plupart des problèmes de choix économiques doivent être posés

en termes dynamiques. Il ne suffit pas de prendre, à un instant donné,
une décision isolée.
D'une part, les conséquences de chaque décision s'échelonnent
sur une période relativement longue et l'évaluation des effets
immédiats ne doit pas constituer le seul critère d'appréciation.
D'autre j)art, il sera nécessaire de prendre ultérieurement de
nouvelles décisions et l'éventail des possibilités dépendra alors de l'évo
lution passée, en particulier des contraintes introduites par les décisions
précédentes.
L'agent de décision doit donc se préoccuper de la cohérence tem
porelle de ses décisions, dont les conditions et les conséquences sont
mutuellement dépendantes.
Les problèmes de régulation de la production et des stocks, de
gestion d'équipements, de choix d'investissements, ou — à l'échelon
macro-économique — de planification nationale, revêtent ainsi un
caractère séquentiel : des décisions de même nature doivent être prises
périodiquement, chacune d'entre elles ayant un effet immédiat, mais
aussi un effet à long terme.
Mais cette exigence de cohérence temporelle ne constitue pas la
seule difficulté rencontrée dans les programmes dynamiques. Dans la
plupart des cas concrets, les effets des décisions se combinent avec
l'intervention du hasard ; une même décision peut avoir des effets
variables suivant 1'« état du monde ». Il ne suffit plus de se fixer, pour
chaque instant, une seule décision, mais de définir un ensemble de
décisions conditionnelles, capable de faire face à toute éventualité. La
notion de politique — ou séquence de décisions — fait alors place à
celle de stratégie.
L'étude des problèmes de décisions séquentielles est relativement
récente. Elle a débuté notamment avec les travaux de P. Massé 1. Puis
R. Bellman a montré que le « principe d'optimalité » fournissait une
méthode générale de résolution des programmes dynamiques 2. Depuis
les recherches en ce domaine se sont multipliées.

1. P. Massé, Les réserves et la régulation de l'avenir, Hermann, Paris, 1946.

2. R. Bellman, On general class of problems involving sequential analysis,
RAND Corp., RM 647, Juillet 1951.
184 REVUE ECONOMIQUE

Cet article ne constitue qu'une introduction à la programmation

dynamique : nous n'entrerons pas dans les détails de l'étude
mathématique des modèles utilisés.
Pour simplifier, nous limiterons notre exposé aux cas où le temps
est une variable discrète 3 : chaque séquence de processus aura une
durée finie. C'est le cas de la plupart des problèmes de décisions
économiques (la période de référence y est le jour, la semaine, le mois
ou l'année).
Nous supposerons également, le plus souvent, que les « variables
d'état » sont discrètes et même qu'elles appartiennent à des ensembles
finis. Ce cas correspond à beaucoup de problèmes concrets (par
exemple, le choix d'investissements, du fait de leur indivisibilité) ; d'autre
part, il est souvent possible (par des approximations) de transposer
en termes discrets un problème initialement posé en termes continus.
Les processus à variables discrètes ou continues relèvent d'ailleurs
— comme nous le verrons — des mêmes méthodes d'optimisation.
Mais la mise en œuvre de ces méthodes dans le cas continu présente
certaines difficultés, alors que la résolution des processus à variables
discrètes est facilitée par le recours à un graphe.
Aussi la première partie de l'étude sera-t-elle consacrée à la
présentation de la théorie des graphes. Nous définirons notamment les
graphes séquentiels, pour lesquels le principe de Bellman fournit une
méthode générale de recherche du chemin de valeur optimale.
Puis nous exposerons les méthodes de résolution des programmes
dynamiques, en étudiant successivement leurs conditions d'application.
Nous envisagerons successivement (par ordre de complexité
croissante) :
— les programmes dynamiques en avenir certain, qui feront l'objet
de la deuxième partie ;
— les programmes dynamiques en avenir aléatoire, en évoquant
pour terminer les problèmes posés par l'introduction du risque et de
l'incertitude. Ce sera l'objet de la troisième partie.

3. La résolution des problèmes en temps continu est rarement abordée.

Nous renvoyons cependant le lecteur aux références suivantes : R. Bellman et
S. Dreyfus, La programmation dynamique et ses applications (traduit de
l'américain), Dunod, Paris, 1965, chap. 5 et 6. — O.L.R. Jacobs, An Introduction
to Dynamic Programming, Chapman and Hall, Londres, 1967, chap. 3.
 LA PROGRAMMATION DYNAMIQUE 185

LISTE DES PRINCIPAUX SYMBOLES

£ symbole d'appartenance (d'un élément à un ensemble)

C symbole d'inclusion (d'un ensemble dans un autre)
V quantificateur universel {a : « pour tout a » ou « quel que soit a »)
R relation binaire définie dans un ensemble
< relation d'ordre strict définie dans un ensemble
G = (X, U) graphe défini par l'ensemble X (des sommets) et l'ensemble U (des arcs)
xv : sommet d'un graphe quelconque
u = (xp, x4) : arc d'un graphe quelconque
Xn sous-ensemble numéro n d'un graphe séquentiel
x''n : sommet de Xn
(xln. xsa+1) : arc d'un graphe séquentiel
À taux d'intérêt
a coefficient d'actualisation
S symbole de sommation
H f(x) = somme des f(x) pour les valeurs de la variable x appartenant
x £X à l'ensemble X
OPT (MAX ou MIN) symbole désignant la valeur optimale (maximale ou
:

minimale) d'une fonction

fa) = OPT f(x)
OPT f(x) = valeur optimale d'une fonction de x définie pour les valeurs
x £X de x appartenant à l'ensemble X

Processus en avenir certain

xr : variable d'état à l'instant n (par assimilation, sommet correspondant du graphe)
(/ (xvn, v\+1) décision faisant passer, au cours de la phase » + 1, de l'état
:

x'n à l'état *sn+1 (notée également (x'n, %sn+jL) par assimilation

à l'arc correspondant)
P (Xo, XJ : politique définie pour l'ensemble du processus
P (Xn, — ) : politique définie à partir de la date n
P (x'n, — ) : politique définie à partir de l'état x'n
P ( — , XJ : politique définie jusqu'à la date n
P ( — , xru) : politique définie jusqu'à l'état x'n
v (s1',,, xs,,_|_P : valeur associée à l'arc (xrn, xs11+1)
Vp (Xo, XN) : valeur associée à la politique P entre Xo et XN
r (Xn, — ) : valeur de la politique P à partir de la date n etc..

Processus en avenir aléatoire et incertain

x variable d'état précédant une décision
y variable d'état précédant l'intervention du hasard
186 REVUE ECONOMIQUE

cl (x, y) (ou (x, y)) décision conduisant de x à y

e (<J> x) (ou (y, x)) événement conduisant de y à x
V (y, x) • .probabilité conditionnelle de cet événement
a (x, y) : valeur associée à un arc de décision
b (y, x) : valeur associée à un arc de hasard
v (xrn, xsn+1) (ou v (yvn, ysn+:)) valeur associée à une phase
S stratégie (séquence de vecteurs de décision)
Les notations S (Xo, XN), S (Xn, —), ... sont équivalentes à celles qui ont
été données pour les politiques
E (S) espérance mathématique des valeurs pouvant être obtenues avec la stratégie
S (d'où les notations Eg (Xu, —), . . .)

N.B. — Les indices écrits au bas d'une lettre indiquent des dates ou des périodes
Exemples xn état à la date n
en événement intervenant à la date n
— Les indices écrits au haut d'une lettre sont associés à un choix parmi des
variables, des décisions (ou des politiques, ou des stratégies), ou des
événements relatifs à une même date ou une même période.
Exemples
1 di. décision
, , n° 'f . \ choisi(e)s
u . ./ \ parmi ceux (ou
/ celles)
un que Ion
v peut
eJ événement n° i
' - , , , N A
,

S1 stratégie
, i[ prendre (ou rencontrer) au même moment
n° i.
cl1 (xln) : décision n° / pouvant être prise à la date n à partir de
l'état x1;,.

INTRODUCTION A LA THEORIE DES GRAPHES

GRAPHES SEQUENTIELS

Un des domaines les plus féconds de l'algèbre moderne est la

théorie des graphes qui a pour origine les travaux de König 4. Les
concepts qu'elle introduit sont dès maintenant d'un emploi courant
dans de nombreux problèmes d'économie, notamment ceux qui ont un
caractère combinatoire. L'objet de cette partie introductive est de
présenter les premiers éléments de cette théorie 5 ; nous nous
intéresserons ensuite au cas particulier des graphes séquentiels, pour lesquels
le théorème de Bellman fournit une méthode de recherche du chemin
de valeur optimale.

4. König, Theorie der Endlichen und Unendlichen graphen, Leipzig, 1936.

5. L'ouvrage de base est actuellement celui de G. Berge, Théorie des graphes
et applications-, Dunod, Paris, 1958. — Cf. également A. Kaufmann, Méthodes
et modèles de la recherche opérationnelle » t. II. Dunod, 1964, chap. I et IV.
 LA PROGRAMMATION DYNAMIQUE 187

1. PREMIERS ELEMENTS DE LA THEORIE DES GRAPHES

1 DÉFINITIONS 6
Considérons un ensemble fini X d'objets x°, x\ ... xp. ... xm~L et un
ensemble U constitué par des couples ordonnés (xp, xq) d'éléments de
X. Le couple G = (X. U) constitue un graphe fini d'ordre m.
Les éléments de X sont appelés sommets, et les éléments de U
arcs du graphe. Soit un arc (xp, xq\ on dit que xp est l'extrémité initiale
de cet arc et que xq est son extrémité terminale.
Un graphe G = (X, U) est généralement représenté par un
diagramme où les sommets sont figurés par des points et où l'on joint un
sommet xp à un sommet xq par une flèche chaque fois qu'existe l'arc
(xp, xq). La figure représente un graphe d'ordre 6 (6 sommets : x°,
x1, ..., x5) comportant 9 arcs [(.r°, x1), (x°, x5), (x1, .r°), (x1, v1),
(x1, x2), (x1, x5), (x3. x°), (x4, x3), (x1, a4)].
Deux sommets sont adjacents
s'ils sont reliés par un arc. Un
chemin est une séquence d'arcs
tels que l'extrémité terminale de
chacun coïncide avec l'extrémité
initiale du suivant. Le nombre
d'arcs du chemin s'appelle sa
longueur : sur le graphe de la fig. 1,
la séquence (x1, x4, x3) est un
chemin de longueur 2. Un circuit est
un chemin dont les extrémités
initiales et terminales sont Figure 1 :
Représentation d'un graphe
confondues : la séquence (x1, x4, x3, x°, x1)
est un circuit de longueur 4 ; une, boucle est un circuit de longueur 1 :
l'arc (x1, x1) est une boucle. On dit qu'un chemin (ou un circuit) est
simple s'il n'emprunte pas deux fois le même arc ; qu'il est élémentaire
si, de plus, il ne passe pas deux fois par le même sommet : sur la fig. 1,
(x1, x4, ix3. x°, x1, x5) est un chemin simple ; (x1, x4, x3, x°, x1) est un
circuit élémentaire.
On dit qu'un graphe est fortement connexe si, quels que soient les

6. Le développement qui suit utilise les définitions habituelles de la théorie

des ensembles, dont des exposés élémentaires peuvent être trouvés, par exemple,
dans : Queysanne et Delachet, L'Algèbre moderne, Coll. « Que sais-je ? »,
n" 66. — J. Bouzitat et E. Berrebi, Eléments de mathématiques, cours polycopié
de 1" année de la Faculté de Droit et des Sciences économiques de Paris, 1966,
chap. I et IL
188 REVUE ECONOMIQUE

deux sommets distincts <xr' et xq, il existe un chemin allant de xp à xq

(dans cet ordre).
Les définitions que nous venons de donner supposent que l'on tient
compte de l'orientation : ainsi, un arc est défini par un couple ordonné
{xv, xq). Aux concepts orientés : arc, chemin, circuit, graphe fortement
connexe correspondent les concepts non orientés : arête, chaîne, cycle,
graphe connexe. Ainsi on dit qu'il existe une arête entre deux sommets
xp et 3cq s'il existe un arc de %p à xq et/ou de xa à oc,, ; une chaîne est
une séquence d'arêtes jointives ; up cycle est une chaîne fermée ; un
graphe connexe est un graphe dans lequel deux sommets quelconques
sont toujours reliés par au moins une chaîne : le graphe de la fig. 1
n'est pas fortement connexe, mais il est connexe. On aj)pelle arbre un
graphe connexe qui ne contient aucun cycle.

2 — Intérêt de la notion de graphe

La notion de graphe apparaît chaque fois qu'on étudie un ensemble
X d'objets dénombrables et qu'on définit une relation binaire R dans
cet ensemble 7. L'ensemble X et l'ensemble U des couples de X2 (carré
cartésien de l'ensemble X) liés par R définissent un graphe G = (X, U)
— Par exemple, un réseau de routes définit un graphe. L'ensemble X
est constitué par les différents lieux envisagés. Les arcs correspondent
aux routes joignant deux quelconques de ces lieux. Le graphe est
orienté si on tient compte du sens de parcours (une route à double
sens xvç=$xn détermine alors deux arcs de sens contraire). On peut
définir pour un tel graphe une fonction de valeur qui sera par exemple
la distance séparant deux extrémités d'un arc ou le coût de cet arc
(cf. infra).

2. GRAPHES SEQUENTIELS - CHEMIN A VALEUR OPTIMALE

DANS UN GRAPHE SEQUENTIEL

1 DÉFINITION D'UN GRAPHE SEQUENTIEL

a) On appelle graphe séquentiel un graphe G = (X, U) satisfaisant
aux conditions suivantes 8 :

7. On appelle relation binaire dans un ensemble une proposition vraie pour

certains couples (x{, x^ de cet ensemble.
8. En toute rigueur, la définition d'un graphe séquentiel passe par celle de
h « fonction ordinale » d'un graphe. Cf. A. Kaufmann et R. Cruon, La
programmation dynamique : gestion scientifique séquentielle, Dunod, Paris, 1965, pp.
32-36. Nous ne donnons ici qu'une définition moins correcte, mais — à notre
sens — plus imagée.
 LA PROGRAMMATION DYNAMIQUE 189

1) L'ensemble X des sommets est réparti en sous-ensembles Xo

X1 ... XN (N étant éventuellement infini) disjoints9, totalement et
strictement ordonnés : Xo précède Xl3 Xx précède X2, ... XN_X précède
XN ; ce que l'on écrit
Xn <x x

Le sous-ensemble Xo qui n'a pas de précédent est dit entrée du graphe.

Le sous-ensemble XN qui n'a pas de successeur est dit sortie du graphe.
2) Un arc ne peut joindre que deux sommets appartenant à deux
sous-ensembles Xn et Xn+1 consécutifs.
Notons qu'un graphe séquentiel est ordonné, et qu'il ne peut
contenir ni circuit ni boucle.
Un tel graphe peut être représenté de la façon suivante (fig. 2).
Les sommets d'un même sous-ensemble Xn sont disposés sur une même
droite ; les droites Xo Xx ... Xn, ... XN sont disposées dans cet ordre.
Chaque arc joint deux sommets de deux droites consécutives ; il n'y a
pas d'arcs joignant deux points d'une même droite.

Figure 2 : Représentation d'un graphe séquentiel

9. En d'autres termes les sous-ensembles XQ X,T définissent une

partition » do l'ensemble X.
190 REVUE ECONOMIQUE

1er tronçon 2ème tronçon 3ewe tronçon Uème tronçon

Figure 3 : Graphe séquentiel associé à un processus de décisions successives

(Cas du réseau routier)

b) La notion de graphe séquentiel est particulièrement intéressante

pour l'étude des processus de décisions successives.
Reprenons l'exemple du réseau routier. Le graphe associé peut
devenir séquentiel si l'on divise les chemins en tronçons (les différentes
localités sont disposées sur des transversales), et si l'on impose un sens
de parcours (chaque chemin est une séquence d'arcs allant d'un sommet
d'une transversale à un sommet de la transversale suivante). Etudions
les chemins allant de l'entrée à la sortie (dans le cas de la figure 3,
partant de A et aboutissant à K).
Le cheminement le long d'un arc (xr„, x*n+i) correspond à la décision
— si l'on se trouve en xrn — d'aller de xrn à x\+1.
Un chemin A -> K est le résultat de 4 décisions successives : par
exemple la séquence A, C, G, I, K correspond aux choix : emprunter
l'arc (A, C), puis l'arc (C, G), puis l'arc (G, I) et enfin l'arc (I, K)
(remarquons que pour la dernière phase le seul « choix » possible est
(I, K).
2 — Recherche du chemin de valeur optimale
a) Le théorème de Bellman 10. Etant donné un graphe G = (X, U), il
arrive qu'on puisse associer à tout arc u = (xv, xq) un nombre v (u) — v
(xv, Xe1) appelé valeur de cet arc. La valeur d'un chemin sera alors la
somme des valeurs des arcs définissant ce chemin.
10. R. Bellman, The Theory of Dynamic Programming, Bull. Amer. Math.
Soc, 1954, pp. 503-515. — R. Bellman, Dynamic Programming, Princeton
University Press, New Jersey, 1957.
 LA PROGRAMMATION DYNAMIQUE 191

On peut alors se poser la question : quel est le chemin de valeur

optimale (selon le cas, minimale ou maximale) conduisant d'un
sommet A à un sommet K ?
— Une première méthode de recherche consisterait à étudier tous les
chemins existant entre les sommets A et K et en établir le classement
en fonction de leur valeur : le chemin optimal est celui qui
correspond au meilleur résultat.
— Mais l'application de cette méthode devient beaucoup trop longue
quand le nombre de chemins A -> K est élevé. Il vaut mieux utiliser
alors une deuxième approche basée sur le théorème d'optimalité
de Bellman.
Ce théorème s'énonce ainsi : « Un chemin optimal ne peut être
formé que de chemins partiels optimaux ». Il peut se démontrer
facilement par l'absurde (cf. fi. 4).

C (A, D) C- (D, J)

Figure 4
Supposons que le chemin A, D, J, K formé par la jonction des chemins
partiels C (A, D), C (D, J), C (J, K) soit optimal. Le chemin partiel
C (D, J) ne peut être qu'optimal, sinon il suffirait de le remplacer pat-
un chemin préférable C (D, J), et le nouveau chemin C (A, D). C
(D, J), C (J, K) serait préférable au chemin primitif, contrairement
à l'hypothèse.
Ce résultat fournit un algorithme de recherche du chemin de valeur
optimale dans un graphe quelconque. La mise en œuvre de cet
algorithme est particulièrement simple dans le cas des graphes
séquentiels n.
b) Application aux processus séquentiels — Algorithme de Bellman.
Une forme légèrement modifiée du théorème de Bellman est la sui-
11. L'algorithme général (pour les graphes séquentiels ou non) est celui de
Belhnan-Kalaba. Tl apparaît comme une variante de l'algorithme de Ford (cf.
A. Kaufmann, R. Cruon, op. cit., pp. 20-27). Cet algorithme s'applique sans
difficulté clans le cas de la recherche du chemin de valeur minimale. Pour la
recherche du chemin de valeur maximale, il faut que le graphe ne contienne
ni circuit, ni boucle : sinon la valeur du chemin optimal risquerait d'être infinie.
Cf. A. Kaufmann, op. cit., pp. 291-295.
192 REVUE ECONOMIQUE

vante : considérons un graphe séquentiel dont les sommets sont

répartis en sous-ensembles Xo, Xl ..., XN, « un chemin optimal de Xn à XN
ne peut être formé que de chemins partiels optimaux de Xn+i à XN ».
Cette propriété permet l'utilisation d'un algorithme « remontant » (vers
les valeurs décroissantes de n) pour trouver le (ou les) chemin(s) à
valeur optimale entre entrée et sortie du graphe (issu d'un sommet
xh0 £ Xo et aboutissant à un sommet xlN e XN).
Présentons cet algorithme sur un exemple simple :
Soit le graphe séquentiel de la figure 5, où l'on a inscrit sur chaque
arc la valeur attribuée à cet arc. Quel est le chemin A -> K de valeur
minimale ?

Figure 5
Ce problème est particulièrement simple puisqu'il n'y a qu'une seule
entrée (A) et une seule sortie (K). Il peut, par exemple, correspondre
au choix d'un parcours sur un réseau routier permettant de se rendre,
en empruntant successivement 4 tronçons, de la localité A à la localité
K (cf. supra) : la valeur d'un chemin représente alors une distance ou
un coût de transport qu'il s'agit de minimiser.
On peut raisonner de la façon suivante :
— Partons de XN_X = X3 (x3 = I ou J).
Le choix est simple puisqu'il n'y a qu'une seule sortie (K)
— sommet I : le chemin optimal est IK, la valeur optimale à partir
de I est v (I, —) = 6 ;
— sommet J : le chemin optimal est JK, la valeur optimale à partir
de J est v (J, — ) = 5.
 LA PROGRAMMATION DYNAMIQUE 193

— Partons de XN_2 = X2 (x2 = E, F, G ou H).

Pour déterminer le chemin optimal issu du sommet xr2 s Xa, il suffit,
d'après le théorème qui précède, de comparer les chemins définis par
la réunion d'un arc allant de cet xr2 à un xs3 s X3, et du chemin optimal
issu de cet cc%.
— - sommet E : le chemin optimal correspond à M I N
v (E, I) + v (I, —) = 10
t> (E, J) + v (J, -) = 13
C'est donc E I K, la valeur optimale à partir de E est v (E, —) = 10
— sommet F : le chemin optimal correspond à M I N
v (F, I) + ô (I, — ) = 11
v (F, J) + v (J, -) = 12
C'est donc F I K, la valeur optimale à partir de F est v (F, —) = 11
— sommet G : le chemin optimal correspond à M I N
v (G, I) + v (I, — ) = 12
v (G, J) + v (J, -) = 10
C'est donc G J K, la valeur optimale à partir de G est v (G, — ) = 10
— sommet H : un seul cheminement est possible. La valeur optimale
est v (H, — ) =10.
Les calculs peuvent être effectués directement sur le diagramme
représentatif du graphe (cf. fig. 6). On affecte à chaque sommet de X3,

Figure 6 : Mise en œuvre de l'algorithme de Bellman

la valeur v (xs3) du chemin optimal qui en est issu. Le chemin optimal

issu d'un sommet xr2 de X2 est celui qui correspond à M I N
xS3 e ^3
v (xT2, x%) + v (xs3, —). On note ce chemin optimal (sur la figure, il
est figuré en trait double), et on affecte au sommet x\ la valeur v
(xT2, — ) correspondante.
Revue Economique — Afo 2, 1969 13
194 REVUE ECONOMIQUE

— Partons de XN_3 = Xj. . (xx = B, C ou D).

On opère comme précédemment (là encore, les calculs peuvent être
menés directement sur le graphique).
— sommet B : le chemin optimal correspond à B.E. ... Sa valeur v (B)
= 4 + 10 = 14
— sommet C : le chemin optimal correspond à M I N
u(C,.E) + ö(E, — ) = 17
v (C, F) + v (F, — ) = 15
v (C, G) + v (G, — ) = 14
v (C, H) + v (H, — ) = 15
C'est donc C G ..., la valeur optimale à partir de C est v (C, — ) = 14
— sommet D : le chemin optimal correspond à M I N
v (D, E) + v (E, —) = 18
v (D, H) + v (H, — ) = 14
C'est donc D H ..., la valeur optimale à partir de D est v (D, — ) = 14
— Partons de Xo (xn = A)
Le chemin optimal issu de A correspond à M I N
v (A, B) + v (B, — ) = 19
v (A, C) + v (C, — ) = 18
v (A, D) + v (D, — ) = 20
C'est donc AC ..., la valeur optimale à partir de A est v (A, — ) = 18.
La recherche peut être effectuée sur le diagramme. Le chemin
optimal issu de A est celui qui est figuré en trait double sur toute sa
longueur. On lit au-dessous de A la valeur de ce chemin optimal (cf.
fig. 6). Ainsi le chemin optimal est (A, C, G, J, K) ; sa valeur est 18.
L'intérêt de cet algorithme apparaît clairement : il évite d'avoir
à comparer directement tous les chemins envisageables (il y en a 14)
de A à K. Le calcul d'optimisation s'effectue en 4 itérations. Chacune
d'entre elles permet d'éliminer — pour les itérations suivantes — tous
les chemins partiels non optimaux.
Remarques :
1. Dans le cas où plusieurs entrées xh0 sont admises, l'algorithme
associe à chaque sommet x\ le chemin optimal c (xh0, —) et sa valeur
û (xh0, —). On compare alors les valeurs v (xh0, — ) : l'entrée et le
chemin optimaux correspondent à la valeur ü (x\, —) optimale.
2. On peut également envisager un algorithme descendant (vers les
valeurs croissantes de n) s'appuyant sur la propriété suivante :
 LA PROGRAMMATION DYNAMIQUE 195

« Un chemin optimal de Xo à Xn ne peut être formé que de chemins

partiels optimaux de Xo à Xn_! ». Les calculs d'optimisation sont
alors effectués en partant de Xi, puis de X2, ..., jusqu'à Xn.

II

PROGRAMMES DYNAMIQUES EN AVENIR CERTAIN

1. GENERALITES

1 — Description des processus « déterministes » (a variables discrètes)

Les processus séquentiels en avenir certain peuvent être ainsi
définis : les décisions à prendre se présentent par étapes ou « phases »
successives. A Tintant n — début de la phase n + 1 — (n = 0, 1, 2, ... N),
le système sur lequel on agit se trouve (sous l'influence des décisions
antérieures) dans un certain état xvn £ Xn (nous supposons pour
l'instant que l'ensemble Xn est dénombrable). Une décision d* (xvn) —
notée également d (xrn, xsn+i) — l'amène dans un état xsn+i e Xn+i (xrn) 12.
Une séquence de décisions d (xhu, x\), ..., d (xrn, xsI1+1), ..., d (xkN_i), x*N
constitue une politique ; une séquence de décisions jointives faisant
partie d'une politique constitue une sous-politique.
On suppose qu'au début de chaque phase n + 1 (en particulier la
phase 1) l'agent de décision connaît l'éventail des décisions
envisageables à partir de chaque état xm pour în^n ainsi que leurs
conséquences. Le choix d'une décision détermine donc parfaitement les
« conditions initiales » de la décision suivante. L'existence de liaisons
entre xn successifs explique d'une part que la décision à prendre au
cours de la phase n + 1 ne peut être choisie isolément, mais dépend
des décisions antérieures, et d'autre part qu'elle doit être intégrée dans
une politique définie de Xn à XN.
On suppose également qu'il est possible d'associer à chaque
transition xrn -> .xsn+1 wie valeur vf (.vrn) = v (xrn, xsn+1) représentant le
résultat immédiat de la décision df (xrn) et ne dépendent que des états
xTn et xns+1 13 (donc parfaitement déterminée par la connaissance de la
décision d1 (x'n)). La valeur d'une politique (x\ ..., x'N) est alors obtenue
par sommation des valeurs élémentaires (auxquelles on ajoute éven-

12. L'ensemble des états qui peuvent être atteints à partir ^ de %r n'est
généralement qu'une partie de Xn+1 (Xn+, (xr ) C Xn+1), puisque l'ensemble des
décisions possibles dépend de l'état initial xTJ.
13. En particulier : indépendante — pour xrn et xsn+1 fixés — de l'évolution
antérieure ou ultérieure du système.
 196 REVUE ECONOMIQUE

tuellement la valeur attribuée à l'état final — cf. l'exemple des pages

202 à 206). Le problème est alors de trouver la politique de Xo à Xn
optimisant 14 la fonction de valeur
V (X\, *y = V (X\, X\) + ... + V (*Vl> *N> + V (X1N)
Comme nous l'avons vu dans la première partie, on peut associer
au processus d'évolution du système un graphe séquentiel. On associe
à chacun des états envisageables à l'instant n un sommet du sous-
ensemble Xn. La possibilité d'une décision d (xrn, xan+i) correspond à
l'existence d'un arc orienté joignant les sommets xrn et ccsn+i. Une
politique (ou une sous-politique) est définie par un chemin empruntant
une séquence d'arcs de décision. On associe à chaque arc (xrn, xsn+i)
la valeur v (xrn, %sn+i) correspondante, et le résultat d'une politique
est obtenu par sommation des valeurs des arcs composant le chemin
figurant cette politique. Les évolutions possibles du système peuvent
ainsi être schématisées par un diagramme séquentiel (cf. fig. 1, où est
figurée en trait double la sous-politique x2^, x\+1, oân+2).

-1
*n+2
2
*N-1
""
2
^n+2

k
-?n+2

'n+l ' n+2-

Etats 0 1 n n+l n +2 - — N— 1 N
Phases < 1 > <n + l>< n+2 > < N >

Figure 1
Diagramme représentatif d'un processus déterministe discret
(à variables discrètes)
14. Minimisant si la fonction u représente par exemple un coût ;
maximisant si la fonction v représente un revenu.
 LA PROGRAMMATION DYNAMIQUE 197

2 — Recherche de la politique optimale

La comparaison directe des différentes politiques possibles devient

rapidement impraticable quand le nombre d'états à envisager à chaque
phase s'élève (cf. p. 191). Le théorème d'optimalité fournit alors une
méthode de résolution. Elle consiste à définir une politique qui soit
constamment optimale. Chaque étape de l'algorithme détermine
simultanément la valeur et la décision (pour la phase envisagée) de la sous-
politique optimale. Appliqué à ce type de processus, le théorème de
Bellman devient : « Une politique optimale ne peut être formée que
de sous-politiques optimales ».
La recherche de la politique optimale sur les N phases du processus
(de l'entrée Xo à la sortie XN du graphe séquentiel) peut alors être
effectuée à l'aide d'un algorithme (cf. pp. 191 à 194). Les calculs
d'optimisation peuvent — en principe — être menés, soit dans le sens
des n croissants (algorithme descendant le cours du temps), soit dans
celui des n décroissantes (algorithme remontant le cours du temps).
a) L'algorithme remontant le cours du temps s'appuie sur la
propriété suivante : « Une politique optimale de Xu à XN ne peut être
formée que de sous-politiques optimales de Xn+i à XN ».
Nous avons déjà présenté un tel algorithme (cf. pp. 192 à 194) ; nous
en fournirons bientôt une nouvelle illustration sur un exemple concret
(problème de remplacement d'équipements).
Dans le cas général, on détermine de proche en proche (dans le
sens des n décroissants) les politiques optimales à partir de Xn, en
résolvant pour chaque xrn à considérer, l'équation fonctionnelle :
(I) OPT v (xrn,—) = OPT [v (x'n, ü-n+1) + OPT v (x-a+1, — )]
*Sn+l £ Xn+1 (*rn> ~)

où les notations sont les suivantes :

— le signe OPT signifie que l'on effectue, soit une maximisation,
soit une minimisation (cela dépend de la nature du problème).
Il joue le même rôle, dans nos notations, que le symbole v. Ainsi
OPT« (x\+l, —) = v (xsn+h — ).
— Xn+1 (xr„, — ) représente l'ensemble des sommets ccn+1 qui sont
à la fois extrémité terminale d'un arc issu du sommet xrn considéré, et
extrémité initiale d'un chemin aboutissant à la sortie XN (les seules
politiques à envisager sont évidemment celles que vont jusqu'à la fin
du processus). Cette notation fait apparaître que le domaine de
variation des sommets xsn+i à envisager pour le calcul d'optimisation à
198 REVUE ECONOMIQUE

partir de x\ dépend de ce sommet xTn et de la disposition des arcs

de décision des phases n + 1 à N.
Les calculs peuvent être menés directement sur le diagramme
associé au graphe séquentiel. On a affecté aux sommets ccsn+i les valeurs
OPT« (xsn+i, —) = v (xsn+i, — ) des chemins optimaux issus de ces
sommets.
La détermination de la (ou des) politique(s) optimale(s) à partir
de chaque sommet xrn conduit à retenir pour chacun de ces sommets
un (ou plusieurs) arc(s) (xTn, xsn+1) — que l'on peut par exemple figurer
en trait double — et on note la valeur O P T v (xTn, — ) correspondante.
b) L'algorithme descendant le cours du temps s'appuie sur la
propriété suivante : « Une politique optimale de Xn à Xn ne peut être
formée que de sous-politiques optimales de Xo à Xn_! ».
L'équation fonctionnelle permettant de trouver la politique optimale
jusqu'à xrn £ Xn est :
(II) OPT v (—, x\) = OPT [OPT (—, x^) + v (x\_v xrn)]
xtn-l £ Xn_x (-, xrn)
où la notation Xn_x (— , xrn) indique que l'ensemble des x\-i à considérer
dépend de l'état d'arrivée xrn et que les seules politiques à considérer
sont celles qui commencent à l'entrée x\
Le choix du sens dans lequel est menée l'optimisation séquentielle
dépend de la nature du problème, en particulier des relations qui
lient les variables d'état entre elles (c'est-à-dire des contraintes
exprimées par la notations Xn+i (xTn, — ) ou Xn_i ( —, afn))-

3 — Remarques et compléments
a) Généralisation de la méthode au cas des processus à variables
continues.
Nous n'avons considéré jusqu'à présent que les processus pour
lesquels les ensembles Xn sont finis. Le théorème d'optimalité peut
s'étendre au cas où les ensembles Xn sont infinis (notamment celui où
les variables xn sont continues), et le principe de l'utilisation de
l'algorithme ne s'en trouve pas modifié : la formulation que nous avons
employée pour l'écriture des relations fonctionnelles (I) et (II) n'implique
pas nécessairement la discontinuité des variables 15. Les méthodes
d'optimisation que nous avons présentées peuvent donc être appliquées
15. Remarquons cependant que dans le cas où Xn est fini la recherche de
l'optimum nécessite seulement la comparaison directe d'un certain nombre de
valeurs. Dans le cas continu, il faut étudier les variations d'une fonction, au
moyen par exemple de sa dérivée.
 LA PROGRAMMATION DYNAMIQUE 199

à la résolution des problèmes à variables continues, dont les

programmes de stockage fournissent d'assez nombreux exemples 16. Mais la
mise en oeuvre de l'algorithme est plus délicate, car l'explicitation des
contraintes liant les variables d'état (résumées par nos notations Xn+1
(xa, — ) ou Xn_! (— , xn) introduit des complications dans la résolution
des équations. D'autre part, il n'est plus possible d'effectuer
directement les calculs sur le diagramme représentatif des évolutions du
processus. En effet, il ne s'agit plus à proprement parler d'un graphe du
type envisagé dans cette étude (tel qu'il a été défini dans I. 1 de la
première partie) puisque les sous-ensembles Xn ne sont plus finis 17.
Sur le diagramme, les intervalles de variations des variables xn sont
figurés par des segments sur les droites Xn, et chaque point xn est
(généralement) l'origine d'une infinité d'arcs de décision 18.
b) Introduction d'un horizon illimité.
Les problèmes de décisions séquentielles interviennent, nous l'avons
vu, quand l'agent de décision désire assurer la cohérence dans le temps
de ses choix. En toute logique, les programmes dynamiques devraient
alors être posés et résolus pour des périodes illimitées 19. Par exemple,
dans un problème de remplacement d'équipements, le choix :
renouvellement immédiat ou renouvellement reporté inaugure des chaînes de
décisions qui resteront en principe indéfiniment différentes. Mais l'étude
de l'influence de l'avenir lointain sur les décisions actuelles oblige
l'agent de décision à prendre en compte des perspectives de plus en
plus floues.
1) Quand l'imprécision sur l'avenir croît ainsi rapidement au fur
et à mesure qu'on s'éloigne vers le futur, il paraît nécessaire de limiter
l'horizon de l'étude : au lieu d'avoir à prendre en considération les
sous-politiques situées au-delà de cet horizon, il suffit alors de se fixer
des conditions de fin de jeu (dans le problème de remplacement étudié
plus loin, ces conditions correspondent à l'arrêt du processus de
fabrication et à la revente de l'équipement au bout de 4 ans). D'une façon
générale, le choix du nombre N de phases à envisager et des conditions

16. Cf. A. Kaufmann, op. cit., pp. 101-112. — R. Bei.lman et S. Dreyfus.

op. cit., pp. 105-114.
Citons également l'ouvrage remarquable de M. K. Stabr et D. M. Miller,
La gestion des stocks : théorie et pratique, Dunod, Paris, 1965. Les applications
— en ce domaine — de la programmation dynamique y sont traitées dans
les chap. 4 à 6.
17. Pour la définition et l'étude des graphes infinis, cf. C. Berge, op. cit.
18. Pour plus de détails, cf. A. Kaufmann et R. Cruon, op. cit., chap. 1.
19. Cf. P. Massé, Le choix des investissements. Dunod, Paris, pp. 58-59 et
pp. 284-290.
200 REVUE ECONOMIQUE

aux limites est largement arbitraire ; mais cet inconvénient est réduit
par le jeu de l'actualisation — grâce auquel les résultats suffisamment
éloignés dans le futur ont un poids moindre.
2) Dans d'autres cas au contraire, la limitation de l'horizon ne
s'impose pas. C'est celui, par exemple, de nombreux problèmes de
stocks ou, plus généralement, des processus stationnaires (où les
évolutions possibles du système sont les mêmes pour toutes les phases).
L'introduction d'un horizon illimité complique notablement
l'application de la méthode récurrente de Bellman. Les difficultés sont de
deux ordres :
— Les valeurs v (xrn, —) qui figurent dans les équations de
récurrence gardent-elles une signification quand N augmente indéfiniment
ou, au contraire, deviennent-elles infinies ?
— Même en admettant que ces valeurs v (xTn, — ) restent finies (ou
qu'on les a remplacées par des fonctions de même nature qui sont
convergentes), comment est-il possible d'approcher la solution
optimale ?
La réponse à ces questions nécessiterait des développements
mathématiques assez longs 20. Nous nous contentons d'indiquer ici que
dans les cas (les plus nombreux) où la convergence de la valeur totale
n'est pas réalisée, on peut utiliser le critère de la valeur totale
actualisée ou celui de la valeur moyenne par période (les conditions de
convergence de ces deux critères sont le plus souvent identiques).

c) Actualisation. 21
Nous venons seulement de mentionner le phénomène de
l'actualisation (si nous ne l'avons pas fait plus tôt, c'est qu'il ne modifie en
rien le mécanisme des calculs). La réalité économique oblige souvent
à pondérer de façon différente des sommes d'argent mises en jeu à des
instants différents. Ce sera nécessaire, quand la durée de chaque phase
sera suffisamment grande ou quand la longueur totale du processus
sera suffisante (en particulier, quand N augmente indéfiniment) pour
que les termes correctifs introduits par l'actualisation ne soient pas
négligeables.
L'actualisation peut être effectuée de la façon suivante : on actualise
les valeurs immédiates du type v (xTn, xsn+i) en prenant par exemple

20. Nous renvoyons, sur ce sujet, à A. Kaufmann et R. Cruon, op. cit.,

chap. 2.
21. Sur le problème de l'actualisation, cf. : P. Massé, op. cit., pp. 6-19.
J. Lesourne, Technique économique et gestion industrielle, Dunod, Paris, 1965,
pp. 32-35.
 LA PROGRAMMATION DYNAMIQUE 201

comme référence la date 0 (début du processus). La formule de

récurrence (I) devient alors (en notant œ les valeurs actualisées) :
OPT m (xra,—) = OPT [w (vV i»„+,)+OPT w (xsn+1, — )]
Si par exemple chaque valeur v (xrn, xsn+i) apparaît à la fin de la phase
n (date n -f 1), et si l'on suppose que les phases ont toutes la même
durée T et que le taux d'actualisation reste constant, soit k (en prenant
T comme unité de temps), les valeurs actualisées w sont obtenues en
écrivant :
(û ( \+l)) = ( ) +i ( )
+

en posant « = (a : coefficient d'actualisation).

La formule (I) devient :

OPT an+i v (x\, xsn+l) = OPT [o^1 v (x\, x\+1) + OPT cn+2 v (x»n+1, — )]
soit
OPT i? (x'n, *°n+1) = OPT [ü (*rn, i-n+i) + O PT a « (x\+v— )]
d) Autres critères que celui du bénéfice actualisé.
Le critère de la valeur actualisée n'est pas le seul à pouvoir être
utilisé pour la comparaison de différents échéanciers de valeurs.
D'autres auteurs lui préfèrent des critères comme celui du taux de
rentabilité, pu encore celui du temps de recouvrement, etc. (cf. P. Massé,
op. cité, pp. 20-38). Ces derniers critères peuvent être plus significatifs
ou plus maniables dans certains cas concrets.
Les développements qui précèdent ont supposé que la fonction
de valeur était additive, c'est-à-dire de la forme 22 :
V (x\, xlN) = v (x\, x\) + ... + v {x\, x\+1) + ... + v (xVx1, *y
Le bénéfice actualisé satisfait à cette condition, mais ce n'est pas le
cas — par exemple — du taux de rentabilité. Il est cependant possible
d'adapter la méthode de Bellman (cf. J.M. Dethoor et J.L. Groboillot,

22. Cette hypothèse n'est pas nécessaire (cf. A. Kaufmann et R. Cruon,

op. cit., p. 266\ La méthode de Bellman est compatible avec toute fonction
de valeur du type
V (*h0, *y = c (x\, x\) T ... T v (*rn, x-n+1) T ... To (x\_v x»N)
relation dans laquelle T désigne une loi de composition interne sur une partie
des réels, associative et compatible avec la relation d'ordre des réels (c'est-à-dire
telle que x > x" => x T x > x T x"). Le produit, par exemple, répond — au
même titre que la somme — à ces conditions : l'algorithme de Bellman permet
donc la résolution de problèmes où la valeur d'une politique est le produit des
valeurs élémentaires.
202 REVUE ECONOMIQUE

La vie des équipements, Dunod, 1968, p. 96). On procède de la façon

suivante : on détermine la politique optimale •— selon le critère de
bénéfice actualisé, donc par l'algorithme qui vient d'être présenté —
pour différents taux d'actualisation a0 ax ... ar ; la politique optimale
— trouvée par itération — correspond au taux a conduisant à un
revenu optimum nul.

2. ETUDE D'UN EXEMPLE :

LE PROBLEME DU REMPLACEMENT D'EQUIPEMENTS ^

1 — Enoncé du problème
Un problème courant de décision industrielle est celui du
remplacement des équipements. Le matériel ancien se détériore : son
rendement diminue, son coût d'entretien augmente. Il arrive un moment
où son revenu « net » (revenu brut moins dépenses d'entretien) devient
inférieur — compte tenu du coût du remplacement — à celui d'un
équipement neuf dont les performances ont, de plus, été améliorées
par suite du progrès technique. Le remplacement doit alors être décidé.
Il s'agit bien d'un programme dynamique : le problème du
remplacement se pose à chaque instant, ou plutôt à échéances successives
(au début de chaque année par exemple) ; et chacun des choix ne
peut être effectué que si l'on s'est fixé les décisions à prendre
ultérieurement ; il dépend d'autre part des décisions antérieures. Dans
l'hypothèse où l'on dispose de prévisions précises sur le futur (concernant
l'évolution des performances et des prix du matériel, quelle que soit
sa date d'acquisition), ce problème relève du cas déterministe que nous
venons d'étudier.
Considérons, par exemple, un processus de fabrication durant 4
années (N = 4). On achète une machine au début de la première
année (instant 0) et les trois années suivantes se pose le choix :
conserver l'ancienne machine ou la revendre et en acheter une neuve 24.
Quelle est la politique qui conduit au bénéfice actualisé maximum ?
La fonction de valeur dont on cherche l'optimum est donc :
W [x\, . . . ., x\] = w (x\, x\) + W (x\, «y + w (xi» x\) + w (x\, x\)
23. Cf. R. Bellman et S. Dreyfus, op. cit., pp. 116-127. — A. Kaufmann,
op. cit., pp. 133-139. Signalons que le problème du remplacement peut être
résolu par d'autres méthodes que la programmation dynamique, par exemple
celles qui ont été proposées par G. Terborgh, Dynamic equipment policy,
Me Graw Hill, Washington, 1949. — J. Desrousseaux, L'évolution économique
et le comportement industriel, Dunod, Paris, 1966, chap. 6 (la théorie de
Desrousseaux, présentée précédemment dans un article, est très clairement exposée
dans l'ouvrage de G. Worms, Les méthodes modernes de l'économie appliquée,
Dunod, Paris, 1965, chap. 5).
24. On exclut donc la possibilité d'acheter des machines d'occasion.
 LA PROGRAMMATION DYNAMIQUE 203

relation dans laquelle x\ désigne l'état du système à l'instant n. Par

exemple l'état xh — D (cf. fig. 2) correspond à la disposition à
l'instant 2 d'une machine âgée d'un an achetée à l'instant 1), et le choix
(xi2 — D, x\ = G) signifie qu'on la conserve au cours de la phase 3
(xr n+l ) = V (xrn, X*n+1)

en désignant par v (xTn, xsn+i) le résultat actualisé à la date n de la

transition xn — > xa+i. Plus précisément
v (xr n+1.) = a R -n+1 ) - C (afn, x«n+1)

avec les notations suivantes R (xn, xn+1) est le revenu net résultant
de la décision d (xn, xn+1) (profit brut moins coût d'entretien).
G (xn, xa+1) est le coût de l'investissement correspondant : il est nul
si l'on conserve l'équipement, égal au coût de remplacement (prix de
la machine neuve moins prix de revente de l'ancienne) si l'on change
la machine.
a est le coefficient d'actualisation (cf. supra), qu'on suppose constant.
La dépense d'investissement est payée en début de période (au
moment de l'achat) ; le revenu est perçu en fin de période.

2 — Exemple numérique

Prenons l'exemple numérique suivant : les revenus nets et les prix

du marché des équipements (prix d'achat d'une machine neuve ou
prix de revente d'une machine ancienne) sont donnés dans le tableau

Machine disponible Machine disponible

à l'instant 0 à l'instant 2

Age 0 1 2 3 4 0 1 2

Revenu net 100 90 80 70 120 110

-
Prix du marché 500 460 430 410 400 540 480 450

Machine disponible Machine

à l'instant 1 disponible à
l'instant S
Age 0 1 2 3 0 1

Revenu net 110 100 90 130

Prix du marché 520 475 440 415 560 490
 204 REVUE ECONOMIQUE

ci-contre (où sont indiqués les prix des machines à l'instant 4, car on
suppose qu'on revend à la fin du processus la machine que l'on vient
d'utiliser. Pour simplifier, on supposera que le coefficient
d'actualisation a est égal à 1. Le problème peut être associé au graphe
séquentiel représenté sur la figure 2.

100
665 c

Dates
Phases
Figure 2
Diagramme représentatif du graphe associé au problème de remplacement

Chaque point représente un état du système, défini par la machine

— caractérisée par son âge — disponible en fin de phase. Chaque arc
correspond à une décision, de chaque sommet partent deux arcs :
conserver (noté C) et remplacer (noté R). Un sommet est l'extrémité
de plusieurs arcs si l'état qu'il figure peut être le résultat de plusieurs
décisions : les arcs « remplacer » d'une même phase aboutissent au
même sommet puisque leur résultat commun est la disposition en fin
 LA PROGRAMMATION DYNAMIQUE 205

de phase d'une machine âgée d'un an (c'est le cas pour DF et EF ;

pour FI, GI et HI).
On attribue à chaque arc la valeur o> (xTn, xan+1) = v (xrn, s^n+i).
Ainsi le résultat de la décision D -> G (conserver au cours de la phase
3 une machine achetée à l'instant 1) est 100. Celui de la décision
E -> F (acheter une machine à l'instant 2 après avoir conservé 2 ans
la première machine) est :
v (E, F) = 120 — (540 — 430) = 120 — 110 = 10
revenu coût de
net remplacement

Résolvons ce programme dynamique à l'aide de l'algorithme de

Bellman (en remontant le cours du temps). Les calculs peuvent être,
soit détaillés dans un tableau (tableau ci-contre), soit effectués
directement sur le diagramme (cf. fig. 2 : à chaque itération, on note
en trait double des arcs optimaux et on inscrit sous chaque
sommet la valeur v (xrn) du chemin optimal correspondant). La politique
optimale correspond au chemin A B D F J. Elle consiste, une fois
utilisée au cours de la phase 1 la machine livrée à l'instant 0 (arc A B),
à la revendre pour en utiliser une nouvelle (achetée à l'instant 1) au
cours de la phase 2 (arc B D), à revendre cette dernière pour en
acheter une nouvelle à la date 2, et l'utiliser au cours des phases 3
(arc D F) et 4, à la fin de laquelle on la revend (arc F J). Le résultat
de cette politique (bénéfice maximum) est 765, qui se décompose ainsi
765 = 100 + 50 + 55 + 110 + 450
arc AB arc BD arc DF arc FJ
 DETAIL DES ITERATIONS DE L'ALGORITHME (problème
A partir de X3
490 + (130 — 80) =
Sommet F, la décision optimale correspond à MAX
450 + 110 =
=
/ 490 + (130 — 120)
Sommet G, la décision optimale correspond à M A X <
( 415 + 90 =
f 490 + (130 — 150) =
Sommet H, la décision optimale correspond à M A X ]
( 400 + 70 =
A partir de X2
/ 560 + (120 — 65) =
Sommet D, la politique optimale correspond à M A X \
( 505 + 100 =
560 + (120 — 110) =
Sommet E, la politique optimale correspond à MAX
470 + 80 =
A partir de X1
( 615 + (110 — 60) =
Sommet B, la politique optimale correspond à M A X <
(570 + 90 =
A partir de Xo
Sommet A : On ne peut prendre que la décision AB, que l'on complète par l
B (A, — ) = V (A, B, D, F, J) = «.(A, B) + v (B, — ) = 10
 LA PROGRAMMATION DYNAMIQUE 207

III

PROGRAMMES DYNAMIQUES EN AVENIR PROBABILISABLE

ET NON-PROBABILISABLE

1. DESCRIPTION DES PROCESSUS EN AVENIR ALEATOIRE

Nous n'avons considéré jusqu'à présent que des programmes

déterministes. On supposait que l'évolution dans le temps du système ne
dépendait que des décisions prises au cours des phases successives.
Dans la plupart des cas concrets, les effets des décisions se
combinent avec l'intervention du hasard. L'évolution du système n'est que
partiellement contrôlée par l'agent de décision : elle est également
soumise à l'influence de facteurs extérieurs qu'il ne peut totalement
maîtriser.
Il y a différents degrés dans l'incertitude. Le cas le plus défavorable
est celui où l'on ignore tout de l'avenir : il n'est alors pas possible
d'élaborer un programme de décisions, puisqu'on ne sait rien des
conséquences possibles des choix effectués. Le plus souvent cependant,
on est capable de prévoir les différents événements susceptibles de
se produire dans l'avenir, et donc de décrire les résultats éventuels des
décisions futures. Dans certains cas, il est même possible de connaître
les vraisemblances relatives — en d'autres termes les probabilités —
de ces éventualités.
Même avec ces hypothèses, la description de l'ensemble des
évolutions envisageables du système est complexe, puisqu'à chaque phase,
l'état x\+1 effectivement atteint à partir d'un état initial donné xru
dépend à la fois de la décision dl (xvn) et de l'événement gJ (xrn). Il
est fréquent cependant que certaines décisions éliminent la possibilité
de certains événements, ou réciproquement. Cette incompatibilité entre
certaines décisions et certains événements s'explique par le fait que,
généralement, les processus aléatoires peuvent être décomposés : dans
les processus D H, on peut considérer que le hasard n'intervient qu'une
fois la décision prise; dans les processus H D, au contraire,
l'intervention du hasard précède la décision.
 208 REVUE ECONOMIQUE

1 — Processus D.H. (décision - hasard). 25

Chaque phase n + 1 (n = 0 ... N — 1) peut être décomposée en
deux périodes : la première (entre les dates n et n') où intervient la
décision, la seconde (entre les dates n et n + 1) où intervient le hasard.
A l'instant n, le système se trouve dans un certain état xTn z Xn. Une
décision c? (afn) l'amène dans un état yan, z Ya, 26. Puis l'événement é
(yaw) conduit à l'état xsn+i £ Xn+i 27 avec la probabilité pi (t/°n>)
(0 ^ pj ^ 1, et 2 pi = 1 si l'on envisage l'ensemble des événements
qui peuvent survenir quand le système arrive dans l'état t/an>)- L'état
afn+i constitue l'état initial du système pour la phase suivante.
Dans le cas où les ensembles Xn et Yn, sont finis, on peut associer
au processus d'évolution un graphe séquentiel. Les états xva et yaa,
définissent les sommets des sous-ensembles ordonnés Xn et Yn, (cf. le
diagramme de la fig. 1). A chaque décision correspond un arc (xTn,
25. Cf. A. Kaufmann, op. cit., pp. 113-114 et pp. 128-129 (pour la
représentation par un graphe) ; A. Kaufmann et R. Cruon, op. cit., pp. 115-117.
26. Généralement les états yan, qui peuvent être atteints à partir de xrn ne
définissent qu'une partie Yn, (xrn) de Yn,.
27. Ou plutôt xsn+1 s Xn+1 (yan,) e Xn+1 (cf. la note précédente).
Phases <- m -> <^ n+l >

n+2
Décision Hasard Décision
Figure 1 : Diagramme représentatif d'une évolution D.H.
 LA PROGRAMMATION DYNAMIQUE 209

y°n,) ; à chaque éventualité correspond un arc (t/a„>, x\+1). Une «

histoire » du système est définie par un chemin entre « entrée » et « sortie »
du graphe, constitué par une succession d'arcs de décision et de hasard.
Pour définir un programme, il suffisait, dans le cas « déterministe »,
de se donner pour chaque phase la décision à prendre. Le choix, à la
date 0, d'une politique déterminait parfaitement l'évolution du
processus. Dans le cas des processus en avenir aléatoire, il est nécessaire
de substituer, aux notions de décision et de politique, celles de vecteur
de décisions et de stratégie.
A la date 0, l'état d'entrée xh0 est connu. Le choix de la décision
d! (xho) conduit à un état y^0' parfaitement déterminé. Mais cet état
t/V peut conduire — sous l'effet du hasard — non à un seul, mais à
un ensemble d'états a^ défini par sa distribution de probabilités. L'état
x\ effectivement atteint ne sera connu qu'à la date 1. Un programme,
défini dès l'instant 0, doit donc donner l'ensemble de décisions
conditionnelles à prendre au cours de la phase 2, en spécifiant l'arc de
décision choisi pour chaque sommet x\ qui peut être atteint. Plus
généralement, l'état xrn du système à la date n n'est pas connu avec
certitude, même si on a précisé les décisions antérieures : un plan élaboré
à la date 0 doit donc spécifier, pour chaque sommet „r'n éventuel, l'arc
de décision choisi. On appelle vecteur de décisions de la phase n + 1
l'ensemble D (Xn) des décisions d (ixr„) choisies selon l'état initial xTa-
Un programme, conçu à l'instant 0 pour toute la longueur du processus,
doit comporter l'ensemble des vecteurs de décisions retenues de la
phase 1 à la phase N ; cette séquence de vecteurs de décisions
constitue une stratégie.
La figure 1 représente le diagramme du graphe séquentiel associé
à une évolution DH. Les sommets x sont notés □, les sommets y sont
notés O- Un arc de décision correspond donc au schéma □ —> O >'
.

un arc de hasard, au schéma Q -> D (on inscrit sur chaque arc de

hasard la probabilité conditionnelle correspondante). On a représenté
en trait double une stratégie possible entre les dates n et n + 2
(constituée par les vecteurs de décisions des phases n + 1 et n + 2).

Exemple de processus D.H. : problème d'investissements 28

Un fabricant de postes de radio décide de lancer un nouveau type
de « transistors » sur le marché. Ses services commerciaux lui
communiquent les prévisions suivantes :

28. Un exemple assez voisin est traité dans J.F. Magee, L'arbre de décision.
Guide pour l'analyse des risques et occasions d'investissement, Bulletin S.E.D.E.I.S.,
étude du 20-7-65, pp. 51-59.
Revue Economique — N" 2, 1969 14
210 REVUE ECONOMIQUE

— il y a (environ) 50 chances sur 100 que la demande de ce nouveau

produit soit seulement moyenne, et reste constante pendant les cinq
premières années ;
— il y a 50 chances sur 100 que la demande soit d'abord élevée. Dans
ce cas, au bout de deux ans, deux éventualités peuvent se produire,
avec des probabilités estimées respectivement à 0,3 et 0,7.
a) Ce succès initial incite les concurrents à imiter leur collègue,
dont la vente va devenir inférieure à celle qui était précédemment
observée.

toujours
OP I—I ^S ^ dêci" ~r\ Pforte r = °'T
I I s ion a prendre \_J „_ .
O »^

Demande toujours
.1 :KP faible
^ c?
Demande toujours
forte p = 0,7

Pas de déc
j — .Pas décision fe^ Demande toujours ~C
[_J à prendre

Décision

Phase 1

Figure 2
 LA PROGRAMMATION DYNAMIQUE , 211

b) Aucune réaction des concurrents n'est enregistrée, et le chiffre

de vente annuel reste égal au précédent.
Les décisions envisagées sont les suivantes :
— construire immédiatement un atelier de grande capacité (coût, y
compris l'entretien, de 80 000 F) capable de satisfaire la totalité de la
demande même si celle-ci est élevée ;
— se contenter au début d'un investissement de capacité moindre
(coût : 50 000 F) quitte à décider au bout de deux ans — si la
conjoncture est favorable (éventualité b) — de la doubler. Cette opération
nécessite un investissement additionnel dont le coût est également
évalué à 50 000 F. Il s'agit d'un processus D.H. à deux phases : la
première dure 2 ans, la seconde 3 ans. La décision d'investissement est
prise au début de chaque phase : comme elle est instantanée (on
suppose par exemple que le fabricant achète immédiatement son
installation), les dates 0 et 0' ou 1 et 1' sont confondues ; cela n'empêche
pas de considérer qu'il y a décomposition D.H. Le hasard intervient
pendant toute la durée de chaque phase pour déterminer le niveau
des ventes (en partie seulement, puisqu'il faut tenir compte de la
contrainte de capacité). La figure 2 représente les évolutions possibles du
système en fonction des décisions et du hasard (on a inscrit sous chaque
arc de hasard, la probabilité conditionnelle correspondante).
Les différentes stratégies apparaissent immédiatement : il y en a
trois :
yr M
— v, yr D > H <T
Stratégie S1 A > B ; "^ N
X E > I > O
Ce schéma traduit les choix suivants = de A on prend la décision
A -> B qui conduit à D ou à E. Si on est en D, on prend la décision
D H qui conduit à M ou N ; si on est en E, on prend la décision E I
qui conduit à 0.
^ p

Stratégie S'2' A > C ^ \Q

\v G *■ L *■ T

S F > K ^
Stratégie S3 A > C ( ^ S
\G > L > T

Remarque. L'horizon de l'étude est limité volontairement à cinq ans.

On peut en invoquer deux raisons :
212 REVUE ECONOMIQUE

— Les prévisions commerciales ne sont jugées valables que pour

cette période. Au-delà de cet horizon, les probabilités attribuées aux
éventualités ne seraient plus significatives ; et il serait même difficile
de déterminer de façon raisonnable les différents événements possibles
(cf. pp. 199 et 232).
— Le fabricant est surtout intéressé par le succès à court terme
de son entreprise. Il ne désire pas engloutir de fortes sommes à faible
rendement initial, même si les espérances ultérieures sont plus
importantes (notons que cette forte préférence pour le présent doit se
traduire par un taux d'actualisation élevé, les résultats à échéance
lointaine auront donc un faible coefficient de pondération).

2 — Processus H.D. (hasard-décision) 29

Chaque phase n + 1 peut être décomposée en deux périodes : la
première (entre les dates n et n) où intervient le hasard, la seconde
(entre les dates n et n + 1) où intervient la décision.
A l'instant n, le système se trouve dans un certain état yrn £ Yn.
L'événement e* (yln) le fait passer à l'état xan, s Xn, avec la probabilité
Pj (?A) (0 ^ Pj f= 1, et S pi = 1 si l'on envisage l'ensemble des
événements qui peuvent survenir à partir de yn). Puis la décision cV (xCTn>)
conduit à l'état ysn+i £ Yn+i.
Dans le cas où les ensembles Yn et Xn, sont finis, on peut associer
au processus d'évolution un graphe séquentiel. A chaque éventualité
correspond un arc de hasard (yTn, x°n>) ; à chaque décision, un arc
(*°n'> î/Sn+l)-
Dès le début de l'évolution, l'intervention du hasard associe à un
état d'entrée t/h0 un ensemble d'états a^0> défini par sa distribution de
probabilités. L'élaboration d'un programme à la date 0 suppose donc
le choix d'un vecteur de décisions pour la phase 1, spécifiant l'arc de
décision pour chaque sommet ida, et plus généralement celui des
vecteurs de décisions pour la phase n + 1. La suite des vecteurs de
décisions de la phase 0 à la phase N constitue une stratégie.
La figure 3 représente le diagramme représentatif du graphe
séquentiel associé à une évolution H.D. Les sommets y son notés O
et les sommets x sont notés G- Le chemin parcouru au cours d'une
phase résulte de la succession d'un arc de hasard (O -> D) et d'un
arc de décision (□ -> O)- Les décisions figurées en trait double
définissent un vecteur de décisions valable pour la phase n + 1.

29. Cf. A. Kaufmann, op. cit., pp. 420-432. — A. Kaufmann et R. Cruon,

op. cit., pp. 125-129 (un exemple est donné pp. 129-130).
 LA PROGRAMMATION DYNAMIQUE 213

2. EVALUATION D'UNE STRATEGIE

1 — Position du problème
Valeur d'un chemin. On suppose qu'il est possible d'attribuer à chaque
arc de décision une valeur a (x, y), et à chaque arc de hasard une
valeur b (x, y), qui représentent les résultats immédiats des transitions
x->y et y —> x et ne dépendent que des. extrémités de ces arcs. La
valeur d'un chemin est alors la somme des valeurs élémentaires des
arcs qui le constituent.

Figure 3 : Diagramme représentatif d'une évolution H.D.

214 REVUE ECONOMIQUE

Figure 4 :

L'unité de valeur est le millier de F. Les dépenses sont précédées du signe

Reprenons l'exemple du fabricant de transistors. A chaque arc de

décision peut être associé le coût de l'investissement correspondant.
A chaque arc de hasard correspond un certain chiffre de ventes : nous
avons inscrit sur la figure 4 le profit annuel en résultant. En fait, le
processus s'étend sur une période assez longue, et les dépenses et
recettes doivent être actualisées. Nous avons inscrit en-dessous de
chaque arc la valeur actualisée (en prenant comme référence la date
0) correspondante, en faisant les hypothèses suivantes : le taux d'intérêt
est de 7 % par an, les investissements sont effectués en début de phase,
les recettes sont perçues à la fin de chaque année. Par exemple —
pour l'arc B D la recette est de 100 000 F par an, soit pour la durée
de la phase considérée (2 ans) lOOOOof- + 1 = 180 800 F

actualisés.
 LA PROGRAMMATION DYNAMIQUE 215

— La valeur actualisée du chemin A B D H (compatible avec la

stratégie S1) est : — 80 000 + 180 8000 + 0 + 229 200 = 330 000 F.
Nécessité d'un critère de comparaison des stratégies. Pour déterminer
la stratégie optimale, il faut être capable de comparer entre elles les
différentes stratégies. Dans le cas « déterministe », il suffisait de
sommer, pour l'ensemble des phases, les valeurs attachées aux décisions
successives constituant une politique ; la politique optimale était celle
qui conduisait au meilleur résultat. Dans le cas aléatoire (ou incertain),
comparer entre elles les stratégies équivaut à comparer plusieurs
ensembles de valeurs : à chaque stratégie correspond autant de résultats
qu'il y a de chemins compatibles avec cette stratégie. Pour résoudre
ce problème, il nous faut donc utiliser un critère de comparaison qui
nous permette de résumer chaque ensemble de valeurs par un nombre
unique : il suffira alors de classer les différentes stratégies en fonction
de ce nombre.

2 — Le critère de l'espérance mathémathique

Supposons qu'une décision D rapporte les revenus R1, R2, ... Rq,
selon que se produisent les événements e1, e2 ... eq de probabilités res-
q.
pectives p1, p2 ... pq ( S p' = 1).
i= 1
On peut alors songer à remplacer l'ensemble des résultats R1, R2 ... Rq
par le nombre unique

E (R) = p1 B1 + p2 R2 + + p* Ri

appelé espérance mathématique du revenu, attachée à la perspective

(e1, e?, ... ea) 30. Cette espérance mathématique représente le revenu
probable — ou moyen (si l'on répète l'expérience un suffisamment
grand nombre de fois) — qui peut résulter de la décision D. La
comparaison de différentes décisions D1, D2, ... Dk pourra alors être effectuée
en comparant directement leurs espérances de revenu E1 (R), ... Ek (R).

Espérance d'une stratégie.

Revenons au cas d'un processus séquentiel. Le choix, à l'instant 0,

d'une stratégie S, définit un certain nombre d'évolutions possibles —
qui ne dépendent plus que du hasard — représentées par autant de

30. Cf. P. Massé, op. cit., pp. 199-200.

216 REVUE ECONOMIQUE

chemins du graphe. La probabilité de parcourir un de ces chemins peut

être calculée à l'aide des théorèmes du calcul des probabilités 31.

Figure 5

Le chemin x0 —> x3 représenté sur la figure 5 correspond à la succession

cli, ß\, d2, e2, cl3, e3. Les décisions dx, d?, dg, sont déterminées par le
choix de la stratégie S. Les événements ex, e2, e3, sont associés aux
probabilités conditionnelles pu p-2, p3 : ainsi p2 représente la probabilité
d'arriver à l'état x2 quand on est passé par l'état yv (donc par l'état Xi).
La probabilité du chemin !Xfl —> x3 (qui correspond à la triple condition :
l'éventualité eh puis l'éventualité e3, puis l'éventualité e3 se produisent),
est égale au produit px p., p3 (d'après le théorème des probabilités
composées).
L'espérance mathématique d'une stratégie est alors obtenue en
calculant la somme des valeurs des différents chemins compatibles avec
cette stratégie, pondérées par leurs probabilités.

Reprenons l'exemple du fabricant de transistors. L'espérance mathé-

matique de la stratégie S1 :

/M
D > H
^ N
^ E > O

est obtenu de la façon suivante :

31. Cf. P. Massé, op. cit., p. 202. — G. Calot, Cours de calcul des
probabilités, Dunod, Paris, 1964, chap. 3. — P. Rosenstiehl et J. Mothes,
Mathématiques de l'action », Dunod, Paris, 1965, chap. 3.
 Valeurs Espérances
Poids (probabilités) en milliers de F en milliers
Chemins
(1) (2) de F
(1) x (2)

A B D H M 0,5 . 0,7 = 0,35 80 + 180,8 + 229,2 = 330,0 115,5

A B D H N 0,5 . 0,3 = 0,15 80 + 180,8 + 114,6 = 215,4 32,3
A B E I O 0,5 . 1 =0,5 ■ 80 + 54,2 + 68,8 = 43,0 21,5

Total 1,00 169,3

En ordonnant différemment les calculs, on peut déterminer cette

espérance par récurrence. Pour chaque sommet x ou y, on peut calculer
l'espérance de la sous-stratégie appartenant à la stratégie S1, et définie
à partir de ce sommet. Les calculs s'effectuent de proche en proche,
en remontant le cours du temps : la valeur d'un arc de hasard est
ajoutée à l'espérance Esi (y, — ) de son extrémité terminale, puis
pondérée par sa probabilité conditionnelle.
A partir des sommets de Y\
pour H E (H, —) = p (H, M) . b (H, M) + p (H, N) b (H, N)
= 0,7 . 229,2 + 0,3 . 114,6 = 194,8
pour I ES1 (I, — ) = 68,8
A partir des sommets de Xt
pour D a (D, H) + ES1 (H, -)
E S1 (D, -) = 194,8

Pour E ES1 (E, — ) = 68,8

A partir des sommets de Yo,
pour B ES1 (B, —) = p (B, D) [b (B, D) + E_, (D, —)]
+ p (B, E) [b (B, E) + ES1 (E, —)]
E (B, — ) = 0,5 [180,8 + 194,8] + 0,5 [54,2 + 68,8]
= 249,3
A partir des sommets X()
pour A E (A, -) = a (A, B) + ES1 (B, —)
= — 80 + 249,3 = 169,3
Cette espérance Esi (A, — ) représente l'espérance mathématique de
la stratégie S1 définie à partir de l'entrée A. On retrouve bien le résultat
déjà obtenu.
Les calculs peuvent être menés directement sur le diagramme
séquentiel, en opérant de droite à gauche (cf. fig. 6).
 218 REVUE ECONOMIQUE

E(A,-) = 169,3 E(E,-) = 68,8 E(I,-) = 68,

Figure 6
Justification de l'emploi- du critère de l'espérance mathématique. 32
L'emploi du critère de l'espérance mathématique trouve sa
justification théorique dans la loi des grands nombres. Cette loi a été
découverte au xvme siècle par J. Bernouilli. Depuis, sa formulation et
ses applications ont été élargies : « Lorsqu'une entreprise effectue un
grand nombre d'opérations, que les aléas encourus sont caractérisés
par des probabilités indépendantes ou faiblement liées en chaîne, et
que les pertes et les gains actualisés successifs sont du même ordre
de grandeur, l'espérance mathématique du profit total actualisé
préfigure celui-ci de très près » 33.
Dès lors, le classement des perspectives aléatoires en fonction des
espérances E (S) est une approximation acceptable du classement qui
s'établirait ex post en fonction du résultat effectif V [C (S)], quand le
nombre N de phases est suffisamment grand (V [C (S)] représente le
revenu actualisé correspondant au chemin C effectivement emprunté
quand on applique la stratégie (S).
Mais il nous faut dès maintenant souligner que l'espérance
mathématique ne représente qu'un résultat probable et que son utilisation
à l'évaluation des stratégies suppose un certain nombre de conditions
idéales qui sont rarement vérifiées dans la réalité. Nous reviendrons
plus loin sur ce point important (cf. section IV). Nous montrerons
auparavant que le recours au critère de l'espérance mathématique
permet l'emploi d'un algorithme de Bellman pour la résolution des
programmes dynamiques en avenir aléatoire.
32. Cf. P. Massé, op. cit., pp. 200-212. — J. Mothes, Prévisions et décisions
statistiques dans l'entreprise, Dunod, Paris, 1962, pp. 91-104.
33. P. Massé, op. cit., p. 200.
 LA PROGRAMMATION DYNAMIQUE 219

3. RECHERCHE DE LA STRATEGIE OPTIMALE

Dans le cas des processus en avenir aléatoire, l'introduction du

hasard oblige à étudier des stratégies et non plus des politiques comme
pour les problèmes de nature déterministe. Mais le critère de
l'espérance mathématique permet de caractériser chaque stratégie (ou sous-
stratégie) par un seul nombre de la même manière que chaque politique
pourrait être évaluée d'après sa valeur (cf. la section précédente). La
stratégie optimale est alors celle qui correspond à l'espérance optimale.
Deux approches de la solution sont possibles 34.
— La première méthode suit le cours normal du temps, au moins
dans un premier stade, et consiste à étudier l'évolution du système
pour chaque stratégie possible, la recherche de l'optimum n'intervenant
qu'à la fin. Il s'agit de faire correspondre à une stratégie quelconque
une description probabiliste de l'évolution du -processus, pour en
déduire l'espérance mathématique de ses résultats (cf. pp. 215-216). On
classe ensuite les stratégies en fonction de leurs espérances. Cette
approche est recommandée pour l'étude des processus markoviens (cf.
infra), mais devient impraticable pour celle de la plupart des processus
non stationnaires, en raison du nombre considérable de stratégies qu'il
faudrait comparer.
— La deuxième méthode, basée sur le théorème d'optimalité,
recherche — en remontant le cours du temps — à définir une stratégie
qui soit constamment optimale. Chaque étape de l'algorithme détermine
simultanément l'espérance et le vecteur de décisions (pour la phase
considérée) de la stratégie optimale. Cette approche devient nécessaire
lorsqu'un grand nombre de stratégies sont possibles. Elle présente en
outre l'avantage de s'adapter facilement au cas où les variables x et y
sont continues (où le nombre de stratégies envisageables est infini).
Le principe d'optimalité s'énonce ainsi : « Une stratégie optimale
ne peut être formée que de sous-stratégies optimales ». La façon
séquentielle dont sont calculées les espérances Es (x, — ) ou Es (y, — )
des sous-stratégies appartenant aux différentes stratégies S à considérer,
et définies à partir d'un sommet x ou y (cf. p. 217) nous impose ici
de mener l'optimisation en remontant le cours du temps. En d'autres
termes, seul l'algorithme de type (I) (cf. p. 198) est applicable. Il
s'appuie sur la propriété suivante : « Une stratégie optimale de Xn à XN
(ou de Yn à YN) ne peut être formée que de sous-stratégies optimales
de Xn+i à XN (ou de Yn+1 à YN).
34. Cf. P. Massé, op. cit., pp. 273-274.
220 REVUE ECONOMIQUE

Nous présenterons d'abord cet algorithme en étudiant un exemple

simple (celui du fabricant de transistors). Nous donnerons ensuite les
formules d'optimisation correspondant au cas général des processus
D.H. et H.D.

1 — Etude d'un exemple : le problème du fabricant de transistors

L'algorithme de résolution est le suivant :
Envisageons d'abord la phase N (IV = 2). -he vecteur de décisions
optimales de cette phase associe à chaque sommet (D, E, F ou G) le
chemin x\ y~tv xe2 de valeur optimale. Il faut donc déterminer pour
chaque x±.
OPT E (x\, — ) = MAX [a (x\, yY,,) + (yr^, —)]

Les calculs se présentent ainsi :

Espérances pour les sommets yu
E (H, —) = 0,7 . 229,2 + 0,3 . 114,6 = 194,8
E (I, —) = = 68,8
E (I, —) = 0,7 . 229,2 + 0,3 . 114,6 = 194,8
E (K, — ) = (0,7 + 0,3) 114,6 = 114,6
E (L, —) = = 68,8
Espérances optimales pour les sommets X\
OPT E (D, — ) = = 194,8
E (E, — ) = = 68,8

E (F, — ) = M A X 194,8—43,7=151,1
=114,6
= 151,1 : choix de
la décision
(FJ)
E (G, — ) = = 68,8
La stratégie optimale S (X1? -) à partir de Xx est donc

r M
D y H C Ë (D, -) = 194,8
*.N
E > i —^ O Ë (E, ) — 68,8
{
F »' J Ë (F, — ) = 151,1
C
*Q
► L »- T Ë (G, -) = 68,8
 LA PROGRAMMATION DYNAMIQUE 221

Envisageons maintenant l'ensemble des phases 1 et 2 (ensemble du

processus). Pour déterminer la stratégie optimale à partir de A (seule
entrée possible), il suffit de comparer les stratégies empruntant les
chemins de la phase 1, puis les chemins optimaux de la phase 2 (c'est-
à-dire les stratégies S1 et S2, puisque l'élimination — au cours de
l'itération précédente — de la décision (F, K) revient à écarter S3). La
stratégie optimale correspond donc à :
OPTE (A, — ) = MAX [a (A, y\, + Ë w\,. — )]

avec Ë (yv0,. — ) = V p (i/vo; ,x\) [b (yvo., x\) + Ë (x\, — )]

xii
(cf. les calculs de la page 217 ; les espérances Ë (x\, —) ont été calculées
lors de l'itération précédente).
Les calculs se présentent ainsi :
— Espérances optimales pour les sommes y^a,
Ë (B, —) = 0,5 [180,8 + 194,8] + 0,5 [54,2 + 68,8] = 249,3
Ë (C, — ) = 0,5 [ 90,4 + 151,1] + 0,5 [54,2 + 68,8] = 182,2

— Espérances optimales pour le sommet A :

E (A, — ) = M A X ioo'ç =50 = 132*9 ! ~ 169,3 choix de la décision (A, B)

La stratégie optimale S est obtenue en joignant la décision (A, B) et

ses terminaisons « hasard » (B, D) et (B, E) aux parties de la sous-
stratégie S (Xj, — ) issues de D et E. Elle s'écrit donc :

* D —> h
A * B \ XX N E (A, — ) = 169,3
X E > I —* O

C'est la stratégie S1, son espérance mathématique est 169 300 F.

En d'autres termes, il vaut mieux, si l'on décide de rechercher le
gain probable maximum, construire dès le début un atelier de grande
capacité (il n'y a plus alors de décision à prendre au cours de la
phase 2).
Les calculs peuvent être effectués directement sur le diagramme.
On calcule pour chaque sommet, en remontant de droite à gauche, les
espérances optimales Ë (x, — ) ou Ë (y, — ) et l'on note à chaque
itération les arcs de décision optimaux : ils sont représentés en trait
double sur la figure 7.
222 REVUE ECONOMIQUE

Remarques :
1. Le diagramme pourrait être légèrement simplifié. Ainsi les deux
événements (K, R) et (K, S) ont le même résultat, on pourrait donc
confondre les deux sommets R et S et écrire directement Ë (K, — )
= 114,6. De même un chemin passant par B —> E emprunte
nécessairement les arcs (E, I) et (I, O), on pourrait donc considérer qu'il
va directement de B à O et écrire v (B, O) = 54,2 + 68,8 = 123
puis : Ë (B, — ) = 0,5 (180,8 + Ë (D, — ) + 0,5 v (B, O).
Nous préférons cependant utiliser le schéma de la figure 7 pour
mieux faire apparaître la décomposition D.H. du processus.
2. L'intérêt de la méthode de Bellman n'apparaît pas clairement ici.
Cela tient à la simplicité de l'exemple étudié, où il n'y a que trois
stratégies à considérer. Il n'en va évidemment pas de même pour
la plupart des problèmes concrets.
 LA PROGRAMMATION DYNAMIQUE 223

2 — Formulation générale de l'algorithme

A) Processus D. H.

Les itérations sont les suivantes :

— Envisageons d'abord la phase N. Le vecteur de décisions optimales
associe à chaque sommet xN~i le chemin xkN_i y?\N^ly xxN de valeur
optimale. Chaque décision optimale est définie par :
OPT E (x\_r — ) = OPT [« («V,, V\s-u>) + E fo\N-i,'' —M

(la notation Y^^,, (xkN_i) est équivalente à celle que nous avons
introduite page 197.
Ces équations spécifient pour chaque sommet .TkN_x l'arc de
décision (xkN_! , Y?'(N_1);) optimal, et indiquent en même temps le résultat
Ë (xkn_r —) = O P T E (.tVi- —) optimal.
Les calculs peuvent être effectués directement sur le diagramme
séquentiel, de la même manière qu'à la page 221. On calcule d'abord
les espérances E (t/(N_i,>) puis on détermine les espérances optimales
Ë (x\_h —) que l'on note sur la figure .en soulignant les arcs de
décision correspondants.
— Envisageons l'ensemble des phases n + 1 à N. Pour déterminer
la stratégie optimale à partir de Xn, il suffit de comparer les stratégies
empruntant les chemins de la phase n + 1, puis les chemins optimaux
des phases n + 2 à N.
Il faut donc déterminer pour chaque sommet xra :
OPTE (x'n, —)=■ OPT [a (*/, j/°n,) + Ë (yan>, _)]
il ,i- ' s in, (.-<■ n> > '
(Y) E~ (j,a , (ii° rs *) \h
j avec v.f n-
Ë (° /\ — v
/. Vn \" n' x n+l ^U (ii° *■" n' , 'vs u+1/'I ^^
4- F^ \x
(rs n+1' ")]
/J

(les espérances optimales Ê (x\lH, — ) ont été déterminées par

l'itération précédente, ainsi que les chemins correspondants).
Ces équations associent à chaque xrn un sommet yan, : la stratégie
optimale à partir de Xn est obtenue en joignant les arcs de décision
(x\v t/V) ainsi obtenus à la sous-stratégie optimale à partir de Xn+1.
Ces opérations peuvent être menées directement sur le graphe. On
affecte à chaque sommet xTn l'espérance optimale Ë (xrn, — ) et souligne
les arcs de décision optimaux (xTn, t/an>)-
224 REVUE ECONOMIQUE

— Envisageons enfin l'ensemble du processus {phases 1 à N).

L'équation fonctionnelle spécifiant la stratégie optimale à partir de x0 est :
E [S (v — )] = OPT E (*o> — ) = y0,
OPT s Yo, (x0, — ) [a (x0, y\,) + Ë (yV —)]
■■

avec Ë (y\,, — ) = £ p (y\,, x\) [b (y\,. x\) + E (x\, —)]

x\
(Les espérances Ë (x\, — ) ont été déterminées par l'itération
précédente). Cette équation indique, pour x0, l'arc de décision optimal d (x0,
yiQ,) et l'espérance de la stratégie optimale S (x0, — ). Cette dernière
s'obtient en prolongeant l'arc (x0, yV) Par la sous-stratégie optimale à
partir de Xx 35.
L'algorithme est alors terminé dans le cas où l'état d'entrée x0 est
unique. Sinon, deux cas sont à envisager :
— xh0 est à choisir à l'intérieur d'un ensemble Xo : le sommet x\
optimal et la stratégie correspondante sont définis par :
OPT E (x\, — )
A o c ^o
— xh0 est connu en probabilité (parce qu'en fait le processus a
« démarré » avant la date 0). La stratégie optimale s'obtient alors en
réunissant les stratégies S (xhn, — ) et son espérance est donnée par :
Ê (xo, — ) = S p (x\) Ë (x\, -)

B) PROCESSUS H. D.
Le principe de résolution est identique. L'équation de récurrence
définissant l'algorithme s'écrit alors :
\ OPT E (yn, — ) = S P (!/„, *°n> —) [b (y\, -t°n,) + Ë «,, — )]
/ x°
(r)
\ avec E (xen,. — ) = O P T [a (*°n>. ysn+1) + E (yn+v —)]
I ysn+i3Yn+1(xGn>,-)

(Les espérances Ë (ysa+i, — ) ont été déterminées par l'itération

précédente). Les calculs peuvent être effectués directement sur le graphe.
On détermine d'abord les arcs de décision (xPa,, ysn+-i), en notant les
espérances Ë (LXan», —) correspondantes. Puis on calcule, pour chaque
sommet t/r„, l'espérance Ë (yTn, — ).

35. Ou plutôt par la partie de cette stratégie S0 (Xp — ) issue des sommets
x\ qui sont extrémités d'un arc de hasard d'origine yn0,.
 LA PROGRAMMATION DYNAMIQUE 225

C) Remarques
a) Processus à variables continues. L'algorithme de Bellman est
encore applicable quand les variables x et y sont continues : les
formules d'optimisation (D, et (I") restent valables 36. Mais l'explicitation
des contraintes liant les x et les y introduit des complications dans
les calculs. D'autre part, il n'est guère possible de se servir du
diagramme représentatif 37.
b) Introduction d'un horizon illimité — Cas des processus
stationnaires. Lorsque l'horizon du programme n'est pas borné, se pose le
problème de la convergence, que nous avons déjà évoqué à propos
des processus en avenir certain (cf. pp. 199-200).
La plupart des théorèmes de convergence concernent les processus
stationnaires, qui correspondent au cas particulier suivant :
— Les ensembles Xn et Yn, (ou Yn et XrP.) sont identiques pour
toutes les phases.
— Les transitions de décision x — > y et de hasard y — > x sont
indépendantes de n, ainsi que les valeurs a {x, y) et b {y, x), et les
probabilités p (y, x).
— La durée Tn de la phase n est constante.
L'application de la méthode de Bellman n'est guère recommandée
pour l'étude des processus stationnaires à horizon illimité. Celle de la
première méthode (cf. p. 219) est préférable, car le nombre de stratégies
à comparer est réduit. En effet, le vecteur des décisions à prendre est
indépendant de n : la stratégie optimale ne peut donc être qu'une
stratégie permanente. Il suffît alors d'évaluer les différentes stratégies
permanentes et d'en établir le classement. L'étude du comportement
du système sous l'influence d'une stratégie permanente se ramène à
celle du comportement asymptotique d'une chaîne de Markov : le
classement des stratégies peut alors s'établir d'après l'espérance
attachée à une phase, i\ est — généralement — indépendant de l'état
d'entrée du processus 38.
36. A condition de remplacer les probabilités p (x, ifi par des densités de
probabilité et les sommes intervenant dans l'expression des espérances
mathématiques par des intégrales.
37. Cf. p. 198. Pour une étude détaillée des processus à variables continues,
cf. A. Kaufmann et R. Cruon, op. cit., chap. III.
38. Une excellente introduction à l'étude des chaînes de Markov est l'ouvrage
de. P. Gordon, Théorie des chaînes de Markov finies et ses applications, Dunod,
Paris, 1965. — Pour l'étude proprement dite des processus markoviens, cf.
R. Howard, Dynamic Programming and Markov Processus, J. Wiley, New
York, 1960. — A. Kaufmann et R. Cruon, op. cit., chap. 5. — R. Bellman et
S. Dreyfus, op. cit.. chap. 11.
Revue Economique — N° 2, 1969 15
226 REVUE ECONOMIQUE

4. LA CRITIQUE DU CRITERE DE L'ESPERANCE MATHEMATIQUE

Nous avons vu (pp. 215-218) que le classement des stratégies

nécessitait que l'on sache résumer un ensemble de plusieurs valeurs —
correspondant aux différentes valeurs des chemins compatibles avec une
stratégie donnée — par un nombre unique. Le critère de l'espérance
mathématique, basé sur la loi des grands nombres, répond à cette
exigence. Mais son application aux programmes dynamiques suppose :
a) que les probabilités des événements soient significatives, et
qu'elles soient connues au début du processus (quelle que soit la phase
qu'elles concernent), pour qu'il soit possible d'élaborer à l'avance la
stratégie sur les N périodes ;
b) cette première condition étant remplie, l'espérance mathématique
attachée à une stratégie — qui peut alors être calculée — doit
effectivement « préfigurer » le résultat final : le nombre N de phases doit
être suffisamment grand ; et les opérations doivent présenter un certain
caractère répétitif, leurs résultats devant être également du même
ordre de grandeur 39.
Ces conditions sont rarement réalisées. Il peut d'abord arriver qu'il
soit possible d'attribuer a priori des probabilités « objectives » aux
différents états du monde, mais que l'absence des conditions b) rende
insuffisant le critère de l'espérance mathématique : il faudra tenir
compte du « risque » que le résultat effectif s'écarte de son espérance
mathématique. Le second cas est celui où l'avenir est incertain :
l'absence de probabilités attribuables aux états du monde rend a priori
impossible le recours au critère de l'espérance mathématique.

1 — Prise en compte du risque

Nous considérons ici des processus où il a été possible d'attribuer
à chacun des « états du monde » des probabilités a priori.
L'existence de telles probabilités peut tenir au mécanisme même
du processus qui conditionne les états du monde : il est alors
logiquement possible de calculer ces probabilités en utilisant des règles
d'analyse combinatoire. Mais plus souvent, elle sera justifiée par la régularité
statistique du processus : par exemple, un chef de service des
approvisionnements, qui doit s'efforcer de satisfaire à des besoins fluctuants
en limitant les frais de stockage, peut tirer parti de l'observation des
variations enregistrées dans le passé du rythme des commandes reçues.

39. Le cas idéal est alors celui des processus stationnaires à horizon illimité.
 LA PROGRAMMATION DYNAMIQUE 227

Cette régularité — observée ex ante, et qui permet la détermination

a priori de probabilités — n'est pas incompatible avec la
non-répétitivité des décisions ultérieures (par exemple, l'horizon du programme
est limité) qui rend injustifiable l'application de la loi des grands
nombres. A la limite, on est conduit à se poser la question du critère de
comparaison de décisions isolées (ou de stratégies portant sur deux
ou trois phases seulement).
Evaluation du risque pour une stratégie*0. Nous avons vu qu'une
stratégie quelconque était compatible avec plusieurs chemins, chacun
de ces chemins ayant une probabilité que l'on peut facilement calculer
(cf. p. 216). On peut donc déterminer la distribution de probabilités des
valeurs qui peuvent être obtenues avec cette stratégie. Le calcul de
l'espérance mathématique permet de connaître la valeur moyenne
de cette distribution, et la loi des grands nombres indique que — dans
certaines conditions — la dispersion autour de cette moyenne est
faible. Dans le cas général, les conditions b) ne sont pas réalisées, et
la distribution est plus dispersée : la probabilité de valeurs éloignées
de la moyenne n'est pas négligeable. Il est alors intéressant d'évaluer
le risque de la stratégie en cherchant la probabilité d'obtenir un
résultat inférieur à une certaine valeur V,, (en supposant que l'optimum
est obtenu par maximation de Y). On peut alors être amené à refuser
la stratégie optimale si la probabilité d'obtenir un résultat inférieur à
Vo dépasse le seuil a que Ion s'est fixé.
Stratégies pen -optimales 41. Dans ce cas, on adoptera une des stratégies
correspondant aux espérances immédiatement inférieures à l'espérance
optimale (stratégies « pen-optimales ») et ne comportant pas un tel
risque.
On établit donc la liste des stratégies, classées par espérances
décroissantes (stratégies 1-optimale, 2-optimale, ...) et on retient la
première qui conduit à un risque acceptable.
Le classement des stratégies pose des problèmes délicats quand
on utilise l'algorithme de Bellman, qui ne fournit en principe que la
stratégie optimale 42. Il est au contraire immédiat dans les cas
d'application — par exemple l'étude des processus marko viens — de la
première méthode (cf. 219), dont il constitue précisément l'objectif.
Montrons sur l'exemple du fabricant de transistors la façon dont

40. Cf. A. Kaufmann, op. cit., pp. 139-142.

41. Cf. A. Kaufmann, op. cit., pp. 142-146.
42. Il est cependant possible d'adapter l'algorithme, mais cela complique
notablement les calculs. Cf, R. Bellman et R. Kalaba, « the kth best policy »,
Journal of Soc. for Ind. and Applied Maths, vol. 8, déc. 1960.
228 REVUE ECONOMIQUE

on peut opérer. On suppose que l'on recherche le revenu maximum,

tout en refusant un risque supérieur à 30% de gagner moins de
50 000 F en cinq ans. Les distributions de valeurs correspondant aux
stratégies S1, S2, S3, sont indiquées dans le tableau ci-après :

Espérances
Chemins Probabilités- Valeurs en milliers de F en milliers
de F

Stratégie S1
A B D H M 0,5 . 0,7 = 0,35 — 80 + 180,8 + 229,2 = 330,0 115,5
A B D H N 0,5 . 0,3 = 0,15 — 80 + 180,8 + 114,6 = 215,4 32,3
A B E I O 0,5 . 1 = 0,50 — 80 + 54,2 + 68,8 = 43,0 21,5

Total 1,00 169,3

Stratégie S2
ACFJR 0,5 . 0,7 = 0,35 — 50 + 90,4 — 43,7 + 229,2 = 225,9 79
A C F J Q 0,5 . 0,3 = 0,15 — 50 + 90,4 — 43,7 + 114,6 = 111,3 16,7
A C G L T 0,5 . 1 = 0,50 — 50 + 54,2 + 68,8 = 73,0 36,5

Total 1,00 132,2

Stratégie Ss
A C F K R 0,5. 1 = 0,5 — 50 + 90,4 + 114,6 = 155 77,5
A C F K S
A C G L T 0,5. 1 = 0,5 — 50 + 54,2 + 68,8 = 73, 36,5

Total 1,00 114,0

Le classement des stratégies est donc : S1, S2, S3. Mais la stratégie S1
(1-optimale) comporte un risque de 50 % (50 > 30) de rapporter
seulement 43 000 F (43 < 50) : il faut donc la refuser. Par contre, la
stratégie S2 est acceptable, car le revenu minimum qu'elle procure est
73 000 F. Elle consiste à investir 50 000 F à la date 0, et à décider au
bout de 2 ans d'investir à nouveau 50 000 F si les deux années
antérieures ont été favorables, de ne rien investir dans le cas contraire.
 LA PROGRAMMATION DYNAMIQUE 229

2 — Cas ou l'avenir est incertain

Nous avons supposé jusqu'à présent que l'avenir était « probabili-

sable ». Il était possible d'attribuer à chaque état du monde une
probabilité objective, même lorsque la nature du processus nous interdisait
d'utiliser sans précautions le critère de l'espérance mathématique (cf.
paragraphe 1). Il peut arriver, au contraire, que l'avenir soit incertain
(par exemple, il est impossible de déduire des probabilités de
répétitions statistiques antérieures).
Dans ce cas, on peut envisager deux méthodes de comparaison des
stratégies. La première consiste à adapter les critères de la théorie des
jeux au cas où l'adversaire est la nature. La seconde consiste à
réintroduire la notion de probabilités en utilisant des probabilités subjectives.

A) Les critères de la théorie des « jeux contre la nature » 43

Reprenons l'exemple du fabricant de transistors. Les résultats V^

correspondant aux différentes stratégies peuvent être inscrits dans la
« matrice de gains » ci-dessous (cf. p. 228).

Etats du inonde E
E1 E2 E3
Les états du monde E sont
S1 330 215,4 43 E1 demande toujours forte
s2 E2 demande forte puis faible
•225,9 111,3 73 E" demande toujours; faible
s:; 155 155 73

Nous supposons qu'il n'est pas possible d'attribuer des coefficients de

pondération aux états du monde E1, E2, E3. La théorie des jeux propose
alors les critères suivants :

Le critère de Wald (critère du Minimax — ou du Maximin —

appliqué à un jeu contre la nature) consiste à regarder pour chaque

43. Nous ne présentons ici que ceux qui nous semblent les plus significatifs.
Pour une présentation plus complète, cf. : P. Massé, op. cit., chap. V, V. —
A. X-vufmann, op. cit., pp. 208-221, et les ouvrages plus spécialisés de L.J.
Savage, The Foundation* of Statistics, Wiley, New York, 1954. — R.D. Luce
et H. Raiffa, Games and Decisions, Wiley, New York, 1957, chap. XIII.
230 REVUE ECONOMIQUE

stratégie S1 ce qui risque d'arriver de pire et à « limiter les dégâts ».

On retient donc pour chaque ligne (stratégie S1)
V1 = MIN VU
j
et l'on détermine i en cherchant
V = MAX V1 = MAX MIN VU
i i j
Dans le cas où l'on est en présence d'une matrice de pertes (ou de
coûts) 0^ le critère de Wald devient M I N M A X CX
i J
Dans l'exemple choisi, les résultats les plus défavorables correspondent
tous à l'éventualité E3 (/ = 3, V i). Les stratégies optimales — suivant
ce critère — sont S2 et S3, qui conduisent au pire à un gain de 73 000 F
(alors que S1 peut conduire à un gain de seulement 43 000 F).
Cette règle assure le maximum de sécurité, puisqu'elle amène à choisir
la stratégie qui minimise la plus grosse perte (ou maximise le gain le
plus faible) que le sort puisse infliger. Mais dans la mesure où elle ne
tient pas compte des éventualités les plus favorables (dans l'exemple,
les chiffres de colonnes 1 et 2 n'interviennent pas), elle peut sembler
exagérément pessimiste.
Le critère de la minimation des regrets a été proposé par L.J.
Savage pour remédier à ce défaut. Il consiste au fond à se placer « ex
post » — et non plus « ex ante » — et son fondement psychologique
paraît plus justifié : « II ne dépend pas de nous que ce soit l'un ou
l'autre état de la nature qui se réalise. Si un état de la nature se réalise,
la seule chose que nous ayons donc à considérer est le « regret »,
différence entre le maximum de profit que nous aurions pu avoir avec cet
état et le profit qui résulte de la décision que nous avons choisie » 44.
Savage substitue donc aux valeurs t>i;> les regrets rij. Le regret r^ est
la différence entre la valeur effectivement perçue quand la stratégie
est S1 et l'événement E^, et celle que l'on aurait obtenue si l'on avait
connu à l'avance cet état Ei et adopté en conséquence la stratégie
appropriée S1. Donc
rü = MAX VU — VU
i
II applique ensuite le critère de Wald (version MINIMAX) aux regrets,
en cherchant
= MIN MAX rij
i j
44. J. Lesouhne, op. cit., p. 53.
 LA PROGRAMMATION DYNAMIQUE 231

Exemple :
Matrice de regrets
E1 E2 E3 Les maxima des regrets (en ligne) sont
soulignés d'un trait.
S1 0 0 30 | Le minimum de ces maxima détermine
la décision optimale : c'est la stratégie
s2 104,1 104,1 S1 qui garantit un regret inférieur à
0
30 000 F.
s3 175 60,4 0

Cet exemple montre que le critère de Savage ne concorde pas

nécessairement avec celui de Wald : il est généralement moins pessimiste.
Mais il conserve le même défaut principal : il n'utilise pas toutes les
données du problème.
Les développements qui précèdent ont montré que l'utilisation du
critère MAXIMIN ou MINIMAX — appliqué aux valeurs ou aux
regrets — ne présente pas de difficultés quand on connaît les valeurs
des chemins compatibles avec les différentes stratégies, ce qui résulte
directement de l'emploi de la première méthode (cf. p. 219). R. Bellman
indique (op. cité, p. 262) que le principe d'optimalité reste valable si
l'on remplace le critère de l'espérance mathématique par le critère
MAXIMIN ou MINIMAX. L'algorithme de Bellman peut donc être
utilisé. Il suffit de ne conserver, sur le graphe séquentiel, à la suite
de chaque sommet y, que l'arc de hasard le plus défavorable. L'agent
de décision n'a plus ensuite qu'à résoudre un programme dynamique
déterministe (l'algorithme peut même être conduit indifféremment
dans le sens passé -> futur ou le sens futur -> passé).
B) Réintroduction des probabilités 45
Pour pallier les défauts des critères précédents, on peut songer à
utiliser le critère de Laplace qui consiste à attribuer aux différents
états du monde E1, E2 ... Ec< des probabilités égales. On associe alors

à chaque stratégie S1 la moyenne A1' = — [v[I + ... + v^ ... + vi(i].

A* qui représente ainsi une espérance mathématique (chaque chemin

compatible avec la stratégie S1 est pondérée par la probabilité — ). On

q
peut donc, en utilisant le critère A1, appliquer les méthodes
d'optimisation exposées dans la section III.

45. Cf. P. Massé, op. cit., pp. 218 à 220 et 243 à 251.
232 REVUE ECONOMIQUE

L'avantage de la règle de Laplace est de tenir compte de tous les

résultats que Ton peut obtenir avec une stratégie. Mais il apparaît
assez irréaliste d'attribuer les mêmes probabilités à tous les états de
la nature. En effet, on dispose presque toujours d'éléments d'information
qui permettent de se faire une idée — intuitive il est vrai — de leur
vraisemblance. Il est donc possible d'attribuer à ces états du monde des
probabilités subjectives. Plus précisément, la probabilité attribuée par
l'agent de décision à l'événement eJ, est un coefficient « rendant
quantitative la notion qualitative de vraisemblance de e*. Nous jugeons
que l'événement ei est plus ou moins vraisemblable, et nous agissons
en lui accordant plus ou moins de poids dans les comparaisons que
nous sommes amenés à faire pour motiver notre choix » 46.
On peut alors utiliser, en pondérant les divers états du monde par
ces probabilités subjectives, le critère de l'espérance mathématique.
Les méthodes de résolution exposées dans la section III sont
applicables, de même que les restrictions (étude du risque) apportées dans
le paragraphe 1 de cette section.
Le problème se complique cependant du fait que, généralement,
les estimations des probabilités deviennent de plus en plus floues au
fur et à mesure qu'on envisage des périodes plus éloignées 47.
L'agent de décision sera alors conduit à établir son programme,
à chaque instant, pour une durée limitée par son « intervalle
d'anticipation », et à réviser périodiquement ses plans pour tenir compte
de l'amélioration progressive de la précision de ses estimations 48.
Dans le cas des processus stationnaires, la prévision des estimations
sur le futur s'améliore en outre par suite de l'accumulation des
informations sur le passé (théorie de l'apprentissage de Bayes). Il s'agit alors
d'un processus avec adaptation 49.
Pierre DUHARCOURT

46. P. Massé, op. cit., p. 218.

47. Ce peut être d'ailleurs1 le cas également quand on procède à l'estimation
de probabilités objectives.
48. Cf. A. Kaufmann, op. cit., pp. 155-160.
49. Cf. A. Kaufmann, op. cit., pp. 160-166.
 LA PROGRAMMATION DYNAMIQUE 233

BIBLIOGRAPHIE ELEMENTAIRE

I — Algèbre - Théorie des graphes

J. Bouzitat et E. Berrebi, Eléments de mathématiques, cours polycopié de 1"
année de la Faculté de Droit de Paris, 1966, chap. I et II.
R. Faure, A. Kaufmann, M. Denis-Papin, Mathématiques nouvelles, t. II, Aide-
mémoire Dunod, Paris, 1964.
J.G. Kemeny, A. Schleiffer, J.L. Snell, G.L. Thompson, Les mathématiques
modernes et la pratique des affaires, (traduit de l'anglais), Dunod, Paris,
1964, chap. I.
Queysanne et Delachet, L'algèbre moderne, Coll. « Que sais-je ? », n° 66.
P. Rosenstiehl, J. Mothes, Mathématiques de l'action, Dunod, Paris, 1965,
chap. 1 et 2.
Références particulières à la théorie des graphes :
C. Berge, Théorie des graphes et applications, Dunod, Paris, 1958.
A. Kaufmann, Méthodes et modèles de la recherche opérationnelle, t. II, Dunod,
Paris, 1964, chap. 1 et 4.
B. Roy, Algèbre moderne et théorie des graphes, Dunod, Paris (à paraître).
G. Worms, Les méthodes modernes de l'économie appliquée, Dunod, Paris
1965, chap. 8.

II — Décisions économiques - Critères de choix

Actualisation - Comparaison d'échéanciers de valeurs :
R. Ghez, « Le budget d'investissements dans l'entreprise », Analyse et Prévision,
S.E.D.E.I.S., n° de mai et juin 1966.
J. Lesourne, Technique économique et gestion industrielle, Dunod, Paris, 1965,
pp. 32-35.
P. Massé, Le choix des investissements, Dunod, Paris, 1964, chap. I.
G. Worms, op. cit., chap. I.
Décisions en avenir aléatoire ou incertain :
M. Barbut, « Calcul des décisions, calcul des espérances, calcul des
probabilités », Mathématiques et sciences humaines, n° 2.
A. Kaufmann, op. cit., pp. 208-221.
J. Lesourne, op. cit., pp. 35-55.
R.D. Luce et H. Raiffa, Games and Decisions : Introduction and critical Survey,
Wiley, New York, 1957 (ouvrage traduit chez Dunod, 1966), chap. XIII.
P. Massé, op. cit., chap. V.
J. Mothes, Prévisions et décisions statistiques dans l'entreprise, Dunod, Paris,
1962, pp. 91-104.

50. Cette bibliographie ne concerne — sauf exceptions — que des ouvrages

postérieurs à 1960. Quelques ouvrages plus anciens sont cités dans le texte.
234 REVUE ECONOMIQUE

J. Mothes, Incertitudes et décisions industrielles, Dunod, Paris, 1967.

L.J. Savage, The Foundations of Statistics, Wiley, New York, 1954.
G. Worms, op. cit., chap. 10 à 12.

Ill — Programmation dynamique 51

R. Bellman, Dynamic Programming, Princeton. 1957.
R. Bellman et J. Dreyfus, La programmation dynamique et ses applications
(traduit de l'anglais), Dunod, Paris, 1965.
R. Bellman and R. Kalaba, Dynamic Programming and Modem Control Theory,
Academic Press, 1965.
R. Atus, Discrete Dynamic Programming, Blaisdell Publishing Co, 1964.
R. Howard, Dynamic Programming and Markov Processes, Wiley, New York, 1960.
O.R.L. Jacobs, An Introduction to Dynamic Programming, Chapman and Hall,
London, 1967.
A. Kaufmann, op. cit., chap. II et V.
A. Kaufmann et R. Cruon, La programmation dynamique : gestion scientifique
séquentielle, Dunod, Paris, 1965.
J. Lesourne, op. cit., chap. XL
T-F. Magee, « L'arbre de décision : guide pour l'analyse des risques et occasions
d'investissement)., Etude S.E.D.E.I.S. du 20-7-1965.
P. Massé, op. cit., chap. VI à VIII.
P. Massé, Le plan ou V anti-hasard, N.R.F. 1965, chap. VI.
P. Rosenstiehl et A. Ghouila-Houri, Les choix économiques : décisions
séquentielles et simulation, Dunod, Paris, 1960, chap. 2.
M.K. Starr et D.M. Miller, La gestion des stocks : théorie et pratique, (traduit
de l'anglais), Dunod, Paris, 1965, chap. 4 à 6.
Exemples et problèmes :
G. Desbazeille, Exercices et problèmes de recherche^ opérationnelle, Dunod,
Paris, 1964, chap. 4, 5 et 7.
A. Kaufmann et R. Faure, Invitation à la recherche opérationnelle, chap. 2 et 3.
H. Levy-Lambert, Problèmes d'économie de l'entreprise, Dunod, Paris, 1965,
problèmes n° 11, 12, 13 (cette lecture constitue une excellente initiation).

51. Le lecteur trouvera une bibliographie très importante à la fin des ouvrages
cités de A. Kaufmann et de P. Rosenstiehl - A. Ghouila-Houri. Nous avons
surtout cité ici les ouvrages les plus récents, en insistant sur ceux qui ont été
publiés en français. Les ouvrages fondamentaux restent ceux de R. Bellman
et de P. Massé. L'exposé le plus brillant est sans doute celui de P. Rosenstiehl
et A. Ghouila-Houri mais il est de lecture assez difficile.