Programmation linéaire avec des tableurs

En tant que manager, vous faites toujours face à des ressources finies ou limitées, tandis que la direction attend de vous que vous en tiriez le meilleur parti. Du temps de productivité à l’utilisation du capital, du foncier à la main-d’œuvre, de la chaîne d’approvisionnement à la production — presque tout ce que vous faites vise à optimiser la productivité.

La plupart des compagnies aériennes optimisent leurs plannings de vol pour maximiser les revenus et minimiser les coûts. Ces plannings impliquent de nombreuses situations et restrictions, comme le nombre d’appareils à un endroit donné, le carburant, les équipages ou le type de ligne (routes populaires et rentables). Ces situations et restrictions constituent les contraintes pour faire voler les avions sur les routes les plus demandées et les plus rentables. La programmation linéaire permet de trouver la solution à ce problème sous contraintes.

Dans ce tutoriel, vous allez découvrir la programmation linéaire. Nous aborderons les points suivants :

• Introduction à la programmation linéaire
• Notions de base de la PL
  • Variable de décision
  • Contraintes
  • Fonction objectif
  • Solution optimale
  • Solution réalisable
  • Solution irréalisable
  • Région réalisable
  • Contraintes de non-négativité
• Formulation d’un problème de PL (avec exemple)
• Méthode graphique pour résoudre une PL dans un tableur
• Cas d’usage de la PL
• Conclusion

Introduction à la programmation linéaire

D’un point de vue mathématique, la programmation linéaire optimise (minimise ou maximise) une fonction objectif linéaire de plusieurs variables sous des conditions/contraintes données exprimées par un système d’inégalités linéaires. Elle s’applique à la planification d’activités économiques comme le transport de biens et services, la fabrication, l’optimisation des réseaux électriques ou des flux sur les réseaux. Les problèmes de PL se résolvent à l’aide de différentes techniques, comme la méthode graphique, le Simplexe ou l’algorithme de Karmarkar.

Notions de base de la PL

Passons en revue les principales terminologies de la programmation linéaire :

• Variables de décision : ce sont les variables utilisées dans la fonction objectif. Elles déterminent votre résultat. Le décideur peut agir sur la valeur de la fonction objectif via ces variables. Pour résoudre un problème de PL, il faut d’abord identifier les variables de décision.

• Contraintes : un ensemble de limitations ou de conditions. Elles peuvent prendre la forme d’égalités ou d’inégalités et restreignent la valeur des variables de décision.

• La fonction objectif est une fonction de profit ou de coût à maximiser ou minimiser. C’est la cible principale de la décision.

• La solution optimale est l’une des solutions réalisables pour laquelle la fonction objectif est maximale ou minimale (par exemple, profit maximal ou coût minimal). C’est la meilleure valeur de la fonction objectif.

• Une solution réalisable est un ensemble de valeurs des variables de décision qui respectent toutes les contraintes. Un problème de PL est réalisable s’il existe au moins une solution réalisable.

• La solution irréalisable désigne l’ensemble des valeurs des variables de décision qui ne respectent pas toutes les contraintes, c’est-à-dire qu’il n’existe pas de solution optimale. Un problème de PL est dit irréalisable si aucune solution ne satisfait l’ensemble des contraintes.

• La région réalisable est la zone formée par l’ensemble des valeurs qui satisfont les contraintes, autrement dit l’intersection de toutes les contraintes. Elle inclut inégalités, égalités et contraintes d’intégrité le cas échéant.

• Les contraintes de non-négativité imposent que les variables de décision ne prennent que des valeurs non négatives, c’est-à-dire supérieures ou égales à zéro.

Formulation d’un problème de PL (avec exemple)

La formulation d’un modèle de programmation linéaire suit les étapes suivantes :

• Identifier les variables de décision
• Déterminer la fonction objectif
• Identifier les contraintes
• Définir les contraintes de non-négativité

Dans un problème de PL, les variables de décision, la fonction objectif et les contraintes doivent toutes être linéaires.

Énoncé du problème : Un commerçant en meubles ne vend que deux articles — des tables et des chaises. Il dispose de 50 000 Rs à investir et d’un espace de stockage d’au plus 60 pièces. Une table coûte 2 500 Rs et une chaise 500 Rs. Il estime qu’il peut réaliser un bénéfice de 250 Rs par table vendue et de 75 Rs par chaise vendue. Il souhaite savoir combien de tables et de chaises acheter avec l’argent disponible pour maximiser son bénéfice total, en supposant qu’il puisse tout vendre. (Source)

Dans cet exemple, on observe que :

1. Le commerçant peut investir son argent en achetant des tables, des chaises ou une combinaison des deux. Différentes stratégies d’investissement mènent à des bénéfices différents. (Source)
2. Son investissement est plafonné à 50 000 Rs, tout comme sa capacité de stockage, limitée à 60 pièces. (Source)

Formulation mathématique :

Supposons qu’il décide d’acheter uniquement des tables, aucune chaise. Il peut alors en acheter 50 000/2 500 = 20 tables. Dans ce cas, il gagnera 250 × 20 = 5 000 Rs de bénéfice. Ou bien il achète uniquement des chaises, aucune table : il peut en acheter 50 000/500 = 100 chaises.

Dans ce cas, il gagnera 75 × 60 = 4 500 Rs de bénéfice.

Il existe de nombreuses combinaisons possibles de tables et de chaises.

Supposons qu’il achète X tables et Y chaises. X et Y doivent être non négatifs.

1. Le commerçant dispose d’au plus 50 000 Rs pour acheter des tables et des chaises, donc :

   2 500 X + 500 Y <= 50 000 (contrainte d’investissement) ou 5 * X + Y <= 100 .................................... Éq.1

