Remerciez-le!

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

´ Ecole Sup´ erieure de Technologie Industrielle D´ epartement de G´ enie Indus

´ Ecole Sup´ erieure de Technologie Industrielle D´ epartement de G´ enie Industriel Sp´ ecialit´ e : Maintenance et ﬁabilit´ e des syst` emes industriels Recherche Op´ erationnelle Notes de Cours Dr. Karabadji Nour El Islem Ann´ ee universitaire 2020-2021 GITHUB.COM/LAURETHTEX/CLUSTERING Ce manuscrit a ´ et´ e r´ edig´ e par Dr. Karabadji Nour EL islem maˆ ıtre de conf´ erences classe B ` a L’´ Ecole Superieure de Technologie Industrial Annaba pour servir comme support de cours aux ´ etudiants de 3e ann´ ee, Sp´ ecialit´ e Energetique et Developpement Durable. Deuxi` eme ´ edition aout 2018 Table des mati` eres 1 Introduction ` a la Recherche Op´ erationnelle . . . . . . . . . . . . . . . . . . . . . 5 2 Programmation lin´ eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 Formalisation 7 2.2 R´ esolution de probl` emes par voie graphique 9 2.2.1 Probl` eme ` a deux variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 Probl` eme ` a trois variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 R´ esolution de probl` emes par m´ ethode du simplexe 13 2.4 Exercices 17 3 Th´ eories des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1 Notions de base 24 3.1.1 Graphes non-orient´ es et orient´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.1.2 Voisinages et degr´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.3 Repr´ esentation d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.4 Chemins et cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.5 Connexit´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Quelques graphes remarquables 33 3.3 Arbre et arborescence 34 3.4 Cycles eul´ eriens et hamiltoniens 40 3.5 Coloration 41 3.5.1 Algorithme de coloration de Welch et Powell . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4 3.6 Plus courts chemins 43 3.6.1 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.6.2 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.7 Flots et r´ eseaux de transport 46 3.8 Probl` emes d’affectations 50 3.9 Exercices : 56 1. Introduction ` a la Recherche Op´ erationnelle Ces derni` eres ann´ ees, une grande attention a ´ et´ e prˆ et´ ee aux probl` emes d’optimisation com- binatoire, en raison de ces nombreuses applications dans le monde r´ eel. En effet, ces probl` emes interviennent souvent comme des sous-probl` emes ` a r´ esoudre dans plusieurs domaines, o` u nous avons toujours un besoin d’optimiser, planiﬁer ou prendre des d´ ecisions rapidement et sur tous les plans. Au niveau des entreprises et des industries, le contexte d´ ecisionnel se r´ esume en mati` ere de maxi- misation de gains et de minimisation de pertes. Pour r´ esoudre ce type de probl` emes d’optimisation, un certain nombre de m´ ethodes ont ´ et´ e propos´ ees. Ces m´ ethodes avaient principalement permis de d´ echarger l’ˆ etre humain de la p´ enible tˆ ache de chercher des solutions optimales parmi l’ensemble de toutes les conﬁgurations possibles. Pour r´ esoudre cette tˆ ache, une solution satisfaisante (ou un ensemble de solutions) est atteinte g´ en´ eralement en explorant toutes les conﬁgurations alternatives possibles sur un espace de recherche. Ce processus de recherche permet de r´ ecup´ erer soit une, ou plusieurs solutions, et peut mˆ eme ne pas renvoyer de solutions, et ce en corr´ elation avec les crit` eres de satisfactions exig´ es. ` A titre d’exemple, soit un ensemble de tˆ aches avec des temps d’ex´ ecutions connus, nous devons affecter les tˆ aches ` a des groupes d’employ´ es. Chaque tˆ ache peut ˆ etre conﬁ´ ee ` a un seul employ´ e ou ` a un groupe d’employ´ es c.-` a-d. un ou plusieurs employ´ es peuvent ˆ etre affect´ es ` a une mˆ eme tˆ ache. Chaque employ´ e peut travailler sur plusieurs tˆ aches, mais en revanche, il ne peut pas ex´ ecuter plusieurs tˆ aches simultan´ ement. L’objectif de cette affectation est d’ex´ ecuter l’ensemble des tˆ aches aussi rapidement que possible. Aﬁn de r´ esoudre efﬁcacement ce probl` eme d’ordonnancement, l’id´ ee est de minimiser le nombre d’employ´ es affect´ es ` a plusieurs tˆ aches diff´ erentes. Cela est dˆ u au fait que le temps d’ex´ ecution de l’ensemble des tˆ aches est alors ´ egal au temps de travail de l’employ´ e le plus occup´ e, ´ etant donn´ e qu’un employ´ e ne peut r´ ealiser qu’une tˆ ache ` a la fois. Par cons´ equent, la meilleure affectation est celle qui permet la restriction d’un nombre important (maximal) d’affecta- tions d’un mˆ eme employ´ e ` a plusieurs tˆ aches. Cependant, atteindre la meilleure affectation revient ` a la chercher parmi l’ensemble de toutes les affectations possibles. Ce nombre de combinaisons n´ ecessite un temps de calcul ´ enorme, et malgr´ e la puissance croissante des machines, l’exploration de 6 Chapitre 1. Introduction ` a la Recherche Op´ erationnelle toutes les combinaisons est toujours un cas d´ elicat et mˆ eme intraitable en pratique. Prenons comme exemple un groupe de n employ´ es, le nombre de combinaisons d’employ´ es possibles est 2n. Pour des donn´ ees de petite taille, il est possible d’explorer toutes les combinaisons dans le pire des cas, mais cela est pratiquement impossible pour des donn´ ees de grande taille. Avant de pr´ esenter le contenu de ce cours faisant un petit tour d’horizon historique, le commence- ment a ´ et´ e ` a partir de la Seconde Guerre mondiale, une m´ ethode d’optimisation (une premi` ere) a ´ et´ e d´ evelopp´ ee lors de l’´ elaboration des radars sous la direction de Watson-Watt. Celui-ci s’int´ eressait ` a l’utilit´ e des radars dans un contexte de d´ efense antia´ erienne et d’intervention de la chasse a´ erienne ` a la ﬁn des ann´ ees 1930. En 1940 aux ´ Etats unis, des groupes d’Operation Research furent cr´ e´ es dans les Etats Majors. Le but ´ etait d’organiser les convois, de mettre en place un blocus sur les ports japonais et de r´ epartir les ´ equipages des avions. Apr` es la guerre, la recherche op´ erationnelle a vu son champ d’application s’´ elargir au milieu ´ economique, ` a l’enseignement (Massachusetts Institue of Technologie), ` a certaines organisations (Society of America), etc. Dans les ann´ uploads/Industriel/ acfr.pdf