Programación Lineal Con Python

por | 20 abril, 2010

Hola, en Python hay diversidad de librerías para hacer programación lineal tanto la normal como la entera. En esta ocasión os voy ha hablar de PyMathPrpog, unas librerías basadas en Glpk y PyGlpk con las cuales podemos calcular nuestros problemas en métodos como el Simplex, Exacto e Interior; o Plain y Avanzado si lo que buscamos son soluciones enteras. También podemos obtener un informe detallado de nuestra solución, las primales, las primales factibles, las duales, etc. y todo ello de forma sencilla. Esta librería no se encuentra (que yo sepa) en los repositorios oficiales de Ubuntu, pero bueno si añades mi repositorio de Launchpad la puedes instalar bajo el nombre de python-mathprog. Supongamos que queremos solucionar el siguiente problema:
Max: z=10x+6y+4z
s.a.  \begin{cases}        x+y+z \le 100 \\   10x+4y+5z \le 600 \\ 2x+2y+6y \le 300 \\ x,y,z \ge 0     \end{cases}

El código en Python usando estas librerías es el siguiente:

  1. from pymprog import *  # Importar el modulo
  2. # indices y datos
  3. xid, rid = range(3), range(3)
  4. c = (10.0, 6.0, 4.0)
  5. mat = [ (1.0, 1.0, 1.0),
  6.         (10.0, 4.0, 5.0),
  7.         (2.0, 2.0, 6.0)]
  8. b = (100.0, 600.0, 300.0)
  9. #definicion del problema
  10. beginModel('basic')   #Lo definimos como basico
  11. verbose(True)
  12. x = var(xid, 'X') #crear variables
  13. maximize( #funcion objetivo
  14.   sum(c[i]*x[i] for i in xid), 'miobjetivo'
  15. )
  16. r=st( #Conjunto de restricciones
  17.   sum(x[j]*mat[i][j] for j in xid) <= b[i] for i in rid
  18. )
  19. solve() #Solucion e Informe
  20. print "Estado Solucionador:", status()
  21. print 'Z = %g;' % vobj()  # Valor funcion Objetivo
  22. #Impresion de nombre de las variables y las primales
  23. print ';\n'.join('%s = %g {dual: %g}' % (
  24.    x[i].name, x[i].primal, x[i].dual)
  25.                     for i in xid)
  26. print ';\n'.join('%s = %g {dual: %g}' % (
  27.    r[i].name, r[i].primal, r[i].dual)
  28.                     for i in rid)
  29.  
  30. print reportKKT()
  31. print "Environment:", env
  32. for pn in dir(env):
  33.     if pn[:2]=='__'==pn[-2:]: continue
  34.     print pn, getattr(env, pn)
  35.  
  36. print ' '
  37. print evaluate(sum(x[i]*(i+x[i])**2 for i in xid))
  38. print sum(x[i].primal*(i+x[i].primal)**2 for i in xid)
  39. endModel() #Finalizar el Modelo

Y la solución por terminal es:


MAX ‘miobjetivo’: 10 X[0]+ 6 X[1]+ 4 X[2]
s.t. R0[0]: X[0]+ X[1]+ X[2] <= 100.0
s.t. R0[1]: 10 X[0]+ 4 X[1]+ 5 X[2] <= 600.0
s.t. R0[2]: 2 X[0]+ 2 X[1]+ 6 X[2] <= 300.0
Estado Solucionador: opt
Z = 733.333;
X[0] = 33.3333 {dual: 0};
X[1] = 66.6667 {dual: 0};
X[2] = 0 {dual: -2.66667}
R0[0] = 100 {dual: 3.33333};
R0[1] = 600 {dual: 0.666667};
R0[2] = 200 {dual: 0}

Karush-Kuhn-Tucker optimality conditions:
=========================================

1) Error in Primal Solutions:
—————————–
Largest absolute error: 0.000000 (row id: 1)
Largest relative error: 0.000000 (row id: 1)
Quality of primal solution: H

2) Error in Satisfying Primal Bounds:
————————————-
Largest absolute error: 0.000000 (var id: 0)
Largest relative error: 0.000000 (var id: 0)
Quality of primal feasibility: H

3) Error in Dual Solutions:
—————————–
Largest absolute error: 0.000000 (col id: 0)
Largest relative error: 0.000000 (col id: 0)
Quality of dual solution: H

4) Error in Satisfying Dual Bounds:
————————————-
Largest absolute error: 0.000000 (var id: 0)
Largest relative error: 0.000000 (var id: 0)
Quality of dual feasibility: H

Environment:
blocks 45
blocks_peak 72
bytes 27508
bytes_peak 28998
mem_limit None
term_hook None
term_on True
version (4, 38)

342288.888889
342288.888889


Como vemos en la salida por terminal obtenemos un informe muy detallado de la solución y sus posibles soluciones.
Obviamente al ser este ejemplo de 3 variables no es factible dibujar su región, al igual que no lo son la mayoría de estos problemas. Tan sólo son posibles sus soluciones gráficas para problemas de 2 variables, que se dan mayoritariamente en Bachiller. A mi estas librerías me parecen una buena alternativa al programa no libre LINGO. Me queda pendiente verlo con python-cvxopt, pero eso os lo cuento otro día

Saludos

4 pensamientos en “Programación Lineal Con Python

  1. rems

    Hola Cristóbal:

    Te quedó muy bonito el nuevo diseño del blog. Saludos y sigue con los aportes matemáticos y estadísticos. En ese tenor, estaría chido un articulo sobre la combinación de sweave, lyx y R para la preparación de documentos reproducibles que incorporan el texto, código y resultados en el mismo archivo.

    Un abrazo,

    Roberto

    Un abrazo

  2. Arturo Calderón

    Hola

    El blog cada vez se ve mejor, felicidades. He agregado ya tu repositorio y me da gusto que subas herramientas tan útiles. Ojalá pudieras extender el soporte a versiones más actuales de Ubuntu.

    Mucha suerte

  3. Tobal Autor

    @Arturo Calderón->¿Versiones más actuales de Ubuntu? El repositorio es para Ubuntu Lucid Lynx, la más actual de todas, hoy todavía no es estable y llevo así un mes, con soporte para 32 y 64 bits. Ciertamente no entiendo qué quieres decir
    Y en cuanto a paquetes hoy he subido la última versión de Carmetal y la de wxMaxima, que no se encuentran disponibles en ninguna distro linuxera a día de hoy, ni en Debian. No entiendo

  4. Arturo Calderón

    Jaja cierto, asumí que karmic koala era la más actual. Fe de erratas jaja

Los comentarios están cerrados.