172
Recherche opérationnelle
Le principe d'une procédure arborescente consiste à restreindre le problème posé à
l'examen, non de mais d'une suite
de sous-ensembles de , en profitant
à chaque fois de l'information disponible pour chacun de ces sous-ensembles.
Pour construire cette suite d'ensembles, on utilise deux grands principes :
- un principe de séparation :
lorsque l'on examine un sous-ensemble
, on doit disposer d'une méthode
permettant de spécifier et d'examiner ensuite des sous-ensembles de
. On
sépare
en plusieurs sous-ensembles qui sont inclus dans la suite
- un principe d'évaluation : il faut être capable de calculer sur chaque sousensemble
une borne inférieure de la fonction .
Grâce au principe de séparation on peut, comme on l'a fait pour l'exemple choisi,
associer à la suite
une arborescence telle que chaque sommet de cette
arborescence représente un sous-ensemble
La procédure consiste à explorer cette arborescence en partant de
et en
respectant certaines règles permettant de trouver la solution optimale.
L'intérêt d'une telle procédure porte sur la faculté que l'on a, à une étape du calcul,
d'exclure de la recherche de l'optimum certains sous-ensembles.
En effet, lorsque l'on considère un sommet de l'arborescence, il se peut que :
a) le sous-ensemble correspondant à ce sommet soit vide, auquel cas on n'aura pas à
séparer ce sommet.
b) on puisse résoudre le problème posé sur le sous-ensemble
correspondant au
sommet; c'est-à-dire que l'on trouve l'élément
de
tel que :
q
q
E
x
x
f
x
f
)
(
)
(
alors, le sommet est terminal non vide et l'on dispose de l'évaluation
qui est le
minimum de sur . On ne le séparera pas dans la suite.
c) un sommet ne soit ni terminal vide ni terminal non vide, mais soit affecté d'une
évaluation par défaut supérieure à l'évaluation d'un sommet terminal non vide; on est
alors sûr que l'optimum ne peut se trouver dans le sous-ensemble correspondant à ce
sommet et on peut l'exclure de la recherche.
Cela dit, les différentes procédures diffèrent entre elles essentiellement par les règles
utilisées pour choisir à chaque étape le sommet que l'on va séparer.
À ce titre, nous citerons deux grands types de procédures.
- les PSES (Procédures de Séparation et d'Evaluations Séquentielles) où le choix
du sommet à séparer se fait indépendamment de la fonction d'évaluation, mais
est intrinsèquement lié au principe de séparation : un ordre transverse étant
donné (cf. le paragraphe précédent) pour ranger les sommets de l'arborescence
Recherche opérationnelle
Le principe d'une procédure arborescente consiste à restreindre le problème posé à
l'examen, non de mais d'une suite
de sous-ensembles de , en profitant
à chaque fois de l'information disponible pour chacun de ces sous-ensembles.
Pour construire cette suite d'ensembles, on utilise deux grands principes :
- un principe de séparation :
lorsque l'on examine un sous-ensemble
, on doit disposer d'une méthode
permettant de spécifier et d'examiner ensuite des sous-ensembles de
. On
sépare
en plusieurs sous-ensembles qui sont inclus dans la suite
- un principe d'évaluation : il faut être capable de calculer sur chaque sousensemble
une borne inférieure de la fonction .
Grâce au principe de séparation on peut, comme on l'a fait pour l'exemple choisi,
associer à la suite
une arborescence telle que chaque sommet de cette
arborescence représente un sous-ensemble
La procédure consiste à explorer cette arborescence en partant de
et en
respectant certaines règles permettant de trouver la solution optimale.
L'intérêt d'une telle procédure porte sur la faculté que l'on a, à une étape du calcul,
d'exclure de la recherche de l'optimum certains sous-ensembles.
En effet, lorsque l'on considère un sommet de l'arborescence, il se peut que :
a) le sous-ensemble correspondant à ce sommet soit vide, auquel cas on n'aura pas à
séparer ce sommet.
b) on puisse résoudre le problème posé sur le sous-ensemble
correspondant au
sommet; c'est-à-dire que l'on trouve l'élément
de
tel que :
q
q
E
x
x
f
x
f
)
(
)
(
alors, le sommet est terminal non vide et l'on dispose de l'évaluation
qui est le
minimum de sur . On ne le séparera pas dans la suite.
c) un sommet ne soit ni terminal vide ni terminal non vide, mais soit affecté d'une
évaluation par défaut supérieure à l'évaluation d'un sommet terminal non vide; on est
alors sûr que l'optimum ne peut se trouver dans le sous-ensemble correspondant à ce
sommet et on peut l'exclure de la recherche.
Cela dit, les différentes procédures diffèrent entre elles essentiellement par les règles
utilisées pour choisir à chaque étape le sommet que l'on va séparer.
À ce titre, nous citerons deux grands types de procédures.
- les PSES (Procédures de Séparation et d'Evaluations Séquentielles) où le choix
du sommet à séparer se fait indépendamment de la fonction d'évaluation, mais
est intrinsèquement lié au principe de séparation : un ordre transverse étant
donné (cf. le paragraphe précédent) pour ranger les sommets de l'arborescence