Problèmes de programmation linéaire, solutions et applications [avec exemple]

La science des données a de nombreuses applications, l'une des plus importantes d'entre elles étant l'optimisation. Nous avons tous tendance à nous concentrer sur l'optimisation des choses. L'optimisation vise à obtenir les résultats les plus souhaités avec les ressources limitées dont vous disposez.

Il existe toutes sortes de problèmes d'optimisation disponibles, certains sont petits, d'autres très compliqués. En les parcourant, vous trouverez une catégorie spécifique appelée problèmes de programmation linéaire. Dans cet article, nous avons discuté de ce qu'ils sont et comment vous pouvez travailler dessus.

Supposons que vous soyez un vendeur de fruits qui peut acheter des oranges ou des pommes ou une certaine combinaison des deux. Cependant, vous n'avez qu'un budget de 5 000 INR et vous ne pouvez en stocker que 30 sacs. Maintenant, vous devez les acheter de la manière qui vous rapporte le plus de profit.

Désormais, un sac d'oranges vous coûte 500 INR tandis qu'un sac de pommes vous coûte 750 INR. Vous pouvez gagner 100 INR avec la vente d'un sac d'oranges et 200 INR avec la vente d'un sac de pommes.

Ce problème a diverses possibilités. Vous pourriez choisir de n'acheter que des oranges, mais vous n'auriez alors que 10 sacs dans votre entrepôt et votre bénéfice serait de 1 000 INR. De même, vous pourriez choisir de n'acheter que des pommes et de réaliser un bénéfice de 1 500 INR. Vous pouvez également acheter une combinaison des deux.

De tels problèmes sont appelés problèmes de programmation linéaire et nous en discuterons en détail. Commençons:

Qu'est-ce que la programmation linéaire ?

La programmation linéaire est une méthode de représentation de relations complexes à l'aide de fonctions linéaires. Notre objectif avec la programmation linéaire est de trouver les solutions les plus appropriées pour ces fonctions. La relation réelle entre deux points peut être très complexe, mais nous pouvons utiliser la programmation linéaire pour les représenter avec simplicité. La programmation linéaire trouve des applications dans de nombreuses industries.

Bases de la programmation linéaire

Voici quelques termes fondamentaux de la programmation linéaire :

Contrainte

Les limitations (ou restrictions) de vos variables de décision sont appelées contraintes. La plupart des contraintes de temps sont les limites que vous avez sur vos ressources pour résoudre un problème.

Variable de décision

Ces variables définissent votre sortie. Votre résultat dépend de ces variables, c'est pourquoi nous les appelons 'variables de décision'.

Restriction de non-négativité

Les variables de décision d'un problème de programmation linéaire ne peuvent avoir que des valeurs non négatives. Cela signifie que les valeurs de vos variables de décision peuvent être égales ou supérieures à zéro uniquement.

Fonction objectif

La fonction objectif est l'objectif de prendre votre décision. En termes simples, c'est le résultat final de votre problème de programmation linéaire. Par exemple, lorsque vous recherchez le profit maximum que vous pouvez réaliser avec un ensemble donné de ressources, le profit maximum est la fonction objectif.

Formulation de problèmes de programmation linéaire

Vous devez savoir formuler une programmation linéaire pour l'appliquer dans la vie réelle. Supposons que vous soyez un fabricant de jouets et que vous ne produisiez que deux jouets : A et B. En gros, vos jouets nécessitent deux ressources X et Y pour être fabriqués. Voici les exigences de vos jouets :

• Une unité de jouet A nécessite une unité de ressource X et trois unités de ressource Y

• Une unité de jouet B nécessite une unité de ressource X et deux unités de ressource Y

Vous avez cinq unités de ressource X et 12 unités de ressource Y. Vos marges bénéficiaires sur la vente de ces jouets sont :

• 6 INR sur chaque unité vendue du jouet A
• 5 INR sur chaque unité vendue de jouet B

Combien d'unités de chaque jouet produiriez-vous pour obtenir le maximum de profit ?

La solution

Représentons notre problème de programmation linéaire dans une équation :

Z = 6a + 5b

Ici, z représente le bénéfice total, a représente le nombre total d'unités de jouet A et b représente le nombre total d'unités B. Notre objectif est de maximiser la valeur de Z (le profit).

Maintenant, votre entreprise voudrait produire autant d'unités de ces jouets que possible, mais vos ressources sont limitées. Les limites de nos ressources sont les contraintes de ce problème. Nous n'avons qu'un total de

un + b 5

