Programmation linéaire (LP): Notes d'étude

Dans cet article, nous discuterons de la programmation linéaire (LP): - 1. Concept de la programmation linéaire 2. Applications de la programmation linéaire 3. Hypothèses du modèle de programmation linéaire 4. Formulation.

Concept de programmation linéaire:

La programmation linéaire (LP) est une technique d'optimisation mathématique largement utilisée qui a été développée en 1947 par George B. Dantzig pour résoudre les problèmes de planification de l'US Air Force. Bien que la "programmation" informatique ne soit pas liée au disque vinyle, le développement de l'ordinateur a grandement contribué au succès de ce dernier.

Dans LP, les équations linéaires sont résolues encore et encore, chaque fois en changeant une variable, jusqu'à arriver à la solution finale. Dans les problèmes industriels actuels, les contraintes sont trop nombreuses et parfois plus de cent équations linéaires sont formées, dont les solutions sont pratiquement impossibles sans l'aide d'un ordinateur.

Un grand nombre de décisions d’affaires économiques, telles que la meilleure combinaison de produits d’une entreprise, l’allocation de fonds du budget publicitaire entre des médias concurrents, la sélection du meilleur processus de production, etc., peuvent être analysées et résolues par LP. Toutes les préoccupations de l’entreprise ont certains objectifs, par exemple: maximisation des profits, de la production, des ventes, réduction des coûts, etc.

L'expression algébrique de l'objectif s'appelle une fonction objectif qui doit être linéaire.

L'optimisation de la fonction objectif linéaire doit être soumise à des contraintes, qui sont aussi des expressions algébriques linéaires sous forme d'égalités ou d'inégalités. De telles contraintes doivent obéir à des "restrictions de non-négativité" car les variables ne peuvent pas avoir de valeurs négatives. La traduction des problèmes de l'entreprise en fonction objective et en un ensemble de contraintes linéaires s'appelle 'Formulation of the LP'

Un problème une fois formulé peut être résolu en utilisant un certain nombre de techniques différentes parmi lesquelles la «solution graphique» et la «méthode simplex» sont très populaires.

Applications de la programmation linéaire :

Les décisions économiques et commerciales portent souvent sur la répartition de ressources rares, par exemple matières premières, argent, temps, espace, personnes, etc. entre projets concurrents, soit pour maximiser certains objectifs, par exemple, production, rendement des investissements, part de marché, etc. etc., ou minimiser certains objectifs, tels que le coût, les déchets, la pollution, etc. Le LP peut être utilisé pour résoudre les problèmes pratiques suivants de l’industrie:

je. Problèmes de mélange de produits :

Le mélange optimal de produits à produire avec la main-d’œuvre rare de la société, la capacité de l’usine, les matières premières, les finances, etc., peut être analysé et résolu par LP. Prenons une usine de transformation des aliments produisant des produits à base de tomates, par exemple tomate cuite au four, pâte de tomate, soupe aux tomates, ketchup, jus de tomates, tomates en conserve, etc.

Il peut produire tout ou partie de ces produits simultanément, mais son offre de tomates, de temps / travail, de sucre, etc. est limitée.

Chaque produit a une contribution de profit différente et il devient donc difficile pour la direction de décider de la quantité de chaque produit à fabriquer. En outre, la direction peut être intéressée à savoir combien elle peut payer pour des unités supplémentaires des facteurs limités en offre. Vous pouvez répondre à ces questions en utilisant la technique LP.

ii. Problèmes de régime :

Les aliments pour animaux sont fabriqués en mélangeant un certain nombre d'ingrédients contenant chacun des proportions différentes de protéines, vitamines, minéraux, etc. Les aliments pour animaux produits doivent satisfaire à certains niveaux nutritionnels spécifiés par le gouvernement, au plus bas coût.

Les producteurs aimeront peut-être connaître l'augmentation du coût lorsque le niveau nutritionnel de l'aliment augmentera. Ce problème est également associé aux industries pharmaceutique, des engrais, des semences de gazon et des aliments pour animaux domestiques. LP est une réponse à de tels problèmes.

iii. Allocation budgétaire publicitaire :

Une entreprise dispose de fonds limités pour l’allocation du budget de publicité (télévision, radio, journaux, magazines, affiches, annonces au néon, etc.) et voudrait savoir combien d’argent devrait être alloué à quel support pour obtenir le maximum d’avantages. La publicité télévisée peut à nouveau être divisée en émissions de jour ou de soirée, selon le type de public. Le problème de l'allocation des fonds peut être résolu par LP

