Resolución Problema Prog. Lineal Entera Binaria Con CVXOPT. Python 3

por | 8 abril, 2014

Hola

PARA INSTALAR CVXOPT CONSULTA ANTES EL SIGUIENTE ARTÍCULO:

Consideremos el siguiente problema de Programación Lineal Entera Binaria:

Max:\; f(x_1,x_2,x_3,x_4,x_5)=3x_1+2x_2-5x_3-2x_4+3x_5
s.a. \begin{cases} x_1+x_2+x_3+2x_4+x_5 \le 4 \\ 7x_1+3x_3-4x_4+3x_5 \le 8 \\ 11x_1-6x_2+3x_4-3x_5 \ge 3\\ x_j \in \{0,1\} \end{cases}

Antes de programarlo con Cvxopt debemos convertirlo a un problema de minimización y convertir las desigualdades de mayor o igual que a menor igual que, así:

Min:\; f(x_1,x_2,x_3,x_4,x_5)=-3x_1-2x_2+5x_3+2x_4-3x_5
s.a. \begin{cases} x_1+x_2+x_3+2x_4+x_5 \le 4 \\ 7x_1+3x_3-4x_4+3x_5 \le 8 \\ -11x_1+6x_2-3x_4+3x_5 \le -3\\ x_j \in \{0,1\} \end{cases}

Éste paso previo es fácil y todo el mundo que conoce algo de Programación Lineal debe saberlo. Ahora sólo resta tener en cuenta que en nuestro código cvxopt para introducir la matriz de coeficientes de la región lo haremos por columnas y no por filas. Para hacerlo con cvxopt debemos importar su módulo GLPK, que es un fork en Python de las librerías en C++ de GLPK. El código es el siguiente:

  1. from cvxopt import glpk
  2. from cvxopt.base import matrix as m
  3.  
  4. c = m([-3., -2., 5., 2., -3.])
  5. A = m([[1., 7., -11.], [1., 0., 6.], [1., 3., 0.], [2., -4., -3.], [1., 3., 3.]])
  6. b = m([4., 8., -3.])
  7. intVars = range(5) #Especificamos que las 5 variables son enteras
  8. binVars = range(5) #Especificamos que las 5 variables son binarias
  9. sol = glpk.ilp(c, A, b, I=set(intVars), B=set(binVars))
  10. print('Los valores óptimos de las variables son: {0}\n'.format(sol[1]))
  11. if sol[0]=='optimal':
  12.  
  13. print('El valor óptimo es {0}'.format((-c.T*sol[1])[0]))
  14. # El valor óptimo debemos transponerlo y cambiarle el signo, estamos maximizando.
  15.  
  16. else:
  17.  
  18. print('El problema no devolvió una solución óptima. El estado del solucionador fue {0}'.format(sol[0]))

La solución del problema es la siguiente:

usuario@nombrepc:~$

/usr/bin/python3 /home/tobal/ProgramasPython3/proglinenterabinaria2.py
GLPK Integer Optimizer, v4.45
3 rows, 5 columns, 13 non-zeros
5 integer variables, all of which are binary
Preprocessing…
1 constraint coefficient(s) were reduced
3 rows, 5 columns, 13 non-zeros
5 integer variables, all of which are binary
Scaling…
A: min|aij| =  1.000e+00  max|aij| =  1.100e+01  ratio =  1.100e+01
GM: min|aij| =  6.077e-01  max|aij| =  1.646e+00  ratio =  2.708e+00
EQ: min|aij| =  3.693e-01  max|aij| =  1.000e+00  ratio =  2.708e+00
2N: min|aij| =  1.875e-01  max|aij| =  7.500e-01  ratio =  4.000e+00
Constructing initial basis…
Size of triangular part = 3
Solving LP relaxation…
GLPK Simplex Optimizer, v4.45
3 rows, 5 columns, 13 non-zeros
0: obj =   0.000000000e+00  infeas =  3.750e-01 (0)
*     1: obj =  -8.181818182e-01  infeas =  0.000e+00 (0)
*     5: obj =  -7.000000000e+00  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins…
+     5: mip =     not found yet >=              -inf        (1; 0)
+     6: >>>>>  -5.000000000e+00 >=  -6.000000000e+00  20.0% (2; 0)
+     6: mip =  -5.000000000e+00 >=     tree is empty   0.0% (0; 3)
INTEGER OPTIMAL SOLUTION FOUND
Los valores óptimos de las variables son: [ 1.00e+00]
[ 1.00e+00]
[ 0.00e+00]
[ 0.00e+00]
[ 0.00e+00]

El valor óptimo es 5.0

Process finished with exit code 0

En resumen, con Cvxopt obtenemos los resultados esperados con un código sencillo y nítido, usando software libre. Espero que esto le sirva a alguien.

Saludos

4 pensamientos en “Resolución Problema Prog. Lineal Entera Binaria Con CVXOPT. Python 3

  1. Pingback: Bitacoras.com

  2. Informático de Guardia

    Interesante aporte Cristobal.

    Por si te resulta de interés, hace tiempo encontré (y anoté como haré con el tuyo ;)) el siguiente artículo en el que explicaban, de forma muy amena, el algoritmo MiniMax

    Espero que te guste y gracias por tu aporte

    Un saludo

  3. Tobal

    Muchas gracias por el enlace, me interesa mucho Ay ése Alan Turing, ¿de qué me suena? Ya caigo, matemático que al parecer contribuyó a descifrar Enigma de los nazis

Los comentarios están cerrados.