Compléments et autres algorithmes
103
une impasse au niveau des calculs). L'arrêt est donné lorsque l'écart entre fonction
primale et fonction duale est faible (ici ce test est particulièrement aisé à manipuler parce
que l'on démontre aisément que cet écart est égal à
.
Là aussi il s'agit de principes généraux, mobilisés dans de nombreuses variantes.
Pour finir sur ces méthodes de point intérieur, la question que l'on est en droit de se
poser est : sont-elles réellement plus efficaces que l'algorithme du simplexe ? La réponse
est en fait ambiguë; on sent bien qu'il n'y a pas de résultats généraux qui permettraient de
statuer sur la supériorité d'une méthode dans tous les cas, et que cela doit dépendre de la
taille et de la forme des PL. Si bien que l'on ne peut faire en la matière qu'œuvre
empirique, c'est-à-dire tester les deux types de méthode sur de nombreux programmes.
Les expériences qui ont été menées jusqu'ici conduisent à des conclusions variables :
même avec des programmes de grande taille l'algorithme du simplexe peut être meilleur
en temps de calcul qu'une méthode de point intérieur. Finalement, la méthode non
polynomiale (alors que Karmarkar, par exemple, a montré que son algorithme
convergeait en un temps borné par une fonction en de la taille n du PL - on précise ces
notions plus loin) se révèle particulièrement efficace ! Attendons les résultats des
recherches en cours pour y voir plus clair...
5.2. PROLONGEMENTS
Il existe de nombreux prolongements de la programmation linéaire, au sens où l'on a
toujours affaire à l'optimisation d'une fonctionnelle linéaire, les variables étant
elles-mêmes soumises à des contraintes linéaires, mais où l'on ajoute des spécifications
qui peuvent notoirement compliquer la résolution du problème.
Programmes linéaires en variables entières
Une de ces complications, et non la moindre, est celle où l'on garde la forme générale du
PL, telle qu'on l'a introduite en début de cette partie, mais où l'on astreint les variables à
prendre des valeurs entières. Cette spécification se présente dans de nombreux cas
concrets. Prenons notamment le programme de production, exemple phare de la
programmation linéaire, mais où les quantités de produit sont nécessairement entières ;
si pour un constructeur aéronautique, à la production nécessairement limitée
quantitativement, on trouve par PL une production de 12, 57 avions d'un type donné par
an, on peut penser que la réponse n'est pas entièrement satisfaisante (la même
problématique se pose différemment pour un constructeur automobile dont la production
annuelle se chiffre en dizaines de milliers d'unités, ce qui permet sans état d'âme de
prendre les arrondis de la solution réelle trouvée en faisant abstraction de la contrainte
d'intégrité sur les variables).
L'autre exemple typique est celui des choix d'investissements : si l'on prend une
entreprise qui est confrontée à n investissements possibles, chacun étant caractérisé par
une performance économique (valeur actuelle, par exemple), et sachant que le budget
d'investissement est limité par une quantité B la question est : quels investissements
choisir ? Il est facile de voir que ce problème peut se mettre sous la forme suivante : on
103
une impasse au niveau des calculs). L'arrêt est donné lorsque l'écart entre fonction
primale et fonction duale est faible (ici ce test est particulièrement aisé à manipuler parce
que l'on démontre aisément que cet écart est égal à
.
Là aussi il s'agit de principes généraux, mobilisés dans de nombreuses variantes.
Pour finir sur ces méthodes de point intérieur, la question que l'on est en droit de se
poser est : sont-elles réellement plus efficaces que l'algorithme du simplexe ? La réponse
est en fait ambiguë; on sent bien qu'il n'y a pas de résultats généraux qui permettraient de
statuer sur la supériorité d'une méthode dans tous les cas, et que cela doit dépendre de la
taille et de la forme des PL. Si bien que l'on ne peut faire en la matière qu'œuvre
empirique, c'est-à-dire tester les deux types de méthode sur de nombreux programmes.
Les expériences qui ont été menées jusqu'ici conduisent à des conclusions variables :
même avec des programmes de grande taille l'algorithme du simplexe peut être meilleur
en temps de calcul qu'une méthode de point intérieur. Finalement, la méthode non
polynomiale (alors que Karmarkar, par exemple, a montré que son algorithme
convergeait en un temps borné par une fonction en de la taille n du PL - on précise ces
notions plus loin) se révèle particulièrement efficace ! Attendons les résultats des
recherches en cours pour y voir plus clair...
5.2. PROLONGEMENTS
Il existe de nombreux prolongements de la programmation linéaire, au sens où l'on a
toujours affaire à l'optimisation d'une fonctionnelle linéaire, les variables étant
elles-mêmes soumises à des contraintes linéaires, mais où l'on ajoute des spécifications
qui peuvent notoirement compliquer la résolution du problème.
Programmes linéaires en variables entières
Une de ces complications, et non la moindre, est celle où l'on garde la forme générale du
PL, telle qu'on l'a introduite en début de cette partie, mais où l'on astreint les variables à
prendre des valeurs entières. Cette spécification se présente dans de nombreux cas
concrets. Prenons notamment le programme de production, exemple phare de la
programmation linéaire, mais où les quantités de produit sont nécessairement entières ;
si pour un constructeur aéronautique, à la production nécessairement limitée
quantitativement, on trouve par PL une production de 12, 57 avions d'un type donné par
an, on peut penser que la réponse n'est pas entièrement satisfaisante (la même
problématique se pose différemment pour un constructeur automobile dont la production
annuelle se chiffre en dizaines de milliers d'unités, ce qui permet sans état d'âme de
prendre les arrondis de la solution réelle trouvée en faisant abstraction de la contrainte
d'intégrité sur les variables).
L'autre exemple typique est celui des choix d'investissements : si l'on prend une
entreprise qui est confrontée à n investissements possibles, chacun étant caractérisé par
une performance économique (valeur actuelle, par exemple), et sachant que le budget
d'investissement est limité par une quantité B la question est : quels investissements
choisir ? Il est facile de voir que ce problème peut se mettre sous la forme suivante : on