iv. Sélection du processus :

Ce problème est similaire aux problèmes de régime. Il traite des produits pouvant être fabriqués en utilisant l’un (ou plusieurs) de plusieurs processus, chacun impliquant différentes proportions d’intrants. Une entreprise souhaite fabriquer le produit en combinant deux procédés ou plus, ainsi que des intrants, de manière à minimiser les coûts de production. LP peut suggérer une réponse à ces problèmes.

v. Problèmes de distribution :

De nombreuses entreprises ont deux usines ou plus dans lesquelles un certain produit est fabriqué et plusieurs entrepôts situés à différents endroits pour stocker les produits avant de les envoyer à divers points de vente.

Les coûts de distribution diffèrent également selon les itinéraires empruntés, de l’usine de production aux entrepôts et aux points de vente. La direction doit décider des affectations d’expédition, c’est-à-dire combien d’unités doivent aller de chaque point de vente, en minimisant les coûts d’expédition. Ces problèmes peuvent être résolus par le transport et les techniques LP.

vi. Problèmes de traitement et de transport du pétrole :

Les grandes entreprises pétrolières reçoivent du pétrole brut de différentes sources qu’elles acheminent vers plusieurs raffineries où différents produits sont fabriqués conjointement dans le processus de craquage. LP est utilisé pour rechercher la combinaison de produits optimale, la meilleure méthode d’affectation du pétrole brut de différentes sources aux différentes raffineries et du transport des produits vers les points de vente. Ainsi, LP est largement utilisé dans l'industrie du pétrole.

vii. Problèmes d'affectation du personnel :

Ces problèmes sont similaires aux problèmes de distribution. Un cabinet comptable souhaiterait trouver la meilleure méthode pour affecter du personnel d’audit à diverses activités d’audit dans le respect des contraintes du bureau d’audit, tout en répondant aux objectifs professionnels et économiques des bureaux. Les techniques de LP et d’affectation peuvent être utilisées pour résoudre de tels problèmes.

viii. Planification de la capacité à long terme pour les services d'électricité :

De bons modèles de planification à long terme sont nécessaires pour les problèmes complexes liés à l'énergie. Les projections de la demande pour les années à venir et les informations relatives aux coûts d'exploitation et d'investissement devraient être intégrées à ces modèles. John R. McNamara a développé un tel modèle de planification de la capacité pour les services publics d'électricité basé sur le système LP afin de minimiser les coûts de satisfaction des demandes prévues.

Le modèle est simple, orienté utilisateur et peut être utilisé pour résoudre rapidement les problèmes. Outre ces LP peut être appliqué à divers autres domaines de la prise de décision.

Hypothèses du modèle de programmation linéaire :

Un modèle LP est basé sur les hypothèses suivantes.

1. Il doit y avoir un objectif qu'une entreprise souhaite maximiser ou minimiser. La fonction objectif (algébrique) doit être linéaire. Des objectifs multiples peuvent également être intégrés à l'analyse.

2. Des solutions de remplacement doivent être disponibles, car aucune décision n'est requise lorsqu'une entreprise est confrontée à un seul plan d'action. Par exemple, si un produit ne peut être fabriqué que par un seul processus, aucune décision n'est requise.

3. La fonction d'objectif linéaire doit être optimisée en fonction de certaines contraintes structurelles, telles que les matériaux, le temps, l'argent, etc.: (ressources), la capacité de l'installation, les accords contractuels, les considérations juridiques, les quotas de commercialisation, etc. Ces contraintes peuvent être exprimées algébriquement., sous forme d'inégalités linéaires ou d'équations linéaires. Comme la fonction objectif, les contraintes doivent également être des fonctions linéaires.

4. Les variables ne prennent pas de valeurs négatives. C'est ce que l'on appelle une restriction de non-négativité, c'est-à-dire que la valeur des variables de décision sera zéro ou positive.

Formulation du problème de programmation linéaire :

Considérons maintenant un problème de mix produit. Une entreprise fabrique deux types de boîtes, de type A et de type B. Le temps de traitement en minutes de soudage, de pressage et de placage de ces boîtes est indiqué ci-dessous. Les capacités de ces départements et les contributions de ces boîtes sont également indiquées.

Combien de boîtes A et B doivent être produites pour obtenir une contribution maximale?

Le processus de formulation des problèmes de LP implique la transformation des informations descriptives relatives aux situations en déclarations mathématiques. L'exemple suivant illustre ce point.

Problème 1:

