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

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

Des problèmes sur les réseaux exprimés en programmes linéaires
Classement

Ici on ne considère qu'un algorithme pour le problème de flot maximum.

L'algorithme de Ford et Fulkerson
Flot maximum

Il suffit de considérer le cas d'une source et un puits

Basé sur l'idée d'une chaîne augmentante: une suite de changements possibles ±α dans une chaîne d'arcs dont le résultat est de transférer quantité α de la source à un autre sommet.

NB: l'augmentation dans une chaîne augmentante peut diminuer le flux dans certains arcs!

Facile de trouver des chaînes augmentantes dans un arbre enraciné à la source

Si on trouve une chaîne augmentante au puits, on peut augmenter le flot actuel (initialisé à 0)
par le minimum des changements possibles sur les arcs de la chaîne

Sinon on a trouvé un flot maximum.

La coupe minimum

Quand l'algorithme ne trouve plus de chaîne augmentante au puits, il a trouvé un ensemble E de sommets autour de la source (ceux pour lesquels il existe une chaîne augmentante) tel que tous les arcs partant de E sont saturés (et tous ceux entrant en E ont flux nul);
dans le flot maximum trouvé le flux total sur ces arcs partant de E est le même que le flot total trouvé;
donc l'algorithme a trouvé une coupe avec cette valeur.
Théorème: cette coupe est minimum parmi les coupes séparant la source et le puits.
Du point de vue de la PL, la recherche d'une coupe minimum est le problème dual du celui du flot maximum!




File translated from TEX by TTH, version 3.05.
On 12 Nov 2007, 15:59.