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.
| Uso por cada unidad de tráiler | Recursos disponibles | |||
| Plataforma plana | Económica | Lujosa | ||
| Días de trabajo en metales | 0,5 | 2 | 1 | 24 |
| Días de trabajo en madera | 1 | 2 | 4 | 60 |
| Contribución ($ x 100) | 6 | 14 | 13 | |
Modelamiento del problema
Sean las variables de decisión del problema:
x0 = Número de remolques de plataforma plana producidos por mes
x1 = Número de remolques económicos producidos por mes
x2 = 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 = 6x0 + 14x1 + 13x2
Sujeto a las siguientes restricciones de capacidad:
0,5x0 + 2x1 + x2 <= 24,
x0 + 2x1 + 4x2 <= 60,
Sujeto a las siguientes restricciones de no-negatividad:
x0 >= 0,
x1 >= 0,
x2 >= 0,
Podemos, del mismo modo, establecer un par de variables que correspondan a las horas ociosas para las dos tareas establecidas (metal y madera):
x3 = Número de horas ociosas en el trabajo en metal al mes,
x4 = 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,5x0 + 2x1 + x2 + x3 = 24,
x0 + 2x1 + 4x2 + x4 = 60,
x0 >= 0,
x1 >= 0,
x2 >= 0,
x3 >= 0,
x4 >= 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 lenguaje 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.