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´ erationnelle Master 2 LT, MPM, MIR Universit´ e du Littoral - Cˆ

Recherche op´ erationnelle Master 2 LT, MPM, MIR Universit´ e du Littoral - Cˆ ote d’Opale, Pˆ ole Lamartine Laurent SMOCH (smoch@lmpa.univ-littoral.fr) Septembre 2013 Laboratoire de Math´ ematiques Pures et Appliqu´ ees Joseph Liouville Universit´ e du Littoral, zone universitaire de la Mi-Voix, bˆ atiment H. Poincarr´ e 50, rue F. Buisson, BP 699, F-62228 Calais cedex 2 Table des mati` eres 0 Introduction g´ en´ erale 1 1 La programmation lin´ eaire - M´ ethode graphique 7 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Mod´ elisation d’un programme lin´ eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Formule g´ en´ erale d’un programme lin´ eaire . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 M´ ethode graphique : probl` eme ` a deux inconnues . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.1 R´ egionnement du plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.2 Les ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.3 R´ esolution de syst` emes d’in´ equations - Exemples . . . . . . . . . . . . . . . . . . . . . 12 1.3.4 R´ esolution de programmes lin´ eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.5 Cas g´ en´ eral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 I II TABLE DES MATI` ERES Chapitre 0 Introduction g´ en´ erale La recherche op´ erationnelle (aussi appel´ ee “aide ` a la d´ ecision”) peut ˆ etre d´ eﬁnie comme l’ensemble des m´ ethodes et techniques rationnelles orient´ ees vers la recherche de la meilleure fa¸ con d’op´ erer des choix en vue d’aboutir au r´ esultat vis´ e ou au meilleur r´ esultat possible. Elle fait partie des “aides ` a la d´ ecision” dans la mesure o` u elle propose des mod` eles conceptuels en vue d’ana- lyser et de maˆ ıtriser des situations complexes pour permettre aux d´ ecideurs de comprendre et d’´ evaluer les enjeux et d’arbitrer et/ou de faire les choix les plus eﬃcaces. Ce domaine fait largement appel au raisonnement math´ ematique (logique, probabilit´ es, analyse des donn´ ees) et ` a la mod´ elisation des processus. Il est fortement li´ e ` a l’ing´ enierie des syst` emes, ainsi qu’au management du syst` eme d’information. La recherche op´ erationnelle trouve son origine au d´ ebut du XXe si` ecle dans l’´ etude de la gestion de stock avec la formule du lot ´ economique (dite formule de Wilson) propos´ ee par Harris en 1913. Mais ce n’est qu’avec la seconde guerre mondiale que la pratique va s’organiser pour la premi` ere fois et acqu´ erir son nom. En 1940, Patrick Blackett est appel´ e par l’´ etat-major anglais ` a diriger la premi` ere ´ equipe de recherche op´ erationnelle, pour r´ esoudre certains probl` emes tels que l’implantation optimale de radars de surveillance ou la gestion des convois d’approvisionnement. Le qualiﬁcatif “op´ erationnelle” vient du fait que la premi` ere application d’un groupe de travail organis´ e dans cette discipline avait trait aux op´ erations militaires. Apr` es la guerre, les techniques de RO-AD se sont consid´ erablement d´ evelopp´ ees grˆ ace, notamment, ` a l’ex- plosion des capacit´ es de calcul des ordinateurs. Les domaines d’application se sont ´ egalement multipli´ es. Citons quelques m´ ethodes : • Plus court chemin (Shortest path) : En th´ eorie des graphes, l’algorithme de Dijkstra sert ` a r´ esoudre le probl` eme du plus court chemin. Il permet par exemple, de d´ eterminer le plus court chemin pour se rendre d’une ville ` a une autre connaissant le r´ eseau routier d’une r´ egion. Il s’applique ` a un graphe connexe dont le poids li´ e aux arˆ etes est un r´ eel positif. L’algorithme porte le nom de son inventeur, l’informaticien n´ eerlandais Edsger Dijkstra et a ´ et´ e publi´ e en 1959. Exemple 0.0.1 Un “serial traveller” am´ ericain recherche le plus court chemin entre Boston et Los Angeles. On donne dans la carte ci-dessous les diﬀ´ erents axes qu’il souhaite emprunter. Figure 1 – Carte des ´ Etats-Unis Quel est le trajet optimal ? 1 2 CHAPITRE 0. INTRODUCTION G´ EN´ ERALE • Voyageur de commerce (TSP - Traveling-Salesman Problem) : En partant d’un groupe de villes donn´ ees, il consiste ` a visiter une fois chacune des villes (une seule et unique fois) tout en minimi- sant la distance de vos d´ eplacements. Ce probl` eme qui paraˆ ıt ` a tord ´ el´ ementaire est eﬀectivement anodin pour un petit nombre de villes, mais, lorsque vous ajoutez d’autres villes, le nombre de che- mins possibles cr` eve le plafond. Il ne faut donc pas s’´ etonner si le probl` eme du voyageur de commerce est class´ e dans la cat´ egorie des probl` emes NP-complets. Dans ce probl` eme, le nombre de chemins hamiltoniens est ´ egal ` a n!/2 o` u n correspond au nombre de villes qui composent le probl` eme. Une so- lution g´ en´ erale eﬃciente n’a pas encore ´ et´ e d´ ecouverte. Les math´ ematiciens ont conclu que le meilleur moyen ´ etait d’utiliser un algorithme avec des polynˆ omes variant en rapport avec le nombre de villes. ` A l’heure actuelle, la meilleure solution varie de fa¸ con exponentielle en fonction du nombre de villes. Exemple 0.0.2 Un voyageur de commerce, bas´ e ` a Toulon, doit visiter ses clients ` a travers la France : Figure 2 – Localisation g´ eographique des clients Quelle tourn´ ee le voyageur de commerce doit-il eﬀectuer aﬁn qu’elle soit la plus courte possible ? • Mariages stables (Stable Marriage problem) : On se donne deux ensembles A et B ayant chacun n ´ el´ ements. On se donne aussi, pour chaque ´ el´ ement de A et B, une fonction de pr´ ef´ erence, qui classe les ´ el´ ements de l’autre ensemble. On cherche alors ` a associer de fa¸ con bijective les ´ el´ ements de A avec ceux de B, pour qu’il n’existe pas a ∈A et b ∈B tels que a pr´ ef` ere b ` a l’´ el´ ement qui lui est associ´ e, et b pr´ ef` ere a ` a l’´ el´ ement qui lui est associ´ e. Exemple 0.0.3 On consid` ere 3 femmes (Alice, B´ en´ edicte et Camille) et 3 hommes (Dominique, Elie et Fran¸ cois) dont voici les pr´ ef´ erences respectives : Pr´ ef´ erences des femmes Pr´ ef´ erences des hommes A : F D E D : A B C B : E D F E : B C A C : F D E F : A C B Table 1 – Pr´ ef´ erences des femmes et des hommes Comment doit-on organiser les couples ? • L’optimisation des ﬂux et l’algorithme de Ford-Fulkerson : L’algorithme de Ford-Fulkerson, du nom de ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une proc´ edure it´ erative qui permet de d´ eterminer un ﬂot (ou ﬂux) de valeur maximale (ou minimale) ` a partir d’un ﬂot constat´ e. Ce uploads/Science et Technologie/ recherche-operationnelle-chap1-pdf.pdf