\include{header}


\begin{slide}{}
\heading{
Pourquoi les problèmes sur les réseaux, sont-ils des programmes linéaires?\\
}
\begin{itemize}
\item Une variable pour le flot dans chaque arête orientée
\item Disponibilités, capacités de transfert, capacités d'absorbtion
sont toutes exprimées par des contraintes linéaires
\item Fonction objective linéaire : flot total arrivant à la destination, coût total, ...
\item Propriété fondamentale d'un réseau : ce qui part doit arriver
\item (et inversément?)
\end{itemize}
\end{slide}




\begin{slide}{}
\heading{
La  coupe minimum\\
}
Pourquoi a-t-on un flot maximum quand il n'existe pas de chaîne augmentante de
la source au puits?

\begin{itemize}
\item Les sommets vers lesquels on peut trouver une chaîne (faire passer un flot)
constituent un ensemble $X$ autour de la source
\item Les autres sommets constituent un ensemble $Y$ autour du puits
\item Chaque arête de $X$ à $Y$ est saturée
\item Chaque arête de $Y$ à $X$ a flot nul
\item  Donc évidemment, le flot de $X$ à $Y$ ne peut pas être incrémenté
et tout le flot de la source au puits doit passer de $X$ à $Y$
\item Les arêtes de $X$ à $Y$ constituent une {\bf coupe} du réseau.
\end{itemize}
Théorème : La coupe minimum est égal au flot maximum.
\end{slide}



\begin{slide}{}
\heading{
Encore une méthode\\
}
\begin{itemize}
\item Construire un flot partiel où chaque sommet sauf la source transmet
au maximum ce qu'il reçoit
\item si possible d'étendre ce flot, faites-le
\item sinon faire reculer ce qui est arrivé à un sommet et ne peut pas
être transmis
\item basé sur l'idée de hauteur : le flot est toujours du haut vers le bas;
pour modifier le flot, il faut incrémenter la hauteur\\
(au minimum des hauteurs des voisins utiles $+1$)
\item au début hauteur nulle sauf pour la source (hauteur = nombre de sommets);
les hauteurs de la source et du puits ne changent pas.
\item complexité $O(n^3)$ (si la recherche du prochain sommet à traiter
est bien gérée). 
\end{itemize}
\end{slide}

\begin{slide}{}
\heading{
Pourquoi cette méthode marche-t-elle?}
\begin{itemize}
\item un petit exemple
\item elle doit trouver un flot (les surplus sont forcément rejetés vers la source; en fait
sans dépasser hauteur de $2\times$ nombre de sommets)
\item ce flot est-il maximum?
\item quand le flot commence à reculer vers la source (première fois une hauteur dépasse 
le nombre de sommets), s'il y avait un chemin faisable pour passer un surplus vers le puits, ce chemin aurait une différence de hauteur entre deux sommets consécutifs
de au moins $2$, ce qui est impossible.
\end{itemize}
\end{slide}

\begin{slide}{}
\heading{
Rapport aux m\'ethodes de parcours des solutions de base
}
L'algorithme de F et F, est-il une m\'ethode 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\'erer un r\'eseau ne poss\'edant que deux chemins source
-- $X$ de capacit\'es $1$ chacun et deux chemins $X$ -- puits
de capacit\'e 2.)

\end{slide}


\begin{slide}{}
\heading{
L'algorithme de Dinic ou Edmonds-Karp\\Un algorithme qui trouve le flot maximum\\
en temps polynomial 
}
A l'it\'eration \colmath{d}, il trouve le flot maximum parmi ceux
qui n'utilisent que les chemins de longueur \colmath{\le d}

Pour l'it\'eration \colmath{d}, il construit un nouveau graphe qui
est une copie partielle de celui du r\'eseau mais qui ne contient
que les arcs susceptibles d'\^etre inclus dans une cha\^{\i}ne
augmentante
de longueur \colmath{d}

Il utilise ce graphe pour chercher une cha\^{\i}ne
augmentante
de longueur \colmath{d} (et termine cette it\'eration s'il
n'y en a pas)

Apr\`es chaque augmentation, il d\'ecoupe du graphe tout arc
dont le flux vient d'\^etre r\'eduit \`a nul ou augment\'e
\`a sa capacit\'e\\
(et aussi tout autre arc qui n'est plus utile pour construire
des cha\^{\i}nes augmentantes).

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

Complexité $O(m^2n)$ (ou $O(mn^2)$ avec des idées de Dinic) pour un graphe
de $n$ sommets et $m$ arêtes.
\end{slide}


\begin{slide}{}
\heading{
Flot maximum avec co\^ut minimum\\
L'algorithme de Busacker et Gowen
}
It\'erativement am\'eliorer un flot (initialis\'e \`a $0$)

A chaque it\'eration construire un graphe \colmath{R} qui d\'epend du
flot actuel \colmath{f} et le graphe du r\'eseau \colmath{G}: si
\colmath{G} a un arc \colmath{(x,y)} avec co\^ut \colmath{c},

\begin{itemize}
\item si \colmath{(x,y)} n'est pas satur\'e, \colmath{R}
a un arc \colmath{(x,y)} valu\'e \`a \colmath{c}
\item si \colmath{(x,y)} a un flux non nul, \colmath{R}
a un arc \colmath{(y,x)} valu\'e \`a \colmath{-c}
\end{itemize}

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

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

La raison pour laquelle cet algorithme r\'eussit est plus
compliqu\'ee,
en particulier, si on commencait d'un flot al\'eatoire,
il ne serait pas garanti qu'on arrive \'a  un flot optimal;\\
mais, en commen\c{c}ant au flot nul, oui.

Equivaut à Ford-Fulkerson avec choix de la chaîne augmentante de
coût minimum.
\end{slide}

\begin{slide}{}
\heading{
La M\'ethode de Balas pour les PLNE en 0-1
}
\begin{itemize}
\item Consid\'erer les cas o\`u \colmath{z} (\`a minimiser)
n'a pas de coefficients
n\'egatifs et les variables sont triées en ordre croissant
de ces coefficients (pas de restriction; tout programme peut être exprimé
de cette façon)
\item Ici s\'eparation consiste \`a fixer une variable soit \`a
\colmath{0}
soit \`a \colmath{1}
\item Ce qui permet \`a simplifier \'enorm\'ement les sous-probl\`emes
\item Si un probl\`eme n'a pas de $b_j$ n\'egatif, on a d\'ej\`a
une solution r\'ealisable (en fixant toutes les variables restant
\`a \colmath{0}) et c'est la solution optimale de ce (sous-)probl\`eme
\item Parcourir l'arbre en profondeur
\item Plusieurs r\`egles d'\'elagage permettent de savoir qu'un
probl\`eme donn\'e est infaisable ou ne peut donner une solution
meilleure d'une solution d\'ej\`a trouv\'ee.
\end{itemize}
\end{slide}
\begin{slide}{}
\heading{
Un exemple}
Minimiser $z=3x_1+5x_2+6x_3+9x_4+10x_5+10x_6$ avec les contraintes\\
$-2x_1+6x_2-3x_3+4x_4+x_5-2x_6~\le~ 2$\\
$-5x_1-3x_2+x_3+3x_4-2x_5+x_6~\le~ -2$\\
$5x_1-x_2+4x_3-2x_4+2x_5-x_6~\le~ 3$\\
\end{slide}

\end{document}














