next up previous
Next: About this document ...

Programmation Linéaire en Nombres Entiers
(PLNE)

Maintenant on peut exprimer des contraintes telles $\color {blue}x_1\ge 1~ou~x_2\ge 1$
par la contrainte $\color {blue}x_1+x_2\ge
1$ parce que des ``solutions'' comme $\color {blue}x_1=x_2=0.5$ 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

Des cas où les deux programmes sont équivalents

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

2. La Méthode de Balas pour les PLNE en 0-1




next up previous
Next: About this document ...
Mike ROBSON
2001-11-06