1

Pauline Matringe

OGO

MODELE METHODE DIFFICILE APPLICATIONS

PCG Heuristiques : OUI Gestion des stocks
(Glouton, Dsatur, tabou (que Confection d’horaires
l’one ne verra pas)) Télécommunications
Ordonnancement
PL Simplexe (& solveur) NON Remplissage de
containers (fluides)
PLNE Simplexe & solveur OUI Gestion d’effectifs
Heuristique quand on a trop Gestion de la production
de variables
FLOTS Ford & Fulkerson NON Affectation
Transport
Gestion de stock
Ordonnancement
PVC Heuristiques (Glouton, OUI Transport
tabou) Ordonnancement
Arbre min poids max Algorithme de Kruskal NON Réseau de métro
Arborescence max Algorithme GQA NON Réseau de pipeline à
poids min partir d’une source
PCGM (Mixte) (arcs Heuristiques OUI
ou arrêtes)
PCGI (Intervalle) Algorithme glouton NON
(exception ici méthode
exacte)

Partie 1 : Problème de la coloration de graphes

• La recherche opérationnelle (RO) fournit des modèles mathématiques et des méthodes

d’optimisation pour résoudre des problèmes économiques et logistiques.
• Un graphe G : G = (V,E) consiste en un ensemble V de sommets et un ensemble E d’arêtes liant
certaines paires de sommets.
• Un algorithme est une méthode d’optimisation, donné sous la forme de séquences
d’instructions.
• Glouton : profit à court terme (qui dépend du problème)

Méthodologie :
1) Formuler un problème (c’est l’énoncé)
2) Trouver un modèle mathématique pour le problème (comme un support sur lequel on va appliquer
une méthode d’optimisation pour connaitre le résultat, le modèle mathématique ne donne pas le
résultat).
3) Trouver une méthode d’optimisation pour le modèle (comme une technique)
4) Evaluer la qualité réelle des solutions obtenues
5) Retourner à l’étape 2 si les solutions sont insatisfaisantes
 2
Pauline Matringe

MODELE : PCG
Modélisation / Correspondance entre le modèle et le problème :
- 1 couleur =
- 1 sommet =
- 1 arrête [x,y] =

Pour PCG, il y a en effet différents gloutons:

- le glouton de base ne classe pas les sommets et est donc généralement le moins bon
- le glouton pour les graphes d'intervalles est optimal pour les graphes d’intervalles (et uniquement
pour ces graphes)
- DSATUR est un glouton "raffiné" et donc le plus adapté pour les autres graphes.

METHODE : Algorithme GLOUTON-PCG de base

Tant qu’il reste des sommets à colorer, faire :
• Choisir un sommet x non coloré
• Attribuer à x la plus petite couleur possible

Dépend de l’ordre de parcours des sommets (de la séquence)

METHODE : Algorithme Glouton pour les graphes d’intervalles

• Classer les sommets par ordre croissant de A.
• A chaque étape choisir le sommet suivant et lui attribuer la plus petite couleur possible.

METHODE : Algorithme DSATUR à méthode exacte

!(#) = Ensemble de sommets adjacents

%&'() = Nombre de sommets de A(x) non colorés
%*+,+(#) = Nombre de couleurs différentes dans A(x)

1) A chaque étape choisir le sommet x maximisant %*,+ et lui attribuer la plus petite couleur possible
2) Si plusieurs possibilités, choisir le sommet x maximisant %&'()
3) Si plusieurs possibilités, choisir x aléatoirement.

! Attention au début ce n’est pas le sommet qui a le plus de sommets adjacents coloriés mais le
sommet qui a le plus de couleurs différentes. Un sommet plus de sommet colorié qu’un autre mais
ses couleurs peuvent être identiques.

Autres choses à connaitre :

ü Les trois types de problème
ü Définition PCG (encadré en rouge)
ü PCG et gestion des stocks
ü PCG et confections d’horaires
ü PCG et télécommunications
ü Algorithme DSATUR
 3
Pauline Matringe

Partie 2 : Programmation linéaire (en nombres entiers)

MODELE : PLNE

Variables
Xi =

Fonction objective à maximiser ou minimiser

…

Contraintes
Xi entier pour tout i
Xi ≥ 0
(Ne pas dépasser certaines bornes par exemple)
…

