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

Hola 🙂

PARA INSTALAR CVXOPT CONSULTA ANTES EL SIGUIENTE ARTÍCULO:

[web]

CÓMO INSTALAR CVXOPT

[/web]

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:


from cvxopt import glpk
from cvxopt.base import matrix as m

c = m([-3., -2., 5., 2., -3.])
A = m([[1., 7., -11.], [1., 0., 6.], [1., 3., 0.], [2., -4., -3.], [1., 3., 3.]])
b = m([4., 8., -3.])
intVars = range(5) #Especificamos que las 5 variables son enteras
binVars = range(5) #Especificamos que las 5 variables son binarias
sol = glpk.ilp(c, A, b, I=set(intVars), B=set(binVars))
print('Los valores óptimos de las variables son: {0}n'.format(sol[1]))
if sol[0]=='optimal':

print('El valor óptimo es {0}'.format((-c.T*sol[1])[0]))
# El valor óptimo debemos transponerlo y cambiarle el signo, estamos maximizando.

else:

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:

[terminal]

/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

[/terminal]

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 🙂

Autor: Tobal

Licenciado en Matemáticas

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

  1. Pingback: Bitacoras.com

    1. 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 😉

      Responder

Deja un comentario