Corollaire 1 - Cours en ligne

ENSE3 Filière ASI
RECHERCHE OPERATIONNELLE Christian Commault
2014-2015
PLAN I. INTRODUCTION
II. QUELQUES ELEMENTS DE THEORIE DES GRAPHES
III. PLUS COURTS CHEMINS
IV. ORDONNANCEMENTS SIMPLES
V. FLOT MAXIMUM INTRODUCTION A LA RECHERCHE OPERATIONNELLE
Objet :
Permettre à un agent économique de prendre la meilleure décision possible
(parfois identifiée à l'Aide à la Décision) Situation:
Au carrefour entre l'économie, les mathématiques (appliquées) et
l'informatique.
Formulation d'un problème :
- modélisation mathématique d'un problème économique d'optimisation,
- analyse mathématique du modèle,
- recherche d'une résolution informatique efficace. Souvent le problème d'optimisation porte sur un ensemble fini de solutions
possibles :
Minx(X f(x) où X est un ensemble fini. Solution triviale : on évalue f pour toutes les valeurs de x et on prend la
meilleure, problème : l'explosion combinatoire. Exemple : Soirée avec 25 garçons 25 filles, pour chaque couple possible (i,j) il
existe un degré d'intérêt mutuel : dij, on suppose que pour que la soirée
soit la plus réussie possible il faut maximiser la somme des intérêts
mutuels, si on appelle p une permutation quelconque sur 25 et P l'ensemble
des permutations sur 25 le problème revient en posant
à résoudre le problème d'optimisation Max p(PFp. Nombre de possibilités d'affectation : 25! Exemple de réalisation informatique : supposons que chaque évaluation de Fp
dure 1?s, alors l'obtention de la solution optimale par recherche
exhaustive nécessite 5 milliards de siècles !
Pourtant il existe un algorithme qui permet de l'obtenir en quelques
secondes (Méthode hongroise). Les domaines d'intérêt de la recherche opérationnelle comprennent :
- l'étude mathématique des problèmes pour en déduire des propriétés et en
particulier essayer de restreindre l'ensemble des solutions possibles,
- la recherche d'algorithmes efficaces de résolution,
- la classification des problèmes pour savoir comment aborder un problème
nouveau. Un outil essentiel pour la modélisation et la résolution de problèmes
d'optimisation combinatoire : les graphes. Un outil essentiel de résolution
: la programmation linéaire.
Quelques problèmes classiques :
1) Dans un graphe trouver un cycle qui passe par toutes les arêtes sans
passer 2 fois par la même (Cycle Eulerien).
2) Dans un graphe trouver un cycle qui passe par tous les sommets sans
passer 2 fois par le même (Cycle Hamiltonien).
3) En supposant que chaque arc d'un graphe a un coût, trouver un circuit
qui passe par tous les sommets et de coût total minimum : problème du
Voyageur de Commerce (Traveling Salesman Problem). Problème ayant de
nombreuses applications pratiques de type séquencement de tâches.
4) Trouver un circuit qui passe par tous les arcs et de coût total minimum
: problème du Postier Chinois.
5) Rechercher le plus court chemin entre 2 sommets donnés d'un graphe.
6) Rechercher l'ordonnancement optimal de tâches de durée donnée et
soumises à des contraintes.
7) Problème d'affectation optimale, comme dans notre exemple.
8) Problème du Sac à Dos : remplissage d'un sac de volume total donné par
des produits d'apports énergétiques donnés, pour obtenir le remplissage
optimal en énergie totale.
....
QUELQUES ELEMENTS DE THEORIE DES GRAPHES
I. DEFINITIONS DE BASE 1) Graphes Un graphe est défini par :
- 2 ensembles finis disjoints X (sommets) et U (arcs),
- 2 applications I (extrémité initiale) et T (extrémité terminale) de U(X,
qui à chaque arc associent son extrémité initiale et son extrémité
terminale. Il s'agit donc ici de graphes orientés. Exemple : G(X, U) avec X=( x1, x2, x3), U=( u1, u2, u3, u4), Arc I T u1 x1 x2
u2 x2 x1
u3 x2 x3
u4 x2 x3 Remarque :
Cette définition autorise l'existence de plus d'un arc entre 2 sommets.
Lorsqu'un graphe a au plus un arc entre 2 sommets on l'appelle graphe
simple. Dans ce cas on peut identifier U à un sous-ensemble de X.X et
représenter un arc u par la paire (I(u), T(u)). Soit x(X,
On appelle demi-degré extérieur de x noté
d+(x) = nombre d'arcs u tels que I(u)=x, arcs "sortants" de x.
On appelle demi-degré intérieur de x noté
d-(x) = nombre d'arcs u tels que T(u)=x, arcs "entrants" dans x.
On appelle degré de x noté
d(x) = d+(x) + d-(x). Soit u(U tel que I(u) = x, T(u) = y, on dit que x et y sont adjacents, que
x est un prédécesseur de y et y un successeur de x. L'arc u est dit
incident (extérieur) à x et incident (intérieur) à y. Proposition 1 Démonstration : chaque arc possédant exactement une extrémité initiale et
une extrémité terminale, chaque arc intervient une fois et une seule dans
chacune des sommes. 2) Chemins et circuits x, y (X, on appelle chemin de x à y une séquence d'arcs (ui1, ui2, ...,
uik) telle que
I(ui1) = x, T(uik) = y et,
I(uij+1) = T(uij) pour j = 1, ..., k-1. Chemin simple si pas 2 fois le même arc, chemin élémentaire si pas 2 fois
le même sommet, circuit si x = y. Proposition 2
S'il existe un chemin de x à y alors il existe un chemin élémentaire de x à
y. Démonstration : On peut décrire un chemin par une succession d'arcs et de
sommets. Si on rencontre 2 fois le même sommet dans la liste, alors le sous-
chemin entre ces 2 sommets est un circuit qui peut être supprimé en créant
un nouveau chemin, on recommence jusqu'à ce que le chemin soit élémentaire. Soient s, p (X, comment construire un chemin élémentaire, s'il existe, de s
à p ?
On donne un algorithme qui utilise la notion très importante de marquage. Algorithme : Recherche d'un chemin de s à p.
Initialisation:
M= {s}; M est l'ensemble des sommets marqués; TANTQUE il existe u tel que I(u)(M et y = T(u)(M
FAIRE M=M ( {y}
FINTQ Si p(M alors il existe un chemin, sinon pas de chemin. Attention : comme tel l'algorithme ne donne pas le chemin solution.
II. NOTION DE FORTE CONNEXITE Un graphe G = (X, U) est fortement connexe si ( x, y (X, il existe un
chemin de x à y. Par convention on dira qu'il existe un chemin de x à x. Pour tester la forte connexité on peut appliquer l'algorithme précédent à
partir de chaque sommet. a (X, on appelle composante fortement connexe de a l'ensemble :
X(a) = { x ( X (( un chemin de a à x et ( un chemin de x à a }. Si on considère la relation, x et y sont en relation si ( un chemin de x à
y et ( un chemin de y à x, il est clair que cette relation est une relation
d'équivalence dont les classes d'équivalence sont les composantes fortement
connexes. On peut donc effectuer une partition des sommets. Construction effective de la composante fortement connexe du sommet a :
X(a) = X+(a) ( X-(a) où,
X+(a) = { x ( X (( un chemin de a à x },
X-(a) = { x ( X (( un chemin de x à a }. A un graphe G(X,U) on associe son graphe réduit GR(X', U') de la manière
suivante :
chaque x' (X' correspond à une composante fortement connexe de G, il existe
un arc (x', y') s'il existe un arc entre deux sommets appartenant aux
composantes fortement connexes correspondantes dans G. Proposition 3
Un graphe réduit ne contient pas de circuit. Démonstration : s'il existe un circuit dans GR, il est facile de démontrer
que, entre toute paire de sommets des composantes fortement connexes
correspondantes il existe un chemin dans G.
III. GRAPHES NON ORIENTES - ARBRES Il existe une correspondance naturelle entre les notions orientées et non
orientées. Notion orientée Notion non orientée Arc Arête
Chemin Chaîne
Circuit Cycle
Forte connexité Connexité Théorème 1
L'adjonction d'une arête à un graphe a l'un et l'un seulement des effets
suivants :
- diminution d'une unité du nombre de composantes connexes,
- création d'un nouveau cycle. Démonstration : les deux possibilités s'obtiennent en choisissant des
arêtes qui ont leurs extrémités dans des composantes connexes différentes
ou dans la même composante connexe.
Corollaire 1 Soit un graphe G(X, U) alors :
a) G connexe ( (U(( (X(- 1
b) G sans cycle ( (U(( (X(- 1. Démonstration : construire un graphe en partant des sommets uniquement, en
ajoutant les arêtes une à une et appliquer le théorème 1. Un arbre est un graphe connexe sans cycle. Théorème 2
Soit un graphe G(X, U) avec m = (X(( 2.
Les propriétés suivantes sont équivalentes et caractérisent un arbre :
1) G est connexe et sans cycle,
2) G est connexe minimal (si on enlève une arête quelconque il n'est plus
connexe),
3) G est connexe et possède (m-1) arêtes,
4) G est sans cycle maximal (si on ajoute une arête quelconque il n'est
plus sans cycle),
5) G est sans cycle et possède (m-1) arêtes,
6) Il existe une chaîne et une seule joignant une paire de sommets
quelconque. Démonstration : par applications du théorème 1 et du corollaire 1.
Pour démontrer que 1)(6) la connexité équivaut à l'existence d'une chaîne,
l'unicité de cette chaîne à l'absence de cycle.
Proposition 3 Un arbre avec m ( 2 possède au moins deux sommets de degré 1 ( sommets
pendants). Démonstration : d'après la proposition 1 et le théorème 2, la somme des
degrés est 2(m - 1), de plus chaque sommet a un degré au moins égal à 1 par
la connexité, il existe au moins deux de ces degrés qui valent exactement
1.
IV. LE PROBLEME DE L'ARBRE DE POIDS MINIMAL Soit G(X, U) un graphe, on appelle graphe partiel de G un graphe G(X, U')
où U' ( U.
G étant un graphe non orienté on appelle arbre recouvrant un graphe partiel
de G qui