! Ceci est un modèle pour résoudre (méthode) on a besoin d’un solveur …

Autres choses à connaître :

ü Exercice 1 : PL remplissage de containers (fluides)
ü Exercice 2 : PLNE Gestion des effectifs + Excel
ü Exercice 3 : PLNE Gestion de la production + Excel
 4
Pauline Matringe

Partie 3 : Flots dans les graphes

• Un graphe orienté : R = (V, U, c, k) V : ensemble de sommet U : ensemble d’arcs

• c : fonction qui attribue une capacité c(u)>0 à chaque arc u de U.
• k : fonction qui attribue un coût à chaque arc
• s : sommet source
• p : sommet puit

• Un flot est une fonction f qui attribue un entier positif f(u) à chaque arc u de U, tel que :
Respect des capacités : 0 ≤ f(u) ≤ c(u) pour tout u appartenant à U
Somme des flots qui entre en x = somme des flots qui quittent x, pour tout x appartenant à V – {s, p}

• La valeur d’un flot de s à p, Val(f), peut être définie comme la somme des flots qui arrivent en
p.
• Le problème du flow max (FM) consiste à trouver un flot maximisant Val(f).

• K(f) : coût du flot f de s à p. ∑[ k(u)*f(u)]

• Le problème du flot max à coût min (FMCM) consiste à trouver le flot qui minimise k(f) parmi
les flots qui maximisent Val(f).

MODELE : Flots
Créer un sommet source et un puit !
Notation : (… , …) D’abord la capacité et ensuite le coût (valable pour 1 unité)

METHODE : Algorithme de Ford & Fulkerson

à Résolution du FM (Construction d’un graphe auxiliaire R* / Algorithme Ford & Fulkerson)

à Résolution du FMCM (Construction d’un graphe auxiliaire R*/ Algorithme Ford & Fulkerson)

Exercice 5 : Transport / Demande de client

Ø Contenu de l’entrepôt (offre entrepôt) à Arc (S,E)
Ø Demande des clients à Arc (C,P) sur les derniers arcs
Ø Souvent entre les entrepôts et les clients la capacité est infinie, seuls les coûts sont donnés
(souvent le seul endroit où ils apparaissent).

Exercice 6 : Gestion des stocks

• Pour les exercices de gestion des stocks on peut créer 3 moments (achats, stockage et vente),
et les sommets entre s et p doivent avoir le même numéro.
- Le coût sur l’arc (s,i) représente le coût d’achat
- Le coût sur l’arc (i,i) représente le coût de stockage. La capacité sur l’arc (i,i)
représente ce que l’on peut stocker.
- Le coût sur l’arc (i,p) est le prix de vente, qui est un coût négatif. La capacité sur l’arc
(i,p) est le nombre d’ordinateurs à vendre à la fin de la période.
• Les ventes sont des coûts négatifs.
Autres choses à connaître : Exercice 4 : Affectation + Excel
 5
Pauline Matringe
 6
Pauline Matringe

Partie 4 : Heuristiques

• Méthode d’énumération exhaustive [METHODE EXACTE] : Générer et évaluer toutes les

solutions possibles et garder la meilleure (qui est la solution optimale). C’est une méthode
exacte.

• L’espace S des solutions représente l’ensemble des solutions à un problème.

• Une heuristique est une méthode de recherche d’une « bonne » solution à un problème, qui
limite sa recherche à une partie de l’espace des solutions, afin d’avoir un temps de calcul
raisonnable mais qui ne garantie pas la solution optimale.

HEURISTIQUES CONSTRUCTIVES

• Une heuristique constructive construit pas à pas une solution, en complétant à chaque étape
une solution partielle.
• A chaque étape, on fait des choix selon des règles spécifiques qui dépendent du problème à
résoudre.
à L’algorithme glouton construit une solution en effectuant à chaque étape le choix qui optimise la
valeur courante de la fonction objective.

HEURISTIQUES DE RECHERCHE LOCALE

• Deux solutions s et s’ sont voisines si on peut obtenir s’ en modifiant légèrement s selon une
règle bien définie.
• On peut passer de s à s’ en effectuant un mouvement. La définition du mouvement dépend
du problème considéré.
• Le voisinage V(s) d’une solution s ∈ S est l’ensemble des solutions voisines de s.
à Descente
à Tabou
à Recuit simulé
à Recherche à voisinages variables

