Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
100
Notons 1 x 0 , x 1 , x 2 , x 3 , x 4 2 1 où x 0 5 A et x 4 5 K 2 une politique de construction.
Son coût est F1 x 0 , x 1 , x 2 , x 3 , x 4 2 5 v 1 x 0 , x 1 2 1 v 1 x 1 , x 2 2 1 v 1 x 2 , x 3 2 1 v 1 x 3 , x 4 2 ,
avec :
x 0 5 5A6, x 1 P5B, C, D6, x 2 P5E, D, G, H6, x 3 P5I, J6, x 4 5 5K6.
Les vraies inconnues du problème sont donc x 1 , x 2 et x 3 . La meilleure politique est
alors celle qui minimise ce coût F.
Figure 4.1
On peut, par exemple, déter mi ner, pour la variable atta chée à chaque phase de la
pro gres sion sur le ter rain, le che min opti mal depuis l’ori gine ; cela revient à déter -
mi ner d’abord, pour les deux pre mières phases, le sous- chemin opti mal entre A et
cha cun des som mets de l’ensemble X 2 5 5E, F, G, H6 ; puis, en ne rete nant que
les sous- chemins opti maux de l’étape pré cé dente, à cal cu ler les sous- chemins opti -
maux entre A et cha cun des som mets de l’ensemble X 3 5 5I, J6, etc. D’où les quatre
tableaux ci- dessous.
x 1 chemin opt
coût
B
AB
8
C
AC
5
D
AD
7
x 2 chemins possibles
chemin opt.
coût
E ABE, ACE, ADE
ACE
10
F
ACF
ACF
9
G ABG, ACG, ADG
ADG
9
H
ACH, ADH
ACH
9
x 3
chemins
possibles
chemin opt. coût
I ACEI, ACFI,
ADGI
ADGI
12
J ACEJ, ACFJ,
ADGJ, ACHJ
ADGJ
11
x 4 5 K chemins
possibles
chemin opt. coût
ADGIK,
ADGJK
ADGIK
17
Le che min de coût mini mal est (A, D, G, I, K), noté en abrégé ADGIK ; son coût est
17 u.m. La meilleure politique est donc de construire les tronçons d’autoroute AD,
DG, GI et IK.