Remerciez-le!

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

ENCG AGADIR 2020-2021 1 La recherche opérationnelle Semestre 7 Pr. A. LAHFIDI P

ENCG AGADIR 2020-2021 1 La recherche opérationnelle Semestre 7 Pr. A. LAHFIDI Pr. A. AAZZAB Présentation du syllabus ENCG AGADIR 2020-2021 2 1. Pré-requis Algèbre linéaire, calcul matriciel et statistique 2. Objectif du cours Ce cours représente une introduction à la recherche opérationnelle et ses applications dans le domaine de l’industrie, du transport, de la finance et de la gestion. L’objectif général de ce cours est de mettre à la disposition des encgistes les outils nécessaires à la modélisation et à la résolution des problèmes du monde réel en exploitant des méthodes et techniques mathématiques et numériques de résolution de problèmes d’optimisation et leurs applications en sciences de gestion. Présentation du syllabus ENCG AGADIR 2020-2021 3 Compétences générales visées Le cours de la recherche opérationnelle vise à développer chez les étudiants les qualités suivantes : Développer une démarche scientifique complète de RO ; Formuler et modéliser les problèmes quotidiens de gestion ; Proposer des méthodes d'optimisation ou d'aide à la décision adaptées au contexte ; Exploiter les différentes techniques d’optimisation à la résolution des problèmes. Présentation du syllabus ENCG AGADIR 2020-2021 4 Moyens pédagogiques Manuels pédagogiques de base disponible sous format pdf : Robert Faure, Précis de recherche opérationnelle Méthodes et exercices d’application, Dunod, Paris, 2014. Notes de cours pour chaque séance ; Apprentissage en hybride (en présentiel et en distanciel) ; Utilisation du vidéo projecteur et du tableau blanc ainsi que d’autres outils d’apprentissage à distance ; Des séries d’exercices sont données aux étudiants avant de les corriger. Présentation du syllabus ENCG AGADIR 2020-2021 5 Plan du cours : Chapitre 1: La Programmation Linéaire Formulation des programmes linéaires Méthode de résolution graphique Méthode de résolution algébrique : Algorithme du simplexe Problème de dualité en programmation linéaire Aspect matriciel de la programmation linéaire Chapitre 2 : Introduction à la théorie des graphes Éléments de théorie des graphes Décomposition des graphes Problèmes d'ordonnancement Introduction Modélisation par un graphe orienté Construction et résolution du diagramme de PERT Diagramme Gantt Problème du plus court chemin Définition du problème de plus court chemin dans un graphe Algorithmes de résolution Présentation du syllabus ENCG AGADIR 2020-2021 6 Évaluation Travaux à rendre 30% Participation & Assiduité 20 % Examen final 50 % TOTAL 100% Introduction générale Définitions de la Recherche Opérationnelle : La RO peut se définir comme « la mise en œuvre de méthodes scientifiques, essentiellement mathématiques, en vue de prendre la meilleure décision possible. » Association Française de Recherche Opérationnelle et d'Aide à la Décision (2011) La RO peut se définir comme «la science de la bonne gestion. C’est un ensemble des domaines scientifiques traitant des questions d’ordre décisionnel ou d’optimisation de systèmes complexes.» La Fédération Européenne de Recherche Opérationnelle Exemples : chercher un itinéraire sur une carte, ordonnancement des tâches, la décision stratégique en finance … ENCG AGADIR 2020-2021 7 Introduction générale Histoire : les problèmes de RO remontent au XVIème siècle (Blaise Pascal, Euler,...) avec les jeux en Mathématiques. Origine de la méthode : Domaine militaire (l'implantation optimale de radars de surveillance durant la 2ème guerre mondiale) Domaine d’application : La gestion de projets : problèmes d'ordonnancement et de planification de projets, problèmes de logistique et de transport et problèmes d'emploi du temps... L’industrie manufacturière : plans de productions (ordonnancement ), problèmes de découpe (optimisation des ressources), optimisation du conditionnement et la livraison… La finance : les problèmes de financement et d'investissement (maximiser le profit et/ou minimiser les coûts)… … ENCG AGADIR 2020-2021 8 Introduction générale Étapes générales d’un problème de RO Étape 1: observation, collecte des données et formulation du problème. Étape 2 : construction d’un modèle scientifique (formulation mathématique). Étape 3 : résoudre le problème en testant le modèle développer en donnant une solution optimale. ENCG AGADIR 2020-2021 9 Définition En mathématiques, les problèmes de programmation linéaire (PL) est la recherche de l’optimum (minimum ou maximum) d’une fonction d’objectif linéaire liées par des équations ou inéquations linéaires appelées contraintes. La fonction d’objectif On appelle fonction d’objectif, ou fonction économique, d’un problème d’optimisation le critère de choix entre les diverses solutions possibles. Les contraintes On appelle contraintes du problème toutes les relations limitant le choix des valeurs possibles des variables. Ce sont des restrictions de nature techniques, économiques ou logiques. Chapitre 1 : la programmation linéaire La forme générale d’un problème linéaire : 1- Formulation mathématique d’un programme linéaire                                                      négativité non de s contrainte ,..., 2 , 1 ; 0 , , x a ... x a x a ... , , x a ... x a x a , , x a ... x a x a , , x a ... x a x a : s contrainte Sous ... Min ou Max n mn 2 m2 1 m1 3 n 3n 3 32 1 31 2 n 2n 2 22 1 21 1 n 1n 2 12 1 11 2 2 1 1 n j x b b b b x c x c x c Z j m n n La forme générale d’un problème linéaire : Z : la fonction économique (fonction d’objectif); c1, c2, …, cn : les coefficients des variables de la fonction Z x1, x2, …, xn : les variables inconnues du modèle; a11, a12, …, amn : les coefficients des variables pour les contraintes du modèle; b1, b2, …, bm : les quantités disponibles de chaque ressource. 1- Formulation mathématique d’un programme linéaire La forme matricielle d’un problème linéaire : 1- Formulation mathématique d’un programme linéaire     : , , : s contrainte Sous Min ou Max avec B AX CX Z                                                 m mn m m n n n b b b B a a a a a a A c c c C x x x X . ; . . . . . . ; . ; . 2 1 2 1 1 12 11 2 1 2 1 1- identifier les variables associées au problème ; 2- formuler les contraintes qui délimitent les valeurs que peuvent prendre les variables ; 3- Formuler la fonction économique linéaire qui mesure l’efficacité des variables. Étapes de construction d’un programme linéaire : • Soit une firme produisant deux biens A et du B avec trois types de matières premières M1, M2 et M3, selon le tableau suivant : Formuler le modèle linéaire qui permet de déterminer les quantités à produire pour maximiser le gain par unité Exemple d’application (1) A B Stocks M1 2 1 8 M2 1 2 7 M3 0 1 3 Gain / unité 4 5 Solution : 1- identification des variables : Les variables sont les quantités x1 et x2 des biens fabriqués A et B. 2- formulation des contraintes : Quelques soient les quantités produites des deux biens, il ne faut pas dépasser les quantités de matières premières disponibles dans les stocks Contraintes techniques Ou de capacité : Contraintes de non négativité Exemple d’application (1)                   3 3 2 7 2 1 8 2 2 2 1 2 1 M pour x M pour x x M pour x x      0 0 2 1 x x Solution : 3- identification de la fonction d’objectif (fonction économique) : L’objectif de cette firme est de maximiser la fonction Z qui représente le gain : Le gain du bien A est de 4x1 Le gain du bien A est de 5x2 Donc Z= 4x1 + 5x2 Exemple d’application (1) Solution : Programme linéaire est de : Exemple d’application (1)                   0 0 3 7 2 8 2 : 5 4 2 1 2 2 1 2 1 2 1 x x x x x x x SC x x Z Max • Une entreprise peut utiliser 2 usines pour fabriquer un certain produit. La capacité de fabrication de chaque usine en temps régulier est la suivante : L’entreprise alimente 3 entrepôts dont les capacités maximales de stockage : Les coûts unitaires de transport sont : Exemple d’application (2) Usines Capacités en unités Coût unitaire U1 1800 7 U2 2200 6 Entrepôts Usines E1 E2 E3 U1 6 4 7 U2 5 3 2 Entrepôts Capacité de stockage en unités E1 1500 E2 2000 E3 1800 Question : Formuler le modèle linéaire qui permet de déterminer les quantités à uploads/Management/ cours.pdf