Introduction

Ce cours est une tentative de conserver ce qui m'a été enseigné en première année de l'IUP MIAGE de Nice... il n'est pas terminé, peu étoffé et encore désagréable à lire (veuillez excuser les trop nombreuses fautes d'orthographes, les paragraphes et les shémas manquant) ... Cependant, il a le mérite d'être écrit par un étudiant et d'être a la disposition de tous.

Si vous trouvez des erreurs ou fautes et que vous avez du temps à lui consacrer, vous serez le (ou la) bienvenue c'est ici...

Tout d'abord, un peu de vocabulaire : Recherche Opérationnelle, Mathématiques de la décision, Techniques quantitatives de la gestion, programation dynamique... Voici quelque uns des termes liés a ce dont traite ce cours, je choisi d'utiliser ''recherche opérationelle'' parcequ'il me plait...

Si on vous demande ce que ça veut dire, Voici une réponse simple : La recherche opérationnelle est l'application de méthodes scientifiques dans la résolution de problèmes courants...

Quelques exemples :

Les problèmes d'affectation

L'exemple le plus courant est le problème de l'affectation de taches a des ouvriers. Chaque ouvrier a des aptitudes et des spécialités différentes, on recherche une répartition des taches qui soit optimale...

Si on se base sur un problème de petite taille, ont peut envisager de créer une liste exhaustive de toutes les combinaisons possibles (pour 3 ouvriers et 3 taches, ont obtient 3! c'est a dire 6 combinaisons possibles...

A une plus grande échelle, l'énumération des différentes combinaisons est impossible (Pour 25!, un ordinateur qui énumèrerait un millions de combinaisons par seconde mettrait approximativement 25 milliards d'années...)

c'est pour ces cas de figure que la recherche opérationnelle propose des méthodes qui permettent de construire une solution optimale, ce qui permet d'éviter l'énumération.

Les problèmes d'ordonnancement

L'exemple qui me vient a l'esprit est celui d'une construction, Pour mener a bien un chantier chacun peut concevoir qu'il faut établir un ordre impératif pour les différentes tâche à accomplir

Imaginez que vous faites construire la maison de vos rêves, vous comprendrez facilement que la maçonnerie et la charpente devront être terminées pour que le peintre commence sont travail...

Les bricoleurs savent qu'il n'et pas toujours facile d'organiser les petits travaux dans lesquels ils se lancent, La recherche opérationnelle propose des méthodes systématiques qui permettent d'obtenir des résultats optimaux... Bien entendu, l'intérêt de ces méthodes est qu'elle s'appliquent avec autant d'efficacité sur les grands projets...

Les problèmes de flot

Les exemples courants sont l'écoulement de liquides dans des conduites, la capacité d'un réseaux de distribution électrique, ou encore le débit d'un réseau de voix routières ou ferroviaires...

Quelques bouquins de référence

