176
Recherche opérationnelle
Remarque : pendant l'exposé, nous n'avons parlé que de problèmes de minimisation. La
procédure exposée reste valable lorsqu'il s'agit de maximiser sur à condition de :
a) remplacer ''évaluation par défaut'' par ''évaluation par excès''
b) sélectionner à chaque itération le sommet d'évaluation maximale
7.4.3. Quelques remarques sur les procédures de recherche arborescente
7.4.3.1. Avantages de ce type de procédure
On constate en général deux défauts concernant les procédures classiques d'optimisation,
tel l'algorithme du simplexe : elles fournissent la solution optimale, mais sont incapables
en général d'en explorer le voisinage; par ailleurs, elles sont liées à une structure définie
de la fonction économique.
Ces défauts apparaissent moins dans les procédures de recherche arborescentes, qui sont
d'une part aptes à explorer certains voisinages, et qui d'autre part peuvent s'adapter à des
formes de fonction très diverses ; en particulier, ces procédures peuvent prendre en
charge mieux que les autres, plusieurs critères économiques, et non plus un seul : on
cherchera par exemple une solution telle que pour chaque critère la valeur pour cette
solution n'est pas trop éloignée à un seuil donné de la valeur optimale de ce critère sur E.
7.4.3.2. Utilisation des procédures de recherche arborescente
Actuellement ces procédures sont fréquemment utilisées, essentiellement pour des
problèmes de graphes (voyageurs de commerce, tournées, typologie) et également pour
la programmation linéaire en nombres entiers, qui n'a pas été étudiée dans la partie
traitant de la programmation linéaire.
Prenons par exemple le problème très simple suivant, mais très connu en recherche
opérationnelle sous la dénomination du ''problème du sac à dos'' : un randonneur doit
partir et le choix entre objets à placer dans son sac à dos, sachant qu'il ne veut pas
dépasser un poids total maximal P. Il attribue à chaque objet une utilité . Par ailleurs,
chaque objet a un poids . Quels objets notre randonneur doit-il emporter, sachant qu'il
veut maximiser l'utilité totale, somme des utilités des objets emportés?
Recherche opérationnelle
Remarque : pendant l'exposé, nous n'avons parlé que de problèmes de minimisation. La
procédure exposée reste valable lorsqu'il s'agit de maximiser sur à condition de :
a) remplacer ''évaluation par défaut'' par ''évaluation par excès''
b) sélectionner à chaque itération le sommet d'évaluation maximale
7.4.3. Quelques remarques sur les procédures de recherche arborescente
7.4.3.1. Avantages de ce type de procédure
On constate en général deux défauts concernant les procédures classiques d'optimisation,
tel l'algorithme du simplexe : elles fournissent la solution optimale, mais sont incapables
en général d'en explorer le voisinage; par ailleurs, elles sont liées à une structure définie
de la fonction économique.
Ces défauts apparaissent moins dans les procédures de recherche arborescentes, qui sont
d'une part aptes à explorer certains voisinages, et qui d'autre part peuvent s'adapter à des
formes de fonction très diverses ; en particulier, ces procédures peuvent prendre en
charge mieux que les autres, plusieurs critères économiques, et non plus un seul : on
cherchera par exemple une solution telle que pour chaque critère la valeur pour cette
solution n'est pas trop éloignée à un seuil donné de la valeur optimale de ce critère sur E.
7.4.3.2. Utilisation des procédures de recherche arborescente
Actuellement ces procédures sont fréquemment utilisées, essentiellement pour des
problèmes de graphes (voyageurs de commerce, tournées, typologie) et également pour
la programmation linéaire en nombres entiers, qui n'a pas été étudiée dans la partie
traitant de la programmation linéaire.
Prenons par exemple le problème très simple suivant, mais très connu en recherche
opérationnelle sous la dénomination du ''problème du sac à dos'' : un randonneur doit
partir et le choix entre objets à placer dans son sac à dos, sachant qu'il ne veut pas
dépasser un poids total maximal P. Il attribue à chaque objet une utilité . Par ailleurs,
chaque objet a un poids . Quels objets notre randonneur doit-il emporter, sachant qu'il
veut maximiser l'utilité totale, somme des utilités des objets emportés?