Universit Hassan 1r
Facult des Sciences et Technique
-Settat-
Anne universitaire :2009/2010
Ralis par:
Mlle Hanaa ZINE-EDDINE
M Jalal Eddine SIRAGI
M Alaa Eddine MOUHABI
Filre dingnieur: PIC
Programmation dynamique
Introduction
La programmation dynamique est une technique
mathmatique qui a pour objet daider prendre
des dcisions squentielles indpendantes les unes
des autres.
Contrairement la programmation linaire, il ny
a pas un formalisme mathmatique standard. Cest
une approche de rsolution o les quations
doivent tre spcifies selon le problme
rsoudre.
La programmation dynamique
Ltat du systme tant reprsent par :
k numrote les priodes (dont le nombre est fix
N)
xk dcrit ltat du systme au dbut de la priode
k
uk est la dcision devant tre prise la priode k
wk est la perturbation alatoire de la priode k
fk est la fonction de transfert (transition) entre les
priodes k et k+1
Formalisme du problme:
La fonction de cot associe la priode k scrit :
On rajoute en plus un cot pour ltat final du
systme :
La fonction-objectif du problme doptimisation
scrit alors :
Un automobiliste doit se rendre de Sville Strasbourg. Il
a dcid deffectuer le voyage en quarte jours et den
profiter pour rendre visite quelques amis. Afin de limiter
les risques daccident dus la fatigue et de disposer dun
maximum de temps auprs de ses amis, il aimerait
minimiser la dure de sa plus longue tape journalire.
Notre conducteur a des amis Madrid, Valence,
Barcelone,Toulouse, Bordeaux, Lyon et Paris. La figure
suivante prsente les diffrentes tapes quil envisage ainsi
que les estimations des temps de trajets.
Exemple: Itinraire de voyage
Exemple: Itinraire de voyage
Rsolution de problme
xk dnote la ville o se trouve
lautomobiliste le matin du jour k.
Uk sa destination du jour.
Le systme dynamique associ au problme
est:
xk+1 = fk(xk,uk) = uk, k=1,2,3,4
Dans ltat xk ,le cot de dcision uk est gal
au temps t(xk,uk) du trajet entre les villes xk
et uk.
La recherche dun itinraire optimal revient
dterminer une suite de destination
{u1,u2,u3,u4} solution de
Rsolution de problme
Etape 4:
Rsolution de problme
x
4
Paris Lyon
J
4
(x
4
) 4 4,5
u(x
4
) Strasbourg Strasbourg
Etape 3:
Pour chaque valeur possible de x3,nous
devons rsoudre:
Rsolution de problme
Pour x3 = 4(bordeaux), il vient
Pour x3=5(Toulouse):
La destination optimale: u3=8Lyon
Pour x3=6(Barcelone),une seule dcision est
possible, Lyon, est son cot est:
En rsum:
x
3
Bordeaux Toulouse Barcelone
J
3
(x
3
) 5 4,5 5
u(x
3
) Paris, Lyon Lyon Lyon
Etape 2:
Pour x2= 2(Madrid) et 3(Valence):
Rsolution de problme
La table optimale de ltape est:
x
2
Madrid Valence
J
2
(x
2
) 5 5
u(x
2
) Barcelone Barcelone
Etape 1:
La ville de dpart est x1 = 1(Sville)
Rsolution de problme
Sville Madrid Barcelone
Lyon Strasbourg
Merci De Votre Attention