¡Hola, mundo!

de la programación matemática

Introducción

¡Hola, Mundo!

Para cualquier persona que haya hecho un curso o un tutorial sobre un lenguaje de programación, esta última frase es bien conocida. Su tradición comenzó con uno de los primeros lenguajes de éxito a gran escala: C. En el libro The C Programming Language (1978), los autores Brian Kernighan y Dennis Ritchie seleccionaron la frase para ejemplificar la sintaxis de impresión del programa, que el usuario del mismo podría ver en un terminal o pantalla. Con la evolución de los lenguajes de programación, persistió la necesidad de contar con ejemplos sencillos para la sintaxis del software, por lo que el ¡Hola, mundo! se convirtió en el caso de introducción a la programación.

Aunque el modelo matemático no tiene un problema universal para presentar sus conceptos a los principiantes, hay un enfoque clásico que se utiliza a menudo. Se trata de una pequeña representación de una decisión empresarial, normalmente con un par de restricciones y palancas, que se pueden resolver fácilmente dibujándolos en un gráfico.

Inspirado en esos ejemplos, el objetivo de este libro electrónico es servir de introducción a su combinación en el uso de los lenguajes de programación matemática. Muestra cómo traducir un modelo de un problema matemático para las siguientes herramientas: Python, Java, C++, AMPL, y Excel.

El modelo matemático

Un fabricante produce dos tipos de juguetes de madera: soldados y trenes. Un soldado se vende a 27 dólares y utiliza materias primas por valor de 10 dólares. Cada soldado que se fabrica aumenta los costos variables de mano de obra y gastos generales en 14 dólares. Un tren se vende a 21 dólares y utiliza materias primas por valor de 9 dólares. Cada tren construido aumenta los costos variables de mano de obra y gastos generales en 10 dólares. La fabricación de soldados y trenes de madera requiere dos tipos de trabajo calificado: la carpintería y el acabado. Un soldado requiere 2 horas de trabajo de acabado y 1 hora de trabajo de carpintería. Un tren requiere 1 hora de trabajo de acabado y 1 hora de trabajo de carpintería.

Cada semana, la empresa puede obtener toda la materia prima necesaria, pero sólo 100 horas de acabado y 80 de carpintería. La demanda de trenes es ilimitada, pero sólo se compran 40 soldados, como máximo, cada semana. La empresa quiere maximizar las ganancias por semana.

Esta descripción se puede traducir en el siguiente sistema de ecuaciones.

Maximizar

Ganancias = (27-10-14)×Soldados + (21-9-10)×Trenes

Sujeto a

2×Soldados+Trenes ≤100 (Restricción de acabado)

Soldados+Trenes ≤80 (Limitación de carpintería)

Soldados ≤40 (Demanda de soldados)

Soldados ≥0 (Cantidad mínima de soldados)

Trenes ≥0 (Cantidad mínima de trenes)

Herramientas de implementación

Excel

Python

JAVA

C++

AMPL

Implementación Excel

Aunque Excel no es un lenguaje de programación propiamente dicho, es una de las herramientas más conocidas del mundo y dispone de opciones de optimización que se pueden utilizar para resolver nuestro caso de base. Lo primero que hay que hacer es asegurarse de que su Excel tiene seleccionado Solver Add-in para utilizarlo. A continuación, la implementación del problema comienza con la construcción de tablas para las entradas del problema, como se muestra en la Figura 2.

El siguiente paso consiste en definir los resultados del modelo, que en este caso dependen del número de soldados y de trenes construidos (Figura 3). Tenga en cuenta que el archivo utiliza la función de nombramiento de celdas, para facilitar la comprensión de las fórmulas.

Con la entrada y la salida definidas, es posible crear el modelo de optimización utilizando el asistente de Excel, que aparece (Figura 4) después de activar la herramienta Solver (Solucionador) (Herramientas > Solver ...). Lo primero es definir el campo Establecer objetivo , que sería el H4, llamado Ganancias. Entonces, la selección Para se debe establecer como Máx, ya que el modelo busca el máximo beneficio posible. El tercer campo Cambiando las celdas de variables quiere conocer las variables del modelo, que son las celdas H9 y H10, denominadas rango Produccion_de_juguete. Después, el campo Sujeto a las restricciones necesita conocer cada uno de los límites de los problemas. Cada restricción se agrega individualmente, como H7 (llamada Operacion_acabado) (es menor o igual a) C15 (llamada Acabado), y así sucesivamente. Lo último es definir el campo Método de resolución, que para este problema lineal es Simplex LP.

