174
Recherche opérationnelle
2) Principe d'évaluation
pour chaque
on peut calculer une quantité
telle que :
-
-
Règles de sélection
La règle de sélection du sommet à séparer est très simple : on choisit le sommet
d'évaluation par défaut minimale.
Dans ces conditions l'algorithme général d'une PSEP est le suivant :
Algorithme
L'algorithme est itératif : nous désignerons par le numéro d'une itération quelconque,
et par
l'ensemble des sommets candidats à une séparation pour l'itération . Toute
itération se décompose en trois phases :
Phase I Sélection
a)
on sélectionne
b)
on sélectionne le sous-ensemble
avec
tel que
7
c'est la règle annoncée.
on va alors tenter de séparer
:
Phase 2 Séparation
Comme on l'a vu, il peut se produire 3 cas, suivant l'état de l'ensemble
sélectionné.
a) vide; revenir alors à la case sélection en posant
b) est un sommet terminal non vide ; on a
Comme pour tout
d'après la règle de sélection, et que
représente, comme on le verra, l'ensemble des sous-ensembles encore séparables à
l'itération , c'est qu'on a trouvé un minimum de la fonction sur , et ce minimum est
7 Comme précédemment, on convient de confondre sommet de l'arborescence et sous-ensemble
représenté par ce sommet.