El modelamiento matemático es una estructura científica que nos permite mediante una formulación,expresar las relaciones que pueden existir entre un conjunto de eventos,parámetros,entidades o sistemas.En este sentido generalmente buscamos modelar las relaciones existentes entre fenómenos reales tangibles o intangibles.Es asi que para distintos tipos de fenómenos, algunos paradigmas permiten explicar o abstraer de mejor forma las situaciones de análisis.Sin embargo hay algunas clasificaciones iniciales que podemos hacer.
Cuando buscamos modelar matemáticamente una situación existen 2 perspectivas fuertes,las que nos permiten distinguir de distinta forma aspectos de la misma naturaleza de la situación o el objeto de análisis y estos son:
Modelos cualitativos:Estos permiten representar mediante diagramas o gráficos,las relaciones entre los sistemas de interés.Asi estos solo buscan describir las direcciones generales o particulares del sistema.
Modelos cuantitativos:En cambio estos buscan mediante números,representar las relaciones y parámetros del o los sistemas,permitiendo la integración de los mecanismos de acción mediante fórmulas o algoritmos de menor o mayor complejidad.
Específicamente en este curso introductorio a optimización,revisaremos el modelamiento de algunos modelos clasicos de programación lineal y entera.
Cuando hablamos de programación lineal,estamos considerando el campo que se dedica a maximizar o minimizar una función lineal,a la cual llamamos función objetivo.En este contexto,las variables que estan presentes en esta función se encuentran sujetas a un conjunto de restriciones establecidas en un sistema de ecuaciones.
Un modelo típico de optimización lineal es como el que consideramos a continuación.
$max \{c^Tx :x \in \Re \wedge Ax \leq b \wedge x \geq 0\} $
Pero tambien podemos desarrollar en su formulación estándar un caso particular.
$f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}$
$a_{11}x_{1}+a_{12}x_{2} \leq b_{1}$
$a_{21}x_{1}+a_{22}x_{2} \leq b_{2}$
$a_{31}x_{1}+a_{32}x_{2} \leq b_{3}$
$x_{1} \geq 0$
$x_{2} \geq 0$
Generalmente el método para la resolución de problemas de programación lineal es el método simplex desarrollado por George Dantzig en 1947,el cual asegura encontrar el optimo global,sin embargo en algunos casos el algoritmo no presenta buenos resultados.Sin embargo existen otros métodos para la resolución de problemas de optimización lineal como el algoritmo de cambio de base,algoritmo de punto interior,algoritmo elipsoide,entre otros los que permiten asegurar óptimos globales pero en mejores tiempos de resolución.
A diferencia de la programación lineal,en este caso todas las variables desconocidas son enteras,entonces consideramos el problema como de programación entera.Cabe destacar que en este caso los valores de las variables pueden solo tomar valores enteros.Sin embargo,si las variables pueden solo tomar los valores 0 y 1,estamos frente a una subcategoria de la programación entera,llamada programación binaria.
Algunos de los métodos mas utilizadas para la resolución de este tipo de modelos corresponden a los algoritmos Branch and bound,Branch and cut,planos de corte,entre otros.
A continuación,veremos el formulamiento de un problema clásico y de bastante interés en la literatura de programación entera,específicamente de programación binaria.
Si disponemos de $n$ objetos para llevar en una mochila.Cada uno de los objetos,tiene un peso $p_{j}$ y tiene una utilidad relativa para el viaje de $c_{j}$.Finalmente consideramos que la mochila solo admite un peso máximo de $b$.
En este problema buscamos tomar la decisión de cuales son aquellos objetos que debemos seleccionar para llevar en la mochila,de manera tal que maximicemos la utilidad total.
Si consideramos que cada objeto que podemos llevar se corresponde con una variable que puede ser asignada o no,entonces podemos definir lo siguiente:
$\begin{equation} x_{j} = \left\lbrace \begin{array}{ll} 1 & \text{si el objeto j se selecciona } \newline 0 & \text{en otro caso } \end{array} \right. \end{equation}$
Luego podemos definir 2 restricciones para el problema,primero el límite de peso de la mochila de acuerdo a los pesos $p_j$
$\sum_{j=1}^n p_{j}x_{j} \leq b$
y luego la condición para que las variables sean binarias.
$x_{j} \in \{0,1\} \ \ \ \ \ \ \forall \ \ \ j=1,...,n$
Finalmente podemos definir la función objetivo que maximiza la utilidad relativa total
$max \sum_{j=1}^n c_{j}x_{j}$
A diferencia del problema anterior,en el problema de la mochila de múltiple elección los objetos se encuentran subdivididos en $k$ clases,en donde solo podemos tomar un item de cada una de las clases.De esta forma podemos formalizar el problema como
$max \sum_{i=1}^k \sum_{j=1}^N v_{i,j}x_{i,j}$
$\sum_{i=1}^k \sum_{j=1}^N w_{i,j} x_{i,j}$
$\sum_{j=1}^N x_{i,j}=1 \ \ \ \ \forall \ \ 1\leq i \leq k$
$x_{i,j} \in \{0,1\} \ \ \ \forall \ \ 1 \leq i \leq k ,\ j \in N$
Guu... que??😅
Gurobi es un software comercial para la resolución de problemas de optimización Lineal,Cuadratica,Lineal Entera,entre otros modelos.La librería fue desarrollada por parte del equipo que desarrollo CPLEX (otro software de optimización con bastante uso industrial y academico).
Uno de los aspectos importantes de Gurobi,es que soporta una amplia variedad de lenguajes como C++,Java,Python,R,MATLAB,AMPL,entre otros.Además es posible realizar cómputo en la nube.
En este curso introductorio,utilizaremos la interfaz de JupyterLab para la resolución de problemas de optimización haciendo uso de la libreria Gurobi,mediante el módulo Gurobipy.
Gurobipy es un módulo que permite utilizar la API con todas las caracteristicas de Gurobi.
Para hacer uso de esta primero deberemos descargar el instalador desde la web de Gurobi https://www.gurobi.com/downloads/
y luego deberemos instalar el módulo desde la terminal en windows.
pip install gurobipy
Sin embargo como ultimo paso y no menos importante,debemos seleccionar el tipo de licencia que queremos ocupar,la cual puede ser: (1) Licencia de evaluación comercial,(2) Licencia Academica,(3) Licencia de curso on-line y para (4) prueba en la nube.
Ya teniendo todo listo,en la próxima sección utilizaremos la libreria gurobi para modelar y resolver algunos problemas clasicos de optimización.
Como ya vimos es posible modelar distintos procesos del mundo real bajo distintos paradigmas,en este caso buscamos optimizar ya sea maximizando o minimizando una función objetivo,la cual se encuentra sujeta a un conjunto de restricciones.Sin embargo la programación matemática generalmente se encuentra al inicio o a medio camino con la visión del negocio,esto implica que no nos centramos unicamente en modelar cualquier proceso,sino aquellos que sean críticos y/o haya una evidente oportunidad de mejora,la cual beneficie de forma directa a la empresa.
Algunas de las áreas en donde existe una mayor aplicación y evidencias de los beneficios de esta técnica es en:
Para diseñar un modelo matemático que represente un sistema real,es necesario abstraer el sistema real mediante el modelamiento matemático.De esta forma primero es necesario definir un set de variables de decisión,las cuales deben ser representativas de aquellas decisiones que buscamos controlar en el sistema real.Sin embargo,estas pueden ser variables de tipo entero o continuas,lo cual podria influir posteriormente en el tiempo de resolución del modelo.
Junto a lo anterior debemos definir un set de restricciones,que capturen los límites globales que definen los valores que pueden tomar las variables de decisión
Finalmente debemos diseñar la función objetivo,la cual captura en gran parte el objetivo principal de la empresa.Esto implica definir si se quiere maximizar o minimizar el costo de la operación completa del proceso y como las variables de decisión interactuan entre ellas para la definición del objetivo.
Para este primer caso resolveremos un problema clásico correspondiente al problema del carpintero.El problema al que se enfrenta el carpintero,corresponde a cuantas mesas y sillas debe fabricar para maximizar sus ingresos.
$max \ \ 5x_{1}+3x_{2}$
$2x_{1}+x_{2}<=40$
$x_{1}+2x_{2}<=50$
$x_{i} \geq 0$
De acuerdo al modelo planteado, los valores 5 y 3 que acompañan a la función objetivo corresponden a los ingresos netos por la cantidad de $mesas (x_{1}) \ \ y \ \ sillas (x_{2})$.Luego tenemos la primera restricción de mano de obra y la segunda de materiales.En la primera solo se cuentan con 40 horas laborales por semana y una mesa se demora 2 horas en construirse y las sillas demoran 1 hora.En cambio para la materia prima se cuenta con 50 unidades por semana,en donde las mesas requieren de 1 materia prima y las sillas de 2.
A continuación se plantea el modelo de optimización mediante la libreria gurobi,asi que primero cargaremos la librería.
from gurobipy import *
Una vez cargada la librería,creamos un modelo genérico con la función *Model()*.Luego en el modelo deberemos generar tanto las variables de decisión que usaremos en el modelo,asi como las constantes,restricciones y función objetivo.
m=Model()
x_1=m.addVar(vtype=GRB.CONTINUOUS,name="x_1")
x_2=m.addVar(vtype=GRB.CONTINUOUS,name="x_2")
c_1=5
c_2=3
Set parameter Username Academic license - for non-commercial use only - expires 2023-09-16
Para crear las variables $x_{1}$ y $x_{2}$ dentro del modelo, usamos la función *addVar()*.En esta debemos especificar si la variable es continua,entera o binaria.Luego definimos las constantes correspondientes a los ingresos netos por la cantidad tanto de mesas como de sillas.
c1=m.addConstr(2*x_1+x_2<=40)
c2=m.addConstr(x_1+2*x_2<=50)
m.setObjective(c_1*x_1+c_2*x_2,GRB.MAXIMIZE)
Luego agregamos las 2 restricciones correspondientes a $2x_{1}+x_{2}\leq 40$ y $x_{1}+2x_{2}$,mediante la función *addConstr().Finalmente podemos definir la función objetivo mediante la funcion setObjective()*,en donde ademas debemos definir si queremos maximizar o minimizar la función.
Una vez definimos todos los elementos necesarios para el modelo de optimización,podemos resolver el problema mediante la función *optimize()*
m.optimize()
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15d58d31
Coefficient statistics:
Matrix range [1e+00, 2e+00]
Objective range [3e+00, 5e+00]
Bounds range [0e+00, 0e+00]
RHS range [4e+01, 5e+01]
Presolve time: 0.02s
Presolved: 2 rows, 2 columns, 4 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 8.0000000e+30 3.000000e+30 8.000000e+00 0s
2 1.1000000e+02 0.000000e+00 0.000000e+00 0s
Solved in 2 iterations and 0.05 seconds (0.00 work units)
Optimal objective 1.100000000e+02
Como se puede observar,el optimizador entrega bastante información una vez resuelto el problema.Primero nos da un detalle de la versión junto con las caracteristicas de la maquina en donde estamos ejecutando el software,luego nos da información respecto al modelo en donde incluso nos muestra cuanto tiempo demora en la resolución...en este caso demoro 0.05s luego de 2 iteraciones,en realidad no es un problema muy complejo 😅.
Finalmente nos entrega aspectos generales de la resolución como el Objective,Primal Inf. y Dual Inf.Sin embargo si quisieramos llamar solo a algunos valores especificos como el valor que toma cada variable de decisión,podemos usar la función *getVars()*
m.getVars()
[<gurobi.Var x_1 (value 10.0)>, <gurobi.Var x_2 (value 20.0)>]
Pero tambien podriamos obtener el valor por separado de la función objetivo con la función ***objval()***
m.objval
110.0
De esta forma podemos corrobar el valor del objetivo mediante el reemplazo de las variables de decisión en la función objetivo.De esta forma tenemos que $5x_{1}+3x_{2}=5*10+3*20=110$,pudiendo comprobar el optimo entregado por el optimizador.
Otro de los problemas de bastante interés y ampliamente desarrollado en la literatura corresponde a los problemas de transporte,específicamente estamos considerando problemas en donde las variables de decisión toman valores enteros.A pesar de que es posible utilizar el algoritmo simplex para su resolución,tambien es posible la utilización de otros algoritmos mas eficientes para su resolución.
Un caso de los problemas de transporte corresponde al suministro que deben realizar $m$ almacenes a $n$ destinos de un determinado producto.Luego la capacidad de la oferta de cada uno de los orígenes $i=1,...,m.$,mientas que la demanda de cada destino $j=1,...,n$ es $b_{j}$.Luego el costo de enviar una unidad de producto del origen $i$ al destino $j$ corresponde a $c_{i,j}$.Asi buscamos determinar cual es la cantidad de unidades de producto que se deben enviar desde los origenes $i$ a los destinos $j$,pero minimizando el costo total de envío y ademas asegurando la demanda en los destinos y no excediendo la capacidad de los origenes.
De esta forma podemos formalizar el problema de la siguiente forma:
$min \sum_{i=1}^m \sum_{j=1}^n c_{i,j} x_{i,j}$
sujeto a las siguientes restricciones
$\sum_{j=1}^n x_{i,j} \leq a_{i} \ \ \ \ i=1,2,...,m$
$\sum_{i=1}^m x_{i,j} \geq b_{j} \ \ \ \ j=1,2,...,n$
$x_{i} \geq 0 \ \ \ \ i=1,2,...,m \ \ \ \ j=1,2,...,n $
Ahora consideremos un caso particular del problema de transporte, en donde 3 almacenes que deben abastecer 6 destinos de un producto.En donde la oferta de cada almacen es 2.045,2.234 y 1.800 y la demanda a suplir por cada destino es de 1.523,1.768, 850 y 1.918 Luego tenemos que los costos de enviar productos desde cada almacen a cada origen se muestran en la siguiente tabla.
| Costo de envio | Valor | |||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $c_{1,1}$ | 10.200 | |||||||||||||||||||||||||||||||||
| $c_{1,2}$ | 13.450 | |||||||||||||||||||||||||||||||||
| $c_{1,3}$ | 11.890 | |||||||||||||||||||||||||||||||||
| $c_{1,4}$ | 19.324 | |||||||||||||||||||||||||||||||||
| $c_{2,1}$ | 15.912 | |||||||||||||||||||||||||||||||||
| $c_{2,2}$ | 15.340 | |||||||||||||||||||||||||||||||||
| $c_{2,3}$ | 12.670 | |||||||||||||||||||||||||||||||||
| $c_{2,4}$ | 11.843 | |||||||||||||||||||||||||||||||||
| $c_{3,1}$ | 16.312 | |||||||||||||||||||||||||||||||||
| $c_{3,2}$ | 16.917 | |||||||||||||||||||||||||||||||||
| $c_{3,3}$ | 13.218 | |||||||||||||||||||||||||||||||||
| $c_{3,4}$ | 14.347 | |||||||||||||||||||||||||||||||||
| Articulo $x_{j}$ | 1 | 2 | 3 | 4 | 5 | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Peso $w_{j}$ | 42 | 23 | 21 | 15 | 7 | ||||||
| Valor $p_{j}$ | 100 | 60 | 70 | 15 | 15 | ||||||