Programación lineal en Google OR-Tools

Tal como lo hemos mencionado en artículos anteriores (programación lineal); la optimización lineal, es el nombre con el que se conoce al cálculo de la mejor solución a un problema modelado como un conjunto de restricciones lineales y una función objetivo también lineal.

El objetivo de este artículo consiste en utilizar las librerías del software Google OR-Tools para abordar problemas de programación lineal (optimización lineal). 

El problema

Con el propósito de evaluar los resultados obtenidos a través del tratamiento de un problema técnicamente formulado y abordado, utilizaremos un caso descrito en el libro Applied Mathematical Programming, de Bradley, Hax, and Magnanti (Addison-Wesley, 1977), del MIT (Cápitulo 2 página 50).

El propietario de una tienda que produce remolques para automóviles desea determinar la mejor combinación para sus tres productos: remolques de plataforma plana, remolques económicos y remolques de lujo. Su taller se limita a trabajar 24 días al mes en el trabajo de los metales y 60 días al mes en el trabajo de la madera para estos productos. La siguiente tabla indica los datos de producción de los remolques.

Modelamiento del problema

Sean las variables de decisión del problema:

x₀ = Número de remolques de plataforma plana producidos por mes

x₁ = Número de remolques económicos producidos por mes

x₂ = Número de remolques de lujo producidos por mes

Suponiendo que los costos de la capacidad de trabajo en metal y madera sean fijos, el problema se convierte en un problema de maximización:

Zmax = 6x₀ + 14x₁ + 13x₂

Sujeto a las siguientes restricciones de capacidad:

0,5x₀ + 2x₁ + x₂ <= 24,

x₀ + 2x₁ + 4x₂ <= 60,

Sujeto a las siguientes restricciones de no-negatividad:

x₀ >= 0,

x₁ >= 0,

x₂ >= 0,

Podemos, del mismo modo, establecer un par de variables que correspondan a las horas ociosas para las dos tareas establecidas (metal y madera):

x₃ = Número de horas ociosas en el trabajo en metal al mes,

x₄ = Número de horas ociosas en el trabajo en madera al mes,

Reescribimos las restricciones (adicionando las variables de horas ociosas). Podemos observar que las inecuaciones ahora serán igualdades, para que de esta forma ahora podamos tener información relacionada a los recursos. En otras palabras, lo que se utiliza (horas productivas) + lo que sobre (horas ociosas) = tiempo disponible:

0,5x₀ + 2x₁ + x₂ + x₃ = 24,

x₀ + 2x₁ + 4x₂ + x₄ = 60,

x₀ >= 0,

x₁ >= 0,

x₂ >= 0,

x₃ >= 0,

x₄ >= 0,

Así entonces, tenemos el problema completamente modelado.

Resolución del modelo mediante Google OR-Tools

De acuerdo a lo mencionado en el artículo de introducción a Google OR-Tools, esta herramienta soporta múltiples lenguajes de programación, así entonces, haremos uso del l enguaje de programación Python.

Paso 1: Importar la librería

El siguiente fragmento de código importa las librerías necesarias:

# Importar la librería de Google OR-Tools
from ortools.linear_solver import pywraplp

Paso 2: Declarar el solucionador

El siguiente fragmento de código declara el solucionador GLOP (Google OR-Tools posee múltiples solucionadores):

solver = pywraplp.Solver.CreateSolver('GLOP')

Paso 3: Crear las variables del modelo

El siguiente fragmento crea las variables del modelo, así mismo indica el tipo de variables correspondientes y su rango de valores. Así entonces, desde la creación de las variables se pueden abordar las restricciones de no-negatividad (entre 0 e infinito):

x0 = solver.NumVar(0, solver.infinity(), 'x0')
x1 = solver.NumVar(0, solver.infinity(), 'x1')
x2 = solver.NumVar(0, solver.infinity(), 'x2')
x3 = solver.NumVar(0, solver.infinity(), 'x3')
x4 = solver.NumVar(0, solver.infinity(), 'x4')

print('Número de variables =', solver.NumVariables())

Paso 4: Definir las restricciones del modelo

El siguiente fragmento de código define las restricciones del modelo:

# Restricción 0: 0.5x0 + 2x1 + x2 + x3 = 24.
solver.Add(0.5 * x0 + 2 * x1 + x2 + x3 == 24.0)

# Restricción 1: x0 + 2x1 + 4x2 + x4 = 60.
solver.Add(x0 + 2 * x1 + 4 *x2 + x4 == 60.0)

print('Número de restricciones =', solver.NumConstraints())

Paso 5: Definir la función objetivo del modelo

El siguiente fragmento de código define la función objetivo del modelo (maximizar):

# Función objetivo (max): 6x0 + 14x1 + 13x2
solver.Maximize(6 * x0 + 14 * x1 + 13 * x2)

Paso 6: Invocar el solucionador

El siguiente fragmento de código sirve para invocar el solucionador del modelo:

status = solver.Solve()

Paso 7: Definir las salidas del solucionador

