268
Recherche opérationnelle
)
(
1
t
t
x
x
Il s'agit donc de la minimalisation d'une fonction de
variables.
Le principe d'optimalité a permis de remplacer ce problème par une série de problèmes
de minimisation du type :
)
problème qui doit être résolu pour chaque
de chaque période , mais qui est un
problème de minimisation d'une fonction à une seule variable.
Pour fixer un peu plus les idées, supposons que le nombre de valeurs de
possibles (ou
nombre d'états à la phase , soit constant quel que soit et égal à
et que, par ailleurs
de la date
à la date on puisse atteindre tous les états de la date .
L'énumération de toutes les solutions possibles conduit à
solutions, pour chacune
desquelles il faut calculer une somme du type :
)
(
1
1
0
=
t
t
t
T
t
x
x
V
Le principe d'optimalité conduit, lui, à résoudre
problèmes de minimisation
d'une fonction à 1 variable. Si l'on s'en tient là aussi à l'énumération, l'exploration de
tous les
pouvant mener à aboutit au calcul de quantités du type
)
(
)
(
1
1
1
1
i
i
i
i
i
x
V
x
x
v
Dans un cas, (principe d'optimalité) on a donc
sommes de
à calculer. Dans
l'autre, (énumération complète) on a
sommes de
à calculer. On voit en
conséquence le gain que l'on peut obtenir en temps de calcul grâce au principe
d'optimalité. On a notamment affaire à un algorithme polynomial.
10.6.2. Le cas aléatoire
Revenons au problème qui nous intéresse ici, c'est-à-dire à l'étude d'un phénomène se
déroulant en plusieurs phases, elles-mêmes séparées en deux étapes : une étape décision
et une étape hasard. Nous nous intéresserons ici au cas où l'étape décision précède l'étape
hasard (DH). Encore une fois, l'étude des autres processus, c'est-à-dire les processus HD
est tout à fait analogue. Dans ces conditions, on a le schéma suivant :