Programmation Linéaire en Nombres Entiers
(PLNE)

Maintenant on peut exprimer des contraintes telles x1 ³ 1 ou x2 ³ 1
par la contrainte x1+x2 ³ 1 parce que des ``solutions'' comme x1=x2=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




File translated from TEX by TTH, version 3.05.
On 19 Nov 2002, 09:16.