Remerciez-le!

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

Présenté par : Faiza Dib 1 Faculté des Sciences et Techniques d’Al Hoceima Rech

Présenté par : Faiza Dib 1 Faculté des Sciences et Techniques d’Al Hoceima Recherche Opérationnelle Master en Systèmes Embarqués et Robotique(SER) I. Introduction La Recherche Opérationnelle c'est une discipline moderne qui utilise : Des modèles mathématiques, statistiques Des algorithmes pour modeler et résoudre des problèmes complexes, en déterminant la solution optimale et en améliorant la prise de décisions. Cette matière reçoit aussi le nom de Recherche Opérationnelle ou Aide à la Décision. 2 Domaines d'application: - Production : maximiser le profit selon disponibilité de la main d’œuvre, demande du marche, capacité de production, prix de revient du matériaux brut. . - Transport : minimiser distance totale parcourue selon quantités de matériaux a transporter, capacité des transporteurs, points de ravitaillement en carburant. . . - Grande importance dans le milieu industriel : production, transport, emploi du temps, Ordonnancement dans l’industrie automobile, Un problème d’emballage Equilibrage des stocks, Planification de personnel Les Techniques de la recherche opérationnelle L'optimisation linéaire Programmation linéaire Programmation quadratique Programmation en nombres entiers Programmation dynamique L'optimisation non linéaire, L'optimisation stochastiques L'optimisation multicritères La théorie de réseaux et des graphes, etc I. Introduction 3 1. Détection de problème 2. formulation de problème 3. Elaboration d’un modèle 4. Collecte des données 5. Résolution du problème 6. Validation du modèle 7. La prise de décision et l’implémentatio n de la solution 4 I. Introduction 1. La détection d’un problème : Les nécessités de l’action viennent des expériences vécues ; c’est la phase préscientifique. 2. La formulation du problème : Quel est le vrai problème à résoudre ? Quels critères permettent de juger si le problème est résolu de façon satisfaisante ? 3. L’élaboration d’un modèle : Il s’agit de représenter les principaux aspects de la réalité par un ensemble de formules, mathématiques le plus souvent qui mettent en jeu les variables de décisions concernées et leurs interactions. On lance des hypothèses, on élabore une théorie, on écrit un modèle. C’est la phase de conceptualisation, de construction théorique ; en un mot, c’est la phase de modélisation. 4. La collecte des données : Il faut préciser les paramètres du modèle en s’appuyant sur l’information recueillie dans l’environnement du problème à résoudre. L’élaboration du modèle s’éclaire à la lanterne des données. Le processus peut requérir plusieurs cycles impliquant les étapes 3, 4 et 5. I. Introduction 5 5. La résolution du modèle : C’est la phase où l’on souhaite recourir aux méthodes appropriées déjà disponible si on a réussi à classer le problème parmi ceux pour lesquels, on connait déjà une méthode d’approche. Sinon, il faut recourir à la simulation ou inventer une technique de résolution. 6. La validation du modèle : On confronte les conclusions obtenues du modèle aux opinions des personnes qui ont suffisamment d’expérience du problème traité pour apprécier ou critiquer la pertinence de la solution proposée. Si les avis reçus sont négatifs, on peut alors remettre en cause soit l’écriture du modèle retenu, soit la valeur de ses paramètres, soit le critères d’appréciation de la solution. On peut aller jusqu’à remettre en cause l’approche choisie pour résoudre le problème et partant le modèle retenu. 7. La prise de décision et l’implémentation de la solution : Comment implémenter la solution obtenue ? Doit-on s’arrêter là ? Il y a ici un retour possible vers le modèle initial pour le modifier ou l’enrichir des observations faites lors de la phase expérimentale. Une fois les révisions nécessaires apportées, le modèle enrichi permettra de tirer des conclusions mieux étayées. 6 I. Introduction • Du point de vue mathématique, on appelle problème de programmation linéaire tout problème dans lequel il s’agit d’optimiser (c’est-à-dire de maximiser ou minimiser selon le cas) une fonction de plusieurs variables, linéaires par rapport à l’ensemble de ces variables, celles-ci devant satisfaire à un ensemble des contraintes linéaires. • la programmation linéaire est une technique mathématique d’optimisation (maximisation ou minimisation) de fonction objectif linéaire sous des contraintes ayant la forme d’inéquations linéaires. Elle vise à sélectionner parmi différentes actions celle qui atteindra le plus probablement l’objectif visé. • Les problèmes de la programmation linéaire (PL) se posent lorsque l’on cherche à rendre optimale (minimum ou maximum) une fonction linéaire de plusieurs variables, ces variables étant assujetties à des contraintes linéaires, c’est à dire, du premier degré. Soulignons à ce propos, qu’une contrainte est linéaire, lorsqu’elle s’exprime par une égalité ou inégalité dont le premier membre est une combinaison linéaire et le second, un nombre réel. • Remarque : C’est grâce à cette méthode que les problèmes de ravitaillement étaient résolus pendant la seconde guerre mondiale. II. Programmation linéaire: • Exemple Une compagnie est spécialisée dans la production de deux types de produits : des climatiseurs et des ventilateurs. Les deux produits nécessitent un certain nombre d’heures de main d’œuvre. Le tableau suivant donne les informations nécessaires sur les deux produits, c’est-à dire les nombres d’heures machine et d’heures main d’œuvre nécessaires à la fabrication d’une unité de chacun de ces produits, ainsi que le profit généré par la production d’une unité de ce produit. Le tableau nous donne aussi le nombre total d’heures machines et d’heures main d’œuvre disponibles. Heures machine Main d’œuvre Profit Climatiseur 2 h/unité 3 h/unité 25 DH/unité Ventilateur 2 h/unité 1 h/unité 15 DH/unité Total disponible 240 h 140 h 8 II. Programmation linéaire: 1. Formulation du programme linéaire a) Variables de décision : doivent complètement décrire les décisions à prendre. La compagnie veut décider du nombre de climatiseurs et du nombre de ventilateurs à produire pour maximiser le profit. Ceci nous amène à choisir les deux variables de décision suivantes : x1 = nombre de climatiseurs x2 = nombre de ventilateurs 9 II. Programmation linéaire: b) Fonction objectif : Dans n’importe quel programme linéaire, le responsable de décision veut maximiser (en général, le revenu ou profit) ou minimiser (en général le coût) une fonction des variables de décisions. Cette fonction est appelée “ fonction objectif ”. L’objectif de l’entreprise est de déterminer le programme de production qui maximisera son profit (Z=profit). La fonction objectif s’écrit alors: Max Z = 25x1 + 15x2 10 II. Programmation linéaire: c) Contraintes du modèle : La limitation des ressources contraint l’entreprise de la manière suivante : 1) Contraintes heure machine 2x1 + 2x2 ≤ 240 2) Contrainte main d’œuvre 3x1 + x2 ≤ 140 3) Contraintes de non-négativité (exprimant que les niveaux d’activité ne peuvent être négatifs) x1 ≥ 0, x2 ≥ 0 Modèle complet : x1 = nbre de climatiseurs, x2 = nbre de ventilateurs Max Z = 25 x1 + 15 x2 sous contraintes 2x1 + 2x2 ≤ 240 3x1 + x2 ≤ 140 x1 ≥ 0, x2 ≥ 0 11 II. Programmation linéaire: Enonce du problème Une entreprise fabrique deux produits A et B, en utilisant une machine m et deux matières premières p et q. On dispose chaque jour de 8 heures de m, de 10 kg de p et de 36 kg de q. On suppose que : — la production d’une unité de A nécessite 2 kg de p et 9 kg de q, et utilise la machine m durant 1 heure ; — la production d’une unité de B nécessite 2 kg de p et 4 kg de q, et utilise la machine m durant 2 heure ; — les profits réalisés sont de 50 dh par unité de A et 60 dh par unité de B. II. Programmation linéaire: L’objectif que poursuit l’entreprise est de maximiser le profit qu’elle pourra tirer, par jour, de ces 2 produits en utilisant au mieux ses ressources. Le tableau suivant résume les données afférentes à ce problème de production : La construction d’un modèle linéaire x1 = la quantité du produit A à produire x2 = la quantité du produit B à produire Les variables x1 et x2 sont dites variables de décision. 13 Le tableau suivant résume les données afférentes à ce problème de production : II. Programmation linéaire: A B Disponible m 1 h 2 h 8 h p 2 kg 2 kg 10 kg q 9 kg 4 kg 36 kg Profit unitaire 50 dh 60 df Quel profit l’entreprise retirera-t-elle de la vente de ces deux produits ? Il s’agit d’additionner les bénéfices à tirer de chacun des 2 produits : — pour le produit A, elle retire 50 dh par unité et en fabrique x1 unités ; cette production lui rapporte donc un profit de (50 x1) dh ; — de même, la quantité x2 du produit B lui permet de faire un profit de (60 x2) dh. Le profit total à tirer des deux produits s’élève donc à : (50 x1 + 60 x2) dh Nous dénoterons ce profit total par z et laisserons implicite l’unité monétaire : z = 50 x1 + 60 x2 Nous cherchons évidemment à rendre z aussi grand que possible en donnant à x1 et x2 des valeurs appropriées. 14 II. Programmation linéaire: 15 La grandeur z est une fonction qui, à chaque plan de production (une quantité de A, une quantité de B), uploads/Industriel/ cours-ro-p1.pdf