Compléments et autres algorithmes
97
5.1.1. Les approches projectives
Ce nom vient du fait que l'on a affaire avec un programme linéaire à l'optimisation d'une
fonction de n variables soumises à m contraintes. Si l'on ne fait pas attention dans un
premier temps à la linéarité de la fonction et des contraintes, une méthode classique
d'optimisation consiste à partir d'une solution réalisable et à l'améliorer en partant dans
une direction appropriée, ce processus étant répété un certain nombre de fois, jusqu'à ce
que l'on estime, grâce à un critère prédéfini, s'être approché avec une précision suffisante
de la solution. Une telle direction est donnée par le gradient de la fonction, qui maximise
la croissance de la fonction (dans un problème de maximisation) pour une petite
variation des variables. (Rappelons que le gradient d'une fonction
est
donné par le vecteur des dérivées premières, si elles existent
. Le
problème est que si l'on part du programme linéaire mis sous forme standard (augmenté
de ses m variables d'écart permettant de convertir les inégalités de départ en égalités), il
est alors facile de voir qu'en suivant cette direction, on sort immédiatement du domaine
des solutions réalisables.
Pour s'en convaincre, prenons un petit exemple. Soit le programme linéaire suivant :
Après addition de la variable d'écart nous obtenons :
Si nous partons du point
il s'agit clairement d'une solution réalisable. Le gradient
de la fonction économique est
et tout point s'écrivant
avec
ne
répond pas à la contrainte.
Ce qui est alors proposé dans l'approche projective est de projeter le vecteur du gradient
sur l'espace des solutions réalisables. Sur le dessin (qui représente le plan passant par
l'axe
et le point
cela consiste à tracer dans
une droite partant de
l'extrémité du gradient
et à calculer l'intersection de cette droite avec le plan de la
contrainte. Le vecteur donne alors la direction dans laquelle se diriger.
97
5.1.1. Les approches projectives
Ce nom vient du fait que l'on a affaire avec un programme linéaire à l'optimisation d'une
fonction de n variables soumises à m contraintes. Si l'on ne fait pas attention dans un
premier temps à la linéarité de la fonction et des contraintes, une méthode classique
d'optimisation consiste à partir d'une solution réalisable et à l'améliorer en partant dans
une direction appropriée, ce processus étant répété un certain nombre de fois, jusqu'à ce
que l'on estime, grâce à un critère prédéfini, s'être approché avec une précision suffisante
de la solution. Une telle direction est donnée par le gradient de la fonction, qui maximise
la croissance de la fonction (dans un problème de maximisation) pour une petite
variation des variables. (Rappelons que le gradient d'une fonction
est
donné par le vecteur des dérivées premières, si elles existent
. Le
problème est que si l'on part du programme linéaire mis sous forme standard (augmenté
de ses m variables d'écart permettant de convertir les inégalités de départ en égalités), il
est alors facile de voir qu'en suivant cette direction, on sort immédiatement du domaine
des solutions réalisables.
Pour s'en convaincre, prenons un petit exemple. Soit le programme linéaire suivant :
Après addition de la variable d'écart nous obtenons :
Si nous partons du point
il s'agit clairement d'une solution réalisable. Le gradient
de la fonction économique est
et tout point s'écrivant
avec
ne
répond pas à la contrainte.
Ce qui est alors proposé dans l'approche projective est de projeter le vecteur du gradient
sur l'espace des solutions réalisables. Sur le dessin (qui représente le plan passant par
l'axe
et le point
cela consiste à tracer dans
une droite partant de
l'extrémité du gradient
et à calculer l'intersection de cette droite avec le plan de la
contrainte. Le vecteur donne alors la direction dans laquelle se diriger.