@Entry[1]

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

Une classe de méthodes

``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

La Méthode de Dakin pour le PLNE général

La Méthode de Balas

Pour les PLNE en 0-1

Un exemple

Minimiser z=3x1+5x2+6x3+9x4+10x5+10x6 avec les contraintes
-2x1+6x2-3x3+4x4+x5-2x6    2
-5x1-3x2+x3+3x4-2x5+x6    -2
5x1-x2+4x3-2x4+2x5-x6    3




File translated from TEX by TTH, version 3.05.
On 16 Nov 2009, 16:53.