4
Appli cA tions
des grAphes
à lA recherche
opé rA tion nelle
4.1 notions de pro grAm mA tion dynA mique (prd)
La pro gram ma tion dyna mique, impli ci te ment conte nue dans l’œuvre de P. de Fermat
(1601-1665), auteur du prin cipe fon da men tal de l’optique, a été uti li sée en recherche
opé ra tion nelle en France par P. Massé (1944), puis aux États-Unis R. Bellman (1952).
Fon dée sur le prin cipe d’optimalité, sur lequel nous revien drons, elle s’est beau coup
déve lop pée, au cours de ces der nières années.
Sous des condi tions, peu res tric tives dans la pra tique, quant à la forme du cri -
tère d’opti mi sation et à la manière dont le graphe est valué
1
, toute par tie (sous- -
chemin) d’un che min opti mal est, elle- même, opti male. En effet, s’il n’en était pas
ainsi, on pour rait lui subs ti tuer une par tie « meilleure », ce qui amé lio re rait la valeur
de l’ensemble du che min, préa la ble ment sup posé opti mal, d’où une contradiction.
Cette idée fon da men tale (qui est un théo rème lorsque les condi tions ci- dessus sont
rem plies) a été géné ra li sée sous forme d’un prin cipe : toute sous- politique d’une
poli tique opti male est elle- même, opti male, qui est utile mais bien trop géné ral pour
être accepté sans démons tra tion dans chaque cas d’espèce. Mais nos appli ca tions de
PRD se ramènent toutes à la déter mi na tion des che mins opti maux dans les graphes.
Le cas dis cret est par ti cu liè re ment simple et nous en don ne rons un exemple avant
de for mu ler les équa tions géné rales de récur rence qui en faci litent l’appli ca tion.
Exemple. Ima
gi nons la fig. que nous ayons à construire une auto route entre les
villes A et K, ainsi que l’indique la Figure 4.1, les points (sommets) inter mé diaires
pou vant être clas sés en groupes ou (phases) et les arcs du graphe ayant été va lués par
l’indi ca tion des coûts totaux (coûts de réa li sa tion 5 coûts des chaus sées, ouvrages
d’art, etc. 1 coûts sociaux, coûts de “regrets”, etc.).
1. Ce cri tère se tra duit par une fonc tion « de retour » (de revenu) qui doit être « décom po sable »
(condi tion de Mitten) et, par exemple, pour un cri tère « multiplicatif » (pro duit de reve nus élé men
taires), les valuations du graphe doivent être posi tives.
Appli cA tions
des grAphes
à lA recherche
opé rA tion nelle
4.1 notions de pro grAm mA tion dynA mique (prd)
La pro gram ma tion dyna mique, impli ci te ment conte nue dans l’œuvre de P. de Fermat
(1601-1665), auteur du prin cipe fon da men tal de l’optique, a été uti li sée en recherche
opé ra tion nelle en France par P. Massé (1944), puis aux États-Unis R. Bellman (1952).
Fon dée sur le prin cipe d’optimalité, sur lequel nous revien drons, elle s’est beau coup
déve lop pée, au cours de ces der nières années.
Sous des condi tions, peu res tric tives dans la pra tique, quant à la forme du cri -
tère d’opti mi sation et à la manière dont le graphe est valué
1
, toute par tie (sous- -
chemin) d’un che min opti mal est, elle- même, opti male. En effet, s’il n’en était pas
ainsi, on pour rait lui subs ti tuer une par tie « meilleure », ce qui amé lio re rait la valeur
de l’ensemble du che min, préa la ble ment sup posé opti mal, d’où une contradiction.
Cette idée fon da men tale (qui est un théo rème lorsque les condi tions ci- dessus sont
rem plies) a été géné ra li sée sous forme d’un prin cipe : toute sous- politique d’une
poli tique opti male est elle- même, opti male, qui est utile mais bien trop géné ral pour
être accepté sans démons tra tion dans chaque cas d’espèce. Mais nos appli ca tions de
PRD se ramènent toutes à la déter mi na tion des che mins opti maux dans les graphes.
Le cas dis cret est par ti cu liè re ment simple et nous en don ne rons un exemple avant
de for mu ler les équa tions géné rales de récur rence qui en faci litent l’appli ca tion.
Exemple. Ima
gi nons la fig. que nous ayons à construire une auto route entre les
villes A et K, ainsi que l’indique la Figure 4.1, les points (sommets) inter mé diaires
pou vant être clas sés en groupes ou (phases) et les arcs du graphe ayant été va lués par
l’indi ca tion des coûts totaux (coûts de réa li sa tion 5 coûts des chaus sées, ouvrages
d’art, etc. 1 coûts sociaux, coûts de “regrets”, etc.).
1. Ce cri tère se tra duit par une fonc tion « de retour » (de revenu) qui doit être « décom po sable »
(condi tion de Mitten) et, par exemple, pour un cri tère « multiplicatif » (pro duit de reve nus élé men
taires), les valuations du graphe doivent être posi tives.