Utilizando o puLP para modelar problemas de programação linear em python

O puLP é um modelador de programação linear escrito em python. Ele pode gerar MPS ou arquivos LP e chamá-los via GLPK. Ele faz chamada externa dos resolvedores de PL (GLPK, CPLEX, XPRESS, etc) para resolver estes modelos e exibir a solução.

Instalação

Instalar o puLP é realmente simples utilizando o pypi ou easy_install. Veja:

$ sudo apt-get install glpk
$ sudo easy_install pulp

Testando a instalação

$ python
>>> from pulp import *
>>> pulpTestAll()

Modelando um problema real com puLP

Utilizei o problema da dieta descrito no livro “Marins, Fernando Augusto Silva: Introdução à Pesquisa Operacional – São Paulo: Cultura Acadêmica: Universidade Estadual Paulista, Pró-Reitoria de Graduação, 2011”. A descrição do problema encontra-se no próprio script.

#!/usr/bin/python
# coding: utf-8
#
# file: dieta.py 
#
# Obter uma dieta de mínimo custo que satisfaça as
# necessidades básicas do indivíduo médio, com
# respeito a Calorias (min. 3,0), Cálcio (min. 0,8)
# e Vitamina B12 (min. 2,7).
#
# +--------------------+----------+-----------+--------+--------+--------+--------+
# | Alimento/Nutriente | Farinha  | Leite po  | Queijo | Figado | Batata | Feijão |
# +--------------------+----------+-----------+--------+--------+--------+--------+
# | Calorias           | 44,7     | 8,4       | 7,4    | 2,2    | 9,6    | 26,9   |
# +--------------------+----------+-----------+--------+--------+--------+--------+
# | Cálcio             | 2,0      | 19,1      | 16,4   | 0,2    | 2,7    | 11,4   |
# +--------------------+----------+-----------+--------+--------+--------+--------+
# | Vitamina B12       | 33,2     | 23,5      | 10,3   | 50,8   | 5,4    | 24,7   |
# +--------------------+----------+-----------+--------+--------+--------+--------+
# | Custos             | 10,8     | 20,5      | 22,5   | 21,2   | 16,1   | 15     |
# +--------------------+----------+-----------+--------+--------+--------+--------+
#
import sys
from pulp import *

# Cria o problema
prob = LpProblem("Problema da Dieta", LpMinimize)

# Cria as variaveis
x1 = LpVariable("Farinha", 0)
x2 = LpVariable("Leite", 0)
x3 = LpVariable("Queijo", 0)
x4 = LpVariable("Figado", 0)
x5 = LpVariable("Batata", 0)
x6 = LpVariable("Feijao", 0)

# Cria a funcao objetivo
prob += 10.8 * x1 + 20.5 * x2 + 22.5 * x3 + 21.2 * x4 + 16.1 * x5 + 15 * x6, "Total custos"

# Restricoes
prob += 44.7 * x1 + 8.4 * x2 + 7.4 * x3 + 2.2 * x4 + 9.6 * x5 + 26.9 * x6 >= 3, "Calorias requeridas"
prob += 2 * x1 + 19.1 * x2 + 16.4 * x3 + 0.2 * x4 + 2.7 * x5 + 11.4 * x6 >= 0.8, "Calcio requerido"
prob += 33.2 * x1 + 23.5 * x2 + 10.3 * x3 + 50.8 * x4 + 5.4 * x5 + 24.7 * x6 >= 2.7, "Vitaminas B12 requeridas"

# Escreve o modelo no arquivo
prob.writeLP("DietaModelo.lp")

# Resolve o problema
prob.solve()

# Imprime o status da resolucao
print "Status:", LpStatus[prob.status]

# Solucoes otimas das variaveis
for variable in prob.variables():
   print "%s = %f" % (variable.name, variable.varValue)

# Objetivo otimizado
print "Custo total dos ingredientes da dieta: R$ %0.2f" % value(prob.objective)

Saída do programa

Esta é saída padrão do modelo que encontra-se no arquivo DietaModelo.lp:

\* Problema da Dieta *\
Minimize
Total_custos: 16.1 Batata + 10.8 Farinha + 15 Feijao + 21.2 Figado
 + 20.5 Leite + 22.5 Queijo
Subject To
Calcio_requerido: 2.7 Batata + 2 Farinha + 11.4 Feijao + 0.2 Figado
 + 19.1 Leite + 16.4 Queijo >= 0.8
Calorias_requeridas: 9.6 Batata + 44.7 Farinha + 26.9 Feijao + 2.2 Figado
 + 8.4 Leite + 7.4 Queijo >= 3
Vitaminas_B12_requeridas: 5.4 Batata + 33.2 Farinha + 24.7 Feijao
 + 50.8 Figado + 23.5 Leite + 10.3 Queijo >= 2.7
End

Como resultado o script em python me retornou os seguintes valores:

GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
 --cpxlp /tmp/2620-pulp.lp -o /tmp/2620-pulp.sol
Reading problem data from `/tmp/2620-pulp.lp'...
3 rows, 6 columns, 18 non-zeros
12 lines were read
GLPK Simplex Optimizer, v4.45
3 rows, 6 columns, 18 non-zeros
Preprocessing...
3 rows, 6 columns, 18 non-zeros
Scaling...
 A: min|aij| =  2.000e-01  max|aij| =  5.080e+01  ratio =  2.540e+02
GM: min|aij| =  2.230e-01  max|aij| =  4.484e+00  ratio =  2.011e+01
EQ: min|aij| =  4.973e-02  max|aij| =  1.000e+00  ratio =  2.011e+01
Constructing initial basis...
Size of triangular part = 3
      0: obj =   0.000000000e+00  infeas =  3.417e-01 (0)
*     4: obj =   1.672862454e+00  infeas =  0.000e+00 (0)
*     7: obj =   1.326169928e+00  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.0 Mb (45875 bytes)
Writing basic solution to `/tmp/2620-pulp.sol'...
Status: Optimal
Batata = 0.000000
Farinha = 0.033487
Feijao = 0.064300
Figado = 0.000000
Leite = 0.000000
Queijo = 0.000000
Custo total dos ingredientes da dieta: R$ 1.33

Em negrito as soluções encontradas para o problema, e por fim a solução ótima encontrada para o custo final foi de R$ 1.33.