96
Recherche opérationnelle
Il est vrai également que d'autres spécialistes se sont ingéniés à construire des problèmes
pour lesquels l'algorithme du simplexe s'est montré particulièrement « poussif » , comme
le problème suivant :
Pour
, on évalue le temps de calcul d'un ordinateur effectuant un million
d'itérations par seconde (ce qui n'est pas mal) à 400 trillions d'années ! Il est vrai que le
problème est très spécifique, ne correspond à aucun exemple économique réel, et est
clairement ad hoc, pour les besoins de la démonstration. Il n'en reste pas moins qu'il
paraît légitime de rechercher si d'autres méthodes que le simplexe ne pourraient pas le
traiter plus rapidement.
Ces méthodes existent maintenant et présentent deux différences de principe essentielles
avec le simplexe :
- elles ne suivent pas le « contour » du polyèdre en passant de sommet en
sommet, mais partent d'un point intérieur à ce polyèdre (une solution réalisable)
en essayant de progresser vers sa frontière en direction de l'optimum
- elles ne visent pas à rencontrer au bout d'un certain nombre d'itérations
l'optimum mais à s'en approcher d'une distance fixée à l'avance, faible,
introduite sous la forme d'un seuil. A ce titre, elles s'apparentent davantage à
des méthodes classiques de convergence pas à pas vers des optima de fonctions
à plusieurs variables, telles qu'on peut les consulter dans des ouvrages généraux
sur l'optimisation (alors que la forme particulière d'un programme linéaire
donne lieu à une méthode de résolution spécifique -en l'occurrence le simplexeet, il faut bien le dire, particulièrement élégante).
On distingue classiquement deux types d'approches pour les nombreuses techniques
relevant de ce chapitre de la R.O., lui-même restant largement de l'ordre de la recherche :
- l'approche projective
- les méthodes de chemin intérieur
En fait, toutes ces méthodes sont assez voisines et d'ailleurs comme on le verra sont
toutes fondées sur l'idée d'un cheminement interne au polyèdre. Comme leur exposé
détaillé devient rapidement technique, nous nous bornerons, dans le cadre de cet ouvrage
de base, à en décrire les grands principes.
Recherche opérationnelle
Il est vrai également que d'autres spécialistes se sont ingéniés à construire des problèmes
pour lesquels l'algorithme du simplexe s'est montré particulièrement « poussif » , comme
le problème suivant :
Pour
, on évalue le temps de calcul d'un ordinateur effectuant un million
d'itérations par seconde (ce qui n'est pas mal) à 400 trillions d'années ! Il est vrai que le
problème est très spécifique, ne correspond à aucun exemple économique réel, et est
clairement ad hoc, pour les besoins de la démonstration. Il n'en reste pas moins qu'il
paraît légitime de rechercher si d'autres méthodes que le simplexe ne pourraient pas le
traiter plus rapidement.
Ces méthodes existent maintenant et présentent deux différences de principe essentielles
avec le simplexe :
- elles ne suivent pas le « contour » du polyèdre en passant de sommet en
sommet, mais partent d'un point intérieur à ce polyèdre (une solution réalisable)
en essayant de progresser vers sa frontière en direction de l'optimum
- elles ne visent pas à rencontrer au bout d'un certain nombre d'itérations
l'optimum mais à s'en approcher d'une distance fixée à l'avance, faible,
introduite sous la forme d'un seuil. A ce titre, elles s'apparentent davantage à
des méthodes classiques de convergence pas à pas vers des optima de fonctions
à plusieurs variables, telles qu'on peut les consulter dans des ouvrages généraux
sur l'optimisation (alors que la forme particulière d'un programme linéaire
donne lieu à une méthode de résolution spécifique -en l'occurrence le simplexeet, il faut bien le dire, particulièrement élégante).
On distingue classiquement deux types d'approches pour les nombreuses techniques
relevant de ce chapitre de la R.O., lui-même restant largement de l'ordre de la recherche :
- l'approche projective
- les méthodes de chemin intérieur
En fait, toutes ces méthodes sont assez voisines et d'ailleurs comme on le verra sont
toutes fondées sur l'idée d'un cheminement interne au polyèdre. Comme leur exposé
détaillé devient rapidement technique, nous nous bornerons, dans le cadre de cet ouvrage
de base, à en décrire les grands principes.