Next: About this document ...
Programmation Linéaire en Nombres Entiers
(PLNE)
- Toutes les variables sont obligées de prendre des valeurs entières
- En général les coefficients
sont aussi entiers
- Et, donc, on peut se limiter à des constantes
entières
- Si, les variables sont aussi constraintes d'être entre
et
, elles n'ont que les deux valeurs possibles
et
et on parle de

Maintenant on peut exprimer des contraintes telles
par la contrainte
parce que des ``solutions'' comme
sont
interdites.
Le PL ordinaire avec les mêmes variables, contraintes et fonction
objective s'appelle le
PL relaxé du PLNE.
Sa solution optimale donne une borne (supérieure pour un problème
de maximisation) sur la solution optimale du PLNE.
(Mais la solution optimale du PLNE peut être très différente
ou même ne pas exister.)
Aspects Théoriques
- Chercher une solution réalisable du PLNE équivaut à chercher un point
dans
le polytope de solutions réalisables avec tous ses coordonnés
entiers
- Si le polytope est long et étroit il n'est pas évident
qu'il contient de tels points
- Décider si un PLNE possède des solutions réalisables
est un exemple d'un problème
NP-complet
une classe de problèmes pour lesquels personne ne sait s'il existe
ou non un algorithme efficace (opérant en temps polynomial)
- Les meilleurs algorithmes connus sont capables de traiter
des programmes avec quelques dizaines de variables
(par comparaison, on peut traiter des PL de plusieurs milliers de variables)
- Méthodes
heuristiques
Des cas où les deux programmes sont équivalents
- Pour quelques types de PL, on sait que (s'il existe une solution
optimale,) il existe une solution optimale entière
- Donc, le PLNE et le PL ont la même valeur optimale
et c'est beaucoup plus vite de résoudre le PL
- Essentiellement des problèmes sur des réseaux
- Des programmes où chaque variable est présente dans
deux contraintes au maximum
- Et avec des coefficients de

Les Méthodes de ``Séparation et Evaluation''
A chaque moment il y a un arbre de problèmes à résoudre et la
solution
optimale est ou la meilleure solution déjà trouvée ou la
meilleure
de celles des problèmes contenus dans l'arbre
1. La Méthode de Dakin pour le PLNE général
- Parcourir l'arbre en profondeur (ce qui a une bonne
chance de produire une solution réalisable assez vite)
- Choisir à chaque itération le problème
possédant
la meilleure solution de son programme relaxé
- Séparer sur une variable dont la valeur (dans
la solution optimale du programme relaxé) est la plus
proche d'un entier
-
est cette valeur (arrondie)
2. La Méthode de Balas pour les PLNE en 0-1
- Considérer les cas où
(à minimiser)
n'a pas de coefficients
négatifs
- Ici séparation consiste à fixer une variable soit à
soit à

- Ce qui permet à simplifier énormément les sous-problèmes
- Si un problème n'a pas de
négatif, on a déjà
une solution réalisable (en fixant toutes les variables restant
à
) et c'est la solution optimale de ce (sous-)problème
- Parcourir l'arbre en largeur
- Plusieurs règles d'élagage permettent de savoir qu'un
problème donné est infaisable ou ne peut donner une solution
meilleure d'une solution déjà trouvée.
Next: About this document ...
Mike ROBSON
2001-11-06