Maison / Technologie / Programmation linéaire en Python: un tutoriel simple

Programmation linéaire en Python: un tutoriel simple

Suivre
( 0 Abonné(e)s )
X

Suivre

E-mail : *
Programmation linéaire en Python: un tutoriel simple 0 vGRp32oF9PkPpNBI

La programmation linéaire est l’une des techniques d’optimisation les plus courantes. Il a un large éventail d'applications et est fréquemment utilisé dans la recherche opérationnelle, le design industriel, la planification, etc. Hélas, il n’est pas aussi populaire que l’apprentissage automatique (qui est certainement une forme d’optimisation elle-même), mais constitue la méthode idéale pour les problèmes pouvant être formulés à l’aide de variables de décision ayant des relations linéaires. Ceci est un tutoriel pratique rapide, je vais peut-être aborder l'algorithme Simplex et la théorie dans un post ultérieur.

Déclaration de problème

Juste pour avoir une idée, nous allons résoudre un problème simple concernant la planification de la production. Imaginez que vous travaillez pour une entreprise qui construit des ordinateurs. Un ordinateur est un produit assez complexe, et plusieurs usines l’assemblent pour lesquelles l’entreprise verse un certain montant par unité. Le coût de ce modèle d'ordinateur sur le marché est fixé à 500 $, différentes usines assemblent les ordinateurs à des vitesses et à des coûts différents. Usine f0 produit 2000 par jour à 450 $ par unité, usine f1 1500 par jour à 420 $ par unité et f2 1000 par jour à 400 $ par unité. Nous avons 1 mois pour assembler 80 000 unités sous la contrainte qu'aucune usine ne produise plus du double d'unités par rapport à toute autre usine. La question est, quelle est la répartition optimale de la production entre les usines tel que nous maximiser le profit obtenu de la vente des ordinateurs sous ces contraintes?

Dans ce tutoriel, nous allons utiliser Python et un logiciel d’optimisation de la programmation linéaire. Pulpe, copier-coller installer avec pip:

pip installer la pulpe

Maintenant, pour résoudre le problème de la production informatique avec la programmation linéaire, nous avons besoin des éléments suivants:

  1. L'ensemble des variables de décision
  2. L'ensemble des contraintes linéaires sur ces variables
  3. Une fonction d'objectif linéaire pour maximiser ou minimiser

Alors, ouvrez votre éditeur favori et commençons. Avant de définir les variables dans PuLP, nous devons créer un objet problématique avec le code suivant:

importation de pâte *
problem = LpProblem ("problemName", LpMaximize)

Nous allons ajouter les contraintes et la fonction objectif à cet objet. Notez que le constructeur du problème reçoit un nom de problème et LpMaximize, ce qui signifie que nous voulons maximiser notre fonction objectif. Dans notre cas, il s’agit des bénéfices tirés de la vente d’un certain nombre d’ordinateurs. De plus, nous définissons également les constantes que nous avons reçues de l’énoncé du problème:

# coût d'usine par jour
cf0 = 450
cf1 = 420
cf2 = 400
# débit d'usine par jour
f0 = 2000
f1 = 1500
f2 = 1000
# objectif de production
objectif = 80000
# limite de temps
max_num_days = 30
num_factories = 3

Dans la section suivante, nous définirons les variables de décision.

Variables de décision

Dans PuLP, une variable de décision est définie de la manière suivante:

variable = LpVariable ("nomVariable")

Parfois, nous devons fournir des limites à la variable (la valeur par défaut n’est pas une limite). Dans ce cas, nous écririons ce qui suit:

var = LpVariable ("boundedVariableName", lowerBound, upperBound)

Un autre moyen utile de définir des variables dans PuLP consiste à utiliser la fonction dict. Cela peut être très utile dans les cas où nous devons définir un grand nombre de variables du même type et des mêmes limites, nomVariable serait une liste de clés pour le dictionnaire:

varDict = LpVariable.dicts ("varDict", noms de variables, lowBound, upBound)

Donc, sur la base des définitions précédentes, les variables de décision pour le problème de production informatique sont les jours que nous passons à la production pour chaque usine:

# des usines
num_factories = 3
factory_days = LpVariable.dicts ("factoryDays", liste (plage (num_factories)), 0, 30, cat = "Continu")

Contraintes

