160
Recherche opérationnelle
Ces différents ordres ont une certaine importance dans les techniques que nous allons
exposer maintenant et qui constituent une illustration particulièrement intéressante des
arborescences : les procédures de recherche arborescentes.
7.4. LES PROCEDURES DE RECHERCHE ARBORESCENTS
Ces procédures tentent de répondre à la question tout à fait générale : comment trouver
un élément
d'un ensemble tel que, si
est une fonction à valeur réelle définie
pour tout
l'on ait
, soit plus simplement : trouver le
minimum de la fonction sur l'ensemble .
Les mathématiques nous ont fait rencontrer ce problème très souvent; en ce qui concerne
la recherche opérationnelle, on peut même dire qu'elle est complètement dominée par
cette question.
Pour certains problèmes, comme on l'a vu, il existe des procédures d'optimisation
permettant d'obtenir le point
: c'est le cas, par exemple, des programmes linéaires, où
est un polyèdre convexe, et pour lesquels l'algorithme du simplexe permet de trouver
l'optimum en un temps de calcul le plus souvent raisonnable.
Pour d'autres problèmes, il n'existait pas encore, jusqu'à une date récente, de procédure
d'optimisation : l'exploration arborescente leur a apporté une solution. C'est le cas du
problème du voyageur de commerce, que nous allons d'abord étudier sur un exemple,
avant de fournir des généralités sur les procédures de recherche arborescente.
1
7
2
5
8
10
13
a
3
4
6
9
11
12 14