Remerciez-le!

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

12 Chapitre 2 ! Programmation linéaire (PL) 13 I : Introduction : L’importance

12 Chapitre 2 ! Programmation linéaire (PL) 13 I : Introduction : L’importance de l’optimisation et la nécessité d’un outil simple pour modéliser des problèmes de décision économique, on fait de la programmation linéaire un des champs de recherche les plus actifs. Les premiers travaux (1947) sont celle de George B. Dantzig. Les problèmes de programmations linéaires sont généralement liés à des problèmes d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit ou de minimiser un coût. Le terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces décisions sont en général le résultat d’un problème mathématique. La programmation linéaire est un procédé mathématique de recherche opérationnelle, il consiste à optimiser (ex : maximiser une marge, minimiser un coût) un critère appelé fonction économique en respectant un certain nombre de contraintes. Il s’agit de modéliser la fonction économique et les contraintes à respecter, donc c’est un instrument puissant d’aide à la décision. I : problèmes de maximisation à deux variables : A : la formulation d’un programme :Soit la détermination d’un maximum d’une fonction économique Z de la forme : ܼ=ݔߙ+ݕߚ Avec : x≥0, y≥0 (les contraintes de non – négativité), et vérifiant un ensemble de contraintes de la forme : ߙ௜ݔ+ߚ௜ݕ≤ܾ௜ Tout élément (x, y) vérifiant les contraintes est appelé programme admissible. Le problème est d’abord formalisé sous la forme canonique, les contraintes sont des inéquations. B :Les conditions de formulation d’un PL : La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces hypothèses sont :  Les variables de décision du problème sont positives  Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces variables. La fonction qui représente le critère de sélection est dite fonction objectif (ou fonction économique).  Les restrictions relatives aux variables de décision (exemple: limitations des ressources) peuvent être exprimées par un ensemble d’inéquations linéaires. Ces inéquations forment l’ensemble des contraintes.  Les paramètres du problème en dehors des variables de décisions ont une valeur connue avec certitude C : Les étapes de formulation d’un PL :Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme linéaire :  Identifier les variables du problème à valeur non connues (variable de décision) et les représenter sous forme symbolique (exp. x, y).  Identifier les restrictions (les contraintes) du problème et les exprimer par un système d’inéquations linéaires.  Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en fonction des variables de décision. Spécifier si le critère de sélection est à maximiser ou à minimiser. D : Présentation Théorique : Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire dite fonction objectif en satisfaisant certaines équations et inégalités dites contraintes. En langage mathématique, on décrira de tels modèles de la manière suivante : Soient n variables de décision x, y l’hypothèse que les variables de décision sont positives implique que : x≥0, y≥0. La fonction objective est une forme linéaire en fonction des variables de décision de type : 14 ܼ=ݔߙ+ݕߚ Où les coefficientsߙ,ߚdoivent avoir une valeur bien déterminée (avec certitude) et peuvent être positifs, négatifs ou nuls. Par exemple le coefficientߙpeut représenter un profit unitaire lié à la production d’une unité supplémentaire du bienܣainsi la valeur de z est le profit total lié à la production des différents biens. Supposons que ces variables de décision doivent vérifier un système d’équations linéaires définis par les inégalités suivantes : ߙ௜ݔ+ߚ௜ݕ≤ܾ௜ Où les coefficients doivent avoir une valeur bien déterminée (avec certitude) et peuvent être positifs, négatifs ou nuls. E : Exemple de formulation : Pour fabriquer deux produits A et B on doit effectuer des opérations sur trois machines M1, M2 et M3, successivement mais dans un ordre quelconque. Les temps unitaires d’exécution sont donnés par le tableau suivant : M1 M2 M3 A 11 mn 7 mn 6 mn B 9 mn 12 mn 16 n On supposera que les machines n’ont pas de temps d’inactivité. La disponibilité pour chaque machine est :  165 heures (9900 minutes) pour la machine M1 ;  140 heures (8400 minutes) pour la machine M2 ;  160 heures (9600 minutes) pour la machine M3. Le produit A donne un profit unitaire de 900 et le produit B un profit unitaire de 1000.Dans ces conditions, combien doit-on fabriquer mensuellement de produits A et B pour avoir un profit total maximum ? Formulation en un PL :  Les variables de décisions sont :  x : le nombre d’unités du produit A à fabriquer  y : le nombre d’unités du produit B à fabriquer  Les contraintes outre les contraintes de non-négativité sont :  11ݔ+ 9ݕ≤9900 pour la machine M1  7ݔ+ 12ݕ≤8400pour la machine M2  6ݔ+ 16ݕ≤9600pour la machine M3  Le profit à maximiser est : ܼ= 900ݔ+ 100ݕ Le programme linéaire résultant est : Maximiser : ܼ= 900ݔ+ 100ݕ ܿ݋݊ݏ݁ݐ݊݅ܽݎݐ൞ ݔ≥0݁ݕݐ≥0 11ݔ+ 9ݕ≤9900 7ݔ+ 12ݕ≤8400 6ݔ+ 16ݕ≤9600 F : Résolution par la méthode graphique : Après avoir illustré par un exemple, comment un problème pratique peut être modélisé par un programme linéaire, l’étape qui va suivre sera certainement celle de la résolution de ce problème mathématique. La méthode graphique est l’une des premières méthodes utilisées à ce sujet. Si on parle de résolution graphique alors on doit se limiter à une représentation à deux variables. 15 A cause des contraintes de non-négativité des variables de décision, nous nous intéressons seulement au cadran positif. Cette région s’appelle la région des solutions possibles du problème. La figure 1 aide à comprendre le principe de la résolution dans le cas simplifié où il n'y aurait que deux variables réelles x et y (représentées par les deux axes) et deux contraintes représentées par deux droites. La forme standard du programme aurait donc deux variables d'écart e1et e2 en plus des variables réelles, soit quatre variables en tout. Les axes et les droites des contraintes délimitent le polygone (en blanc) représentant l'ensemble des solutions possibles. Figure 1 Les intersections entre deux droites ou axes (petits cercles) représentent chacune une solution de base pour laquelle deux variables (réelles ou d'écart), dites variables hors base, sont égales à zéro et les deux autres variables, dites variables de base, sont positives. Il y a nécessairement une solution de base qui est optimale. La solution de base initiale est à l'origine des axes. Pour cette solution de base, ce sont les variables réelles x et y qui sont nulles (hors base) et les variables d'écart e1et e2 qui sont positives (variables de base). La fonction économique Z égale zéro, comme les variables réelles. L'algorithme passe successivement d'une solution de base à l'autre en augmentant la valeur de la fonction économique jusqu'à ce qu'elle ne puisse plus être améliorée. Pour la détermination graphique de maximum, il faut :  Représenter dans le plan l’ensemble des programmes admissibles,  Tracer la droite ∆d’équation :ݔߙ+ݕߚ= 0, cette droite passe par l’origine,  Déterminer la droite parallèle à Δ la plus éloignée de l’origine O, mais coupant l’ensemble des programmes admissibles en un point au moins. En ce point, Z atteint le maximum. Parmi les solutions possibles d’un problème, il y a ceux qui vont satisfaire toutes les contraintes du programme, appelés solutions réalisables, et ceux qui vont satisfaire une partie ou aucune de ces contraintes, appelés solutions non réalisables. Une représentation graphique des inégalités (des contraintes) va nous permettre de déterminer l’ensemble des solutions réalisables. Exemple 1 : ensemble des points vérifiant : 6ݔ+ 2ݕ≤18 Figure 2 Exemple 2 : déterminer le maximum de Z = 34 x + 28 y ൝ ݔ≥0,ݕ≥0 6ݔ+ 2ݕ≤18 2ݔ+ 4ݕ≤16 Il faut tracer les droites :  D1 d’équation : 6ݔ+ 2ݕ= 18  D2 d’équation : 2ݔ+ 4ݕ= 16  Δ d’équation : 34ݔ+ 28ݕ= 0  Déterminer sur le graphique l’ensemble des programmes admissibles (sans oublier les contraintes de positivité), on obtient la portion hachurée (OCBA).  Déterminer la droite parallèle à Δ et la plus éloignée de l’origine O et coupant la portion hachurée, cette droite est celle qui passe par le point B. voir figure 3 Déterminer les cordonnées de ce point par la résolution de système d’équation S puisque B est le point d’intersection des deux droites D1 et D2 : 16 ൜6ݔ+ 2ݕ= 18 2ݔ+ 4ݕ= 16 On obtient x = 2 et y =3. Et Z vaut 152. Théorème : le maximum de Z est atteint en un sommet du polygone convexe, frontière de l’ensemble des programmes admissibles. On remarque que la solution optimale du problème est un point extrême qui se trouve sur le bord de l’ensemble des solutions. Une telle solution est dite solution réalisable de base. On peut admettre le résultat suivant : " Si uploads/Voyage/ chapitre-02 4 .pdf