Soit x 1 = nombre de boîtes de type A, x 2 = nombre de boîtes de type B. La fonction objectif devient de maximiser Z = 30x 1 + 20x 2, où Z représente le profit et 30 et 20 la contribution des cases de type A et de type B, respectivement.

La prochaine étape de la formulation d’un problème consiste à spécifier les contraintes. Comme x 1 et x 2 prennent 3 minutes. pour l'opération de soudage et le total disponible minutes. dans le département de soudage est de 60 minutes, l'équation de la contrainte sera la suivante:

3x 1 + 3x 2 ≤ 60 (Département de soudage)

c'est-à-dire le total des minutes. nécessaire pour produire x 1 et

x 2 cases doivent être inférieures ou égales à 60 minutes.

De même, les autres équations de contrainte sont:

S'il n'y a que deux variables, le problème peut être résolu par une simple méthode graphique. Lorsque plus de deux variables sont impliquées, nous appliquons la «méthode simplex».

Solution graphique (maximisation) :

Laissez-nous résoudre le même problème graphiquement. Ici, seules deux variables de décision, à savoir x 1 et x 2, sont impliquées. Ces variables sont tracées en abscisse (horizontale) et en ordonnée (verticale).

Pour tracer les contraintes sur un graphique, celles-ci sont exprimées sous la forme des équations suivantes:

3x 1 + 3x 2 = 60 (1)

6x 1 + 2x 2 = 60 (2)

8x 1 = 60 (3)

Maintenant, OABCD sur la figure 5.1 est la région convexe et les points en O, A, B, C et D sont appelés les solutions possibles au problème de LP. Il existe un théorème fondamental de LP qui stipule que la fonction objectif est optimisée à l'un des points d'angle, à savoir, O, A, B, C, D. Ainsi, pour un profit maximum, seuls ces points d’angle, également appelés solutions de base réalisables, doivent être évalués.

Les points peuvent également être directement obtenus du graphique.

Ici, Z = Rs. 450 (maximum en B lorsque x 1 = 5 et x 2 = 15).

Une autre méthode permettant d’obtenir la solution optimale de base réalisable est illustrée à la fig. (5.2), identique à la fig. (5.1) avec plusieurs lignes iso-profit en pointillés, c.-à-d. L 1 L 1, L 2 L 2, L 3 L 3, etc. Une ligne iso-profit est une représentation graphique de toutes les combinaisons possibles de deux produits donnant le même profit. Ce sont des lignes parallèles ayant la même pente. Il peut y avoir un nombre infini de telles lignes. Plus une ligne iso-profit partant de l'origine, plus le profit est grand.

Ici, nous sélectionnons un bénéfice raisonnable et traçons la ligne de fonction objectif associée à ce bénéfice. Ensuite, nous retirons la ligne iso-profit de l’espace de la solution jusqu’à ce qu’elle touche l’espace de la solution à un point extrême seulement. Nous pouvons maintenant trouver le profit optimal et les valeurs de la variable de décision à partir du graphique.

Z = 30x 1 + 20x 2 (fonction objectif) est une équation linéaire du premier degré. Si nous prenons différentes valeurs de Z, par exemple 150, 300, 600, etc. et les reportons sur le graphique, les lignes seront parallèles.

L 1 L 1, L 2 L 2, L 3 L 3, sont les lignes iso-profit. L 3 L 3 touche l'espace de la solution 0ABCD en un point quelconque, c'est-à-dire B (5, 15).

. . . Z = Rs. 450 (profit optimal) et x 1 = 5 et x 2 = 15 (composition optimale du produit).

Solution graphique: Minimisation :

Laissez-nous discuter d'un problème de minimisation.

Problème 2

Une personne a besoin de 10, 12 et 12 unités de produits chimiques A, B et C respectivement pour son jardin. Un produit liquide contient 5, 2 et 1 de A, B et C respectivement par pot. Un produit sec contient 1, 2 et 4 unités de A, B et C par carton. Si le produit liquide se vend à Rs. 3 par pot et le produit sec se vend à Rs. 2 par carton, combien faut-il en acheter pour minimiser les coûts et répondre aux exigences?

Solution:

Soit x 1 = unités de produit liquide achetées et x 2 = unités de produit sec achetées.

La fonction objectif devient:

Réduire Z = 3x 1 + 2x 2 (1)

sous réserve des contraintes suivantes

Pour tracer les contraintes sur un graphique, celles-ci sont exprimées sous la forme des équations suivantes:

