166
Recherche opérationnelle
Attention : l'évaluation par défaut correspondant à cette matrice est toujours 52; elle
correspond à l'exclusion de
des circuits hamiltoniens et prend en compte le regret
calculé précédemment.
Les nouveaux regrets de cette matrice sont :
0
=
2
=
0
=
2
=
3
=
DB
CB
BD
BC
AD
0
=
0
=
4
=
0
=
ED
EB
EA
DE
On sélectionne l'arc
pour partitionner
en deux sous-ensembles, le sous-ensemble
des circuits hamiltoniens qui ne contiennent ni
ni
et l'ensemble
des circuits
hamiltoniens qui ne contiennent pas
, mais contiennent
.
Pour
l'évaluation par défaut est
. Pour
la nouvelle matrice est
(suppression de la ligne E et de la colonne A).
A
B
C D E
A +
3
5
0
+
B 7
+
0
0
0
C 9
0
+
2
+
D 4
0
2
+
0
E 0
0
+
0
+
Matrice 7
48
52
H
H1
H2
AE
AE
H3
H4
EA
EA
52