Mémorandum @ Python OR Séminaire: Pulp

Une bibliothèque pour la modélisation d'optimisation mathématique. Des solveurs tels que «Gurobi», «CBC» et «GLPK» peuvent être utilisés. Je ne connais pas grand-chose à l'optimisation, je prévois donc d'étudier à l'avenir.

Procédure de création de modèle mathématique

La procédure pour résoudre un problème avec un modèle mathématique est la suivante.

• () Est le nom de la classe dans pulp.

1. Créez un modèle mathématique (LpProblem)
2. Ajoutez une variable (LpVariable)
3. Ajoutez l'expression de fonction objective (LpAffineExpression)
4. Ajoutez une contrainte (LpConstraint)

Modèle mathématique: LpProblem

LpProblem(name='NoName', sense=LpMinimize)

--name: nom du modèle mathématique. La valeur par défaut est «NoName». --sense: Soit minimiser (LpMinimize), soit maximiser (LpMaximize).

Variable: LpVariable

LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)

--name: nom de la variable -- lowBound: limite inférieure --ʻUpBound: limite supérieure --cat`: type de variable

• LpContinuous: variable continue
• LpInteger: variable entière
• LpBinary: variables binaires
• ʻE`: Utilisé pour le modèle basé sur des colonnes (je ne suis pas sûr)

Fonction objective: LpAffineExpression

Peut être créé comme " x + 2 * y "en utilisant des variables Il est également possible d'ajouter des termes à l'expression ultérieurement Spécifiez la fonction objectif comme "m + = expression" (cependant, m est un modèle mathématique)

Contrainte: LpConstraint

Peut être créé à l'aide de variables telles que " x + y <= 1 " Il est également possible d'ajouter un terme plus tard sur le côté gauche de la contrainte Les contraintes sont spécifiées comme " m + = expression <= côté droit "

Autre

Des fonctions qui semblent souvent utilisées value (): Récupère la valeur de la variable lpSum (): trouve la somme des termes lpDot (): trouve le produit interne de deux listes

La feuille de triche est ici

Essayez de résoudre le problème du sac à dos

Problèmes d'optimisation courants

Mettez autant d'articles que possible dans un sac à dos puis:

• Le poids maximum que l'on peut mettre dans un sac à dos est de 600 grammes.

Il y a des restrictions comme. Donc que fais-tu?

Formuler

Insérez l'élément $ s_i $ → $ v_i = 1 $ Ne pas mettre l'élément $ s_i $ → $ v_i = 0 $

\begin{array}{cl}
\max & \sum_i{s_i \ v_i} \\
\mbox{subject to} & \sum_i{s_i \ v_i} \leq C \\
                 & v_i \in \{0, 1\} ~ \forall i
\end{array}

Mettre en œuvre avec de la pulpe

>>> #Le poids de l'article
>>> s = [128, 108, 34, 53, 71, 224, 299, 181, 336, 15]
>>> #Capacité de charge maximale du sac à dos
>>> C = 600
>>> #Préparation de la bibliothèque
>>> from pulp import LpProblem, LpVariable, LpMaximize, LpBinary
>>> rn = range(len(s))
>>> #Préparation du modèle
>>> m = LpProblem('knapsack', LpMaximize)
>>> #variable(0 s'il faut inclure le i-ème élément/1)
>>> v = [LpVariable('v%d' % i, cat = LpBinary) for i in rn]
>>> #Fonction objective
>>> m += lpDot(s, v)
>>> #Contrainte
>>> m += lpDot(s, v) <= C
>>> #résoudre
>>> m.solve()
>>> #production
>>> print(LpStatus[m.status], sum(s[i] * value(v[i]) for i in rn))
>>> print([s[i] for i in rn if value(v[i]) > 0.5])
Optimal 600.0
[108, 34, 53, 224, 181]

Autres problèmes d'optimisation

D'autres problèmes d'optimisation peuvent être résolus en formulant (comme)

Problème de placement des installations (p-médiane)

Le problème de la sélection de p parmi les installations candidates et de la minimisation de la distance totale entre le point de demande et l'installation

Exemple

• Sélectionnez 4 refuges parmi les candidats pour les refuges et minimisez la distance totale parcourue entre les résidents et les refuges (p == 4)
• $ x_ {ij} $ indique si le résident j évacue vers l'installation i, et $ y_i $ indique si l'installation i est sélectionnée ou non (la distance est $ d_ {ij} $).

Formulation

\begin{array}{cl}
\min & \sum_i{\sum_j{d_{ij} \ x_{ij}}} ~ ~ ~ ~ (1) \\
\mbox{subject to} & \sum_i{y_i} = p ~ ~ ~ ~ (2) \\
                 & \sum_i{x_{ij}} = 1 ~ \forall j ~ ~ ~ ~ (3) \\
                 & x_{ij} \leq y_i ~ \forall i, j ~ ~ ~ ~ (4) \\
                 & x_{ij} \in \{0, 1\} ~ \forall i, j
\end{array}

Sudoku

C'est courant.

• Ne définissez pas la fonction objectif tant que la contrainte est satisfaite
• Une variable 0/1 indique s'il faut utiliser le nombre k à la position de la ligne i et de la colonne j.
• représenté par v [i, j, k]
• Contrainte
• Un seul chiffre peut être utilisé aux positions verticale i et horizontale j (1)
• Un seul nombre j peut être utilisé dans chaque ligne i (2)
• Un seul chiffre j peut être utilisé dans chaque colonne i (3)
• Un seul nombre j peut être utilisé en 3 $ \ fois 3 $ (4)

Formulation

\begin{array}{cl}
\min & \mbox{no objective function} \\
\mbox{subject to} & \sum_k{v_{ijk}} = 1 ~ \forall i, j ~ (1)\\
                 & \sum_k{v_{ikj}} = 1 ~ \forall i, j ~ (2) \\
                 & \sum_k{v_{kij}} = 1 ~ \forall i, j ~ (3) \\
                 & 3\Il en va de même pour les carrés des temps3~ (4) \\
                 & v_{ijk} \in \{0, 1\} ~ \forall i, j, k
\end{array}

Autres problèmes d'optimisation