Remerciez-le!

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

Cours de recherche opérationnelle Hamid Zouaki ii Introduction La Recherche Opé

Cours de recherche opérationnelle Hamid Zouaki ii Introduction La Recherche Opérationnelle (RO) est la discipline des méthodes scientiﬁques utili- sables pour élaborer de meilleures décisions. Elle permet de rationaliser, de simuler et d’optimiser l’architecture et le fonctionnement des systèmes de production ou d’organi- sation. La RO propose des modèles conceptuels pour analyser des situations complexes et permet aux décideurs de faire les choix les plus eﬃcaces. On peut décrire une étude de recherche opérationnelle par les trois étapes suivantes : – Modélisation du problème: batir un modèle scientiﬁque (mathématique) repré- sentant schématiquement la réalité. – Résolution du problème: résoudre le modèle mathématique construit à travers la mise en oeuvre de méthodes numériques permettant d’obtenir des réponses ef- fectives. – Retour au problème pratique et confrontation des résultats du modèle et de la réalité. La RO apparaît comme une discipline carrefour associant les mathématiques, l’écono- mie et l’informatique. Elle est par nature en prise directe sur l’industrie et joue un rôle-clé dans le maintien de la compétitivité. Les apports de la RO sont visibles tout autour de nous et dans les domaines les plus divers. Ce cours se veut une introduction à la recherche opérationnelle. Il est composé de deux parties. La première partie est consacrée à la présentation de la théorie des graphes. Discipline, au départ, des mathématiques discrètes et qui fournit des outils eﬃcaces pour la résolution de grand nombre de problèmes. Après avoir présenté les propriétés de base des graphes, on aborde les techniques de recherche du plus court chemins et leurs application. On s’arrétera sur le problème important de la gestion de projets. La deuxième partie de ce support est une introduction à l’optimisation appliquée. On consacrera cette partie à l’étude des problèmes de programmation linéaires, leurs réso- lutions eﬀectives ainsi que leur interprétation économique. La méthode du simplexe est étudiée d’une manière détaillée. On consacrera aussi un petit chapitre pour introduire la théorie importante de la dualité. iii Recherche opérationnelle Prof. Hamid Zouaki iv Recherche opérationnelle Prof. Hamid Zouaki PARTIE I Théorie des Graphes 1 Recherche opérationnelle Prof. Hamid Zouaki 2 Chapitre 1 Déﬁnitions et concepts fondamentaux 1.1 Introduction La théorie des graphes ou théorie mathématique de l’interconnection, constitue un domaine des mathématiques qui s’est développé aussi au sein de disciplines diverses telles que la chimie (modélisation de structures), la biologie (génome), le sciences sociales (mo- délisation de relations) et dans beaucoup d’applications industrielles. Elle constitue un outil eﬃcace pour résoudre des problèmes discrets de la recherche opérationnelle. Un graphe permet de représenter simplement la structure et les cheminements d’un en- semble comprenant un grand nombre de situations, en exprimant les relations de dé- pendances entre ses éléments. On peut citer les réseaux de communication, les réseaux routiers et ferroviaires, les diagrammes de succession de tâches dans la gestion d’un projet ... etc. Le graphe est aussi une structure de donnée puissante en informatique. Mais, au-delà de la représentation de données, les graphes servent aussi et surtout pour proposer des solutions à certains problèmes. 1.1.1 Exemples 1. Problème du voyageur de commerce: Un voyageur de commerce ayant n villes à visiter souhaite établir une tournée qui lui permette de passer une fois et une seule dans chaque ville pour ﬁnalement revenir à son point de départ, ceci en minimisant le chemin parcouru. Il s’agit donc en terme de graphe, étant donné un réseau R = (X, U, d). (X, U) étant un graphe orienté dont les sommets représentent les villes et d : U →R qui à chaque arc associe un coût de parcours, de trouver un circuit élémentaire contenant tous les sommets du graphe dont la longueur, égale à la somme des longueurs des arcs le constituant, soit minimale. 2. Fiabilité dans les réseaux: Un réseau est un système de communication dans lequel des sites communiquent entre eux soit directement, soit par l’intermédiaire d’autres sites, en envoyant des messages qui circulent le long de lignes de communication. La représentation de tels réseaux par des graphes est telle que, les sites et les lignes correspondant respecti- vement aux sommets et aux arcs. 3 Recherche opérationnelle Prof. Hamid Zouaki Dans un réseau, il peut se produire qu’une ligne de communication soit coupée, ne transmettant plus aucun message. Il en est de même pour un site dont la panne peut être assimilée à la coupure de toutes les lignes qui y aboutissent ou qui en partent. Supposons que, dans un réseau, on achemine des informations d’un som- met A vers un sommet B, éventuellement via des sites intermédiaires servant de relais. De telles informations doivent emprunter des chemins allant de A vers B. Ainsi, une information issue de A parviendra à B si et seulement si au moins un chemin est valide (c’est à dire la séquence d’arcs qui le constitue ne comporte que des arcs non détériorés). Le problème posé est alors le suivant : quel est le nombre maximum de pannes auquel cet acheminement peut résister ? Autrement dit, quel est le nombre maximum de chemins indépendants existant entre A et B ? (deux chemins sont indépendants si et seulement si ils sont disjoints au sens des arcs et des sommets intermédiaires). 3. Problème d’ordonnancement: Un projet complexe est en général décomposé en tâches élémentaires ayant chacune une durée donnée. Ces tâches étant reliées les unes aux autres par des contraintes de précédence. Il s’agit de déterminer un calendrier d’éxecution des tâches qui respecte les contraintes de précédence et permette l’achèvement du projet dans une durée optimale. 1.2 Notion de graphe Déﬁnition 1.2.1. Un grahe est un couple G = (X, U) constitué par – Un ensemble ﬁni X = {x1, . . . , xn}. Les éléments de X sont appelés sommets du graphe – une famille U = {u1, . . . , um} d’éléments du produit cartésien X × X = {(x, y) : x ∈X, y ∈X}. Les éléments de U sont appelés des arcs. Un graphe est représenté par un schéma dans le plan où les sommets sont représentés par des points et les arcs par des branches orientées reliant deux sommets. E A D C B Pour un arc u = (xi, xj) ∈U on dit que l’arc u relie le sommet xi au sommet xj. Examinons l’exemple simple suivant : 4 Recherche opérationnelle Prof. Hamid Zouaki A B C u1 u2 u3 u4 G = (X, U) avec X = {A, B, C}, U = {u1, u2, u3, u4, u5}. u1 = (A, B), u2 = (A, B), u3 = (A, B), u4 = (B, C) et u5 = (C, C). G est un graphe ayant 3 sommets et 5 arcs. On appelle ordre du graphe le nombre n de ses sommets. • Un graphe est un p-graphe si ∀xi, xj sommets de G, le nombre d’arcs de xi vers xj est au maximum égale à p. • Une boucle est un arc de la forme (xi, xi). Dans l’exemple ci dessus, G est un 3-graphe avec une boucle (C, C). Dans le cas d’un 1-graphe, tous les éléments de U sont distincts et on peut alors déﬁnir G d’une manière fonctionnelle : Déﬁnition 1.2.2. Un graphe est un doublet G = (X, Γ) constitué par – X = {x1, . . . , xn} un ensemble ﬁni de sommets. – Γ fonction de X dans l’ensemble des parties de X. Ainsi, à tout sommet x est associé l’ensemble Γ(x) ⊂X. Γ(xi) = {xj ∈X : (xi, xj) ∈U}. Considérons le 1-graphe G : x1 x2 x3 x4 G peut être déﬁni par G = (X, Γ) où : Γ(x1) = {x2}, Γ(x2) = {x3, x4}, Γ(x3) = {x4} et Γ(x4) = ∅. Pour certaines applications, l’orientation des arcs importe peu : on s’intéressera aux paires de sommets reliés et on parle de graphe non orienté. Au lieu de parler d’un arc u = (x, y) on parle de l’arête e = [x, y]. On n’utilise pas la notation ensembliste {x, y} car elle désignerait le sommet x dans le cas où x = y et non pas l’arête. L’ensemble des arêtes d’un graphe non orienté est souvent noté E. 5 Recherche opérationnelle Prof. Hamid Zouaki Vocabulaire : Soit G = (X, U) un gaphe où X = {x1, . . . , xn}. • Si u = (xi, xj) est un arc de G, on dit que xi est l’extrémité initiale de u et xj l’extrémité terminale. • Un sommet xi est voisin d’un sommet xj s’ils appartiennet au même arc. On dit qu’ils sont adjacents. • Un sommet x est isolé s’il n’est voisin d’aucun sommet. • Un sommet x est pendant s’il n’existe qu’un seul arc qui le relie à un autre sommet. • Un arc u est incident à un sommet x vers l’extérieur, si x est l’extrémité initiale de u et l’extrémité terminale de u est diﬀérente de x. • Un arc u est incident à un sommet x vers l’intérieur, si x est l’extrémité ﬁnale de u et l’extrémité initiale de u est uploads/Science et Technologie/ zouaki.pdf