La Optimización Estocástica busca la mejor decisión en un escenario dependiente de sucesos aleatorios, dependientes del azar. Esos sucesos aleatorios pueden ser los precios de un producto, la duración de una tarea, el número de personas en la cola de un cajero, el número de averías en una flota de camiones, o incluso la aprobación de una normativa. Vamos, cualquier cosa.
¿Estocástico? ¿Intentas asustarme?
“Estocástico” es una palabra especialmente temida, ya que como en otros lenguajes especializados, esa era la idea inicial. Los expertos celosos que buscan guardar sus secretos utilizan términos complicados de cara al exterior para “amedrentar” a las personas externas al sector. Ahí tenemos el lenguaje jurídico, el económico, o más cerca de nuestro trabajo, corre el rumor de que el creador del lenguaje C++ lo hizo tan complicado para diferenciar a los buenos programadores de los malos. En realidad, la palabra “estocástico” no es peligrosa, significa sencillamente aleatorio, dependiente del azar. La idea es bastante sencilla, pero como adjetivo puede complicar cualquier disciplina.
Problemas de Optimización Estocástica
Los problemas de optimización estocástica son en general mucho más complejos que los que no consideran el azar. Principalmente porque el azar implica que no tenemos un solo escenario a optimizar, sino un conjunto de escenarios posibles. Por ejemplo, si queremos optimizar el diseño de una red de distribución de energía, trabajaremos en un escenario de incertidumbre en el que desconocemos la demanda real de energía en el momento de uso de la red. En lugar del dato de la demanda, tendríamos una estimación, quizás un conjunto finito de demandas posibles, con una probabilidad asociada.
Con esto ya podemos intuir que el mundo de la empresa está lleno de problemas estocásticos, ¿qué se suele hacer para resolverlos? En escenarios con decisiones sencillas, es decir, con pocas variables de decisión y con pocos estados, se pueden enumerar explícitamente todas las posibilidades utilizando arboles de decisión (que además son muy intuitivos). Por ejemplo, una señora se entera en la peluquería de que dan un 50% de probabilidad de lluvia y debe decidir si comprar o no comprar un paraguas de pésima calidad.
- Si compra el paraguas,
- Si llueve (probabilidad 0.5) habrá gastado 5 euros en un paraguas de pésima calidad.
- Si no llueve habrá gastado lo mismo 5 euros.
- Si no compra el paraguas,
- Si llueve tendrá que volver a ir a la peluquería y pagar otros 15 euros.
- Si no llueve no tiene que pagar ni un euro más.
En conclusión, si compra el paraguas la pérdida esperada será de 5 euros, y si no lo compra de 7.5 euros. Si la señora está en sus cabales debe comprar el paraguas. Aunque a priori parezca un comportamiento pesimista y despilfarrador, sería el más acertado. Pero si el problema es más complicado, se acaba optando por simplificar usando el escenario esperado o el escenario más probable, ya que éstos son deterministas y se pueden resolver usando optimización convencional. Por ejemplo, en el caso de la planificación de la red de distribución de energía, podría fijarse la demanda a la estimación del INE, sin pararse a valorar el impacto que podría tener una caída o un aumento inesperado de la demanda. Otras veces para ahorrarse el dolor de cabeza directamente se simplifica el negocio. Esto es lo que hizo Alejandro Magno con el famoso nudo Gordiano, o por poner un ejemplo más cercano y más contemporáneo, poner una caja más en un supermercado en vez de hacer una única cola. En muchos casos estas simplificaciones pueden llevar a tomar decisiones que no son las más acertadas.
Optimización Estocástica
Aunque se considera que esta disciplina nació en los años 50 con Dantzig y Beale, históricamente la optimización ha tenido bastante con restringirse a problemas no estocásticos, esencialmente por la complejidad que los problemas estocásticos entrañan. Afrontar problemas reales sigue siendo imposible en muchos casos, pero los avances en capacidad de computación y el desarrollo de las técnicas de optimización, han permitido resolver problemas hasta hace poco impensables. Además, a veces tan sólo una aproximación estocástica puede mejorar enormemente la solución, lo que se traduce en ahorro de costes, mejora de servicio o incremento de beneficios, entre otros.
Y entonces, ¿qué sería la optimización estocástica? Un problema de optimización tiene:
- una serie de variables o decisiones que hay que tomar,
- una serie de restricciones que limitan esas decisiones
- y una función objetivo, una medida de coste o de calidad del conjunto de decisiones tomadas.
Los datos asociados a las restricciones y a la función objetivo suelen ser valores conocidos, pero, ¿y si estos valores vinieran dados por sucesos aleatorios? Entonces el problema es de optimización estocástica. Hay dos preguntas especialmente incómodas:
¿Qué ocurre con la factibilidad cuando las restricciones son aleatorias?
Una solución es factible cuando satisface todas las restricciones. Pero con restricciones aleatorias no podemos hablar estrictamente de factibilidad, sino de probabilidad de que una cierta solución sea factible. Así, en el problema de planificar la red de distribución de energía, una restricción podría ser “la capacidad de la red de distribución es mayor o igual que la demanda”. Pero si la demanda resulta ser muy alta puede ocurrir que no la podamos satisfacer.
¿Cómo redefinir la función objetivo?
La respuesta a esta pregunta es menos obvia. Podríamos redefinir la función objetivo como el valor esperado de la función objetivo anterior, pero podría ser más interesante reducir el riesgo de la decisión utilizando el peor de los casos (dada una solución, ¿qué es lo peor que puede pasar?). En general este tipo de problemas se han afrontado utilizando programación lineal. Por lo que también se habla de Programación Estocástica.
¿Qué tienen de complicado estos problemas?
La complejidad de estos problemas radica en su tamaño. Pensemos en la aparentemente inofensiva señora que sale de la peluquería. Supongamos que además deba decidir si ir en autobús o andando a hacer un recado. Cada nueva variable aleatoria (el estado del tráfico, una huelga, una manifestación, ¿a qué hora cerraba, 20:00 o 20:30?) y cada nueva decisión (ir en autobús, ir dando un rodeo por zona de soportales) multiplica las posibilidades. En vez de considerar cuatro posibles resultados deberíamos considerar decenas o cientos. Si seguimos considerando elementos de incertidumbre que pueden amenazar a la señora, el número de posibles resultados aumentará exponencialmente. Volvamos ahora al problema de planificación de la red de distribución de energía. La demanda es aleatoria, los precios futuros de la energía son aleatorios, la producción de energía eólica es aleatoria, así como los precios de los combustibles. El resultado de cualquier decisión en este contexto dependerá de lo que ocurra con cada uno de esos sucesos aleatorios, ¡hay millones de escenarios posibles! Por suerte para nosotros hay técnicas que permiten resolver estos problemas de forma más eficiente, Descomposición de Dantzig-Wolfe , Descomposición de Benders o Generación de Columnas.
Conclusión
La mayor parte de los problemas reales son de naturaleza estocástica. Hay pocos negocios en que se conozcan todos los datos de antemano.
No podemos seguir evitándolos, entonces… ¿por qué simplificar el problema y renunciar al uso de optimización avanzada?
La optimización estocástica nos puede permitir afrontar problemas que hasta ahora se han resuelto por “intuición”, por “sentido común”, o porque “de toda la vida se ha hecho así”. De una forma más eficiente a través de la optimización estocástica, podemos tener soluciones que nos situarán en clara ventaja frente a nuestros competidores. Siempre merece la pena intentarlo.
Si quieres saber más sobre optimización matemática o sobre decide4AI, contáctanos o síguenos en las redes sociales (Linkedin, Twitter, Youtube).