Précis de recherche Opérationnelle : R. Faure, éditions DUNOD (1 volume de 3 chapitres)
Méthodes & modèles de la RO : A Kaufman, éditions DUNOD (3 volumes de 800 pages)
Exercices de RO : ROSEAUX, (c'est une équipe de profs), éditions MASSON (3 volumes)

La théorie des graphes

Cette partie présente de façon minimaliste la théorie des graphes... Bouquin de référence : Graphes & Hypergraphes...

On distingue 2 familles de graphe :

- Les graphes orientés
- Les graphes non orientés

Graphe, graphe valué, boucle :

	Un graphe est ensemble de noeuds reliés par des segments.
	On peut donner une valeur pour chaque segment, on parle alors de graphe valué un segment qui relie un noeud a lui même est une boucle

Graphe simple (non orienté) :

Pour les graphes non orientés, on parle d'arrêtes & de chaînes...

c'est un graphe simple (non orienté) AB est une arrête ABC est une chaîne

Graphe orienté :

Pour les graphes orientés, on parle d'arcs, de chemins, ou de circuits

c'est un graphe orienté AB est un arc ABCD est un chemin ABCA est un circuit

Graphe & composante Connexe

Soit X un noeud du graphe G. La composante connexe de X dans un graphe G est l'ensemble des sommets pouvant être atteints à partir de X dans G.
Si X = G, le graphe est connexe...

Graphe fortement connexe...

Si G est un graphe orienté, il sera dit fortement connexe si pour tout couple de sommet (X,Y), il existe un chemin de X à Y.

Les algorithme de recherche de plus court chemin

Algorithme de Ford...

Son but est la recherche du plus court chemin entre 2 noeuds d'un graphe.

Quelques conventions

On note X₀, X₁, ... ,X_n les différents noeuds
Pour chacun d'entre eux, on crée une variable λ : λ₀, λ₁, ... ,λ_n
X_j désigne l'extrémité de tout arc ayant pour origine X_i
(X_i,X_j) désigne la valuation de l'arc X_i,X_j

Déroulement de l'algorithme :

Initialisation :

λ₀=0;
λ_i=+ ∞ quelquesoit i ≠ 0
On initialise λ₀ à la valeur 0 puis et on donne à tout les autres λ la valeur la plus grande possible...

Itérations :

Pour i de 0 à n :

Pour chaque X_j    (j désigne l'extrémité de tout les arcs ayant X_i pour origine...) :

Si λ_i + v(X_i,X_j) < λ_j, alors

λ_j <= λ_i + v(X_i,X_j)     (λ_j prend la valeur de λ_i + v(X_i,X_j)...)

Sinon

ne rien faire...

Condition d'arrêt :

On arêtte le déroulement si pour i de 0 à n, la relation (λ_i + v(X_i,X_j) < λ_j) n'a jamais été vraie...

quelques explications

l'idée utilisé est de parcourir tous les noeuds du graphe [X₀, X₁, ... ,X_n].
Pour chacun de ces noeuds, ou va parcourir les arcs qui en sont issus pour arriver au noeud succésseur (les noeuds X_j).
On associe à ces X_j une valutation (λ₀, λ₁, ... ,λ_n) en aditionant la valeur de l'arc et la valuation du noeud dont l'arc est issu [λ_j <= λ_i + v(X_i,X_j)].
On recomence alors le parcours de tous les noeuds (X₀, X₁, ... ,X_n)
L'algorithme s'arette si on a parcouru tous les noeuds sans faire de modification dans les λ_n

Présentation du résultat :

La valeur du plus court chemin entre X₁ et X_nest représentée par le dernier X_n calculé.
Pour retrouver ce chemin, on va choisir les arcs en suivant la règle suivante :
- on calcule la différence λ_j - λ_i et on la compare à la valuation de l'arc.
- Le plus court chemin est constitué par les arcs pour lesquels v(X_i,X_j) = λ_j - λ_i

Essai sur un graphe de taille modeste...

Comment on retrouve le résultat ??

λ₅ - λ₄ = 7 - 6 = 1 => on choisis l'arc X₄, X₅...
λ₄ - λ₂ = 6 - 3 = 3 => on choisis l'arc X₂, X₄...
λ₂ - λ₃ = 3 - 1 = 2 => on choisis l'arc X₃, X₂...
λ₃ - λ₁ = 1 - 0 = 1 => on choisis l'arc X₀, X₃...
et c'est terminé : Le chemin le plus court est donc X₀, X₃, X₂, X₄, X₅, sa valeur est 7.

Démonstration de la validité de cet algo...

Pour la démo, il va falloir attendre que j'ai un peu plus de temps...

Avantages & inconvénients ...

- l'algo de Ford est sensible à la numérotation (CF fonction ordinale)
- Il ne supporte pas les graphes comportant des circuits

Algorithme de Dantzig : En cours de frappe...

Voici l'algorithme :

Initialisations

  μ0 = 0;  A0 = {X0};    k = 0;

Itérations

  Poser Bk = Ensemble des sommets de Ak ayant au moins 1 successeur hors de Ak

  Pour chaque Xi ∈  Bk, parmi ses successeurs 

Algorithme de Bellman

Cet algo est simple mais il pose 2 restrictions :
- Le graphe ne doit pas comporter de circuit.
- La numérotation doit suivre une fonction ordinale : quelquesoit X_i, X_j On a i < j

Comment construire une numérotation conforme ?

On dispose d'un algorithme :

Initialisations

k= 0;

Itérations

- Attribuer le numéro k+1 à un sommet sans prédécesseur ou a défaut a un sommet dont tous les prédécesseurs ont étés numérotés...
- Incrémenter k et recommencer tant que tous les sommet ne sont pas numérotés.

Application :

Si on applique cet algo à notre graphe, on obtient la numérotation suivante :

Voici l'algorithme :

Comme l'algo de Ford, on se propose d'associer des valeurs λ_k aux sommets X_k, avec k allant de 0 à n...

Initialisations

Poser λ₀ = 0 et k = 1;

Itérations

Pour k de 0 à n, poser :

λ_k = Min_j {λ_j + v(X_j,X_k)}
(j représente tous les sommets prédécesseurs du sommet courant (X_k))

Application sur notre exemple :

λ₀ = 0

calcul de λ₁ : le sommet X₁ n'a qu'un prédécesseur :

λ₁ = λ₀ + v(X₀,X₁) = 0 + 2 = 2

calcul de λ₂ : le sommet X₂ n'a qu'un prédécesseur :

λ₂ = λ₀ + v(X₀,X₂) = 0 + 1 = 1

calcul de λ₃ : le sommet X₃ a 3 prédécesseurs :

λ₃ = λ₁ + v(X₁,X₃) = 1 + 3 = 4
λ₃ = λ₀ + v(X₀,X₃) = 0 + 6 = 6
λ₃ = λ₂ + v(X₂,X₃) = 1 + 2 = 3      => On choisit la valeur minimum : λ₃ = 3

calcul de λ₄ : le sommet X₄ a 3 prédécesseurs :

λ₄ = λ₁ + v(X₁,X₄) = 2 + 7 = 9
λ₄ = λ₃ + v(X₃,X₄) = 3 + 6 = 6      => On choisit la valeur minimum : λ₄ = 6
λ₄ = λ₂ + v(X₂,X₄) = 1 + 6 = 7

calcul de λ₅ : le sommet X₅ a 2 prédécesseurs :

λ₅ = λ₃ + v(X₃,X₅) = 3 + 5 = 8
λ₅ = λ₄ + v(X₄,X₅) = 6 + 1 = 7      => On choisit la valeur minimum : λ₅ = 7

Comment trouver le chemin minimal :

- La valeur du chemin minimal est la dernière valeur calculée
- Pour retrouver le chemin, on remonte dans la trace de l'algorithme : pour notre exemple, λ₅ est issu de λ₄, λ₄ est issu de λ₃, λ₃ est issu de λ₂ qui est lui même issu de λ₂.
Le chemin minimal est donc : X₀, X₂, X₃, X₄, X₅ pour une valeur de 7.

Retrouver les niveaux dans un graphe

Dans un graphe sans circuit, on peut trouver des niveaux successifs de la façon suivante :
- Ce sont des ensembles consécutifs de sommets.
- On appellera niveaux 0 l'ensemble des sommets sans prédécesseur. - Le niveau n est constitué des sommets sans prédécesseur après suppression du niveaux n-1.

Voici un algorithme :

Cet algorithme est basé sur la liste des prédécesseurs. (c'est une liste des sommet du graphe ou on associe a chaque sommet la liste de ces prédécesseurs...)

Initialisation :

n = 0;
Créer la liste des prédécesseur;

Itérations :

tant que tous les sommets ne sont pas marqués, faire :
     - On marque dans la liste tout sommet sans prédécesseur, ce sera les sommets de niveau n
     - On Supprime tous les sommets marqués
     - on incrémente n

Voici un Exemple :

Table des prédécesseurs :

Le concept de réseaux de transport

Un réseau de transport est un graphe qui a les propriétés suivantes :
     - il est orienté, connexe, valué et sans boucle.
     - 1 seul de ces sommet n'a pas de prédécesseurs : c'est la source.
     - 1 seul de ces sommet n'a pas de successeurs : c'est le puit.
     - La valuation des arcs de ce graphe est appéllée la capacité (α), elle est positive.

Le flot (Φ) dans un réseau de transport

c'est une seconde valuation qui répond a 2 règles :

     - Φ(i,j) <= α(i,j) quelquesoit i,j
     (le flot de l'arc i,j est inférieur ou égal à la capacité de cet arc quelquesoit i et j)

     (le flot entrant est égal au flot sortant quelquesoit le noeud (sauf pour la source et le puit...))

Quelques définitions

La coupe :

C’est une partition d’un réseau telle que P contienne la source (noté a) et P contienne le puit (noté z).

Capacité d’une coupe :

C’est la somme de tous les arcs dont l’origine se trouve dans P et l’extrémité dans P barre

Algorithme de Ford & Fulkerson

Cet algorithme se propose d'améliorer le flot dans un réseau de transport. Chaque itération se compose de 2 phases :
     - On crée une liste des sommets marqués du réseau. Cette liste représente un chemin pour atteindre le puit en partant de la source.
     - Cette liste est utilisée pour mettre a jour le flot du réseau de transport.

conventions pour la notation :

Algorithme :

Initialisation :

Φ(x,y) = 0;
On associe à chaque arc un flot nul.

v(Φ) = 0;
Le flot dans le réseau est alors nul lui aussi.

Itérations : étape 1

Poser a(-,∞);

Ajouter des sommets dans cette liste en respectant les règles suivantes :
     - Le nouveau sommet (y) doit être relié par un arc à un sommet (x) déjà marqué au cours de l'itération.

     - Le coefficient Δy doit être non nul, on le calcule de la façon suivante :

         - Si y est successeur de x :
             - Δy = MIN [ Δx , α(xy) - Φ(xy) ]
             - On marque le sommet (X⁺ , Δy)

         - Si y est le prédécesseur de x :
             - Δy = MIN [ Δx , Φ(xy) ]
             - On marque le sommet (X^- , Δy)

Itérations : étape 2

si on a terminé l'étape 1, 2 cas sont possibles :

- Soit on a pu marqué le puit :

- On va faire une mise a jour des Φ(x,y) :

- Φ(x,y)_nouveau = Φ(x,y)_ancien +/- Δz.
(on ajoute ou retranche Δz selon le signe de l'exposant dans la liste)

- On change les Φ(x,y) en "remontant" le chemin indiqué par la liste depuis le puit vers la source.

- puis recommencer à l'étape 1. (on crée une nouvelle liste...)

- Soit on n'a marqué tous les sommets possibles et on ne peut pas atteindre le puis (c'est la condition d'arrêt) : le travail est terminé.

Comment vérifier le résultat :

on construit une coupe en utilisant d'un coté la dernière liste construite, de l'autre le reste des noeuds du réseau. La valeur de cette coupe doit être égale au flot maximum.

Quelques remarques :

Quand on fait un exo sur cet algo, la tentation est grande de s'arrêter en croyant a voir fini : Il ,n'y a que 2 bonnes raisons pour s'arrêter :

- Il est impossible de marquer le puit...
- Tous les arcs issus de la source, ou tous ceux qui vont vers le puits, sont saturés.

Lors de l'initialisation, on vous propose de mettre tous les &Phi(x,y) = 0. On peut gagner pas mal de temps en essayant de saturer "a la main" le réseau de transport : il y a 2 pièges a éviter :

- il faut faire attention à vérifier la loi de conservation du flot...
- Cette opération doit vous prendre 1 minute : ne vous cassez pas la tête, l'algo est la pour valider ou améliorer votre choix...

Algorithme de Roy

On a remarqué qu’il y a souvent plusieurs répartitions ayant un flot maximal. L’algorithme de Roy se propose de choisir parmi ces solutions une (ou plusieurs) répartition ayant un coût minimal.

Pour introduire cette notion, on ajoute une seconde valeur sur chacun des arcs : Le coût

Quelques définitions

Graphe antisymétrique :

Un graphe est antisymétrique si quel que soit l’arc arc (xy) il n’existe pas d’arc (yx),

Si un graphe n’est pas antisymétrique, ont peut le modifier pour qu’il le devienne, il suffit d’ajouter un sommet fictif et de répartir le coût sur les 2 arcs créés

Graphe d’écart :

Soit G 1 graphe antisymétrique avec un flot , on construit G_E en suivant la recette suivante :

G_E à les mêmes sommets que G.
Pour chaque arc xy de G :

- Si xy est non saturé dans G (α > Φ), on crée dans G_E un arc xy de capacité α_E(xy) = α(xy) –(xy).
- Sinon (xy est saturé), on ne crée pas d’arc dans G_E

- Si le flot Φ(xy) ≠ 0, on crée dans G_E un arc YX dont la capacité est :

α_E(yx) = α(yx) - Φ(xy).

- Sinon, on ne crée pas d’arc yx dans G_E

Un dessin vaut mieux que de long discours :

Algorithme de Tabourier

Quelques définitions

Sommet saturé :

Soit x un sommet de X, x sera dit couplé par W s’il existe un sommet y tels que (xy) appartienne a W. On dira alors que x est saturé par y

De même, Soit y un sommet de Y, y sera dit couplé par W s’il existe un sommet x tel que (yx) appartienne a W. On dira alors qu’y est saturé par x

Sommet insaturé :

Un sommet est insaturé s’il n’est pas saturé

Chaîne alternée :

C’est une suite d’arrêtes prises alternativement dans W et hors de W. Chaque arrête ayant une extrémité commune avec l’arrête précédente et l’arrête suivante.

Chaîne alternée saturante (CAS) :

μ = (α₁ , α₂ , α₃ , ... , α_n) est une Chaîne Alternée Saturante si et seulement si :

α₁ appartient à W
α_n appartient à W
le sommet de classe X de α₁ est insaturé
le sommet de classe Y de α_n est insaturé

Chaîne alternée tronquée :

μ = (α₁ , α₂ , α₃ , ... , α_n) est une Chaîne Alternée Tronquée si et seulement si :

α₁ appartient à W
α_n n'appartient pas à W
le sommet de classe X de α₁ est insaturé

Longueur d’une arrête :

L(xy) = - v(xy) si xy appartient à W sinon, L(xy)= v(xy)

Longueur d’une chaîne alternée :

Soit μ = (α₁ , α₂ , α₃ , ... , α_n) une Chaîne alternée, alors :

Inversion de chaîne 

Présentation de l’algorithme :

Il se décompose en une phase préliminaire et une autre itérative :

Phase A : travail préliminaire

Le but est de construire un couplage minimal : On parcourt chaque ligne dans l’ordre croissant des indices.
On repère le terme minimal dans la ligne.
Si ce terme n’est pas déjà couplé en Y (dans une colonne contenant déjà un terme marqué), on le marque.
Le couplage ainsi obtenu est appelé W₀

Phase B : algorithme

Nous allons numéroter les n lignes non marquées, ont les parcours dans l’ordre croissant des indices et ont leur affecte un numéro du type X_ji(ou i va de 1 à n).

Pour i allant de de 1 à n : on va effectuer les 2 opérations suivantes

rechercher dans G muni de W_i-1 une CAS (ou a défaut une CAT) de longueur minimale ayant pour origine un γ_ji dont x_ji est le sommet de classe X.

inverser cette chaîne alternée et appeler W_i le couplage ainsi obtenu.

Quelques remarques