1. Le nombre maximum d’unités qu’il peut stocker est 60.

   X + Y <= 60 .................................... Éq.2

1. Le commerçant souhaite acheter des quantités qui maximisent son profit Z, d’où :

   Max Z : 250 X + 75 Y

Fonction objectif : Max Z : 250 X + 75 Y

Sous contraintes :

5 * X + Y <= 100,
X + Y <= 60 and
X,Y >= 0

Source : http://ncert.nic.in/ncerts/l/lemh206.pdf

Méthode graphique pour résoudre une PL dans un tableur

Exemple de programmation linéaire

Fonction objectif : Max Z : 250 X + 75 Y

Sous contraintes :

5 * X + Y <= 100,

X + Y <= 60 and

Where X,Y >= 0

Étape 1 : Saisissez la fonction dans Excel comme montré ci-dessous.

Étape 2 : Après avoir noté la fonction objectif et les contraintes dans le tableur, calculons les valeurs pour les contraintes C1 et C2. Vous pouvez obtenir ces valeurs en annulant l’autre variable. Par exemple pour C1, à X = 0, la valeur de Y est Y = 100 et à Y = 0, la valeur de X est X = 20. De même pour la contrainte C2.

Étape 3 : Après avoir calculé les valeurs, traçons le graphique. Sélectionnez les valeurs de la contrainte C1, allez dans Insertion et créez un nuage de points avec lignes lissées. Vous obtiendrez un graphique de ce type.

S’il ressemble à ceci, pas d’inquiétude : suivez les étapes ci-dessous pour le modifier. Faites un clic droit sur le graphique, choisissez Sélectionner des données, vous verrez deux séries : supprimez la série 2 et modifiez la série 1.

Nommez la série C1 et remplacez sa valeur en X par les valeurs de la colonne A de C1 et sa valeur en Y par les valeurs de la colonne B de C1. Cliquez sur OK. Votre graphique devrait ressembler à ceci :

Étape 4 : Retournez dans Sélectionner des données via un clic droit sur le graphique et ajoutez une autre série. Nommez-la C2, sélectionnez pour X les valeurs de la colonne X de C2 et pour Y les valeurs de la colonne Y de C2. Votre graphique devrait maintenant ressembler à ceci :

Étape 5 : Le graphique est tracé ; il faut maintenant identifier la région réalisable :

Vous avez désormais 4 points (O, A, B, C) dans la région réalisable. Calculez la valeur de la fonction objectif en chacun de ces points pour identifier celui qui la maximise.

Étape 6 : Pour calculer les valeurs de la fonction objectif, procédez comme suit :

Calculez la fonction objectif pour chaque point :

• Au point O, les coordonnées (X, Y) sont (0, 0). La valeur de la fonction objectif est donc = (2500 + 750) = 0
• Au point A, les coordonnées (X, Y) sont (0, 60). La valeur de la fonction objectif est donc = (2500 + 7560) = 4 500
• Au point B, les coordonnées (X, Y) sont (20, 0). La valeur de la fonction objectif est donc = (25020 + 750) = 5 000

• Au point C : pour trouver ses coordonnées, déterminez le point d’intersection des droites de contraintes C1 et C2. Utilisez les fonctions MMULT() et MINVERSE() pour calculer l’intersection de deux équations.

• MMULT(MINVERSE(array), array) # renvoie la solution d’un système de deux variables. Ou : =MMULT(MINVERSE(AB17:AC18), AE17:AE18). Avant d’utiliser cette formule, sélectionnez les cellules X et Y (en jaune), appliquez la fonction pour calculer l’intersection des deux équations et appuyez sur CTRL+MAJ+ENTRÉE.

Valeurs finales de Z :

Comme vous pouvez le constater, pour ce problème de maximisation, la valeur maximale de Z est obtenue au point B, et elle vaut 6 250 Rs. Ainsi, pour maximiser le profit, le commerçant doit acheter 10 tables et 50 chaises.

Cas d’usage de la PL

La programmation linéaire sert à trouver des solutions optimales en recherche opérationnelle. Elle identifie la meilleure solution dans un ensemble donné de contraintes et de limitations. Elle s’applique à de nombreux domaines : activités économiques en agriculture, ingénierie, fabrication, énergie, logistique et chaîne d’approvisionnement.

• Les ingénieurs l’utilisent dans l’industrie manufacturière et de production pour optimiser les ressources disponibles et ainsi maximiser les profits.

• Le secteur de la logistique et du transport s’appuie sur la PL pour trouver le plus court chemin/itinéraire, estimer les temps de trajet et définir des stratégies tarifaires.

• Dans le secteur de l’énergie, elle permet d’optimiser la charge électrique, de minimiser la longueur des lignes de distribution et d’améliorer la conception du réseau.

• Dans le secteur agricole, la PL aide à déterminer les types et quantités de cultures à produire pour accroître efficacement les revenus.

• Dans l’industrie agroalimentaire, elle assiste responsables santé et nutritionnistes dans la planification de régimes alimentaires et la constitution de paniers à faible coût pour prévenir les maladies non transmissibles.

Conclusion

Félicitations, vous êtes arrivé au bout de ce tutoriel !

Vous avez couvert de nombreux aspects de la programmation linéaire : définition, concepts et terminologie, formulation d’un problème de PL, résolution par la méthode graphique, et principaux cas d’usage.

Vous devriez désormais pouvoir mobiliser ces concepts pour prendre des décisions dans votre organisation ou aider les décideurs à optimiser les résultats. Merci de votre lecture !

Découvrez notre tutoriel Graphs in Spreadsheets.

Si vous souhaitez aller plus loin sur les tableurs, suivez les cours DataCamp ci-dessous :