Resolución Problema Programación Lineal Secundaria, Python 3

por | 14 febrero, 2014

Hola
En esta ocasión voy a tratar sobre un típico problema de Programación Lineal de Bachiller, vamos a resolverlo y dibujarlo gráficamente con Python 3. Para resolverlo analíticamente utilizaremos las librerías de Python CVXOPT, por su sencillez y claridad. Estas librerías son muy completas, se pueden resolver gran cantidad de problemas de optimización de muy alto nivel; y se pueden utilizar desde programas como Sagemath, Ipython. Incluso posee un plugin para LibreOffice u OpenOffice, con el cual podemos enseñar a nuestros alumnos cómo resolver sus problemas de forma sencilla y didáctica. Veamos un problema como ejemplo, de enunciado el siguiente:

Unos grandes almacenes encargan a un fabricante pantalones y chaquetas deportivas. El fabricante dispone para la confección de 750 m. de tejido de algodón y 1000 m. de tejido de poliéster. Cada pantalón precisa 1m. de algodón y 2m. de poliéster. Para cada chaqueta se necesitan 1’5m. de algodón y 1m. de poliéster. El precio del pantalón se fija en 50€, y el de la chaqueta de 40€. ¿Qué número de pantalones y chaquetas debe suministrar el fabricante para conseguir el beneficio máximo?

La formulación del problema es la siguiente:
x=numero\; pantalones\quad\quad\quad y=numero\; chaquetas
Max:\; f(x,y)=50x+40y
s.a. \begin{cases} x+1.5y \le 750 \\ 2x+y \le 1000 \\ x,y \ge 0 \end{cases}\; \Rightarrow\; s.a. \begin{cases} 2x+3y \le 1500 \\ 2x+y \le 1000 \\ x,y \ge 0 \end{cases}
El código en Python para resolverlo es tan sencillo como la formulación anterior:

  1. x = variable()
  2. y = variable()
  3. c1 = (2*x+3*y <= 1500)
  4. c2 = (2*x+y <= 1000)
  5. c3 = (x >= 0)
  6. c4 = (y >= 0)
  7. lp1 = op(-50*x-40*y, [c1, c2, c3, c4])
  8. lp1.solve()

Como se ve en el código creamos las 2 variables del problema, las 4 restricciones y decirle que lo resuelva con el comando op. Por defecto se realiza la minimización, así que para maximizar cambiamos el signo a la función objetivo. Añadiendo los print de la solución y cómo dibujar el polígono utilizando Matplotlib el código es el siguiente:

  1. #/usr/bin/env python3
  2. # -*- coding: utf-8 -*-
  3.  
  4.  
  5. from cvxopt.modeling import variable, op
  6. import matplotlib.pyplot as plt
  7. import numpy as np
  8.  
  9. x = variable()
  10. y = variable()
  11. c1 = (2*x+3*y <= 1500)
  12. c2 = (2*x+y <= 1000)
  13. c3 = (x >= 0)
  14. c4 = (y >= 0)
  15. lp1 = op(-50*x-40*y, [c1, c2, c3, c4])
  16. lp1.solve()
  17. print('\nEstado: {}'.format(lp1.status))
  18. print('Valor óptimo: {}'.format(-round(lp1.objective.value()[0])))
  19. print('Óptimo x: {}'.format(round(x.value[0])))
  20. print('Óptimo y: {}'.format(round(y.value[0])))
  21. print('Mult óptimo primera restricción: {}'.format(c1.multiplier.value[0]))
  22. print('Mult óptimo segunda restricción: {}'.format(c2.multiplier.value[0]))
  23. print('Mult óptimo tercera restricción: {}'.format(c3.multiplier.value[0]))
  24. print('Mult óptimo cuarta restricción: {}\n'.format(c4.multiplier.value[0]))
  25.  
  26. p1, p2, p3, p4 = [(0, 0), (0, 500), (375, 250), (500, 0)]
  27. pol = plt.Polygon([p1, p2, p3, p4], closed=True, alpha=0.5)
  28. ax = plt.gca()
  29. ax.cla()
  30. ax.set_xlim((0, 1000))
  31. ax.set_ylim((0, 1000))
  32. ax.set_aspect('equal')
  33. fig = plt.gcf()
  34. fig.gca().add_artist(pol)
  35. t = np.linspace(0, 1000, 100)
  36. ax.plot(t, (1500-2*t) / 3., color='red', lw=2.0)
  37. ax.plot(t, 1000-2*t, color='green', lw=2.0)
  38. ax.plot(round(x.value[0]), round(y.value[0]), 'ko', lw=2.0)
  39. ax.set_title('Problema Grandes Almacenes')
  40. plt.legend([r'$2x+3y=1500$', r'$2x+y=1000$', r'$P=(375,\; 250)\; f(P)=28750$'])
  41. ax.grid('on')
  42. plt.show()

Por terminal obtenemos la solución:


pcost dcost gap pres dres k/t
0: -2.6571e+04 -4.5500e+04 6e+03 0e+00 5e-01 1e+00
1: -2.8624e+04 -2.9702e+04 3e+02 3e-16 3e-02 2e+01
2: -2.8749e+04 -2.8760e+04 3e+00 3e-17 3e-04 2e-01
3: -2.8750e+04 -2.8750e+04 3e-02 1e-16 3e-06 2e-03
4: -2.8750e+04 -2.8750e+04 3e-04 2e-16 3e-08 2e-05
Optimal solution found.

Estado: optimal
Valor óptimo: 28750
Óptimo x: 375
Óptimo y: 250
Mult óptimo primera restricción: 7.500000355728008
Mult óptimo segunda restricción: 17.50000041884287
Mult óptimo tercera restricción: 2.3072048317749625e-07
Mult óptimo cuarta restricción: 1.6760561401731335e-07

Y la solución gráfica es la siguiente imagen:

almacenes

Ahora podemos guardar la gráfica como imagen, pdf, etc y poderla mostrar a nuestros alumnos en el aula. El código, con unos pocos cambios nos sirve para resolver cualquier otro problema de optimización lineal. De esa forma nos podemos hacer en poco tiempo con una buena colección de problemas resueltos con calidad para que nuestros alumnos puedan aprender de forma más amena
Saludos

5 pensamientos en “Resolución Problema Programación Lineal Secundaria, Python 3

  1. Pingback: Bitacoras.com

  2. José Cifuentes

    Muchas gracias, muy bien explicado el código, lo utilizaré con mis estudiantes ;).
    Sabes, si en python se pueden resolver problemas de programación entera con variables binarias? tengo por ahí unos modelos que están implementados en AMPL y me gustaría pasarlos a python, te agradecería mucho si me puedes dar una mano con esto.
    Desde ya muchas gracias, tu blog es un gran aporte XD.

  3. Tobal

    Hola José, perdona el retraso, es que esta semana he empezado a trabajar. Supongo que sí se puede. Hagamos una cosa, pásame un problema que tengas con su solución e investigo, ok?. Gracias

  4. José Cifuentes

    Hola Tobal, perdona por mi retraso pero recién me vengo incorporando al trabajo. A través del formulario de contacto te haré llegar los problemas.
    Muchas gracias!

  5. Tobal

    He encontrado cómo hacerlo, pero necesito problemas hechos, con la solución, y a poder ser hecho a mano con el método aplicado. Se puede hacer con cvxopt, sólo hay que instalarlo correctamente para tener apoyo GLPK. Por favor, pásame algo hecho, no encuentro nada por la red hecho a mano con lo que me pides.

Los comentarios están cerrados.