Compléments et autres algorithmes
99
L'idéal est de partir du point
. Un moyen simple d'obtenir un tel point est de faire
subir à notre problème de départ une transformation affine. Posons
matrice carrée à
trois dimensions dans notre exemple (à m+n dimensions dans le cas général), dont la
diagonale principale est composée des , dans l'ordre, les autres éléments étant nuls. Il
est facile de voir que la transformation
donne un vecteur colonne rempli de 1. Evidemment il faut transformer également la
matrice (la ligne dans l'exemple) et la fonction économique, par les formules suivantes :
(A matrice des contraintes, c vecteur des coefficients de la fonction, le PL étant sous
forme standard).
On s'assure sans mal que ce nouveau PL est équivalent au précédent.
Prenons alors le point de départ
(vecteur colonne rempli de 1). C'est sur ce point de
départ et sur le PL transformé que nous faisons les opérations précédentes. Après calcul
de la projection du gradient sur l'espace des contraintes, la longueur du pas est a priori
donnée par la formule (2). Sauf que si nous répétons cette séquence d'opérations,
transformation affine comprise (pour chaque nouveau point trouvé, on le transforme,
ainsi que le PL), par la formule (3), il est clair que nous nous interdisons que l'un
quelconque des
soit nul. On introduit alors un autre coefficient, , choisi pour aller
vite (en général
), qui réduit un peu la longueur du pas trouvé.
De façon générale, et sur un problème
cette méthode se traduit par les itérations
suivantes (avec une adaptation des notations précédentes):
a)
solution itération
Faire
b)
(projection du gradient
sur l'espace des solutions réalisables)
c)
d)
e)