if status == pywraplp.Solver.OPTIMAL:
    print('Solución:')
    print('Valor objetivo =', solver.Objective().Value())
    print('Número de remolques de plataforma plana producidos por mes =', x0.solution_value())
    print('Número de remolques económicos producidos por mes =', x1.solution_value())
    print('Número de remolques de lujo producidos por mes =', x2.solution_value())
    print('Número de horas ociosas en el trabajo en metal al mes =', x3.solution_value())
    print('Número de horas ociosas en el trabajo en madera al mes =', x4.solution_value())
else:
    print('El problema no tiene solución óptima.')

Es posible que el desarrollo de los siete pasos anteriores demande algún grado de complejidad subyacente del uso de un lenguaje de programación; sin embargo, es preciso mencionar que, el modelo anterior queda perfectamente configurado, y puede replicarse con modificaciones menores en múltiples problemas de optimización lineal.

¿Cómo ejecutar el modelo?

Alternativa 1, ejecución en nuestro equipo:

Lo primero que debemos considerar, en el caso de que queramos ejecutar este código en nuestro equipo, es que es preciso contar con la instalación de Python en nuestro equipo de cómputo, así mismo debemos contar con la última versión del comando pip y por supuesto, el software OR-Tools. Una guía detallada de la instalación de estos requerimientos la podrás encontrar en el siguiente enlace:

Instalación de OR-Tools para Python

Ahora, lo recomendable es trabajar con algún editor de código práctico (IDE), por ejemplo: Sublime Text, o Spyder (Una herramienta más completa y por ende más robusta y pesada).

Alternativa 2, ejecución en un entorno virtual (Recomendado):

Podemos utilizar del mismo modo, un entorno virtual. En este caso recomendamos el uso de Colaboratory de Google, un entorno que cuenta con todas las herramientas necesarias para nuestros desarrollos. No tendremos que instalar nada en nuestro equipo, y aprovecharemos la potencia de las máquinas de Google.

El código completo de nuestro desarrollo lo presentamos a continuación. También puedes ver el cuaderno de este módulo en nuestro Colaboratory: Programación Lineal.

#Desde: Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', Chapter 2

# Importar la librería de Google OR-Tools
from ortools.linear_solver import pywraplp

def LinearProgrammingExample():
    solver = pywraplp.Solver.CreateSolver('GLOP')

    x0 = solver.NumVar(0, solver.infinity(), 'x0')
    x1 = solver.NumVar(0, solver.infinity(), 'x1')
    x2 = solver.NumVar(0, solver.infinity(), 'x2')
    x3 = solver.NumVar(0, solver.infinity(), 'x3')
    x4 = solver.NumVar(0, solver.infinity(), 'x4')

    print('Número de variables =', solver.NumVariables())

    # Restricción 0: 0.5x0 + 2x1 + x2 + x3 = 24.
    solver.Add(0.5 * x0 + 2 * x1 + x2 + x3 == 24.0)

    # Restricción 1: x0 + 2x1 + 4x2 + x4 = 60.
    solver.Add(x0 + 2 * x1 + 4 *x2 + x4 == 60.0)

    print('Número de restricciones =', solver.NumConstraints())

    # Función objetivo (max): 6x0 + 14x1 + 13x2
    solver.Maximize(6 * x0 + 14 * x1 + 13 * x2)

    # Declarar el solucionador.
    status = solver.Solve()

    # Declarar las salidas del solucionador
    if status == pywraplp.Solver.OPTIMAL:
        print('Solución:')
        print('Valor objetivo =', solver.Objective().Value())
        print('Número de remolques de plataforma plana producidos por mes =', x0.solution_value())
        print('Número de remolques económicos producidos por mes =', x1.solution_value())
        print('Número de remolques de lujo producidos por mes =', x2.solution_value())
        print('Número de horas ociosas en el trabajo en metal al mes =', x3.solution_value())
        print('Número de horas ociosas en el trabajo en madera al mes =', x4.solution_value())
    else:
      if status == solver.FEASIBLE:
        print('Se encontró una solución potencialmente subóptima.')
      else:
        print('El problema no tiene solución óptima.')

    # Información avanzada del solucionador

    print('\nUso avanzado:')
    print('Problema resuelto en %f  milisegundos' % solver.wall_time())
    print('Problema resuelto en %d iteraciones' % solver.iterations())

LinearProgrammingExample() 

                                                            
                                                            
  

                                                            
 

Al ejecutar nuestro desarrollo en Colaboratory, tenemos:

Podemos observar que se ha obtenido la misma respuesta que se encuentra consignada en el libro Applied Mathematical Programming (Página 51).

Ahora bien, el modelo de optimización lineal y el script del solucionador quedaron desarrollados en un lenguaje de programación estándar y ampliamente utilizado. Desde luego, las posibilidades de integrar datos de entrada y procesar los datos de salidas son interesantes. Por ejemplo, es posible desarrollar un script mediante el cual el código ya desarrollado tome los datos de entrada desde un archivo de Excel, o desde un servidor externo.

También, es posible desarrollar una interfaz amigable desde la cual se ingrese la información; o vincular los datos de salida con algún modelo o documento determinado.

En próximos artículos abordaremos algunos scripts haciendo uso de las librerías de Google OR-Tools que nos permitan utilizar bucles de matrices, con el objetivo de automatizar el proceso de definición de variables y restricciones, mejorando la eficiencia del modelamiento.