Remerciez-le!

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

prograMMation linéaire 6 chapitre 2: introDuction et propriétés De la prograMMa

prograMMation linéaire 6 chapitre 2: introDuction et propriétés De la prograMMation linéaire 1. Introduction Le développement technologique, soumet l'homme aux contraintes d'un système de relations économique de plus en plus complexe. On constate qu'il a de plus en plus d'éléments nouveaux qui doivent être prise en compte lors des prises de décision concernant une action donnée (organisation d'une production, un réseau de transport,…) et que ces prises de décision deviennent l'objet de véritables recherches qui ne peuvent être menées sans l'aide d'outils mathématiques. C'est ainsi que s'est développé un domaine des mathématiques basé sur l'activité de décision, appelé recherche opérationnelle. Les premiers problèmes, qui marquent le début de la recherche opérationnelle ont été posés pendant la seconde guerre mondiale. A cette époque l'homme était préoccupé par l'organisation des opérations militaires et surtout aériennes (nombre d'avions, la formulation à adapter, la fréquence des vols pour avoir un maximum d'efficacité, …. ). Par la suite, les méthodes de recherche opérationnelle se sont de plus en plus appliquées aux problèmes économiques et commerciaux. Une des parties essentielle de la recherche opérationnelle est la programmation linéaire, qui étudie la maximisation ou la minimisation de fonction linéaire soumise à des contraintes linéaires. Remarque: La programmation linéaire permet la résolution d’un programme linéaire. Un programme linéaire est un système d’équations ou d’inéquations appelées "contraintes" qui sont linéaires (c’est-à- dire que les variables ne sont pas élevées au carré, ne servent pas d’exposant, ne sont pas multipliées entre elles...). Et à partir de ces contraintes, on doit optimiser une fonction également linéaire appelée objectif. 2. Exemple de problème de programmation linéaire Avant de donner le modèle mathématique général du problème de la programmation linéaire, nous présentons un exemple concret. Exemple: Une unité de production de parpaings fabrique quatre types de produit: Les parpaings de dimensions respectivement 10 cm (noté P1), 15 cm (noté P2), 20 cm (noté P3) et l'ourdi (noté P4). Pour la fabrication de ces produits, on utilise quatre matières premières, le sable (M1), le gravier (M2), le ciment (M3) et l'eau (M4), disponibles en quantité respectivement de 5000, 3000 et 2000 unités. L'eau est disponible en quantité illimitée. Le plan de production de l'unité est donné dans le tableau ci-dessous: Produit Matières premières P1 P2 P3 P4 Quantités de matières premières disponibles M1 2 3 5 6 5000 M2 1 2 3 3 3000 M3 0.8 1 2 3 2000 M4 1 1 2 2 / Le tableau signifie que pour fabriquer un parpaings de 10 cm, il faut 2 unités de M1, 1 unité de M2, 0.8 unité de M3 et 1 unité de M4 et de la même manière pour P2, P3 et P4. Les parpaings sont vendus respectivement à raison de 6,7,9 et 10 DA l'unité. Le problème pour la direction de l'unité est de trouver le nombre maximal de produit P1, P2, P3 et P4 à fabriquer pour avoir un bénéfice maximal, tout en respectant les contraintes de l'unité. prograMMation linéaire 7 Résolution: Désignons par x1, x2, x3 et x4 les quantités de produits P1, P2, P3 et P4. Ces quantités doivent vérifier les conditions suivantes:  Les quantités utilisées en matières premières ne doivent pas dépasser les quantités disponibles:  1 .......... .......... 2000 3 2 8 . 0 3000 3 3 2 5000 6 5 3 2 4 3 2 1 4 3 2 1 4 3 2 1                  x x x x x x x x x x x x  Les quantités à produire sont toutes positives ou nulles: 0 , 0 , 0 , 0 4 3 2 1     x x x x ou . 4 , 3 , 2 , 1 , 0   j x j ………(2) Comme l'eau est disponible en quantité illimitée, donc on n'a aucune contrainte sur la matière première M4. Le chef de production de l'unité choisira le programme réalisable qui donnera le maximum de la fonction bénéfice Z.   ) 3 ..( .......... max 10 9 7 6 , , , 4 3 2 1 4 3 2 1      x x x x x x x x Z La fonction bénéfice (3) appelée aussi fonction objective ou fonction but, représente le bénéfice que va réaliser l'unité. En résume le chef de production aura pour objectif, de trouver la solution optimale du problème de programmation linéaire suivant:                               4 , 3 , 2 , 1 , 0 2000 3 2 8 . 0 3000 3 3 2 5000 6 5 3 2 max 10 9 7 6 , , , 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 j x x x x x x x x x x x x x x x x x x x x x Z j 3. Formulation du PL: Un programme linéaire est un modèle mathématique donnée sous la forme suivante: Maximiser ) ,....., ( 1 n x x f (ou minimiser ) ,....., ( 1 n x x f )  ) ,....., ( 1 n x x domaine, ou Domaine = . ,..., 1 , . . / ) ,....., ( 1 1 m i b R x a x x f i n j j ij n n       avec              i ij b a R , , , , , , De plus:    n j j j n x c x x f 1 1 ) ,....., ( où n j c j ,..., 1 ,     a) Exemple: Max 2x1+x2 est un PL b) Notations et définitions: 1. la fonction ) ,....., ( 1 n x x f sera notée n n n j j j t x c x c x c x C x C x f         ... ) ( 2 2 1 1 1 2. i n j j ij b R x a . 1   est appelé contrainte. 3. Formulation Matrice : Max ) ,....., ( 1 n x x f A.x R b et 0  x où                0 , 0 10 2 10 2 7 2 1 2 1 2 1 2 1 x x x x x x x x prograMMation linéaire 8   m j n i ij a A ,..., 1 ,..., 1    et            n x x x . 1 et            m b b b . 1 Exemple: Max 2x1+x2 Max 2x1+x2 Ecriture matricielle                               10 10 7 2 1 1 2 1 1 2 1 x x 4. Différentes formes d'un PL a) Forme canoniques: Min Ct.x Max Ct.x ) 1 ........( 0 .      x b x A où ) 2 ........( 0 .      x b x A Dans ce cours on ne s'intéressera qu'aux PL, données sous la forme (2) b) Forme standard: Max Ct.x (ou Min)      0 . x b x A Théorème 1: Tout PL ayant une forme canonique peut être écrit sous forme standard et inversement. Théorème 2: Tout PL peut être écrit sous forme canonique. 5. Résolution graphique: Cette méthode de résolution ne concerne que des PL avec 2 variables. Son principe est basé sur une représentation graphique du Domaine, ainsi que de la fonction objective. Nous allons voir le fonctionnement de cette méthode à travers l'exemple suivant: Modèle Max 2x1+x2                             2 10 2 10 7 0 , 10 2 10 2 7 1 2 1 2 1 2 2 1 2 1 2 1 2 1 x x x x x x x x x x x x x x Si on pose : D1:la droite d'équation 1 2 7 x x   D2:la droite d'équation 1 2 2 10 x x   D3:la droite d'équation 2 10 1 2 x x   Posons : k x x   2 1 2 (fonction objective) k x x    1 2 uploads/Industriel/ cours-pl-chapitre-2-introduction-a-la-pl.pdf