6
Recherche opérationnelle
Prenons deux exemples pour illustrer ce propos.
Dans le problème du voyageur de commerce, ce dernier doit passer dans n villes, sachant
qu'il souhaite visiter chacune d'entre elles une fois et une seule. Il connaît les temps de
transport entre chaque ville et les autres, temps que l'on suppose fixes. Dans quel ordre
doit-il effectuer ses visites de façon à ce que son temps de transport total soit minimal ?
La réponse est a priori facile. La ville de départ importe peu, on s'en rend compte
rapidement. Il se peut de toute façon qu'elle soit fixée. A partir de ce point de départ,
notre voyageur de commerce a n-1 possibilités pour la ville suivante, puis
pour la
deuxième, puis
pour troisième etc. Au total, il y a
solutions à ce problème, soit
On peut alors avoir comme idée d'explorer
systématiquement ces solutions, en calculant à chaque fois la somme des temps de
parcours, donc le temps de parcours total, et retenir, parmi ces
temps totaux le
plus petit. Or le nombre
devient très vite important lorsque n augmente. Pour
six villes, le calcul reste possible, puisque l'on a 120 permutations à explorer et à
chiffrer. Pour
, ce nombre est à peu près égal à 1,2164×10
17
. Si par exemple on
écrit un programme informatique permettant d'évaluer toutes les solutions (et un
programme est facile à écrire) et si l'ordinateur dont on dispose nécessite un
nanoseconde pour chaque solution on explorera l'ensemble des possibilités en 3,8 ans
environ ! C'est dire que les performances des ordinateurs actuels ne libèrent pas de la
nécessité de trouver des méthodes permettant de nous orienter dans la prolifération des
solutions possibles liées à la présence de nombreux problèmes de gestion combinatoire.
Cet exemple est intéressant car le problème posé est tout à fait réaliste (dans les cas
concrets il se complique souvent considérablement ce qui ajoute encore à la complexité
de sa résolution) et renvoie à des questions que se posent de nombreuses entreprises
(tournées de postiers, de camions de coopératives laitières etc.). Des méthodes existent
en effet pour traiter ce problème de façon efficace (même si elles ne sont pas entièrement
satisfaisantes comme on le verra dans cet ouvrage à propos de l'exposé de l'une d'entre
elles).
Le deuxième exemple est issu lui aussi d'un problème tout à fait pratique : un marchand
de journaux se pose la question de la quantité optimale d'exemplaires d'un quotidien qu'il
doit acheter à un distributeur. La demande est variable ; il ne sait pas à l'avance combien
de clients lui achèteront le journal chaque jour ; il connaît évidemment le prix d'achat au
distributeur et le prix de vente, si bien que pour un niveau de vente donné il peut calculer
sans difficultés le bénéfice (ou la perte s'il achète trop de journaux) obtenu. Le problème
est qu'il ne sait pas intégrer dans un calcul unique les différents bénéfices correspondant
aux événements non prévisibles constitués par les niveaux de vente. Le calcul vient alors
à son secours par deux modalités consécutives : il est tout d'abord invité à analyser sur
un certain nombre de jours la chronique des ventes ; si cette analyse est suffisamment
poussée, il peut éventuellement raccorder par un test statistique cette chronique de
ventes à une distribution de probabilités. Ce faisant il a déjà « domestiqué »
considérablement l'incertitude : certes il ne sait pas à l'avance quelle quantité de
journaux il vendra tel ou tel jour, mais il a une information précieuse, à savoir la
probabilité de vendre une quantité donnée (et toutes les probabilités associées aux
diverses quantités possibles). La deuxième étape est alors constituée par une
démonstration, qui aboutit à un résultat qui est loin d'être intuitif : si le phénomène est
Recherche opérationnelle
Prenons deux exemples pour illustrer ce propos.
Dans le problème du voyageur de commerce, ce dernier doit passer dans n villes, sachant
qu'il souhaite visiter chacune d'entre elles une fois et une seule. Il connaît les temps de
transport entre chaque ville et les autres, temps que l'on suppose fixes. Dans quel ordre
doit-il effectuer ses visites de façon à ce que son temps de transport total soit minimal ?
La réponse est a priori facile. La ville de départ importe peu, on s'en rend compte
rapidement. Il se peut de toute façon qu'elle soit fixée. A partir de ce point de départ,
notre voyageur de commerce a n-1 possibilités pour la ville suivante, puis
pour la
deuxième, puis
pour troisième etc. Au total, il y a
solutions à ce problème, soit
On peut alors avoir comme idée d'explorer
systématiquement ces solutions, en calculant à chaque fois la somme des temps de
parcours, donc le temps de parcours total, et retenir, parmi ces
temps totaux le
plus petit. Or le nombre
devient très vite important lorsque n augmente. Pour
six villes, le calcul reste possible, puisque l'on a 120 permutations à explorer et à
chiffrer. Pour
, ce nombre est à peu près égal à 1,2164×10
17
. Si par exemple on
écrit un programme informatique permettant d'évaluer toutes les solutions (et un
programme est facile à écrire) et si l'ordinateur dont on dispose nécessite un
nanoseconde pour chaque solution on explorera l'ensemble des possibilités en 3,8 ans
environ ! C'est dire que les performances des ordinateurs actuels ne libèrent pas de la
nécessité de trouver des méthodes permettant de nous orienter dans la prolifération des
solutions possibles liées à la présence de nombreux problèmes de gestion combinatoire.
Cet exemple est intéressant car le problème posé est tout à fait réaliste (dans les cas
concrets il se complique souvent considérablement ce qui ajoute encore à la complexité
de sa résolution) et renvoie à des questions que se posent de nombreuses entreprises
(tournées de postiers, de camions de coopératives laitières etc.). Des méthodes existent
en effet pour traiter ce problème de façon efficace (même si elles ne sont pas entièrement
satisfaisantes comme on le verra dans cet ouvrage à propos de l'exposé de l'une d'entre
elles).
Le deuxième exemple est issu lui aussi d'un problème tout à fait pratique : un marchand
de journaux se pose la question de la quantité optimale d'exemplaires d'un quotidien qu'il
doit acheter à un distributeur. La demande est variable ; il ne sait pas à l'avance combien
de clients lui achèteront le journal chaque jour ; il connaît évidemment le prix d'achat au
distributeur et le prix de vente, si bien que pour un niveau de vente donné il peut calculer
sans difficultés le bénéfice (ou la perte s'il achète trop de journaux) obtenu. Le problème
est qu'il ne sait pas intégrer dans un calcul unique les différents bénéfices correspondant
aux événements non prévisibles constitués par les niveaux de vente. Le calcul vient alors
à son secours par deux modalités consécutives : il est tout d'abord invité à analyser sur
un certain nombre de jours la chronique des ventes ; si cette analyse est suffisamment
poussée, il peut éventuellement raccorder par un test statistique cette chronique de
ventes à une distribution de probabilités. Ce faisant il a déjà « domestiqué »
considérablement l'incertitude : certes il ne sait pas à l'avance quelle quantité de
journaux il vendra tel ou tel jour, mais il a une information précieuse, à savoir la
probabilité de vendre une quantité donnée (et toutes les probabilités associées aux
diverses quantités possibles). La deuxième étape est alors constituée par une
démonstration, qui aboutit à un résultat qui est loin d'être intuitif : si le phénomène est