[PYTHON] Comment résoudre les problèmes de planification linéaire avec PuLP

Qu'est-ce que PuLP

Un package Python qui résout les problèmes de programmation linéaire. https://code.google.com/p/pulp-or/ https://pythonhosted.org/PuLP/index.html

Le problème de planification linéaire est un problème d'optimisation dans lequel la fonction objectif et les contraintes sont exprimées par des expressions linéaires. Par exemple

• Trouvez une combinaison de quantités qui maximise les profits lors de la fabrication d'une quantité fixe de plusieurs produits avec différents coûts et avantages.
• Résoudre le puzzle

Est l'un des problèmes de planification linéaire.

Depuis qu'il a été introduit à PyConJP 2014, lorsque j'ai étudié comment l'utiliser, C'est assez facile à utiliser, alors je l'ai résumé.

Comment installer

sudo pip install pulp

procédure

Créer un objet de problème de planification linéaire

Cela exprime tous les problèmes. Pour le constructeur, choisissez le nom du problème et s'il faut minimiser ou maximiser la fonction objectif.

import pulp
problem = pulp.LpProblem('Problem Name', pulp.LpMinimize) #Lors de la réduction
problem = pulp.LpProblem('Problem Name', pulp.LpMaximize) #Lors de la maximisation

Créer un objet variable

Créez des variables à utiliser dans la planification linéaire. Il y a deux façons de le faire. Vous utiliserez souvent 2 lorsque vous avez un grand nombre de variables.

(1) Faites un par un

pulp.LpVariable('name', 0, 1, 'Continuous') 

Les variables sont dans l'ordre de l'avant

1. Nom de variable
2. Valeur minimale de la variable
3. Valeur maximale de la variable
4. Type de variable. 'Continu' pour les flottants, 'Integer' pour les entiers, 'Binary' pour les variables binaires

Avec ce code, vous pouvez générer une variable qui prend une valeur continue de 0 à 1 avec le nom de la variable.

(2) Passez la liste et faites le tout ensemble

var = pulp.LpVariable.dicts('VAR', ([1,2,3], ['a', 'b']), 0, 1, 'Continuous')

Les variables sont dans l'ordre de l'avant

1. Préfixe de nom de variable
2. Un tuple d'une liste de suffixes avec des noms de variables
3. Valeur minimale de la variable
4. Valeur maximale de la variable
5. Type de variable

3-5 est le même que précédemment.

Lorsque ce code est exécuté, il prend des valeurs continues avec une valeur minimale de 0 et une valeur maximale de 1. Vous pouvez obtenir un dictionnaire avec les variables VAR_1_a, VAR_1_b, VAR_2_a, .... La méthode d'accès est var [1] ['a'] comme ceci. Cela sera utilisé dans un prochain article.

Créer une fonction objective

Créez une expression à l'aide de variables et ajoutez-la à l'objet Problème de planification mathématique ** C'est incroyable.

Par exemple, si vous voulez maximiser la somme de «a» et «b»

import pulp

problem = pulp.LpProblem('test', pulp.LpMinimize)
a = pulp.LpVariable('a', 0, 1)
b = pulp.LpVariable('b', 0, 1)
problem += a + b

Si vous imprimez le problème dans cet état, le problème s'affichera.

test:
MINIMIZE
1*a + 1*b + 0
VARIABLES
a <= 1 Continuous
b <= 1 Continuous

Créer des contraintes

Faites une comparaison à l'aide de variables et ajoutez-la à l'objet Problème de planification mathématique ** C'est également très bien.

Par exemple, pour les variables «a» et «b»

1. «a» vaut 0 ou plus
2. «b» est égal ou supérieur à 0,1
3. La somme de «a» et «b» est de 0,5 Lorsque vous souhaitez créer une contrainte

problem += a >= 0
problem += b >= 0.1
problem += a + b == 0.5

Seule l'anti-inégalité (<=, =>) pourrait être utilisée.

résoudre

problem.solve()

seulement ça.

Il peut ne pas être possible de le résoudre en fonction des conditions de contrainte, donc si vous voulez connaître le résultat,

status = problem.solve()
print pulp.LpStatus[status]

OK si Optimal apparaît dans

Obtenez le résultat.

Vous pouvez obtenir la valeur en appelant la méthode value de la variable ajoutée à problem.

Résumé

import pulp

problem = pulp.LpProblem('sample', pulp.LpMinimize)

a = pulp.LpVariable('a', 0, 1)
b = pulp.LpVariable('b', 0, 1)

problem += a + b

problem += a >= 0
problem += b >= 0.1
problem += a + b == 0.5

status = problem.solve()
print "Status", pulp.LpStatus[status]

print problem

print "Result"
print "a", a.value()
print "b", b.value()

Le résultat est,

Status Optimal
sample:
MINIMIZE
1*a + 1*b + 0
SUBJECT TO
_C1: a >= 0

_C2: b >= 0.1

_C3: a + b = 0.5

VARIABLES
a <= 1 Continuous
b <= 1 Continuous

Result
a 0.4
b 0.1