Ici, la zone de solution se situe au-delà des lignes (2) ', (3)' et (4) ', comme indiqué par la zone ombrée sur la figure (5.3).

Ensuite, nous déplaçons la ligne iso-profit vers l'origine jusqu'à atteindre le dernier point de la limite de la zone de solution, c'est-à-dire B (ici).

Les coordonnées de B peuvent également être obtenues en résolvant les équations (2) 'et (3)', comme suit:

Maintenant, Z est minimum à B = 3 X 1 + 2 X 5 = Rs. 13. Les coordonnées de B peuvent également être obtenues directement du graphique.

La méthode simplex :

Les problèmes complexes de LP ne peuvent pas être résolus par des solutions graphiques. Pour de tels problèmes, nous utilisons la méthode simplex. Laissez-nous discuter d'un problème de maximisation simple.

Problème 1

La société de fabrication ABC peut fabriquer deux produits P 1 et P 2 . Chacun des produits nécessite du temps sur une machine de découpe et une machine de finition.

Le nombre d'heures de coupe disponibles par semaine est de 390. Le nombre d'heures de finition disponibles par semaine est de 810. Quelle quantité de chaque produit doit être produite pour que l'entreprise réalise un profit maximal?

Solution:

Laisser

x 1 = sortie du produit P 1 ;

x 2 = sortie du produit P 2 ;

x 3 = variable de jeu, c'est-à-dire heures de coupe inutilisées;

x 4 = variable de jeu, c'est-à-dire heures de finition non utilisées;

et

Z = profit optimal.

Maintenant, la fonction objectif devient: Maximiser Z = 6x 1 + 4x 2 + 0x 3 + 0x 4 sous réserve des contraintes:

Comme toutes les valeurs de (C j - Z j ), c'est-à-dire la ligne d'index de la passe II, sont nulles ou négatives, la solution optimale a été obtenue.

Les fabricants doivent produire 120 unités par semaine et 150 unités par semaine de P 1 et P 2, respectivement, pour obtenir la contribution maximale, c’est-à-dire Rs. 1320.

Calculs :

Le processus de calcul suit quelques étapes. Celles-ci sont expliquées ci-dessous.

Table de départ :

Mettez les rhs des équations (2) et (3) dans les carrés CC 'et DC', respectivement. Mettez les coefficients de x 1, x 2, x 3 et x 4 dans l'équation (2) dans les carrés CD ', CE', CF 'et CG' respectivement. De même, inscrivez les coefficients x 1, x 2, x 3 et x 4 dans l'équation (3) dans les carrés DD ', DE', DF 'et DG', respectivement. Mettez les variables de jeu, x 3 et x 4, et leurs contributions 0 et 0, comme le montre l'équation (1) dans les carrés CB ', DB', CA 'et DA', respectivement.

Z j calculs de ligne

EC 'carré = 390 x 0 + 810 x = 0

ED 'carré = 2 x 0 + 3 x 0 = 0 et ainsi de suite.

C j - Z j calculs de ligne

FD 'carré = 6 - 0 = 6 (c.-à-d. AD' - FD ')

FE 'carré = 4 - 0 = 4 et ainsi de suite.

Réussite I Calculs:

Pass II Calculs:

Similaire au Pass I

Les valeurs de la ligne d'index (c'est-à-dire, C j - Z j ) dans le Passage II pour les variables de jeu, c'est-à-dire X 3 et X 4, ont une interprétation économique significative. Leurs valeurs absolues, c'est-à-dire 2 et 2/3 ici, montrent l'ampleur du changement de la valeur optimale de la fonction objectif qui se produirait en relâchant la contrainte correspondante d'une unité.

Cette valeur est appelée «prix fictif». Par conséquent, nous pouvons dire que si une heure supplémentaire de temps de coupe était disponible, la société de fabrication ABC pourrait augmenter le bénéfice de Rs. 2, c’est-à-dire que le prix fictif du temps de coupe est de RS. 2. De même, le prix fictif du temps de finition est de Rs. 2/3.

Aspects supplémentaires de la méthode simplex :

Méthode Big-M :

Jusqu'à présent, nous avons discuté de contraintes de type inférieur ou égal à. Mais beaucoup de problèmes ont des contraintes d'égalité, ou supérieures ou égales aux inégalités. Prenons un problème et résolvons-le.

Problème 1:

Maximiser la fonction de profit et donner votre commentaire:

Solution :

En introduisant les variables de jeu x 4 et x 5 et la variable artificielle x 6, nous avons la fonction objectif:

