Chapitre 5 Compléments et autres algorithmes
Ce chapitre bref est destiné à indiquer au lecteur un certain nombre de travaux parfois
récents visant soit à proposer d'autres méthodes de résolution que l'algorithme du
simplexe soit à prolonger la programmation linéaire elle-même vers la résolution de
problèmes différents de ceux qui ont été traités jusqu'ici.
5.1. AUTRES METHODES
L'algorithme du simplexe est jugé de façon générale comme performant. Il existe de
nombreux programmes dans les bibliothèques des ordinateurs relevant des principes de
calcul que nous avons développés et capables de traiter des problèmes de grande taille
(plusieurs milliers de contraintes et de variables) dans des temps acceptables.
L'algorithme du simplexe n'est pas exactement programmé comme l'indique
l'organigramme de la page 59. On utilise en général une forme un peu différente, plus
économe en place mémoire, et fondée sur le fait que lorsque l'on passe d'une itération à
l'autre, on change à la marge la matrice
.
Cela dit, ces performances mêmes ne manquent pas d'étonner. En effet, l'algorithme du
simplexe n'a aucune raison a priori de converger rapidement. Souvenons-nous en effet
que l'optimum de la fonction linéaire est trouvé en un sommet du polyèdre convexe
formé par les contraintes (celles de non négativité des variables incluses) et que ce
nombre de sommets est borné par
Ce nombre croît exponentiellement avec m et n,
et même si l'algorithme n'explore pas tous les points correspondants (l'intersection de n
hyperplans pris parmi les contraintes peut n'être pas réalisable), il peut en explorer un
grand nombre. Plus précisément il est facile de voir que le temps de calcul d'une
application du simplexe à un problème donné ne peut être borné par une fonction
polynomiale de la taille de ce problème (représentée par le nombre de bits nécessaire
pour entrer les données dans un ordinateur). On a affaire, et on verra cela plus
précisément à propos de l'application de la théorie des graphes, à un algorithme non
polynomial.
Les spécialistes de programmation linéaire se sont longuement inquiétés de ce fait,
uniquement rassurés par les performances empiriques du simplexe, sans trouver de
parade, jusqu'à ce qu'un article du russe N. Karmarkar, publié en 1984, propose un
algorithme polynomial et provoque une véritable avalanche d'approches nouvelles, se
présentant souvent comme des variantes peu différentes les unes des autres. En fait la
publicité faite à cette contribution ne doit pas cacher que d'autres auteurs avaient déjà
trouvé auparavant de telles méthodes, mais c’est une autre histoire
Ce chapitre bref est destiné à indiquer au lecteur un certain nombre de travaux parfois
récents visant soit à proposer d'autres méthodes de résolution que l'algorithme du
simplexe soit à prolonger la programmation linéaire elle-même vers la résolution de
problèmes différents de ceux qui ont été traités jusqu'ici.
5.1. AUTRES METHODES
L'algorithme du simplexe est jugé de façon générale comme performant. Il existe de
nombreux programmes dans les bibliothèques des ordinateurs relevant des principes de
calcul que nous avons développés et capables de traiter des problèmes de grande taille
(plusieurs milliers de contraintes et de variables) dans des temps acceptables.
L'algorithme du simplexe n'est pas exactement programmé comme l'indique
l'organigramme de la page 59. On utilise en général une forme un peu différente, plus
économe en place mémoire, et fondée sur le fait que lorsque l'on passe d'une itération à
l'autre, on change à la marge la matrice
.
Cela dit, ces performances mêmes ne manquent pas d'étonner. En effet, l'algorithme du
simplexe n'a aucune raison a priori de converger rapidement. Souvenons-nous en effet
que l'optimum de la fonction linéaire est trouvé en un sommet du polyèdre convexe
formé par les contraintes (celles de non négativité des variables incluses) et que ce
nombre de sommets est borné par
Ce nombre croît exponentiellement avec m et n,
et même si l'algorithme n'explore pas tous les points correspondants (l'intersection de n
hyperplans pris parmi les contraintes peut n'être pas réalisable), il peut en explorer un
grand nombre. Plus précisément il est facile de voir que le temps de calcul d'une
application du simplexe à un problème donné ne peut être borné par une fonction
polynomiale de la taille de ce problème (représentée par le nombre de bits nécessaire
pour entrer les données dans un ordinateur). On a affaire, et on verra cela plus
précisément à propos de l'application de la théorie des graphes, à un algorithme non
polynomial.
Les spécialistes de programmation linéaire se sont longuement inquiétés de ce fait,
uniquement rassurés par les performances empiriques du simplexe, sans trouver de
parade, jusqu'à ce qu'un article du russe N. Karmarkar, publié en 1984, propose un
algorithme polynomial et provoque une véritable avalanche d'approches nouvelles, se
présentant souvent comme des variantes peu différentes les unes des autres. En fait la
publicité faite à cette contribution ne doit pas cacher que d'autres auteurs avaient déjà
trouvé auparavant de telles méthodes, mais c’est une autre histoire