Con el modelo totalmente completado, llamando a Resolver, se encuentra un resultado óptimo (Figura 5).

Implementación Python

Además de su gran rendimiento en el tratamiento de datos, Python también tiene mucha bibliografía dedicada a los algoritmos de optimización. Esta implementación utiliza el paquete OR-Tools de Google, importando

from ortools.linear_solver import pywraplp

Después, es necesario definir la función del modelo que tendrá todas las declaraciones del modelo.

def holaMundo():

El primer comando de la función es definir el objeto que encapsula el modelo, incluyendo el solucionador (GLOP).

# Crear el resolvedor lineal con el backend GLOP

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

El siguiente paso consiste en la declaración de las variables, utilizando la función NumVar. Para definir cada variable esta función utiliza tres argumentos, en este orden: valor mínimo posible, valor máximo posible y etiqueta. Por lo tanto, la declaración está implícita en la definición de las restricciones.

# Crear las variables soldados y trenes

soldados = resolvedor.NumVar(0, 40, 'Soldados')

trenes = resolvedor.NumVar(0, 10000, 'Trenes')

Tras la declaración de las restricciones, utilice las funciones Constraint y SetCoefficient. El primero utiliza tres argumentos, en este orden: valor mínimo posible, valor máximo posible y etiqueta; mientras que el segundo utiliza dos argumentos: la variable y su coeficiente en la restricción.

# Crear restricción de acabado, 0 <= 2*soldados + trenes <= 100

acabado = resolvedor.Constraint(0, 100, 'acabado')

acabado.SetCoefficient(soldados, 2)

acabado.SetCoefficient(trenes, 1)

// Crear restricción de carpintería, 0 <= soldados + trenes <= 80

carpintería = resolvedor.Constraint(0, 80, 'carpintería')

carpintería.SetCoefficient(soldados, 1)

carpintería.SetCoefficient(trenes, 1)

Sólo falta la declaración del objetivo para completar el modelo, cuyo formato es similar al de las restricciones

# Crear la función objetivo, 3 * soldados + 2 * trenes

ganancia = resolvedor.Objective()

ganancia.SetCoefficient(soldados, 3)

ganancia.SetCoefficient(trenes, 2)

ganancia.SetMaximization()

Para ejecutar el modelo, hay que llamar a la función Solve() del objeto solucionado

# Solucionar el modelo

resolvedor.Solve()

Por último, los resultados se pueden mostrar en la interfaz utilizando el comando de impresión, como:

print('Ganancia = ', ganancia.Value())

print('Soldados' = ', soldados.solution_value.Value())

print('Trenes' = ', trenes.solution_value.Value())

Que devuelve lo siguiente

Ganancia = 180

Soldados = 20

Trenes = 60

Implementación JAVA

Java es conocido por ser un lenguaje orientado a objetos que se puede ejecutar fácilmente en todo tipo de máquinas y logra un buen equilibrio entre velocidad y curva de aprendizaje. Esta implementación también utiliza el paquete OR-Tools de Google, importando las siguientes clases:

import com.google.ortools.Loader;

import com.google.ortools.linearsolver.MPConstraint;

import com.google.ortools.linearsolver.MPObjective;

import com.google.ortools.linearsolver.MPSolver;

import com.google.ortools.linearsolver.MPVariable;

Las bibliotecas nativas se deben cargar con el siguiente comando

// Cargar bibliotecas

Loader.loadNativeLibraries();

Como es típico en java, empezaremos creando una clase Modelo con un campo para el solucionador, las variables y la función objetivo. Incluiremos un constructor y un método de resolución en la clase:

class Modelo {

private MPSolver resolvedor; // LP resolvedor

private MPVariable soldados; // Variable de los soldados

private MPVariable trenes; // Variable de los trenes

private MPObjective ganancia; // Función objetivo

public Modelo() {..}

public void resolver() {...}

}

En el constructor, primero definimos el objeto que encapsula el modelo, incluyendo el solucionador (GLOP).

// Iniciar el solucionador lineal con el backend GLOP

resolvedor = MPSolver.createSolver("GLOP");

También se instancian las variables y se declaran las restricciones, que siguen estructuras similares a las descritas en la sección de Python

// Crear las variables soldados y trenes

soldados = resolvedor.makeNumVar(0, 40, "soldados");

trenes = resolvedor.makeNumVar(0, 1000, "trenes");

// Crear restricción de acabado, 0 <= 2*soldado + trenes <= 100

MPConstraint finishing = resolvedor.makeConstraint(0, 100, "acabado");

finishing.setCoefficient(soldados, 2);

finishing.setCoefficient(trenes, 1);

// Crear restricción de carpintería, 0 <= soldados + trenes <= 80

MPConstraint carpentry = resolvedor.makeConstraint(0, 80, "carpintería");

carpentry.setCoefficient(soldados, 1);

carpentry.setCoefficient(trenes, 1);

Para completar el modelo instauramos el objetivo, que sigue estructuras similares a las descritas en la sección de Python

// Crear la función objetivo, 3 * soldados + 2* trenes

ganancia = resolvedor.objective();

ganancia.setCoefficient(soldados, 3);

ganancia.setCoefficient(trenes, 2);

ganancia.setMaximization();

Finalmente creamos un método resolución que llama a las herramientas OR solve e imprime el resultado

public void resolver() {

// Resolver el modelo

resolvedor.solve();

// Imprimir la función objetivo y solución

System.out.println("Soluciones: ");

System.out.println("Valor objetivo= " + ganancia.value());

System.out.println("soldados = " + soldados.solutionValue());

System.out.println("trenes = " + trenes.solutionValue());

}

Que devuelve lo siguiente

Soluciones:

Valor objetivo = 180

soldados = 20

trenes = 60

Implementación C++

Los lenguajes C y C++ son probablemente los más utilizados en el solucionador porque son lenguajes de alto rendimiento. Al igual que en las otras implementaciones, comenzamos importando las bibliotecas significativas, y también utilizamos el espacio de nombres operations_research

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {...}

Dentro del espacio de nombres creado, definimos nuestra función Hola Mundo y declaramos el modelo GLOP

void holaMundo() {

// Crear el resolvedor lineal con el backend GLOP

std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));

// …

}

A continuación, declaramos nuestras variables y restricciones, que siguen estructuras similares a las de las secciones anteriores.

// Crear las variables soldados y trenes

MPVariable* const soldados = solver->MakeNumVar(0, 40, "Soldados");

MPVariable* const trenes= solver->MakeNumVar(0, 1000, "Trenes");

// Crear restricción de acabado, 0 <= 2*soldado + trenes <= 100

MPConstraint* restr acabado = solver->MakeRowConstraint(0,100,"acabado");

acabado ->SetCoefficient(soldados, 2);

acabado ->SetCoefficient(trenes, 1);

// Crear restricción de carpintería, 0 <= soldados + trenes <= 80

MPConstraint* const carpintería = solver->MakeRowConstraint(0, 80, "carpintería");

carpintería->SetCoefficient(soldados, 1);

carpintería->SetCoefficient(trenes, 1);

Para completar el modelo declaramos la función objetivo, que sigue estructuras similares a las de las secciones anteriores

// Crear la función objetivo, 3 * soldados + 2* trenes

MPObjective* const objetivo = solver->MutableObjective();

objetivo->SetCoefficient(soldados, 3);

objetivo->SetCoefficient(trenes, 2);

objetivo->SetMaximization();

Para ejecutar el modelo, hay que llamar a la función Solve() del objeto solucionador.

// Resolver el modelo

solver->Solve();

std::cout << "SOluciones:" << std::endl;

std::cout << "Valor objetivo = " << objetivo->Value() << std::endl;

std::cout << "soldados = " << soldados->solution_value() << std::endl;

std::cout << "trenes = " << trenes->solution_value() << std::endl;

Finalmente, creamos una función principal del programa, y llamamos a la función holaMundo().

int main() {

operations_research::holaMundo();

return 0;

}

Que devuelve lo siguiente

Soluciones:

Valor objetivo = 180

soldados = 20

trenes = 60

Implementación AMPL

La A Mathematical Programming Language (AMPL), está dedicada a la representación algebraica de modelos y es muy similar a la formulación del problema. Una vez instalado este software en la máquina, abra su Terminal y abra AMPL utilizando el comando ampl. A partir de ahí, la declaración del modelo es sencilla. Lo primero que hay que hacer es definir los conjuntos del modelo:

set Juguetes;

set Costos;

set Operaciones;

Entonces los parámetros:

param costos_de_produccion {j in Juguetes, c in Costos};

param precio {j in Juguetes};

param demanda {j in Juguetes};

param tiempo_de_operacion {j in Juguetes, o in Operaciones};

param horas_de_trabajo {o in Operaciones};

Seguido por variables:

var Produccion {j in Juguetes} >= 0;

A continuación, las restricciones del modelo:

subject to Restricciones_operativas {o in Operaciones}:

sum{j in Juguetes} (Produccion[j] * tiempo_de_operacion [j,o]) <= horas_de_trabajo[o];

subject to Restricciones_de_demanda {j in Juguetes}: Produccion[j] <= demanda[j];

Y finalmente, la función objetivo:

maximize Ganancia: sum{j in Juguetes} (Produccion[j] * (precio[j] - sum{c in Costos} costos_de_produccion [j,c]));

Con todas las estructuras en su lugar, lo único que queda es definir los elementos de los conjuntos y el valor de los parámetros, utilizando el comando data:

data;

set Juguetes := 'Soldado' 'Trenes';

set Costos := 'Materia prima' 'Mano de obra y gastos generales';

set Operaciones := 'Acabado' 'Carpintería';

param costos_de_produccion :

'Materia prima' 'Mano de obra y gastos generales':=

'Soldado' 10 14

'Trenes' 9 10;

param: precio demanda :=

'Soldado' 27 40

'Trenes' 21 10000;

param tiempo_de_operacion :

'Acabado' 'Carpintería' :=

'Soldado' 2 1

'Trenes' 1 1;

param horas_de_trabajo :=

'Acabado' 100

'Carpintería' 80;

Finalmente, el programador selecciona un solucionador, utilizando el comando option, y encuentra una solución, llamando al comando solve. Por ejemplo, utilizamos Xpress como motor de resolución.

option solver xpress;

solve;

Que imprime la solución en el Terminal:

XPRESS 8.5(33.01.05): Optimal solution found

Objective 180

2 simplex iterations

Comparación de Tecnologías

Aunque todos los enfoques dieron los mismos resultados para el caso simple, puede que no sea así para otros modelos. La elección tecnológica para el desarrollo debe tener en cuenta varios factores más, como: la complejidad del modelo, la capacidad de procesamiento, los conocimientos de programación, el presupuesto reservado, la interfaz gráfica de usuario (GUI), el sistema de versiones, etc.

Por ejemplo, Excel es una gran opción para problemas sencillos de optimización, ya que puede generar fácilmente visualizaciones de la solución y cambiar los valores de los parámetros. Sin embargo, tiene un número reducido de variables que puede considerar y una baja capacidad de procesamiento, por lo que los problemas de mayor envergadura suelen estar fuera de su alcance. Además, no tiene ningún sistema de versiones, lo que puede resultar confuso si muchos colegas deben utilizar el mismo modelo.

Los tres principales lenguajes de programación enumerados, Python, Java y C/C++, son muy similares en sus capacidades para resolver problemas, y pueden resolver problemas de gran complejidad y con una potente capacidad de procesamiento. A su favor, se pueden utilizar de forma gratuita, y son compatibles con las tecnologías de versionado, como git. Sin embargo, la creación de una aplicación para mostrar los resultados e interactuar con los usuarios exige excelentes conocimientos de programación.

La principal ventaja del software AMPL es su clara división del modelo y los datos, pero es la única opción que requiere una licencia, que es gratuita para estudiantes y es paga para investigadores y empresas. AMPL permite a los no programadores modelar fácilmente problemas complejos y seguir alcanzando los mismos niveles de rendimiento y sistemas de versiones de otros lenguajes de programación. Además, cuenta con una interfaz flexible con gráficos y tablas, llamada Quandec, que tiene una estructura de datos incorporada para la gestión de escenarios, acceso en línea, colaboración paralela, herramientas de comparación y mucho más.

Conclusión

El mundo está lleno de oportunidades de optimización que sólo necesitan la herramienta adecuada para el trabajo. Esperamos que este libro electrónico haya incorporado una más a su caja de herramientas. Sin embargo, si el reto parece exigir más experiencia en programación matemática, póngase en contacto con Cassotis a través de nuestros canales y podremos iniciar un proceso de colaboración.