Lorsque la contrainte est de type ≥, il faut soustraire une variable de jeu pour obtenir une contrainte d'égalité. Pour générer une solution de base initiale réalisable avec de telles contraintes, une «variable artificielle» est ajoutée à chacune de ces contraintes. Contrairement aux variables de jeu, les variables artificielles n'ont aucune signification économique et ne sont utilisées que pour établir une solution de base réalisable initiale.

Comme cette variable n'a pas de signification économique, nous ne souhaitons pas qu'elle apparaisse dans le mix de solutions final. En conséquence, nous attribuons une très grande valeur négative à la fonction objectif. Dans notre équation (1), M est un grand nombre positif arbitraire.

Voir maintenant le tableau 5.2. Comme toutes les valeurs de la ligne d'index final (C j - Z j ) sont soit négatives, soit égales à zéro, la solution optimale a été atteinte.

. . . x 1 = 900, x 2 = 1000, x 3 = 0 et Z (maximum = 62 400).

Les calculs sont similaires au problème précédent.

Problème 2

Utilisez la méthode Big-M pour maximiser Z = 6x 1 + 4x 2 sous réserve de contraintes

Donnez deux solutions différentes, si la solution n'est pas unique.

Solution:

En introduisant des variables de jeu x 3 et x 4, des variables excédentaires x 5 et des variables artificielles x 6, nous obtenons les contraintes suivantes:

Et la fonction objectif est: Maximiser Z = 6x 1 + 4x 2 + 0x 3 + 0x 4 + 0x 5 - Mx 6

Maintenant, obtenez la solution en éliminant big-M.

Problème de minimisation :

Si longtemps, nous avons discuté des problèmes de maximisation. Mais dans de nombreuses situations pratiques, la fonction objective doit être minimisée. Ici, nous convertissons le problème de minimisation en un problème de maximisation en utilisant l'expression suivante.

Minimiser Z = - Maximiser (-Z).

Ensuite, nous maximisons (-Z) comme auparavant et prenons la valeur négative de maximiser (-Z).

Problème 3

Utilisez la méthode Big-M pour minimiser Z = 15x 1 + 12x 2 sous réserve des contraintes:

Solution:

En introduisant les variables excédentaires x 3 et x 4 et les variables artificielles x 5 et x 6, on obtient

Réduit Z = 15x 1 + 12x 2 + 0x 3 + 0x 4 + Mx 5 + Mx 6

soumis à des contraintes

Maintenant, Minimize Z = - Maximize (-Z). Maximize (-Z) = -15x 1 - 12x 2 - 0x 3 - 0x 4 - Mx 5 - Mx 6 ici .

Appliquez ensuite la méthode Big-M pour résoudre l’agrandissement (-Z). La valeur optimale de minimiser Z = la valeur négative de maximiser (-Z).

L'énoncé mathématique général du modèle LP :

Le double :

Chaque problème de programmation linéaire a un deuxième problème complémentaire de LP, appelé «dual». Le problème initial s'appelle 'primal'. La solution du "primal" peut être obtenue en résolvant "dual" ou "primal". Si «primal» est un problème de maximisation, «dual» est un problème de minimisation et inversement.

Relation entre le primal et le duel :

Problème 1

Problème primordial:

Maximiser z = 60x 1 + 80x 2,

Dans les deux cas, z (max.) = Α (min), y 1 et y 2 sont les variables «doubles». Nous pouvons résoudre les problèmes duels par la méthode graphique ou simplex.

Analyse de sensibilité :

Après avoir obtenu la solution optimale d'un problème LP, nous pouvons étudier les modifications de la solution optimale en modifiant les paramètres du problème.

Les modifications suivantes peuvent être apportées:

(1) Changer les coefficients de la fonction objectif.

(2) Changer le coefficient de coefficients des variables sur les lhs des contraintes.

(3) Modifiez les nombres sur le rhs des contraintes.

(4) Ajouter / soustraire de nouvelles variables et

(5) Ajouter / soustraire des contraintes, etc.

Cette étude est significative car elle montre à quel point la solution optimale actuelle est sensible aux changements de paramètres. La direction peut être disposée à connaître la plage de variation des paramètres qui n’affecte pas la solution optimale à l’étude.

Cette étude d’un problème de PL est appelée «analyse de sensibilité». La plupart des analyses sont effectuées à l'aide de codes informatiques. Nous devrions pouvoir interpréter le résultat de ces codes, par exemple, Code LPGOGO, etc.

 

Laissez Vos Commentaires