Maintenant, chaque unité de jouet A et B nécessite respectivement 3 et 2 unités de ressource Y. Et nous n'avons qu'un total de 12 unités de ressource Y donc mathématiquement, cela ressemblerait à ceci :

3a + 2b 12

N'oubliez pas que les valeurs des unités du jouet A ne peuvent être que des nombres entiers. Cela signifie que nous avons aussi les contraintes de a->0 et b<-0.

Donc, maintenant vous avez un problème de programmation linéaire approprié. Vous pouvez formuler d'autres problèmes de programmation linéaire en suivant cet exemple. Bien que cet exemple soit assez simple, les problèmes LP peuvent devenir très compliqués.

Lire : Idées et sujets de projets de programmation linéaire

Étapes de la formulation des problèmes de programmation linéaire

Pour formuler un problème de programmation linéaire, suivez ces étapes :

• Trouver les variables de décision
• Trouver la fonction objectif
• Identifier les contraintes
• Rappelez-vous la restriction de non-négativité

Si un problème répond aux critères ci-dessus, il s'agit d'un problème de programmation linéaire. Il est recommandé de garder ce critère à l'esprit lorsque vous travaillez sur l'identification du type de problème.

Résoudre des problèmes de programmation linéaire avec R

Si vous utilisez R, la résolution des problèmes de programmation linéaire devient beaucoup plus simple. C'est parce que R possède le package lpsolve qui contient diverses fonctions spécialement conçues pour résoudre de tels problèmes. Il est fort probable que vous utiliserez R très fréquemment pour résoudre des problèmes de LP en tant que data scientist. C'est pourquoi nous avons partagé deux exemples distincts pour vous aider à mieux comprendre sa mise en œuvre :

Exemple

Commençons par un problème de base. Une organisation a deux produits avec des prix de vente de 25 INR et 20 INR et sont appelés produit A et B respectivement. Chaque jour, ils disposent de 1800 unités de ressources pour fabriquer ces produits. Le produit A nécessite 20 unités de ressources et B nécessite 12 unités de ressources. Le temps de production de ces deux produits est de quatre minutes et l'organisation dispose d'un total de huit heures de travail par jour. Le problème est de savoir quelle devrait être la quantité de production de chacun de ces produits pour maximiser les profits de l'entreprise ?

Solution:

Nous allons commencer à résoudre ce problème en définissant sa fonction objectif :

max(Ventes) = max( 25 ans 1 + 20 ans 2 )

Ici, 25 et 20 sont respectivement les prix des produits A et B, y1 est le nombre total d'unités de produit A produites et y2 est le nombre total d'unités de produit B produites. Nos variables de décision sont y1 et y2.

Nous allons maintenant définir les contraintes de notre problème :

Contrainte de ressources :

20 ans 1 + 12 ans 2 1800

Contrainte de temps:

4 ans 1 + 4 ans 2 8*60

Notre objectif est de trouver le nombre correct de produits que nous devons fabriquer pour obtenir le maximum de profit.

Utiliser R pour résoudre le problème :

Nous allons utiliser lpsolve pour résoudre ce problème LP et commencer par définir la fonction objective :

> exiger (lpSolve)

Chargement du package requis : lpSolve

> objectif.en <- c(25, 20)

> objectif.in

[1] 25 20

Ensuite, nous allons construire une matrice pour les contraintes :