Maintenant que nous avons défini nos variables de décision, nous pouvons maintenant définir les contraintes du problème. Notez que les contraintes doivent être linéaires dans un paramètre de programmation linéaire. Les contraintes qui nous importent sont que le nombre d'unités assemblées doit être supérieur ou égal au montant cible et la contrainte de production qu'aucune usine ne devrait produire plus que le double de celle de l'autre usine:

# contrainte d'objectif
c1 = jours_usine[0]* f1 + jours_usine[1]* f2 + jours_usine[2] * f3> = objectif
# contraintes de production
c2 = jours_usine[0]* f0 <= 2 * jours_usine[1]* f1
c3 = jours_usine[0]* f0 <= 2 * jours_usine[2]* f2
c4 = jours_usine[1]* f1 <= 2 * jours_usine[2]* f2
c5 = jours_usine[1]* f1 <= 2 * jours_usine[0]* f0
c6 = jours_usine[2]* f2 <= 2 * jours_usine[1]* f1
c7 = jours_usine[2]* f2 <= 2 * jours_usine[0]* f0
# ajouter les contraintes au problème
problème + = c1
problème + = c2
problème + = c3
problème + = c4
problème + = c5
problème + = c6
problème + = c7

La fonction objective du problème d’assemblage d’ordinateurs consiste essentiellement à réduire le coût d’assemblage de tous ces ordinateurs. Ceci peut être écrit simplement comme maximisant le coût négatif:

# fonction objective
problème + = -factory_days[0]* cf0 * f0 - jours_usine[1]* cf1 * f1 - factory_days[2]* cf2 * f2

Regardons la définition du problème, cela peut être réalisé simplement par l'appel:

imprimer (problème)

Cela aboutit au résultat suivant qui, à mon avis, est explicite, il répertorie la fonction objectif, les contraintes et les différentes variables de décision dans le problème:

ordinateurAssemblage:
MAXIMISER
-900000 * factoryDays_0 + -630000 * factoryDays_1 + -400000 * factoryDays_2 + 0
SUJET À
_C1: 1500 factoryDays_0 + 1000 factoryDays_1 + 1000 factoryDays_2> = 80000

_C2: 2000 factoryDays_0 - 3000 factoryDays_1 <= 0

_C3: 2000 factoryDays_0 - 2000 factoryDays_2 <= 0

_C4: 1500 factoryDays_1 - 2000 factoryDays_2 <= 0

_C5: - 4000 factoryDays_0 + 1500 factoryDays_1 <= 0

_C6: - 3000 factoryDays_1 + 1000 factoryDays_2 <= 0

_C7: - 4000 factoryDays_0 + 1000 factoryDays_2 <= 0

VARIABLES
factoryDays_0 <= 30 en continu
factoryDays_1 <= 30 Continu
factoryDays_2 <= 30 en continu

La résolution

Une fois que nous avons défini tout ce qui est nécessaire dans notre problème de programmation linéaire, nous pouvons appeler la méthode de résolution qui fournit 1 si le problème est résolu et -1 s'il était impossible, c’est une simple ligne:

# résolution
problem.solve ()

Les solutions au problème peuvent être obtenues en accédant à l'attribut varValue de chaque variable:

pour i dans la plage (3):
print (f "Factory {i}: {factory_days[i].varValue} ")

Cela se traduit par la sortie suivante:

Usine 0: 23.076923
Usine 1: 15.384615
Usine 2: 30.0

En programmation linéaire, on suppose que les relations entre les variables sont linéaires et que les variables elles-mêmes sont continues. Pour faire suite à ce tutoriel, je couvrirai la programmation mixte d’entiers, où les variables peuvent être des entiers, ce qui s'avérera très utile car il peut être utilisé pour simuler une logique booléenne.

Programmation linéaire en Python: un tutoriel simple stat event post


Programmation linéaire en Python: un tutoriel simple a été publié à l'origine dans Hacker midi sur Medium, où les gens poursuivent la conversation en soulignant et en répondant à cette histoire.

Source

A propos newstrotteur-fr

Découvrez également

MAVERICK décolle! &#8211; Newstrotteur the first trailer for top gun maverick takes off social 310x165

MAVERICK décolle! – Newstrotteur

Suivre ( 0 Abonné(e)s ) X Suivre E-mail : * Suivre Ne plus suivre Tom …

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *