Remerciez-le!

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

1 EFREI-L3 Introduction au cours "Optimisation et complexité" F. Huet (recherch

1 EFREI-L3 Introduction au cours "Optimisation et complexité" F. Huet (recherche opérationnelle = RO) I. Définition RO : la recherche opérationnelle est un outil d’aide à la décision qui permet d'optimiser une fonction économique en présence de contraintes multiples. remarque : la RO prend des formes très diverses en univers certain ou univers aléatoire. règle : - les choix des objectifs + critère d’optimisation sont à la charge de l'entrepreneur - la RO consiste à trouver l’optimum. II. Domaines d’application 1) Domaine combinatoire : le but est d'éviter l’énumération des solutions (affecter 25 secrétaires à 25 postes → 25! ≈ 1,5 1025 solutions : 1 solution/µs → 5 109 siècles) • Chemin optimal dans un graphe valué : trouver le chemin le moins (plus) cher pour aller de A à B. • Problème d’ordonnancement : pour la réalisation d'un projet consistant à accomplir des tâches soumises à des contraintes (d'antériorité, de dates…), trouver l'ordre des tâches, la solution la moins longue (et/ou la moins chère), les marges de réalisation des tâches… • Problème de flot maximal dans un réseau de transport (graphe valué avec E/S) : acheminer le plus possible de marchandises de E vers S compte tenu des capacités de transport de chaque arc. • Problème d'affectation : pour 25 personnes à affecter dans 25 postes : chaque personne donne ses préférences (classement de 1 à 25) et on cherche une solution satisfaisant le plus possible de personnes. • Problème de transport : trouver les quantités xij à transporter depuis m usines vers n distributeurs pour minimiser la somme des coûts de transport. • Problème du voyageur de commerce : trouver le parcours minimisant le coût total (déplacement + hôtel) du voyageur qui doit visiter tous ses clients et revenir chez lui. 2) Domaine aléatoire : le hasard intervient (→ probabilité, espérance, processus stochastique…) • Files d'attente (grandeurs aléatoires de base : instants d'arrivée des clients, durée du service) : optimiser le compromis entre le nombre de serveurs et la durée d'attente des clients. • "Fiabilité" = usure et renouvellement des équipements (grandeurs aléatoires : instants des pannes, durée des réparations) : optimiser le compromis entre le coût des arrêts du matériel et le taux de renouvellement du matériel. • Gestion des stocks (grandeurs aléatoires : instants des demandes de pièces, quantités demandées) : optimiser le compromis entre le coût de stockage et le coût des ruptures de stock. 3) Domaine combinatoire continu : la variable est réelle (non entière) • Programmation mathématique linéaire (ou non linéaire) : par exemple, pour calculer le nombre de produits de plusieurs types fabriqués par la même machine pour maximiser un bénéfice avec des contraintes de fabrication et de vente. 2 Conclusion : RO = discipline carrefour entre mathématiques : algèbre de Boole, algèbre linéaire, théorie des graphes, probabilités, processus stochastiques. informatique : l'informatique est un outil pour la RO (algorithmes rapides) ; la RO est un outil pour l'informatique (problème de files d'attentes). économie. III. Bref historique et bibliographie succincte • La RO est une technique récente : Blackett (1940) pour optimiser l'emplacement des radars pour prévenir l'arrivée des bombardiers allemands. • La plupart des outils mathématiques existaient déjà : Pascal et Fermat (1654) : espérance mathématique Monge (1776) : problème des déblais et remblais Borel (1921-1925) : théorie mathématique des jeux Erlang (1917) : théorie des files d'attente (réseau téléphonique) Kantorovitch (1930-1940) : programmation linéaire pour planification König (1936) : théorie des graphes. • Gros développements depuis l’apparition des ordinateurs (1955-56). Il existe deux écoles : américaine et française (Robert Faure). • Bibliographie : - R. Faure , J-P. Boss , A. Le Garff, La recherche opérationnelle, Que sais-je n° 941 (PUF), 1974. - V. Cohen, La recherche opérationnelle, Que sais-je n° 941 (PUF), 1995. - R. Faure, B. Lemaire, C. Picouleau, Précis de recherche opérationnelle : Méthodes et exercices, Dunod, 5ème édition, 2004 (1ère édition 1979). - A. Alj et R. Faure, Guide de la recherche opérationnelle. Tome 1, les fondements, Masson 1986. - A. Alj et R. Faure, Guide de la recherche opérationnelle. Tome 2, les applications, Masson 1990. - Roseaux, Exercices et problèmes résolus en recherche opérationnelle Tome 1, Graphes : leurs usages, leurs algorithmes, Dunod 2005 (1ère édition 1983). Tome 2, Phénomènes aléatoires en RO, Dunod 2004 (1ère édition 1983). Tome 3, Programmation linéaire et extensions, Dunod 2003 (1ère édition 1985). IV. Plan du cours (12 h cours, 14 h TD, TAI) • Chapitre 1 : applications de la théorie des graphes - programmation dynamique pour problèmes de décision séquentielle - chemin optimal (voir le cours sur les graphes) - méthodes d’ordonnancement (MPM, PERT) - problème de flot maximal dans un réseau (Ford-Fulkerson) - problèmes d’affectation (méthode hongroise) - problèmes de transport (stepping -stone) • Chapitre 2 : phénomènes aléatoires en recherche opérationnelle - files d’attente • Chapitre 3 : programmation mathématique linéaire - méthode des tableaux (simplexe). 3 Chapitre 1. Applications de la théorie des graphes I. Programmation dynamique 1) Généralités • Principe : "tout sous-chemin d'un chemin optimal est forcément optimal". Dn : Soit un chemin optimal AB (trait plein). On suppose qu'il existe un sous-chemin CD en pointillés meilleur que le sous-chemin CD en trait plein → le chemin total en pointillés serait meilleur que le chemin initial optimal en trait plein, ce qui est contraire à l'hypothèse. • Ancien (Fermat, Euler, Lagrange) mais mise en pratique récente : Masse (1944), Bellman (1950- 1957)… • Intérêt : - résoudre des problèmes de décisions séquentielles (prises l'une après l'autre). - atténuer le caractère combinatoire du problème (sous-chemins non optimaux non traités). • Application aux problèmes discrets (graphes) ou continus, en univers certain ou aléatoire. 2) Exemple simple (Roseaux, tome 1 p. 61) énoncé : Une voie de chemin de fer doit être construite entre les villes A et L. Trouver les villes intermédiaires pour que le coût de construction soit minimal (coût 0 = voie déjà construite). remarques : - pas de retour en arrière, - les arcs vont tous d'un rang i à un rang i+1. → apparition de phases : à chaque phase i, on va choisir le meilleur chemin allant de A vers chacun des sommets de la phase i. → on construit progressivement (= dynami- quement) le chemin optimal de A à L par des décisions séquentielles. • Algorithme. Notations : si la ville de niveau i : s0 = A, s1 ∈ {B, C, D}, s2 ∈ {E, F, G, H}, s3 ∈ {I, J, K}, s4 = L vi+1(si, si+1) : valuation de si à si+1 f(si) : coût minimal de construction de A à si Principe : - on calcule f1(s1) = v1(A, s1) pour s1 ∈ {B, C, D} - on calcule f2(s2) = Min (f1(s1) + v2(s1, s2)) pour chaque s2 ∈ {E, F, G, H} s1 antécédent de s2 - de même : f3(s3) = Min (f2(s2) + v3(s2, s3)) pour chaque s3 ∈ { I, J, K} s2 antécédent de s3 (f3(s3) ne dépend plus de s1) B A C D 4 Intérêt de la méthode : - lecture de fi(si) dans la case mémoire allouée - élimination des chemins non-optimaux. les sommets doivent être préalablement ordonnés par rang (de i à i+1). 3) Deuxième exemple : problème du sac à dos (Roseaux, tome 1 p. 71) • énoncé : un randonneur veut remplir son sac à dos en maximisant la valeur nutritive totale du sac sans dépasser le poids de 15 kg. On dispose de 3 aliments avec les caractéristiques suivantes : aliment 1 2 3 Poids pi (kg) 6 3 9 Valeur nutritive ci 15 10 35 Soit xi le nombre de boites retenues pour l'aliment i. On cherche les xi qui maximisent c1 x1 + c2 x2 + c3 x3 sous la contrainte de poids p1 x1 + p2 x2 + p3 x3 ≤ 15. • Problème de programmation dynamique (ou programmation mathématique linéaire, cf. chapitre 3) car on va faire un choix successif des valeurs de x1 (phase 1), puis de x2 (phase 2), puis de x3 (phase 3). • Notation : yi = état du système (poids du sac) après la phase i (y0 = 0) phase 1 phase 2 phase 3 choix de x1 choix de x2 choix de x3 ↓ ↓ ↓ y0 = 0 → y1 → y2 → y3 retour élémentaire c1 x1 c2 x2 c3 x3 état du sac y1 = p1 x1 y2 = y1 + p2 x2 y3 = y2 + p3 x3 • But : ∑ − − = + + i i i i i 3 3 2 2 1 1 y y p c x c x c x c ) ( Max ) ( Max 1 de la forme générale ∑ − − i i i i y y v ) ( 1 construction du graphe : pour Oy il faut prendre l'état du système (ici le poids yi) : le choix de yi n'est pas toujours simple. • uploads/Ingenierie_Lourd/ plet-opti.pdf