Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

RECHERCHE OPÉRATIONNELLE - 3 - INTRODUCTION La recherche opérationnelle est une

RECHERCHE OPÉRATIONNELLE - 3 - INTRODUCTION La recherche opérationnelle est une discipline dont le but est de fournir des méthodes pour répondre à un type précis de problème, c'est-à-dire à élaborer une démarche universelle pour un type de problème qui aboutit à la ou les solutions les plus efficaces. La particularité de la recherche opérationnelle est que les méthodes proposées sont des démarches rationnelles basées sur des concepts et outils mathématiques et/ou statistiques. Généralement, ces méthodes sont employées sur des problèmes tels que leur utilisation "manuelle" devient impossible. C'est pourquoi, du fait qu'elles sont rationnelles, les démarches proposées par la recherche opérationnelle peuvent être traduites en programmes informatiques. Cette traduction d'une démarche en un programme informatique n'est pas sans difficulté. Tout d'abord, le temps d'exécution du programme résultant et/ou la place occupée dans la mémoire de l'ordinateur peuvent ne pas être acceptables. Ainsi, une méthode en recherche opérationnelle sera jugée sur ces critères de temps et de place. Plus une méthode sera rapide et peu gourmande en mémoire, plus elle sera considérée bonne. Les ordinateurs ont une structure particulière qui fait que toutes les propriétés des mathématiques traditionnelles ne sont pas toujours respectées. Ainsi, une démarche prouvée fonctionner admirablement en théorie peut s'avérer être complètement inexploitable en pratique. Notamment, les nombres réels dans un ordinateur ne peuvent pas être représentés de manière exacte, ils sont arrondis. On voit donc facilement qu'une répétition excessive d'arrondis dans un calcul peut entraîner des erreurs importantes dans les résultats finaux. Les méthodes employées en recherche opérationnelle doivent prendre en compte ce genre de problème. - 4 - PLAN DU COURS Dans ce cours, nous verrons différents outils de recherche opérationnelle sans apporter de justifications mathématiques très détaillées et rigoureuses. Après quelques exemples qui permettront de mieux cerner le domaine de la recherche opérationnelle, nous introduirons un outil à la fois graphique et théorique: les graphes. Afin de mieux appréhender la complexité d'un problème ou la rapidité d'un algorithme, nous nous intéresserons à la théorie de la complexité. Enfin, nous verrons un autre outil important de la recherche opérationnelle qui est la programmation linéaire. L'avantage de cet outil est d'apporter une solution générique à la résolution de nombreux problèmes. De plus, cet outil est disponible sous différentes formes pour une utilisation informatique. Voici le plan du cours. Présentation Les graphes Les arbres Représentation des graphes Efficacité des algorithmes, complexité des problèmes Recherche du plus court chemin Ordonnancement, recherche du plus long chemin Recherche du flot maximum Programmation linéaire - 5 - (S) (T) X=4 1 (a) (b) 2 1 4 (c) (e) (d) 1 6 2 1 2 Algorithme de : Dijkstra, les plus court chemin d’un point à un autre. Floyd, calcule les plus courtes distances entre tous les sommets d'un graphe. Ford & Fulkerson, résolution du problème de flot maximal Pollack - 6 - (A) (B) (C) (D) (E) (F) (G) (H) (I) (J) (A) Faire une étude préliminaire de la structure du système. (B) Élaborer un modèle théorique (C) Collecter les données (D) Mettre sous forme codée les données relatives modèle élaboré. (E) Tester le modèle à l’aide de données engendrées artificiellement. (F) Présenter le modèle aux collègues théoriciens pour examen critique. (G) Corriger le modèle si nécessaire. (H) Tester le modèle si nécessaire. (I) Tester le modèle à l’aide de données réelles. (J) Faire les corrections finales (K) Délivrer le modèle aux utilisateurs. - 7 - Programmation linéaire : Optimisation linéaire en variable continue Danntzig (1948). Maximiser une fonction linéaire de variable sous contrainte. Exemple : Optimiser le fonctionnement d’un aéroport : Maximiser le nombres d’atterrissage. Exemples : Le directeur d’une station de radio veut minimiser les frais de production d’une émission qui est composée de la publicité (coût 1F/Min) de l’information (5F/Min) de la musique (6F/Min). Proposer une composition pour 1 heure sachant que : 1) Le temps consacré à la pub doit être au plus égal à 15mn. 2) Le temps consacré aux informations doit être au plus égal à 10mn. 3) Le temps consacré à la musique doit être au moins égal au quadruple du temps publicitaires. x1 = temps de publicités x2 = temps d’informations x3 = temps musiques Min c1 x1 + c2 x2 + c3 x3 (1) a11 x1 + a12 x2 + a13 x3 (2) a21 x1 + a22 x2 + a23 x3 (3) a31 x1 + a32 x2 + a33 x3 Min 1 x1 + 5 x2 + 6 x3 (1) 1 x1 <= 15 (2) 1 x2 <= 10 (3) 4 x1 -1 x2 <= 0 x3 >= 4x1 4x - x3 <= 0 { { 1 LES GRAPHES Un graphe est un ensemble de nœuds qui sont reliés entre eux par des arcs. Mathématiquement, un graphe est représenté par un couple de deux ensembles G=(X ;U) où X est l’ensemble des nœuds et U l’ensemble des arcs. ARC BOUCLE ADJACENCE u=(x ;y) • x est adjacent à y • y est adjacent à x, • x et y sont adjacents à u - 8 - X Y X Y = = (x ;y) (y ;x) ARC non orienté ARC orienté X X Boucle non orienté Boucle orienté X Y u DEGRÉ x= (X,U) X= { (a) ; (b) ; (c) ; (d) ; (e) ; (f)} U={ (a,b) ; (a,c) ; (b,c) ; (b,d) ; (b,c) ; (c,e) ; (c,f) ; (d,f) ; (e,f) ; (b,f) } Le demi degré exterieur: Le demi-degré extérieur d’un noeud est le nombre d’arcs adjacents qui en partent. d+(a)= | { (a,b) ; (a,c)} | = 2 d+(c)= | { (c,b) ; (c,e) ; (c,f) } | = 3 Le demi degré interieur: Le demi-degré interieur d’un nœud est le nombre d’arcs adjacents qui y arrivent. d-(c)= | { (b,c) ; (a,c) } | =2 Le degré : Le degré d’un nœud est le nombre d’arc qui lui sont adjacents : d(x)=d+(x) + d-(x) d(c)= | { (c,b) ; (c,e) ; (c,f) ; (b,c) ; (a,c) } | = 5 GRAPHE RÉGULIER Un graphe est dit régulier si les degrés de tous ses sommets sont égaux. - 9 - a b c e f d a d b c GRAPHE COMPLET Un graphe est dit complet si tous les nœuds sont adjacents deux à deux. Graphe non complet : Graphe complet : CHAÎNE Une chaîne de x à y est une séquence d’arcs c = { (x ;e) , (z ;e) , (z ;a)…(s ;t) , (u ;t) , (u ;y) } où deux arcs qui se suivent sont adjacents et où x doit être une extrémité du premier arc et y une extrémité du dernier. - 10 - a c b a c b a d b c CHEMIN Un chemin de x à y est une chaîne dans laquelle les arcs sont orientés et tels que :  x est l’extrémité initiale du premier arc,  y est l’extrémité terminale du dernier arc,  l’extrémité terminale d’un arc est l’extrémité initiale de l’arc qui le suit dans la séquence. • Ch1 = ( (a ;c) , (c ;e) ) est un chemin de a à e. • Ch2 = ( (a ;c) , (c ;f) , (f ;a) , (a ;c) , (c ;e) ) est un chemin de a à e. • Ch3 = ( (a ;c) , (c ;f) , (f ;d) , (d ;c) , (c ;e) ) est un chemin de a à e. • Ch4 = ( (a ;b) , (b ;d) , (d ;e) ) est un chaîne de a à e. • Ch5 = ( (a ;b) , (b ;d) , (d ;c) , (c ;a) , (a ;b) , (b ;d) , (d ;e) ) est une chaîne de a à e. • Ch6 = ( (a ;b) , (b ;d) , (d ;c) , (c ;f) , (f ;d) , (d ;e) ) est une chaîne de a à e. CHEMIN, CHAÎNE SIMPLE Un chemin simple est un chemin qui ne contient pas plusieurs fois le même arc. Dans l’exemple précédent, ch1 et ch3 sont des chemins simples mais pas ch2 Une chaîne simple est une chaîne qui ne contient pas plusieurs fois le même arc. Dans l’exemple précédent, ch4 et ch6 sont des chaînes simples mais ch5. CHEMIN, CHAÎNE ÉLÉMENTAIRE Un chemin élémentaire est un chemin qui ne passe pas plus d’une fois par un nœud. Dans l’exemple précédent, ch1 est un chemin élémentaire mais pas ch2, ni ch3. Une chaîne élémentaire est une chaîne qui ne passe pas plus d’une fois par un nœud. Dans l’exemple précédent , ch4 est une chaîne élémentaire mais pas ch5, ni ch6. CONNEXITÉ, FORTE CONNEXITÉ On définit la connexité par une relation entre deux nœuds de la manière suivante. x et y ont une relation de connexité ⇔ il existe une chaîne entre x et y ou bien x=y On définit la forte connexité par une relation entre deux nœuds de la manière suivante. x et y ont une relation de forte connexité ⇔ il existe uploads/Science et Technologie/ cours-recherche-operationnelle-concepts-et-outils-mathematiques.pdf