100
Recherche opérationnelle
On s'arrête lorsqu'un critère de convergence est respecté. Il peut être de plusieurs types.
Classiquement, si
est la valeur de la fonction économique à l'itération k, on peut
s'arrêter lorsque
étant un seuil prédéfini faible (
5 par exemple).
D'autres critères peuvent être utilisés comme la longueur du gradient lui même. Un
critère plus sophistiqué et plus sûr utilise le dual du PL. En effet, on peut, parallèlement
à la séquence d'itérations décrites ci-dessus et effectuées sur le primal, traiter le dual de
la même façon. On sait que lorsque l'on a deux solutions réalisables, l'une dans le primal
et l'autre dans le dual, on a toujours (cf. chapitre 3) :
On s'arrête alors lorsque :
Quant au choix du point de départ, il n'est pas toujours évident. Il doit en effet
correspondre à une solution réalisable; évidemment la situation idéale est celle où le
point
satisfait aux contraintes. Mais, comme on le sait, les PL n'ont pas toujours
le bon goût de se présenter comme cela. Des procédures existent, qui dépassent le cadre
de cet exposé, mais qui peuvent sensiblement affecter la performance de ce type de
méthode.
Sur l'exemple choisi, une telle procédure fournit l'optimum
en sept
itérations avec une précision de
. Le simplexe de son côté donne l'optimum exact en
une itération seulement. Cela dit, il est clair que ces algorithmes de point intérieur se
justifient sur des PL plus « gros » et /ou plus « tordus ».
Remarque : il s'agit d'une procédure particulière. De nombreuses variantes existent.
D'ailleurs, l'algorithme initiateur de ce courant, celui de Karmarkar, ne se présentait pas
tout à fait de la même façon. Il proposait une transformation initiale du PL de telle façon
qu'aux contraintes classiques s'ajoute
(ce qui est toujours possible si on calcule
les bornes supérieures des et si l'on pose
= où M est la somme de ces bornes).
Ensuite la transformation projective utilisée était un peu plus complexe que celle
proposée ci-dessus. Enfin, Karmarkar exploitait le fait que le point trouvé à chaque
itération pouvait être considéré comme le centre d'une sphère inscrite dans le simplexe
dans
, c'est-à-dire l'espace défini par
. Le point suivant était défini alors
par l'intersection de la projection du gradient avec cette sphère.
Peu importe : le but de cet exposé n'est pas de développer toutes ces méthodes mais d'en
faire comprendre la logique générale qui, comme on le voit, est qualitativement
différente de celle qui préside à l'algorithme du simplexe.
Recherche opérationnelle
On s'arrête lorsqu'un critère de convergence est respecté. Il peut être de plusieurs types.
Classiquement, si
est la valeur de la fonction économique à l'itération k, on peut
s'arrêter lorsque
étant un seuil prédéfini faible (
5 par exemple).
D'autres critères peuvent être utilisés comme la longueur du gradient lui même. Un
critère plus sophistiqué et plus sûr utilise le dual du PL. En effet, on peut, parallèlement
à la séquence d'itérations décrites ci-dessus et effectuées sur le primal, traiter le dual de
la même façon. On sait que lorsque l'on a deux solutions réalisables, l'une dans le primal
et l'autre dans le dual, on a toujours (cf. chapitre 3) :
On s'arrête alors lorsque :
Quant au choix du point de départ, il n'est pas toujours évident. Il doit en effet
correspondre à une solution réalisable; évidemment la situation idéale est celle où le
point
satisfait aux contraintes. Mais, comme on le sait, les PL n'ont pas toujours
le bon goût de se présenter comme cela. Des procédures existent, qui dépassent le cadre
de cet exposé, mais qui peuvent sensiblement affecter la performance de ce type de
méthode.
Sur l'exemple choisi, une telle procédure fournit l'optimum
en sept
itérations avec une précision de
. Le simplexe de son côté donne l'optimum exact en
une itération seulement. Cela dit, il est clair que ces algorithmes de point intérieur se
justifient sur des PL plus « gros » et /ou plus « tordus ».
Remarque : il s'agit d'une procédure particulière. De nombreuses variantes existent.
D'ailleurs, l'algorithme initiateur de ce courant, celui de Karmarkar, ne se présentait pas
tout à fait de la même façon. Il proposait une transformation initiale du PL de telle façon
qu'aux contraintes classiques s'ajoute
(ce qui est toujours possible si on calcule
les bornes supérieures des et si l'on pose
= où M est la somme de ces bornes).
Ensuite la transformation projective utilisée était un peu plus complexe que celle
proposée ci-dessus. Enfin, Karmarkar exploitait le fait que le point trouvé à chaque
itération pouvait être considéré comme le centre d'une sphère inscrite dans le simplexe
dans
, c'est-à-dire l'espace défini par
. Le point suivant était défini alors
par l'intersection de la projection du gradient avec cette sphère.
Peu importe : le but de cet exposé n'est pas de développer toutes ces méthodes mais d'en
faire comprendre la logique générale qui, comme on le voit, est qualitativement
différente de celle qui préside à l'algorithme du simplexe.