> const <- matrice(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> constante

[,1] [,2]

[1,] 20 12

[2,] 4 4

> contraintes_de_temps <- (8*60)

> contraintes_ressources <- 1800

> contraintes_de_temps

[1] 480

> contraintes_ressources

[1] 1800

Créons maintenant les équations déjà définies :

> rhs <- c(ressource_constraints, time_constraints)

> droite

[1] 1800 480

> sens <- c(“<=”, “<=”)

> orientation

[1] "<=" "<="

Une fois toutes les informations nécessaires ajoutées, nous pouvons commencer à trouver la réponse optimale. La syntaxe de notre package est la suivante :

lp( direction, objectif, const.mat, const.dir, const.rhs )

> optimal <- lp(direction=”max”, objectif.in, const, direction, rhs)

> optimale

Succès : la fonction objectif est 2625

> résumé (optimal)

Mode classe de longueur

sens 1 -aucun- numérique

x.count 1 -aucun- numérique

objectif 2 -aucun- numérique

const.count 1 -aucun- numérique

contraintes 8 -aucune- numérique

int.count 1 -aucun- numérique

int.vec 1 -aucun- numérique

bin.count 1 -aucun- numérique

binaire.vec 1 -aucun- numérique

num.bin.solns 1 -aucun- numérique

objval 1 -aucun- numérique

solution 2 -aucune- numérique

presolve 1 -aucun- numérique

compute.sens 1 -aucun- numérique

sens.coef.from 1 -aucun- numérique

sens.coef.to 1 -aucun- numérique

duals 1 -aucun- numérique

duals.from 1 -aucun- numérique

duals.to 1 -aucun- numérique

échelle 1 -aucune- numérique

use.dense 1 -aucun- numérique

dense.col 1 -aucun- numérique

dense.val 1 -aucun- numérique

dense.const.nrow 1 -aucun- numérique

dense.ctr 1 -aucun- numérique

use.rw 1 -aucun- numérique

tmp 1 -aucun- caractère

état 1 -aucun- numérique

Après avoir exécuté le code ci-dessus, vous pouvez obtenir les solutions souhaitées pour notre problème.

Les valeurs optimales pour y1 et y2 :

Rappelons que y1 et y2 étaient les unités du produit A et du produit B que nous devions fabriquer :

> solution$optimale

[1] 45 75

Le chiffre d'affaires optimal :

Le profit maximum que nous pouvons générer avec les valeurs obtenues de y1 et y2 est :

> optimal$objval

[1] 2625

Lisez aussi: Algèbre linéaire pour l'apprentissage automatique

Utilisations de la programmation linéaire

Comme nous l'avons mentionné précédemment, la programmation linéaire trouve des applications dans de nombreuses industries. Voici quelques domaines où nous l'utilisons :

• Avec la popularité croissante des services de livraison, la programmation linéaire est devenue l'une des méthodes préférées pour trouver les itinéraires optimaux. Lorsque vous prenez un Ola ou un Uber, le logiciel utilise la programmation linéaire pour trouver le meilleur itinéraire. Les sociétés de livraison comme Amazon et FedEx l'utilisent également pour déterminer les meilleurs itinéraires pour leurs livreurs. Ils se concentrent sur la réduction des délais et des coûts de livraison.
• L'apprentissage supervisé de l'apprentissage automatique fonctionne sur les concepts fondamentaux de la programmation linéaire. Dans l'apprentissage supervisé, vous devez trouver le modèle mathématique optimal pour prédire la sortie en fonction des données d'entrée fournies.
• Le secteur de la vente au détail utilise la programmation linéaire pour optimiser l'espace en rayon. Avec autant de marques et de produits disponibles, déterminer où les placer dans le magasin est une tâche très rigoureuse. Le placement d'un produit dans le magasin peut affecter considérablement ses ventes. Les grandes chaînes de distribution telles que Big Bazaar, Reliance, Walmart, etc. utilisent la programmation linéaire pour déterminer le placement des produits. Ils doivent garder à l'esprit l'intérêt des consommateurs tout en assurant le meilleur placement de produit pour générer un profit maximum.
• Les entreprises utilisent la programmation linéaire pour améliorer leurs chaînes d'approvisionnement. L'efficacité d'une chaîne d'approvisionnement dépend de nombreux facteurs tels que les itinéraires choisis, les horaires, etc. En utilisant la programmation linéaire, ils peuvent trouver les meilleurs itinéraires, horaires et autres allocations de ressources pour optimiser leur efficacité.

En savoir plus sur la programmation linéaire et la science des données

La programmation linéaire est l'un des concepts les plus essentiels de la science des données. C'est également un sujet fondamental que vous devez connaître pour devenir un data scientist compétent. Comme nous en avons discuté, il existe de nombreuses applications pour ce concept et vous pouvez trouver ses cas d'utilisation dans votre vie quotidienne.

Vous pouvez en savoir plus sur la science des données et ses concepts associés en vous rendant sur notre blog. Nous avons de nombreuses ressources précieuses pour vous aider à en savoir plus. En voici quelques-unes pour votre lecture ultérieure :

• Principales raisons de devenir Data Scientist
• Les algorithmes que tout data scientist devrait connaître
• Comment devenir un scientifique des données

D'autre part, vous pouvez suivre un cours de science des données pour apprendre des experts de l'industrie. Vous apprendrez de manière interactive à travers des vidéos, des quiz et des projets. Suivre un cours vous aidera à acquérir les compétences nécessaires pour devenir un data scientist professionnel. Découvrez le diplôme PG en science des données de IIIT-B & upGrad, créé pour les professionnels en activité et proposant plus de 10 études de cas et projets, des ateliers pratiques, un mentorat avec des experts de l'industrie, des entretiens individuels avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.