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 Université Hassan II – Casablanca- Licence Professionnelle: Logistique et Com

1 Université Hassan II – Casablanca- Licence Professionnelle: Logistique et Commerce Cours Recherche opérationnelle Programmation linéaire AU:2016-2017 M Y.DHIBA AU:2016-2017 2 Plan du cours 1) Introduction 2) Objectifs de la programmation linéaire 3) Méthode graphique 4) Méthode de simplex 5) Dualité M Y.DHIBA AU:2016-2017 3 A) Recherche opérationnelle  Méthodes et techniques d’aide a la décision  Trouve son origine au début du XXème siècle et a commencé à ce développer lors de la 2ème guerre mondiale.  Plusieurs modèles mathématiques traitant des problèmes: - Optimalisation linéaire; - ordonnancement et gestion de projets; - Optimisation des flux; introduction . M Y.DHIBA AU:2016-2017 4 B) Programmation linéaire  Ensemble de techniques d’optimisation sous des contraintes dont l’objectif est de déterminer une solution optimale pour une fonction objective.  Plusieurs domaines d’application: - Gestion de la production: -- élaboration de plan de production et de stockage. -- Choix de techniques de production; -- affectation de moyens de production -- etc. - MARKETING: -- Détermination de politique de prix. -- répartition des efforts de la force de vente; -- etc. -Finance(Choix de programmes d’investissements), en logistique( gestion des transports); en RH( affectation de personnel) introduction . M Y.DHIBA AU:2016-2017 5 Modélisation d’un problème en PL: -Un programme linéaire contient deux parties: Une fonction objective à maximiser ou minimiser et un ensemble de contraintes à satisfaire. C’est un programme mathématique dont la fonction objective et les contraintes sont des fonctions linéaires. -La modélisation d’un problème consiste à identifier: -- les variables du problème(les inconnus ou les variables de décision); -- la fonction objectif à optimiser (Fonction économique); -- Les différentes contraintes linéaires auxquelles sont soumises ces variables. -En pl, un problème doit être formulé sous la forme: ..Maximiser Fonction objectif: F(x1, x2, ….., xn)= .. Sous les contraintes: Eléments fondamentaux de la programmation Linéaire . M Y.DHIBA AU:2016-2017 6 Exemple 1: -P1 et P2 rapportent à la vente 6dh et 4dh par unité Quelles quantités de produits P1 et P2 doit produire l’usine pour maximiser le bénéfice total venant de la vente des deux produits? Eléments fondamentaux de la programmation Linéaire . M Y.DHIBA AU:2016-2017 7 Modélisation de l’exemple 1: Eléments fondamentaux de la programmation Linéaire . M Y.DHIBA AU:2016-2017 8 Exemple 2: Quelles quantités de produits A et B doit produire l’usine pour maximiser le bénéfice total venant de la vente des deux produits? Eléments fondamentaux de la programmation Linéaire . M Y.DHIBA AU:2016-2017 9 Modélisation de l’exemple 2: Eléments fondamentaux de la programmation Linéaire M Y.DHIBA AU:2016-2017 10 Exemple 3: Eléments fondamentaux de la programmation Linéaire . M Y.DHIBA AU:2016-2017 11 Modélisation de l’exemple 3:  Variables:  Objectif : Maximiser le profit apporter par la culture de tomates et de piments.  Contraintes: Eléments fondamentaux de la programmation Linéaire M Y.DHIBA AU:2016-2017 12 Modélisation de d’un PL: cas de minimisation de la fonction objectif.  En PL, l’optimisation formulé par un cas peut exiger la minimisation de la fonction objectif. Dans ce cas, le problème doit être formulé de la façon suivante: ..Minimiser F(x1, x2, ….., xn)= .. Sous les contraintes: Eléments fondamentaux de la programmation Linéaire M Y.DHIBA AU:2016-2017 13 A) Régionalisation du plan Exemple: Cas de la droite 2x+Y-4=0 Méthode graphique . M Y.DHIBA AU:2016-2017 14 B) Démarche de la méthode graphique Cette méthode ne s’applique que dans le cas de deux variables de décision. Elle repose sur les éléments suivants: Solution réalisable: Une solution est réalisable si les valeurs numériques associées aux variables de décision satisfont à l’ensemble des contraintes du programme linéaire. Région réalisable: Ensemble de solution réalisable. La solution optimale (s’il en existe une) se trouve sur la frontière de la région réalisable. Quand une solution optimale existe, il existe toujours une sur un sommet (point extrême ) de la région réalisable. Méthode graphique . M Y.DHIBA AU:2016-2017 15 C) Exemples: Cas 1: Maximiser Z(x1,x2)=2x1+4x2 Sachant que: La région réalisable est donnée graphiquement par: Méthode graphique . M Y.DHIBA AU:2016-2017 16 C) Exemples: Cas 1: (D1): x1 +3x2 -18=0; (D2): x1 + x2 -8=0; (D3): 2x1 + x2 -14=0 La région réalisable est délimitée par le polygone OABCD Méthode graphique . M Y.DHIBA AU:2016-2017 17 Cas 1: Lorsque Z augmente, la droite Dz (2x1+4x2=z) se déplace parallèlement à elle-même vers le haut: Quand une solution optimale existe, il existe une sur un sommet (point extrême ) de la région réalisable càd un des sommets: O, A, B, C ou D Méthode graphique . M Y.DHIBA AU:2016-2017 18 Cas 1: Lorsque Z augmente, la droite Dz (2x1+4x2=z) se déplace parallèlement à elle-même vers le haut: Méthode graphique . M Y.DHIBA AU:2016-2017 19 C) Exemples: Cas 2: Exemple 2 précédent (Cas fabrication des yaourts A et B) Méthode graphique . M Y.DHIBA AU:2016-2017 20 C) Exemples: Cas 2: Exemple 2 précédent (Cas fabrication des yaourts A et B) Méthode graphique . M Y.DHIBA AU:2016-2017 Région réalisable 21 C) Exemples: Cas 2: Exemple 2 précédent (Cas fabrication des yaourts A et B) Méthode graphique . M Y.DHIBA AU:2016-2017 Pour maximiser le bénéfice total, l’usine doit produire 300kg de A et 200 kg de B. Le bénéfice maximal est de 2200€ 22 D) Exercices 1) Traiter le cas de l’exemple 3 (Allocation des ressources pour l’agriculture): 2) Cas de production: Méthode graphique . M Y.DHIBA AU:2016-2017 23 A) Démarche de la méthode simplex 1) Ecrire le PL sous forme standard -- Un PL est dit sous forme canonique s’il s’écrit: La mise sous forme standard consiste à introduire des variables supplémentaires (une pour chaque contrainte) de manière à réécrire les inégalités sous la forme d’égalités. Chacune des variables supplémentaires représente le nombre de ressources non utilisées. On les appel les variables d’écart. Tout PL sous forme canonique s’écrit de façon équivalente sous forme standard et inversement. Méthode simplex . M Y.DHIBA AU:2016-2017 Où 24 A) Démarche de la méthode simplex 1) Ecrire le PL sous forme standard -- La forme standard d’un PL s’écrit donc: Méthode simplex . M Y.DHIBA AU:2016-2017 25 A) Démarche de la méthode simplex 1) Ecrire le PL sous forme standard -- Exemple: Soit le PL sous la forme canonique suivante: --La forme standard de ce PL est: --Variables de décision: --Variables d’écart: Méthode simplex . M Y.DHIBA AU:2016-2017 Max F(x1, x2, x3)=2x1+ x2 + x3 S.C Max F(x1, x2, x3)=2x1+ x2 + x3 26 A) Démarche de la méthode simplex 2) Application de l’algorithme de simplex: -- La méthode de simplex repose sur le théorème fondamental suivant : --L’algorithme du simplex consiste à: Méthode simplex . M Y.DHIBA AU:2016-2017 27 A) Démarche de la méthode simplex 2) Application de l’algorithme de simplex: -- Chaque itération de l’algorithme du simplex consiste à : Choisir la variable entrante: Celle qui a le plus grand coût marginal positif Choisir la variable sortante: Celle qui a le minimum des Déterminer le pivot: Intersection entre la ligne de la variable sortante et la colonne de la variable entrante. Remplacer les coefficients de la ligne du pivot par: Remplacer les coefficients des autres lignes selon la formule: --Condition d’arrêt: La solution est optimale si les coûts marginaux sont négatifs ou nuls. Sinon on recommence une nouvelle itération Méthode simplex . M Y.DHIBA AU:2016-2017 e: est le numéro de la colonne de la variable entrante. 28 B) EXEMPLES CAS 1:Soit le PL suivant: Maximiser 1) Introduire les variables d’écart pour avoir la forme standard suivante : Max: -- Solution de base: -- Variables de Base: -- Variables hors Base: Méthode simplex . M Y.DHIBA AU:2016-2017 S.C S.C 29 B) EXEMPLES CAS 1: 2) Préparation du tableau initial : Méthode simplex . M Y.DHIBA AU:2016-2017 bi 30 B) EXEMPLES CAS 1: 3) 1ère itération: Variable entrante: X1; (Celle dont le coefficient de z est Maximal) Variable sortante: X3 (Celle dont le rapport bi sur ai1 est minimal) Pivot=1 (Intersection de la colonne de la variable entrante avec celle de la variable sortante) Replacer la variable entrante et diviser la ligne du pivot par le pivot Recalculer les autres lignes selon la formule précédente Méthode simplex . M Y.DHIBA AU:2016-2017 bi 31 B) EXEMPLES CAS 1: 3) 1ère itération: Les coefficients de Z ne sont pas tous nuls ou négatifs. On passe donc à une 2ème itération. La variable entrante est X2 et la variable sortante est X6. Pivot=1. Méthode simplex . M Y.DHIBA AU:2016-2017 bi Tableau 2 32 B) EXEMPLES CAS 1: 3) 2ème itération: Les coefficients de Z ne sont pas tous nuls ou négatifs. On passe donc à une 3ème itération. La variable entrante est X3 et la variable sortante est X5. Pivot=1. Méthode simplex . M Y.DHIBA AU:2016-2017 Tableau 3 bi 33 B) EXEMPLES CAS 1: 3) 3ème itération: Les coefficients de Z sont tous nuls ou négatifs (Condition d’arrêt). Fin de l’algorithme et la solution optimale est: X1=200 et X2=300 pour que la fonction objectif Z atteint la valeur de 2900. Méthode simplex . M Y.DHIBA AU:2016-2017 Tableau 4 34 B) EXEMPLES CAS 2: Appliquer la méthode de simplex au cas suivant: Maximiser : Méthode simplex . M Y.DHIBA uploads/Management/cours-ro-lc.pdf