Remerciez-le!

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

Chapitre 1 : Introduction à la Programmation Linéaire Un problème de programmat

Chapitre 1 : Introduction à la Programmation Linéaire Un problème de programmation linéaire est représenté par un problème de programmation mathématique : les variables de décision sont des variables numériques, la représentation des décisions possibles et du critère fait appel à des équations ou fonctions mathématiques. Plus précisément, nous introduisons ici le problème particulier de programmation linéaire. I. Exemples d’introduction Exemple 1 Le problème Une entreprise spécialisée dans la fabrication de matériels informatiques, propose à son catalogue d'ordinateurs des centaines de référence. Pour simplifier, on ne s'intéresse ici qu'à deux types d'ordinateurs : le IM4 et le IM5. Chacun d'eux comporte un processeur - le même - mais les deux modèles diffèrent en particulier par le nombre de barrettes mémoires. Plus précisément, le IM4 comporte 2 barrettes alors que le IM5 en comporte 6. Le marché pour ces composants est tel qu'on ne peut espérer acheter auprès des fournisseurs habituels plus de 10 000 processeurs pour le trimestre à venir et plus de 48 000 barrettes. Une autre limitation risque d’intervenir sur la production. L’assemblage est caractérisé, en particulier, par une opération délicate, qui pour l’IM4 est de 3 minutes alors que pour l’IM5 elle n’est que d’une minute ; on ne dispose a priori pour l’assemblage de ces deux types de machines que de 24 000 minutes pour le trimestre à venir. Enfin, compte tenu des conditions actuelles du marché, on peut espérer retirer un profit de 400 euros sur l’IM4 et de 800 euros sur l’IM5. Le problème est de déterminer les quantités de chacun des deux types d'ordinateurs à fabriquer de manière à obtenir le plus grand profit possible. Modélisation du problème Nous examinons dans l’ordre la représentation des décisions, des contraintes et de la fonction objective. 1. Les variables de décisions Les variables de décisions concernent les quantités à fabriquer, ce qui se représente naturellement par deux nombres positifs x1 pour l’IM4 et x2 pour l’IM5. 2. Les contraintes Il s’agit de représenter les différentes contraintes limitant la production de ces deux types d’ordinateur. La première porte sur la limitation du nombre de processeurs disponibles : chaque machine utilise un processeur et on peut en disposer de 10 000. On doit donc imposer : x1 + x2 ≤ 10 000 De même, le nombre de barrettes est limité. Compte tenu du nombre de barrettes dans chacun des 2 ordinateurs et du nombre de barrettes disponibles, cette contrainte se traduit par : 2x1 + 6x2 ≤ 48 000 Enfin, la contrainte portant sur le temps d'assemblage s'écrit : 3x1 + x2 ≤ 24000 L’ensemble des contraintes est donc caractérisé par l’ensemble des valeurs de x1 et x2 vérifiant : x1 + x2 ≤ 10 000 2x1 + 6x2 ≤ 48 000 3x1 + x2 ≤ 24 000 x1 ≥ 0 x2 ≥ 0 3. La fonction objective : On souhaite maximiser le profit qui est représenté par : 400x1 + 800x2. Le problème initial est donc modélisé par le problème de programmation mathématique suivant : Max Z = 400 x1 + 800 x2 Sous les contraintes x1 + x2 ≤ 10 000 2x1 + 6x2 ≤ 48 000 3x1 + x2 ≤ 24 000 x1 ≥ 0x2 ≥ 0 Le modèle obtenu est un exemple de problème de programmation linéaire. Exemple 2 Le problème Une entreprise disposant de plusieurs lieux de production doit transporter ses produits finis vers des entrepôts régionaux pour répondre aux besoins locaux. Pour simplifier l’exemple, on se contente de 2 usines avec 3 entrepôts. On peut a priori faire transiter le produit de n'importe quelle unité de production vers n'importe quel entrepôt. Chaque unité de production a une capacité limitée. Supposons, par exemple, que la capacité de production de l’usine 1 (notée U1) soit de 100 (en milliers de tonnes) et celle de l’usine U2 de 150. Les entrepôts ont exprimé une demande qui doit être satisfaite : l'entrepôt 1, noté E1, a une demande de 50 (en milliers de tonnes), le deuxième 70 et le troisième 80. Le coût de transport dépend bien sûr du trajet à effectuer et du mode de transport, donc de l'usine de départ et de l'entrepôt d'arrivée. Le coût de transport par tonne de l’usine i (i = 1,2) vers l’entrepôt j (j = 1,2,3) est donné dans le tableau suivant. E1 E2 E3 U1 4 3 6 U2 3 5 3 Le problème est de déterminer les quantités à transporter de chaque usine vers chaque entrepôt, de manière à minimiser le coût total de transport tout en respectant les contraintes de capacité des usines et de demande des entrepôts. Le modèle 1. Les variables de décisions Elles portent sur les quantités à transporter. La quantité transportée (en milliers de tonnes) de l'usine i vers le dépôt j est représentée par la variable positive xij (i = 1,2 et j = 1,2,3). 2. Les contraintes Il s’agit de traduire les contraintes limitant les décisions. Il y a deux types de contraintes, celle portant sur la capacité des usines et celle portant sur la demande des magasins. - Limitation sur la capacité de production des usines Il faut exprimer que, de chaque usine, ne peut partir une quantité supérieure à ce qu’elle est capable de produire. Pour l’usine U1, x11 + x12 + x13 représente, en milliers de tonnes, ce qui part vers les entrepôts. La contrainte sur la capacité de l’usine U1 est traduite par : x11 + x12 + x13 ≤ 100 Pour l'usine 2, on a de même : x21 + x22 + x23 ≤ 150 - Limitation sur la demande des entrepôts. Ce qui arrive à chaque entrepôt doit être égal à ce qu’il a demandé. Pour l’entrepôt E1, x11 + x21 représente la quantité qui lui est livrée. Sa demande étant de 50, on doit donc imposer : x11 + x21 = 50 On a de même pour les 2 autres entrepôts : x12 + x22 = 70 x13 + x23 = 80 L’ensemble des décisions possibles est donc caractérisé par l’ensemble des valeurs des xij vérifiant : x11 + x12 + x13 ≤ 100 x21 + x22 + x23 ≤ 150 x11 + x21 = 50 x12 + x22 = 70 x13 + x23 = 80 xij ≥ 0 i = 1,2 j = 1,2,3 3. La fonction objective On souhaite minimiser le coût total de transport. Si on fait l’hypothèse que sur chaque trajet le coût est proportionnel aux quantités transportées, le coût total s’écrit : 4 x11 + 3 x12 + 6 x13 + 3 x21 + 5 x22 + 3 x23 que l’on souhaite minimiser. Le problème initial est donc modélisé par le problème de programmation mathématique. Min Z= 4 x11 + 3 x12 + 6 x13 + 3 x21 + 5 x22 + 3 x23 sous les contraintes x11 + x12 + x13 ≤ 100 x21 + x22 + x23 ≤ 150 x11 + x21 = 50 x12 + x22 = 70 x13 + x23 = 80 xij ≥ 0 i = 1,2 j = 1,2,3 Ce problème, appelé "problème de transport classique", est, comme dans le premier exemple, modélisé par un problème de programmation linéaire. II. Définition d’un problème de programmation linéaire Le modèle type de programmation linéaire peut être retenu pour représenter de nombreux problèmes. Un problème sera modélisé par un problème de programmation linéaire si : • les décisions peuvent être représentées par des nombres réels (généralement positifs), • les contraintes portant sur ces variables peuvent être représentées par des équations ou des inéquations linéaires c'est-à-dire que les variables n'interviennent qu'au premier degré (pas de carrés, pas de produit de variables), • le critère de choix peut être représenté par une fonction linéaire des variables que l'on souhaitera minimiser ou maximiser. La forme générale d’un problème de programmation linéaire de n variables et p contraintes est : Min ou Max c1x1 + c2x2 +....+ cj xj +…+ cnxn Sous les contraintes ai1 x1 + ai2 x2 +…+ ain xn ≤ , ≥ ou = di pour i = 1, ..p xj ≥ 0 j = 1, ...,n Les coefficients cj de la fonction objectif, les coefficients aij du premier membre des contraintes et les seconds membres di des contraintes sont des données du problème. Définitions Une solution réalisable est un n-uplet (x1,...,xn) vérifiant toutes les contraintes. Le domaine réalisable est l’ensemble de toutes les solutions réalisables. Une solution optimale est une solution réalisable qui donne à la fonction objective la plus grande (problème de maximisation) ou la plus petite valeur possible (problème de minimisation) sur l’ensemble des solutions réalisables. Les exemples de problème qui relèvent de la programmation linéaire sont fort nombreux. On peut citer : o les problèmes de mélange : quelle est la composition optimale d’un produit ? o les problèmes de planification de production : quand et à quel moment doit-on planifier la production d’un bien, o les problèmes de transport, généralisation du problème de transport classique, o les problèmes de planification d’horaires, o les problèmes de découpe industrielle uploads/Industriel/ chapitre-1-2-3.pdf