Elles se distinguent par

- la définition du voisinage d’une solution
- la manière de choisir une solution voisine
- le critère d’arrêt

s = solution initiale, solution que l’on traite

s’ = solution voisine
s* = solution record

Ø Une fonction objective f

Ø Un critère d’arrêt
Ø Une heuristique constructive
Ø Définir ce qu’est un mouvement (= structure du voisinage)
Ø Définir ce qu’est un mouvement tabou (=structure de la liste tabou)
Ø Taille de la liste tabou
Ø Quels infos (type d’info) interdire
 7
Pauline Matringe

Autres choses à connaître :

ü Heuristique de recherche locale – principe (slide 8)
ü Heuristique de descente
Choix de la solution voisine et critère d’arrêt (slide 10)
Algorithme de descente (slide 11)
ü Algorithme Tabou
Critère d’arrêt (slide 12)
Solution voisine (slide 13)
Algorithme Tabou (slide 14)
ü Algorithme Tabou pour le PVC (slide 15)
ü Application de l’algorithme Tabou (slide 16 : 21)
 8
Pauline Matringe

Partie 5 : Arbres et Arborescences optimaux

PROBLEME DE L’ARBRE MAX DE POIDS MIN

• Une chaine est une séquence d’arrêtes adjacentes.
• Un cycle est une chaine fermée.
• Un graphe G est connexe s’il existe au moins une chaine entre chaque pair {x,y} de sommets.
• Arbre T : graphe connexe sans cycle.
• Un arbre T est maximal dans G = (V,U) s’il touche tous les sommets du graphe G.
• Le poids w(T) d’un arbre T de G = (V,U,w) est la somme des poids des arrêtes qui le composent.
• Un réseau est graphe pondéré.

PROBLEME DE L’ARBORESCENCE MAX DE POIDS MIN

• Un chemin est une séquence d’arcs adjacents orientés dans le même sens.
• Un circuit est un chemin fermé.
• Un sommet r est une racine dans G = (V,U) s’il existe un chemin de r à x pour tout x de V.
• Un graphe est quasi-fortement connexe (qfc) s’il contient une racine.
• Une arborescence est un arbre orienté qui contient une racine.
• Une arborescence A est maximale dans G = (V,U) si elle touche tous les sommets du graphe
G.
• Le poids w(A) d’une arborescence A de G = (V,U,w) est la somme des poids des arcs qui la
composent.

Récapitulatif des graphes et réseaux :

• Un graphe non orienté (orienté) est un ensemble de sommets/nœuds et d’arrêtes (arcs).
• Dans un graphe non orienté (orienté), une chaine (un chemin) est une suite d’arrêtes (arcs)
adjacentes (tous orientés dans le même sens) ;
• Lorsque l’on attribue un poids aux arêtes/arcs, le graphe est appelé réseau.

Montrer que l’arbre est maximal :

Autres choses connaître :

ü Algorithme de Kruskal + illustration
ü Algorithme GQA
ü Application de GQA
ü Contractions et décontractions fiche
 9
Pauline Matringe

Partie 6 : Qui a tué le Duc de Densmore ? (graphes d’intervalles)

• Le triangle et le rectangle avec une diagonale sont des graphes d’intervalle.

• Le carré n’est pas un graphe d’intervalle

Technique pour savoir si c’est un graphe d’intervalle :

1. Tracer un axe horizontal (sens de l’axe de abscises)
2. Essayer de placer tous les sommets (numérotés) en faisant des traits horizontaux qui se
chevauchent si les sommets se touchent dans le graphe et sans chevauchement si les
sommets ne se touchent pas dans le graphe.
3. Tracer des traits verticaux entre chaque sommet qui se touchent dans le graphe.
à S’il n’est pas possible d’appliquer cette méthode alors le graphe n’est pas un graphe d’intervalle.

MODELE : Graphes d’Intervalle

• Pour chaque sommet x, on peut attribuer un intervalle I(x) = [A(x) ; B(x)].
• Construction du graphe : arrête [x,y] si I(x) ∩ I(y) est un intervalle.

METHODE : Algorithme Glouton pour les graphes d’intervalles

• Classer les sommets par ordre croissant de début d’intervalle.
• A chaque étape choisir le sommet suivant et lui attribuer la plus petite couleur possible.