Remerciez-le!

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

Parcours « ECONOMIE & GESTION » Semestre 6 Chapitre 1 LA PROGRAMMATION LINEAIRE

Parcours « ECONOMIE & GESTION » Semestre 6 Chapitre 1 LA PROGRAMMATION LINEAIRE Professeur Abdelhamid SKOURI A.U. 2020 / 2021 1 Résolution des problèmes de P.L. Section 1- La méthode graphique Section 2- La méthode du simplexe Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 2 • Résoudre un problème de P.L. c’est déterminer le niveau d’activité qui optimise la fonction - objectif. On obtient alors un programme optimal. • La résolution suppose l’utilisation de méthodes adaptées, les outils classiques de l’analyse mathématique n’étant applicables que dans le cas où la fonction à optimiser est définie, continue et dérivable dans son domaine de définition. • La résolution d’un programme linéaire se déroule selon un processus illustré par le schéma suivant: Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 3 Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 4 Section 1- La méthode graphique Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 5 Déroulement de la méthode graphique • La méthode est adaptée à la résolution des problèmes à 2 variables: 1. Détermination du polygone des solutions possibles : intersection des demi - plans représentant les contraintes techniques. L’ensemble des points de ce polygone vérifie le système des contraintes techniques et forme l’ensemble des solutions possibles. Ce polygone est convexe. Quant à la solution optimale, elle se situe sur la frontière du polygone et correspond à un sommet ; 2. Détermination de la solution optimale par substitution progressive dans la fonction économique et calcul des valeurs de cette dernière pour les coordonnées des sommets du polygone. Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 6 Déroulement de la méthode graphique Détermination du polygone des solutions possibles: intersection des demi - plans représentant les contraintes techniques. L’ensemble des points de ce polygone vérifie le système des contraintes techniques et forme l’ensemble des solutions possibles. Quant à la solution optimale, elle se situe sur la frontière du polygone et correspond à un sommet ; Détermination de la solution optimale en substituant progressivement dans la fonction économique et en calculant les valeurs de cette dernière pour les coordonnées des différents sommets du polygone. • Le sommet correspondant à l’optimum est le point de tangence entre le polygone des solutions possibles et la famille de droites représentant la fonction - objectif. ◙Un problème de P.L. peut avoir soit une solution unique, soit une infinité de solutions, soit une solution infinie. Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 7 Remarques: ◙Le sommet correspondant à l’optimum est le point de tangence entre le polygone des solutions possibles et la famille de droites représentant la fonction - objectif. ◙un problème de P.L. peut avoir soit une solution unique, soit une infinité de solutions, soit une solution infinie. Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 8 Exemple 1: • Une entreprise de menuiserie fabrique et vend deux types de meubles : M1 et M2. • Cette activité génère un bénéfice unitaire de 100,- u. m pour M1 et de 300,- u. m pour M2. • L’entreprise dispose de deux ateliers A1 et A2 dont les capacités journalières sont limitées à 12 heures et à 16 heures respectivement. La fabrication d’une unité de M1, nécessite 4 heures de travail dans A1 et 8 heures dans A2. La fabrication d’une unité de M2, nécessite 6 heures de travail dans A1 et 4 heures dans A2. On suppose qu’il y a une demande élevée des 2 produits, et que l’entreprise désire déterminer la combinaison de production qui générera le bénéfice total maximal. • Déterminer la solution optimale en utilisant la méthode graphique Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 9 Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 10 •Le sommet correspondant à l’optimum, constitue le point de tangence entre le polygone des solutions possibles et la famille de droites représentant la fonction - objectif. Les variables sont x1 et x2. Les contraintes sont d’abord exprimées comme des égalités pour la représentation graphique : Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 11 Représentation graphique du demi- plan représentant la première contrainte technique • La droite correspondant à la première contrainte : • 4X1 + 6X2 ≤ 12 (1) • 4x1 + 6x2 = 12 • A1 ➔(x1 = 0 ; x2 = 2) • (x1 = 3 ; x2 = 0). • Cette droite coupe le plan en 2 demi plans et le demi - plan inférieur vérifie la contrainte. Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 12 Représentation graphique du demi- plan représentant la deuxième contrainte technique • La droite correspondant à la deuxième contrainte : 8x1 + 4x2 ≤ 16 (2) • 8x1 + 4x2 = 16 • A2 ➔(x1 = 0 ; x2 = 4) • (x1 = 2 ; x2 = 0). • Cette droite coupe le plan en 2 demi plans ; le demi - plan inférieur vérifie la contrainte Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 13 L’ intersection des demi- plans représentant les 2 contraintes techniques donne le polygone des solutions possibles (OABC). Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 14 • Le tableau suivant énumère les sommets et donne la valeur de la fonction – objectif Z pour chacun de ces sommets, • Donc pour maximiser son profit, l’entreprise ne doit produire que 2 unités du meuble M2 uniquement • => Solution optimale unique. Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 15 Exemple 2: Résoudre , à l’aide de la méthode graphique, le P.L. suivant: Min Z = 16 x1 + 18 x2 3x1 + 6x2 ≥1200 4x1 + 3 x2 ≥1000 xi≥ 0 (i = 1, 2) Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 16 Représentation graphique du demi- plan représentant la première contrainte technique On représente graphiquement le demi- plan représentant la contrainte technique (1): 3x1 + 6x2 ≥1200 3x1 + 6x2 = 1200 (x1 = 0 ; x2= 200) et (x2 = 0 ; x1 = 400) Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 17 Représentation graphique du demi- plan représentant la deuxième contrainte technique On représente graphiquement le demi- plan représentant la contrainte technique (2): 4x1 + 3 x2 ≥1000 4x1 + 3x2 = 1000 (x1 = 0 ; x2 = 333,33) et (x2 = 0 ; x1 = 250) Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 18 L’ intersection des demi- plans représentant les 2 contraintes techniques donne le polygone des solutions possibles (ABC). Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 19 Sommets Valeur de Z = 16 x1 + 18 x2 A ( 0 ; 333,33) ZA = 16.0 +18.333,33 = 6000 B ( 160 ; 120 ) ZB = 16.160 + 18. 120 = 4720 C (400 ; 0 ) ZC = 16.400 + 18.0) = 6400 Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 20 Exemple 3: Résoudre, graphiquement, le P.L. dans chacun des cas suivants: 1. c = 5. 2. c = 4. Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 21 1er cas : c = 5 Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 22 1er cas : c = 5 Représentation graphique du demi- plan représentant la première contrainte technique On représente graphiquement le demi- plan représentant la contrainte technique (1): x1 + x2 ≤10 x1 + x2 = 10 (x1 = 0 ; x2= 10) et (x2 = 0 ; x1 = 10) Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 23 Représentation graphique du demi- plan représentant la deuxième contrainte technique On représente graphiquement le demi- plan représentant la contrainte technique (2): 2x1 + 3x2 ≤24 2 x1 + 3x2 = 24 (x1 = 0 ; x2= 8) et (x2 = 0 ; x1 = 12) Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 24 Représentation graphique du demi- plan représentant la troisième contrainte technique On représente graphiquement le demi- plan représentant la contrainte technique (3): 4x1 + x2 ≥8 4 x1 + x2 = 8 (x1 = 0 ; x2= 8) et (x1 = 2 ; x2 = 0) Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 25 L’ intersection des demi- plans représentant les 3 contraintes techniques donne le polygone des solutions possibles (ABCD). Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 26 • Le tableau suivant énumère les sommets et donne la valeur de Z pour chacun de ces sommets, • Le sommet C est à l’intersection des contraintes (1) et (2). Ses coordonnées sont donc la solution du système d’équations : • x1 + x2 = 10 • 2x1 + 3x2 = 24 • => x1 = 6 et x2 = 4 • Le PL admet une solution optimale unique en (6,4) avec • Z max = 54 Sommets Valeur de Z = 5x1 + 6x2 A (2, 0) ZA = 10 B (0, 8) ZB = 48 C (6, 4) ZC = 54 D (10, 0) ZD = 50 Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 27 2ème cas : c = 4 Remarque : Le système des contraintes techniques n’a pas changé. Donc on travaillera sur le même polygone des possibles Pr. Abdelhamid SKOURI Cours de recherche opérationnelle 28 2ème cas : c = 4. Comme les uploads/Science et Technologie/ p-l-resolution.pdf