Réalisé par : EL IDRISSI Aziz NB : D’après le Cours de Recherche Opérationnelle

Réalisé par : EL IDRISSI Aziz NB : D’après le Cours de Recherche Opérationnelle de la faculté de AIN CHOCK route d’EL JADIDA (5ème semestre) TABLE DES MATIÈRES Table des Matières ..................................................................................................................... 2 Introduction : ............................................................................................................................... 3 Partie I : programmation linéaire ............................................................................................... 3 Partie II : Algorithme du simplexe : ............................................................................................ 8 Introduction : .......................................................................................................................... 8 Résolution simplexe du P.L : .................................................................................................. 8 Notion dualité : ...................................................................................................................... 12 partie III : Gestion de projet ..................................................................................................... 14 Introduction : ......................................................................................................................... 14 Méthode P.E.R.T temps (gestion optimale du temps de réalisation d’un projet) ................. 14 Notion de tache critique : ...................................................................................................... 16 2 INTRODUCTION : La recherche opérationnelle est un ensemble de méthodes d’analyse scientifiques tournées vers la recherche de la meilleur façon d’approcher les problèmes afin d’aboutir aux meilleurs solutions. Les deux classes de problèmes traités dans ce cours sont : I – la programmation linéaire : qui consiste à gérer de façon optimale les systèmes de production qui évoluent de façon proportionnelle. II – Ordonnancement et planification optimale : des temps de réalisation d’un projet par la méthode P.E.R.T (Program Evaluation and Reviews techniques). PARTIE I : PROGRAMMATION LINÉAIRE Exemple de travail Exemple de travail : : Enoncé : la conception de la production de deux types de pièces P1 et P2 a été décidée selon la fiche technique et financière suivante : Pièces à produire Heures machines de fabrication P1 P2 Disponibilité Maximale en H. machine M1 5 3 270 M2 4 6 360 Prix de vente unitaire des pièces produites 1500 DH 1800 DH TAF : 1 – formuler le problème de l’entreprise qui cherche à maximiser leur CA global en respectant les disponibilités en facteurs de production M1 et M2. 2 – donner la solution optimale du problème ainsi que son interprétation économique. Réponse : 1 – Formulation du problème (démarche à suivre) : 1 / Définition de l’objectif : Maximiser le CA global qui est fonction des quantités à produire en P1 et P2. 2/ Définition des variables économiques (V.E) : X1 : quantité de pièces P1 à produire ; X2 : quantité de pièces P2 à produire. 3/ Définition de la fonction économique : Max Z : 1500 X1+1800X2 4/ Définition des contraintes : 5X1 + 3X2≤270 (Disponibilité en H machine M1) 4X1+6X2≤360 (Disponibilité en H machine M2) X1≥0 ; X2≥0 (contrainte de positivité) 3 D’où le programme linéaire (P.L) à résoudre : Max Z : 1500 X1+1800X2 5X1 + 3X2≤270 (Disponibilité en H machine M1) (P) (0;90) ;(54;0) (D) 4X1+6X2≤360 (Disponibilité en H machine M2) (0;60) ; (90;0) X1≥0 ; X2≥0 (contrainte de positivité) 2 - Résolution graphique du (P.L) (P) : -20 0 20 40 60 80 100 0 10 20 30 40 50 60 70 80 90 100 A B Commentaire : Le domaine (D) est l’ensemble des points admissibles c'est-à-dire l’ensemble des points qui vérifient toutes les contraintes. Le domaine (D) du problème est borné. Les points O, A, B, C sont appelés les points sommets du (D). Théorème d’optimalité : On démontre que si solution optimale existe, elle est obligatoirement l’une des points sommets. Lecture de la solution optimale par la méthode des sommets : 4 Disponibilité = Capacité maximale = au maximum  ≤ Quantité requise = Capacité minimale=au minimum ≥ D « B » est l’intersection des droites frontières (1) et (2) donc ses coordonnées sont solution du système d’équation (1) 5x1 + 3x2 = 270 (2) 4x1+ 6x2 = 360 e1 = 270 – (5x1 + 3x2) e2 = 360 – (4x1 + 6x2) Interprétation économique de la solution optimale : Pour réaliser un CA maximal de 117 000 DH on doit produire 30 unités de pièces P1 et 40 unités de pièces P2 avec plein emploi en heures machines M1 et M2 Cas n ° 2 : Enoncé : Dans une exploitation agricole, on doit choisir entre 2 types d’engrais A et B pour fertiliser un hectare de terre. Celui-ci requiert au moins 60 kg de potassium, 120 Kg de calcium et 90 Kg de sodium par hectare. • dans un paquet d’engrais A, il y a 1Kg de potassium, 3 Kg de calcium et 3 Kg de sodium • dans un paquet B, il y a 2 Kg de potassium, 2 Kg de calcium et 1 Kg de sodium. Les coûts d’achat unitaires sont de 100 DH pour le paquet de A et 100 DH pour le paquet B. TAF : 1 – formuler le problème qui permet de réaliser la fertilisation souhaitée au moindre coût en respectant les contraintes d’exploitation. 2 – par une résolution graphique, donner et interpréter la solution optimale du problème. Paquets d’engrais A B Quantités requises en produits chimiques Potassium 1 2 60 Calcium 3 2 120 Sodium 3 1 90 Coût d’achat unitaire des paquets en DH 100 100 1- Formulation du problème Calcul des écarts Coordonnées du sommet S Valeur de Z au sommet Si : Zs Ecart en M1 :e1 Ecart en M2 : e2 O (0 ;0) 0 DH 270 H 360 H A (0 ; 60) 108 000 DH 90 H 0 H B (30 ; 40) 117 000 DH 0 H 0H C (54 ; 0) 81 000 DH 0 H 144 H 5 1°) Objectif : « Question » Minimiser le coût de la fertilisation souhaitée qui est fonction des quantités de paquets d’engrais A et B à acheter et à utiliser. 2°) V.E : X1 : quantité de paquets A à acheter X2 : quantité de paquets B à acheter 3°)- Fonction Economique : Min Z : 100x1 + 100x2 4°)- Les contraintes : 1x1 + 2x2 ≥ 60 potassiums 3x1 + 2x2 ≥ 120 Calciums 3x1 + 1x2 ≥ 90 Sodiums X1≥0; X2≥0 D’où le programme linéaire (P.L) à résoudre Min Z : 100x1 + 100x2 1x1 + 2x2 ≥ 60 (P) 3x1 + 2x2 ≥ 120 (D) 3x1 + 1x2 ≥ 90 X1≥0; X2≥0 Résolution graphique : . -40 -20 0 20 40 60 80 100 0 10 20 30 40 50 60 70 80 90 100 1 2 3 3 – Lecture graphique de la solution optimale :(méthode des sommets). * notre domaine (D) est un domaine non borné (ouvert). * si solution existe elle est obligatoirement un des points sommets : A, B, C ou D • Le point B est l’intersection des droites frontières (2) et (3) donc ses coordonnées sont solution du système d’équations : 3x1 + 2x2 ≥ 120 (2) 3x1 + 1x2 ≥ 90 (3) Après résolution on trouve : x1= 20 et x2= 30 6 (D) .A . B . C D . • Le point C est l’intersection des droites frontières (1) et (2) et donc solution du système d’équations : 1x1 + 2x2 ≥ 60 (1) 3x1 + 2x2 ≥ 120 (2) Après résolution on trouve x1= 30 et x2 = 15 Coordonnées du sommet S Valeur de Z en chaque sommet : Zsi e1= x1+ 2x2- 60 e2= 3x1 + 2x2 + 120 e3= 3x1+ x2-90 A (0 ; 90) ZA= 9000 DH 120 Kg 60 Kg 0 Kg B (20, 30) ZB= 5000 DH 20 Kg 0 Kg 0 C (30 ; 15) ZC= 4500 DH 0 0 15 Kg D (60 ; 0) ZD = 6000 DH 0 60 Kg 90 Kg 4) Conclusion : La solution optimale est : X*=(x1* ; x2*)= (30 ; 15) avec e1= 0 ; e2=0 ; e3=15 Et Z*min = 4500 DH 5) Interprétation économique : Pour réaliser la fertilisation souhaitée au moindre coût de 4500 DH on doit acheter et utiliser 30 paquets d’engrais A et 15 paquets d’engrais B. Cet achat a assuré exactement la quantité requise en potassium (e1=0) et a assuré exactement la quantité requise en calcium (e2=0) avec un surplus de 15 Kg de sodium (e3=0). 7 PARTIE II : ALGORITHME DU SIMPLEXE : Introduction : Un algorithme n’est autre q’une méthode de résolution d’un certain type de problème. L’algorithme du simplexe permet la résolution d’un programme linéaire de deux variables et plus. L’algorithme du simplexe peut être présenté de 3 façons équivalentes : 1- la forme matricielle dont l’intérêt est purement théorique. 2- La forme algébrique dont l’intérêt est purement pédagogique. 3- Ces deux premières formes peuvent être mises sous une forme appelée méthode des tableaux. C’est cette dernière qui va être retenue dans notre cours. 5 3 X1 270 ≤ 4 6 X2 360 5X1 + 3X2 ≤ 270  270 – (5X1 + 3 X2) ≥ 0  Posons : e1 = 270 – (5x1 + 3x2)  5x1 + 3x2 + e1= 270 Et e1≥0 Résolution simplexe du P.L : 1ère étape : mettre le PL (P) sous sa forme standard ≡ introduire les variables d’écart Max Z : 1500 X1+1800X2 + 0e1+ 0e2 5X1 + 3X2 +e1=270 (D) 4X1+6X2+ e2=360 info X1≥0 ; X2≥0 ; e1≥ 0 ; e2≥0 2ème étape : Démarrage standard à partir de l’origine O x1= 0 ; x2 = 0 e1= 270 ; x2 = 360 uploads/Industriel/ recherche-operationnelle.pdf

  • 44
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager