104
Recherche opérationnelle
définit une variable
pour chaque investissement i, avec
si on ne fait pas
l'investissement et
si on le fait. Répondre à la question, c'est alors résoudre le PL
suivant :
i
i
n
i
x
v
Max
1
=
B
B
x i
i
n
i 1
=
mais où les variables sont astreintes à prendre deux valeurs et deux valeurs seulement, 0
ou 1. C'est un cas particulier des programmes linéaires en nombres entiers, dit « à
variables bivalentes ».
Le problème général des PL en variables entières est qu'il faut se garder de l'intuition :
résoudre le PL en variables réelles et prendre la solution « arrondie » aux entiers
inférieurs peut non seulement conduire à une solution non optimale, mais aussi à une
solution non réalisable !
Si bien que là aussi de nombreuses recherches se sont développées sur ce type de
programme linéaire, qui s'est révélé particulièrement rebel à l’algorithmique.
Sans entrer dans la description de ces méthodes, on peut simplement dire ici qu'elles se
classent en deux catégories : les méthodes dites de troncature, où l'on introduit des
contraintes supplémentaires qui, dans l'espace des solutions réalisables, définissent des
hyperplans tels que tous les points réalisables entiers du domaine sont dans un seul des
demi-espaces délimités par ces hyperplans. On résout alors une série de PL « emboîtés »
en variables réelles, ajoutant à chaque fois une de ces troncatures, jusqu'à trouver un
optimum entier.
Un autre type de méthode consiste à utiliser des procédures d'optimisation arborescentes,
telles qu'elles sont définies dans la partie suivante.
D'autres méthodes mixent les deux approches. Comme on n'a pas encore trouvé pour ce
problème de méthodes performantes (au sens où l'on est jamais sûr, pour un cas donné,
de la convergence en un temps informatique raisonnable) on peut également utiliser des
heuristiques, telles que les algorithmes génétiques, eux aussi évoqués plus loin.
Goal programming
Ce terme vient du fait que les finalités sur lesquelles repose le problème que l'on veut
traiter, et qui jusqu'ici étaient résumées par la fonction économique, peuvent être
multiples, plus ou moins contradictoires et floues (on veut par exemple maximiser le
surplus de l'entreprise tout en diminuant si possible la pollution de l'environnement). On
peut alors introduire des seuils à atteindre pour certains critères et optimiser l'un d'entre
eux, ou encore introduire les critères avec des marges autour de « buts » à atteindre. En
Recherche opérationnelle
définit une variable
pour chaque investissement i, avec
si on ne fait pas
l'investissement et
si on le fait. Répondre à la question, c'est alors résoudre le PL
suivant :
i
i
n
i
x
v
Max
1
=
B
B
x i
i
n
i 1
=
mais où les variables sont astreintes à prendre deux valeurs et deux valeurs seulement, 0
ou 1. C'est un cas particulier des programmes linéaires en nombres entiers, dit « à
variables bivalentes ».
Le problème général des PL en variables entières est qu'il faut se garder de l'intuition :
résoudre le PL en variables réelles et prendre la solution « arrondie » aux entiers
inférieurs peut non seulement conduire à une solution non optimale, mais aussi à une
solution non réalisable !
Si bien que là aussi de nombreuses recherches se sont développées sur ce type de
programme linéaire, qui s'est révélé particulièrement rebel à l’algorithmique.
Sans entrer dans la description de ces méthodes, on peut simplement dire ici qu'elles se
classent en deux catégories : les méthodes dites de troncature, où l'on introduit des
contraintes supplémentaires qui, dans l'espace des solutions réalisables, définissent des
hyperplans tels que tous les points réalisables entiers du domaine sont dans un seul des
demi-espaces délimités par ces hyperplans. On résout alors une série de PL « emboîtés »
en variables réelles, ajoutant à chaque fois une de ces troncatures, jusqu'à trouver un
optimum entier.
Un autre type de méthode consiste à utiliser des procédures d'optimisation arborescentes,
telles qu'elles sont définies dans la partie suivante.
D'autres méthodes mixent les deux approches. Comme on n'a pas encore trouvé pour ce
problème de méthodes performantes (au sens où l'on est jamais sûr, pour un cas donné,
de la convergence en un temps informatique raisonnable) on peut également utiliser des
heuristiques, telles que les algorithmes génétiques, eux aussi évoqués plus loin.
Goal programming
Ce terme vient du fait que les finalités sur lesquelles repose le problème que l'on veut
traiter, et qui jusqu'ici étaient résumées par la fonction économique, peuvent être
multiples, plus ou moins contradictoires et floues (on veut par exemple maximiser le
surplus de l'entreprise tout en diminuant si possible la pollution de l'environnement). On
peut alors introduire des seuils à atteindre pour certains critères et optimiser l'un d'entre
eux, ou encore introduire les critères avec des marges autour de « buts » à atteindre. En