Pourquoi les problèmes sur les réseaux, sont-ils des programmes linéaires?

La coupe minimum

Pourquoi a-t-on un flot maximum quand il n'existe pas de chaîne augmentante de la source au puits?

Théorème : La coupe minimum est égal au flot maximum.

Encore une méthode

Pourquoi cette méthode marche-t-elle?

Rapport aux méthodes de parcours des solutions de base

L'algorithme de F et F, est-il une méthode de parcours des solutions de base comme le simplexe?

...?

Non. Il peut trouver un flot maximum qui n'est pas une solution de base du PL.

(Considérer un réseau ne possédant que deux chemins source - X de capacités 1 chacun et deux chemins X - puits de capacité 2.)

L'algorithme de Dinic ou Edmonds-Karp
Un algorithme qui trouve le flot maximum
en temps polynomial

A l'itération d, il trouve le flot maximum parmi ceux qui n'utilisent que les chemins de longueur d

Pour l'itération d, il construit un nouveau graphe qui est une copie partielle de celui du réseau mais qui ne contient que les arcs susceptibles d'être inclus dans une chaîne augmentante de longueur d

Il utilise ce graphe pour chercher une chaîne augmentante de longueur d (et termine cette itération s'il n'y en a pas)

Après chaque augmentation, il découpe du graphe tout arc dont le flux vient d'être réduit à nul ou augmenté à sa capacité
(et aussi tout autre arc qui n'est plus utile pour construire des chaînes augmentantes).

Equivaut, grosso modo à Ford et Fulkerson, mais avec recherche en largeur pour une chaîne augmentante au lieu de recherche en profondeur.

Complexité O(m2n) (ou O(mn2) avec des idées de Dinic) pour un graphe de n sommets et m arêtes.

Flot maximum avec coût minimum
L'algorithme de Busacker et Gowen

Itérativement améliorer un flot (initialisé à 0)

A chaque itération construire un graphe R qui dépend du flot actuel f et le graphe du réseau G: si G a un arc (x,y) avec coût c,

On cherche un chemin de la source au puits avec une valeur minimum
s'il existe, on augmente le flot selon la chaîne augmentante correspondant
sinon l'algorithme termine.

Cette recherche est effectuée par un algorithme bien connu de recherche du plus court chemin entre deux sommets (seule complication ici, arcs de ``distance'' négative mais c'est pas grave)

La raison pour laquelle cet algorithme réussit est plus compliquée, en particulier, si on commencait d'un flot aléatoire, il ne serait pas garanti qu'on arrive á un flot optimal;
mais, en commençant au flot nul, oui.

Equivaut à Ford-Fulkerson avec choix de la chaîne augmentante de coût minimum.

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 25 Nov 2008, 10:26.