investigación operativa – El blog de Víctor Yepes

Introducción a la teoría de juegos

La teoría de juegos es un área de las matemáticas aplicadas que utiliza modelos para estudiar interacciones en estructuras formales de incentivos, es decir, los llamados «juegos».

Se ha convertido en una herramienta clave para la economía y la administración de empresas, ya que ayuda a entender mejor la conducta humana en la toma de decisiones.

Los investigadores analizan las estrategias óptimas, así como el comportamiento previsto y observado de los individuos en dichos juegos. Tipos de interacción aparentemente distintos pueden tener estructuras de incentivos similares, lo que permite representar el mismo juego una y otra vez.

La teoría de juegos estudia las estrategias óptimas de los jugadores, así como su comportamiento previsto y observado, y ha contribuido a una mejor comprensión de la toma de decisiones humana.

La teoría de juegos aborda situaciones de decisión en las que hay dos oponentes inteligentes con objetivos opuestos. Algunos ejemplos típicos son las campañas de publicidad para productos de la competencia y las estrategias bélicas entre ejércitos. Estas situaciones difieren de las estudiadas previamente, en las que no se tiene en cuenta a la naturaleza como oponente adverso.

El juego es un modelo matemático que se utiliza para entender la toma de decisiones y la interacción entre los participantes, siendo el «dilema del prisionero» uno de los más conocidos. En este escenario, dos personas son arrestadas y encarceladas, y se fija la fecha del juicio. El fiscal se entrevista con cada prisionero por separado y les ofrece la siguiente opción: si uno confiesa y el otro no, el que confiesa queda libre y el otro recibe 20 años de prisión; si ambos confiesan, ambos cumplen 5 años; y si ninguno confiesa, ambos reciben 1 año de prisión. En este dilema, el destino de cada uno depende de la decisión del otro. Aunque confesar parece ser lo mejor, si ambos lo hacen, el castigo es peor que si guardan silencio.

https://www.bbc.com/mundo/noticias/2015/02/150220_teoria_de_juegos_que_es_finde_dv

La teoría de juegos se ha desarrollado y formalizado a partir de los trabajos de John von Neumann y Oskar Morgenstern, especialmente durante la Guerra Fría, debido a su aplicación en la estrategia militar. Los principales conceptos de la teoría de juegos incluyen los juegos de suma cero, los juegos de suma no cero, los equilibrios de Nash, los juegos cooperativos y los juegos de información perfecta e imperfecta.

En la teoría de juegos existen conceptos fundamentales para entender las interacciones estratégicas entre los agentes. Algunos de ellos son:

Estrategia: conjunto de acciones posibles que un jugador puede llevar a cabo en un juego. Las estrategias pueden ser puras (una acción única) o mixtas (una distribución de probabilidad sobre varias acciones).
Equilibrio de Nash: situación en la que ningún jugador tiene incentivos para cambiar su estrategia, dado el conjunto de estrategias de los demás. Es un concepto clave que describe una situación estable en la que las decisiones de los jugadores están equilibradas.
Juego de suma cero: tipo de juego en el que la ganancia total es constante, es decir, lo que uno gana, otro lo pierde. En estos juegos, el objetivo es maximizar la ganancia propia a expensas de los demás jugadores.

La matriz de recompensas es una herramienta clave en la teoría de juegos que representa las combinaciones de decisiones de los jugadores. Muestra los resultados, generalmente en forma de recompensas, para cada jugador según las decisiones de todos los participantes. Es decir, describe cómo las elecciones de cada jugador afectan a sus pagos o beneficios según las decisiones de los demás.

En un conflicto de este tipo hay dos jugadores, cada uno con una cantidad (finita o infinita) de alternativas o estrategias. Cada par de estrategias tiene una recompensa que un jugador paga al otro. A estos juegos se les llama de suma cero, ya que la ganancia de un jugador es igual a la pérdida del otro. Si los jugadores se representan por A y B, con m y n estrategias respectivamente, el juego se suele ilustrar con la matriz de recompensas para el jugador A.

La representación indica que si A usa la estrategia i y B usa la estrategia j, la recompensa para A es a_ij, y entonces la recompensa para B es —a_ij.

Aquí os dejo un esquema conceptual sobre la teoría de juegos.

Os dejo unos vídeos explicativos, que espero, os sea de interés:

En este vídeo se presentan los conceptos fundamentales de la teoría de juegos, que estudia cómo las decisiones de varios jugadores están interconectadas en situaciones estratégicas. A través de ejemplos visuales como matrices y árboles de decisión, se explica cómo los jugadores eligen estrategias para maximizar su utilidad teniendo en cuenta las acciones de los demás. Se destaca la importancia de entender los pagos y resultados de cada estrategia, lo que permite analizar comportamientos competitivos y cooperativos en diversos contextos.

En este otro vídeo se explican distintos tipos de juegos en teoría de juegos, como el dilema del prisionero, el juego del gato y el ratón y la batalla de los sexos, y se destacan sus equilibrios de Nash y las estrategias cooperativas o no cooperativas.

Referencias:

Binmore, K. (1994). Teoría de juegos. McGraw-Hill.
Friedman, J. W. (1991). Teoría de juegos con aplicaciones a la economía. Alianza Universidad.
Kreps, D. M. (1994). Teoría de juegos y modelación económica. Fondo de Cultura Económica.
Martínez-Muñoz, D., Martí, J. V., & Yepes, V. (2025). Game theory-based multi-objective optimization for enhancing environmental and social life cycle assessment in steel-concrete composite bridges. Mathematics, 13(2), 273. https://doi.org/10.3390/math13020273
Meyerson, R. (1991). Game theory: Analysis of conflict. Harvard University Press.
Nash, J. (1950). Equilibrium points in n-person games. Proceedings of the National Academy of the USA, 36(1), 48-49.
Poundstone, W. (1992). Prisoner’s dilemma: John von Neumann, game theory, and the puzzle of the bomb. Doubleday.

Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Fases de un estudio de investigación operativa

La investigación operativa busca determinar la solución óptima para un problema de decisión con recursos limitados. Se trata de un procedimiento científico que analiza las actividades de un sistema de organización.

Las principales componentes de un modelo de investigación operativa son: alternativas, restricciones y un criterio objetivo para elegir la mejor opción. Las alternativas se representan como variables desconocidas que luego se utilizan para construir las restricciones y la función objetivo mediante métodos matemáticos. El modelo matemático establece la relación entre estas variables, restricciones y función objetivo. La solución consiste en asignar valores a las variables para optimizar (maximizar o minimizar) la función objetivo y cumplir con las restricciones. A esta solución se le denomina solución posible óptima.

El enfoque del estudio de la ingeniería de operaciones está relacionado con la toma de decisiones para aprovechar al máximo los recursos limitados. Para ello, utiliza herramientas y modelos adaptados a las necesidades para facilitar la toma de decisiones en la resolución de problemas. Implica un trabajo en equipo entre analistas y clientes, con una estrecha colaboración. Los analistas aportan conocimientos de modelado y el cliente, experiencia y cooperación.

Como herramienta para la toma de decisiones, la investigación de operaciones combina ciencia y arte. Es ciencia por sus técnicas matemáticas y arte, porque el éxito en todas las fases, antes y después de resolver el modelo matemático, depende de la creatividad y experiencia del equipo. La práctica efectiva de la investigación de operaciones requiere más que competencia analítica, e incluye la capacidad de juzgar cuándo y cómo utilizar una técnica, así como habilidades de comunicación y adaptación organizativa.

Es complicado recomendar acciones específicas, como las de la teoría precisa de los modelos matemáticos, para abordar factores intangibles. Solo pueden ofrecerse directrices generales para aplicar la investigación de operaciones en la práctica.

El estudio de investigación operativa consta de varias etapas principales, entre las que destacan las siguientes:

Formulación y definición del problema.
Construcción del modelo.
Solución del modelo.
Verificación del modelo y de la solución.
Puesta en práctica y mantenimiento de la solución.

Aunque las fases del proyecto suelen iniciarse en el orden establecido, no suelen completarse en el mismo orden. La interacción entre las fases requiere revisarlas y actualizarlas continuamente hasta la finalización del proyecto. La tercera fase es la única de carácter puramente matemático, ya que en ella se aplican las técnicas y teorías matemáticas necesarias para resolver el problema. El éxito de las demás etapas depende más de la práctica que de la teoría, siendo la experiencia el factor clave para su correcta ejecución.

Definir el problema implica determinar su alcance, tarea que lleva a cabo todo el equipo de investigación de operaciones. El resultado final debe identificar tres elementos principales: 1) descripción de las alternativas de decisión, 2) determinación del objetivo del estudio y 3) especificación de las restricciones del sistema modelado. Además, se deben recolectar los datos necesarios.

La formulación del modelo es quizá la fase más delicada del proceso, ya que consiste en traducir el problema a relaciones matemáticas. Si el modelo se ajusta a un modelo matemático estándar, como la programación lineal, puede resolverse con los algoritmos correspondientes. Para ello, deben definirse las variables de decisión, la función objetivo y las restricciones. Si las relaciones son demasiado complejas para una solución analítica, se puede simplificar el modelo mediante un método heurístico o recurrir a una simulación aproximada. En algunos casos, puede ser necesaria una combinación de modelos matemáticos, simulaciones y heurísticas para resolver el problema de toma de decisiones.

La solución del modelo es la fase más sencilla de la investigación de operaciones, ya que utiliza algoritmos de optimización bien definidos para encontrar la solución óptima. Un aspecto clave es el análisis de sensibilidad, que proporciona información sobre la forma en que la solución óptima responde a cambios en los parámetros del modelo. Esto es crucial cuando los parámetros no se pueden estimar con precisión, puesto que permite estudiar cómo varía la solución cerca de los valores estimados.

La validación del modelo verifica si cumple su propósito, es decir, si predice adecuadamente el comportamiento del sistema estudiado. Para ello, se evalúa si la solución tiene sentido y si los resultados son aceptables, comparando la solución con datos históricos para verificar si habría sido la correcta. Sin embargo, esto no garantiza que el futuro imite al pasado. Si el modelo representa un sistema nuevo sin datos históricos, se puede usar una simulación como herramienta independiente para comprobar los resultados del modelo matemático.

La implantación de la solución de un modelo validado consiste en traducir los resultados en instrucciones claras para quienes gestionarán el sistema recomendado. Esta tarea recae principalmente en el equipo de investigación de operaciones. En esta fase, el equipo debe capacitar al personal encargado de aplicar el modelo, asegurándose de que puedan traducir sus resultados en instrucciones de operación y usarlo correctamente para tomar decisiones sobre los problemas que motivaron su creación.

Os dejo algún vídeo al respecto.

Referencias:

Altier, W. J. (1999). The thinking manager’s toolbox: Effective processes for problem solving and decision making. Oxford University Press.

Checkland, P. (1999). Systems thinking, system practice. Wiley.

Evans, J. (1991). Creative thinking in the decision and management sciences. South-Western Publishing.

Gass, S. (1990). Model world: Danger, beware the user as a modeler. Interfaces, 20(3), 60-64.

Morris, W. (1967). On the art of modeling. Management Science, 13, B707-B717.

Paulos, J. A. (1988). Innumeracy: Mathematical illiteracy and its consequences. Hill and Wang.

Taha, H. A., & Taha, H. A. (2003). Operations research: an introduction (Vol. 7). Upper Saddle River, NJ: Prentice hall.

Willemain, T. R. (1994). Insights on modeling from a dozen experts. Operations Research, 42(2), 213-222.

Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Los algoritmos genéticos

Charles Darwin en una fotografía tomada por J.M. Cameron en 1869.

Resulta fascinante comprobar cómo aplicando los mecanismos básicos de la evolución ya descrita por Darwin en su obra fundamental, El origen de las especies por medio de la selección natural, o la preservación de las razas preferidas en la lucha por la vida, publicada en 1859, se pueden generar algoritmos capaces de optimizar problemas complejos. Este tipo de metaheurísticas inspiradas en la Naturaleza ya se comentaron en artículos anteriores cuando hablamos de la optimización por colonias de hormigas o de la cristalización simulada. Aunque es un algoritmo ampliamente conocido por la comunidad científica, voy a intentar dar un par de pinceladas con el único afán de divulgar esta técnica. La verdad es que las implicaciones filosóficas que subyacen tras la teoría de Darwin son de una profundidad difícil de entender cuando se lleva a sus últimos extremos. Pero el caso es que estos algoritmos funcionan perfectamente en la optimización de estructuras de hormigón, problemas de transporte y otros problemas difíciles de optimización combinatoria.

Para aquellos interesados, os paso en las referencias un par de artículos donde hemos aplicado los algoritmos genéticos para optimizar rutas de transporte aéreo o pilas de puente huecas de hormigón armado.

Sin embargo, para aquellos otros que queráis un buen libro para pensar, os recomiendo “La peligrosa idea de Darwin”, de Daniel C. Dennett. A más de uno le hará remover los cimientos más profundos de sus creencias. Os paso la referencia al final.

Básicamente, los algoritmos genéticos “Genetic Algorithms, GA”, simulan el proceso de evolución de las especies que se reproducen sexualmente. De manera muy general, se puede decir que en la evolución de los seres vivos, el problema al que cada individuo se enfrenta diariamente es el de la supervivencia. Para ello cuenta, entre otras, con las habilidades innatas provistas en su material genético. A nivel de los genes, el problema consiste en la búsqueda de aquellas adaptaciones beneficiosas en un medio hostil y cambiante. Debido en parte a la selección natural, cada especie gana cierta “información” que es incorporada a sus cromosomas.

Durante la reproducción sexual, un nuevo individuo, diferente de sus padres, se genera a través de la acción de dos mecanismos fundamentales: El primero es el cruzamiento, que combina parte del patrimonio genético de cada progenitor para elaborar el del nuevo individuo; el segundo es la mutación, que supone una modificación espontánea de esta información genética. La descendencia será diferente de los progenitores, pero mantendrá parte de sus características. Si los hijos heredan buenos atributos de sus padres, su probabilidad de supervivencia será mayor que aquellos otros que no las tengan. De este modo, los mejores tendrán altas probabilidades de reproducirse y diseminar su información genética a sus descendientes.

Holland (1975) estableció por primera vez una metaheurística basada en la analogía genética. Un individuo se puede asociar a una solución factible del problema, de modo que se pueda codificar en forma de un vector binario “string”. Entonces un operador de cruzamiento intercambia cadenas de los padres para producir un hijo. La mutación se configura como un operador secundario que cambia, con una probabilidad pequeña, algunos elementos del vector hijo. La aptitud del nuevo vector creado se evalúa de acuerdo con una función objetivo.

Los pasos a seguir con esta metaheurística serían los siguientes:

Generar una población de vectores (individuos).
Mientras no se encuentre un criterio de parada:
1. Seleccionar un conjunto de vectores padre, que serán reemplazados de la población.
2. Emparejar aleatoriamente a los progenitores y cruzarlos para obtener unos vectores hijo.
3. Aplicar una mutación a cada descendiente.
4. Evaluar a los hijos.
5. Introducir a los hijos en la población.
6. Eliminar a aquellos individuos menos eficaces.

Normalmente este proceso finaliza después de un numero determinado de generaciones o cuando la población ya no puede mejorar. La selección de los padres se elige probabilísticamente hacia los individuos más aptos. Al igual que ocurre con en la Naturaleza, los sujetos con mayor aptitud diseminan sus características en toda la población.

Esta descripción de los GA se adapta a cada situación concreta, siendo habitual la codificación de números enteros en vez de binarios. Del mismo modo se han sofisticado los distintos operadores de cruzamiento y mutación.

Os dejo a continuación un vídeo explicativo que he elaborado para mis clases de “Modelos predictivos y de optimización heurística de estructuras de hormigón“, del Máster Universitario en Ingeniería del Hormigón, de la Universitat Politècnica de València.

Referencias:

DENNETT, D.C. (1999). La peligrosa idea de Darwin. Galaxia Gutenberg. Círculo de Lectores, Barcelona.

HOLLAND, J.H. (1975). Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor.

MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2010). Heuristic Optimization of RC Bridge Piers with Rectangular Hollow Sections. Computers & Structures, 88: 375-386. ISSN: 0045-7949. (link)

MEDINA, J.R.; YEPES, V. (2003). Optimization of touristic distribution networks using genetic algorithms. Statistics and Operations Research Transactions, 27(1): 95-112. ISSN: 1696-2281. (pdf)

PONZ-TIENDA, J.L.; YEPES, V.; PELLICER, E.; MORENO-FLORES, J. (2013). The resource leveling problem with multiple resources using an adaptive genetic algorithm. Automation in Construction, 29(1):161-172. DOI:http://dx.doi.org/10.1016/j.autcon.2012.10.003. (link)

YEPES, V. (2003). Apuntes de optimización heurística en ingeniería. Editorial de la Universidad Politécnica de Valencia. Ref. 2003.249. Valencia, 266 pp. Depósito Legal: V-2720-2003.

Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Optimización heurística mediante aceptación por umbrales

En algunos posts anteriores hemos comentado lo que es un modelo matemático de optimización, qué son las metaheurísticas, o cómo poder optimizar las estructuras de hormigón. A continuación os presentamos un Polimedia donde se explica brevemente cómo podemos optimizar siguiendo la técnica de optimización heurística mediante aceptación por umbrales. Podréis comprobar cómo se trata de un caso similar a la famosa técnica de la cristalización simulada. Espero que os sea útil.

Podéis consultar, a modo de ejemplo, algunos artículos científicos que hemos escrito a ese respecto en las siguientes publicaciones:

CARBONELL, A.; GONZÁLEZ-VIDOSA, F.; YEPES, V. (2011). Heuristic optimization of reinforced concrete road vault underpasses. Advances in Engineering Software, 42(4): 151-159. ISSN: 0965-9978. (link)
MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2010). Heuristic Optimization of RC Bridge Piers with Rectangular Hollow Sections. Computers & Structures, 88: 375-386. ISSN: 0045-7949. (link)
YEPES, V.; MEDINA, J.R. (2006). Economic Heuristic Optimization for Heterogeneous Fleet VRPHESTW. Journal of Transportation Engineering, ASCE, 132(4): 303-311. (link)

Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

¿Qué es la optimización por cristalización simulada?

La cristalización simulada (también llamado recocido simulado) “Simulated Annealing, SA” constituye una de las estrategias a las que se recurre en la resolución de los problemas de optimización combinatoria. Kirkpatrick, Gelatt y Vecchi la propusieron por primera vez en 1983 y Cerny en 1985 de forma independiente. Estos autores se inspiraron en los trabajos sobre Mecánica Estadística de Metrópolis et al. (1953). La metaheurística despliega una estructura que se inserta cómodamente en la programación, mostrando además una considerable habilidad para escapar de los óptimos locales. Fue una técnica que experimentó un auge considerable en la década de los 80 para resolver los modelos matemáticos de optimización.

La energía de un sistema termodinámico se compara con la función de coste evaluada para una solución admisible de un problema de optimización combinatoria. En ambos casos se trata de evolucionar de un estado a otro de menor energía o coste. El acceso de un estado metaestable a otro se alcanza introduciendo “ruido” con un parámetro de control al que se denomina temperatura. Su reducción adecuada permite, con una elevada probabilidad, que un sistema termodinámico adquiera un mínimo global de energía. Conceptualmente es un algoritmo de búsqueda por entornos, que selecciona candidatos de forma aleatoria. La alternativa se aprueba si perfecciona la solución actual (D menor o igual que cero); en caso contrario, será aceptada con una probabilidad (e^(-^D/T) si D>0, donde T es el parámetro temperatura) decreciente con el aumento de la diferencia entre los costes de la solución candidata y la actual. El proceso se repite cuando la propuesta no es admitida. La selección aleatoria de soluciones degradadas permite eludir los mínimos locales. La cristalización simulada se codifica fácilmente, incluso en problemas complejos y con funciones objetivo arbitrarias. Además, con independencia de la solución inicial, el algoritmo converge estadísticamente a la solución óptima (Lundy y Mees, 1986). En cualquier caso, SA proporciona generalmente soluciones valiosas, aunque no informa si ha llegado al óptimo absoluto. Por contra, al ser un procedimiento general, en ocasiones no resulta competitivo, aunque sí comparable, ante otros específicos que aprovechan información adicional del problema. El algoritmo es lento, especialmente si la función objetivo es costosa en su tiempo de computación. Además, la cristalización simulada pierde terreno frente a otros métodos más simples y rápidos como el descenso local cuando el espacio de las soluciones es poco abrupto o escasean los mínimos locales.

Os dejo un vídeo explicativo:

Referencias

CERNY, V. (1985). Thermodynamical approach to the traveling salesman problem: an efficient simulated algorithm. Journal of Optimization Theory and Applications, 45: 41-51.

KIRKPATRICHK, S.; GELATT, C.D.; VECCHI, M.P. (1983). Optimization by simulated annealing. Science, 220(4598): 671-680.

LUNDY, M.; MEES, A. (1986). Convergence of an Annealing Algorithm. Mathematical programming, 34:111-124.

METROPOLIS, N.; ROSENBLUTH, A.W.; ROSENBLUTH, M.N.; TELLER, A.H.; TELER, E. (1953). Equation of State Calculation by Fast Computing Machines. Journal of Chemical Physics, 21:1087-1092.

GONZÁLEZ-VIDOSA-VIDOSA, F.; YEPES, V.; ALCALÁ, J.; CARRERA, M.; PEREA, C.; PAYÁ-ZAFORTEZA, I. (2008) Optimization of Reinforced Concrete Structures by Simulated Annealing. TAN, C.M. (ed): Simulated Annealing. I-Tech Education and Publishing, Vienna, pp. 307-320. (link)

¿Qué es la optimización combinatoria?

Los problemas de optimización en los que las variables de decisión son enteras, es decir, donde el espacio de soluciones está formado por ordenaciones o subconjuntos de números naturales, reciben el nombre de problemas de optimización combinatoria. En este caso, se trata de hallar el mejor valor de entre un número finito o numerable de soluciones viables. Sin embargo la enumeración de este conjunto resulta prácticamente imposible, aún para problemas de tamaño moderado.

Las raíces históricas de la optimización combinatoria subyacen en ciertos problemas económicos: la planificación y gestión de operaciones y el uso eficiente de los recursos. Pronto comenzaron a modelizarse de esta manera aplicaciones más técnicas, y hoy vemos problemas de optimización discreta en diversas áreas: informática, gestión logística (rutas, almacenaje), telecomunicaciones, ingeniería, etc., así como para tareas variadas como el diseño de campañas de marketing, la planificación de inversiones, la división de áreas en distritos políticos, la secuenciación de genes, la clasificación de plantas y animales, el diseño de nuevas moléculas, el trazado de redes de comunicaciones, el posicionamiento de satélites, la determinación del tamaño de vehículos y las rutas de medios de transporte, la asignación de trabajadores a tareas, la construcción de códigos seguros, el diseño de circuitos electrónicos, etc. (Yepes, 2002). La trascendencia de estos modelos, además del elevado número de aplicaciones, estriba en el hecho de que “contiene los dos elementos que hacen atractivo un problema a los matemáticos: planteamiento sencillo y dificultad de resolución” (Garfinkel, 1985). En Grötschel y Lobas (1993) se enumeran otros campos en los cuales pueden utilizarse las técnicas de optimización combinatoria.

REFERENCIAS

GARFINKEL, R.S. (1985). Motivation and Modeling, in LAWLER, E.L.; LENSTRA, J.K.; RINNOOY KAN, A.H.G.; SHMOYS, D.B. (eds.) The Traveling Salesman Problem: A Guide Tour of Combinatorial Optimization. Wiley. Chichester.

GRÖTSCHEL, M.; LÓVASZ, L. (1993). Combinatorial Optimization: A Survey. Technical Report 93-29. DIMACS, May.

YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universitat Politècnica de València. 352 pp. ISBN: 0-493-91360-2. (pdf)

Optimización y programación matemática

George Bernard Dantzig (1914-2005), “padre de la programación lineal”

Optimizar significa buscar la mejor manera de realizar una actividad, y en términos matemáticos, hallar el máximo o mínimo de una cierta función, definida en algún dominio. La optimización constituye un proceso para encontrar la mejor solución de un problema donde “lo mejor” se concilia con criterios establecidos previamente.

La programación matemática constituye un campo amplio de estudio que se ocupa de la teoría, aplicaciones y métodos computacionales para resolver los problemas de optimización condicionada. En estos modelos se busca el extremo de una función objetivo sometida a un conjunto de restricciones que deben cumplirse necesariamente. Las situaciones que pueden afrontarse con la programación matemática se suelen presentar en ingeniería, empresas comerciales y en ciencias sociales y físicas.

Con carácter general, un programa matemático (ver Minoux, 1986) consiste en un problema de optimización sujeto a restricciones en de la forma:

Continue reading “Optimización y programación matemática” →

¿Cómo decidir cuando tenemos un dilema? El óptimo de Pareto

Los problemas de decisión están presentes en todos los ámbitos del ser humano: finanzas, empresa, ingeniería, salud, etc. Una de las grandes dificultades al tomar una decisión ocurre cuando queremos conseguir varios objetivos distintos, muchos de ellos incompatibles o contradictorios. Por ejemplo, si queremos un vehículo que sea muy veloz, debería tener un perfil aerodinámico que a veces es incompatible con la comodidad de los usuarios; si queremos hacer un negocio con grandes beneficios, a veces tenemos que asumir ciertos riesgos, etc. Una herramienta que permite afrontar este tipo de problemas de decisión es el denominado “óptimo de Pareto“. A continuación os paso un vídeo explicativo de este tema. Espero que os guste.

¿Por qué son tan complicados los problemas de distribución física?

Aspecto de diversas soluciones al problema de rutas

Los problemas de distribución física consisten básicamente en asignar una ruta a cada vehículo de una flota para repartir o recoger mercancías. Los clientes se localizan en puntos o arcos y a su vez pueden presentar horarios de servicio determinados; el problema consiste en establecer secuencias de clientes y programar los horarios de los vehículos de manera óptima. Los problemas reales de transporte son extraordinariamente variados. Yepes (2002) propone una clasificación que contiene un mínimo de 8,8·10⁹ combinaciones posibles de modelos de distribución. Si alguien fuese capaz de describir en un segundo cada uno de ellos, tardaría cerca de 280 años en enunciarlos todos. La investigación científica se ha centrado, por tanto, en un grupo muy reducido de modelos teóricos que además tienden a simplificar excesivamente los problemas reales. Son típicos problemas de optimización matemática combinatoria. Continue reading “¿Por qué son tan complicados los problemas de distribución física?” →

¿Qué son las metaheurísticas?

¿Cómo se podrían optimizar en tiempos de cálculo razonable problemas complejos de redes de transporte, estructuras de hormigón (puentes, pórticos de edificación, túneles, etc.) y otro tipo de problemas de decisión empresarial cuando la dimensión del problema es de tal calibre que es imposible hacerlo con métodos matemáticos exactos? La respuesta son los métodos aproximados, también denominados heurísticas. Este artículo divulgativo trata de ampliar otros anteriores donde ya hablamos de los algoritmos, de la optimización combinatoria, de los modelos matemáticos y otros temas similares. Para más adelante explicaremos otros temas relacionados específicamente con aplicaciones a problemas reales. Aunque para los más curiosos, os paso en abierto, una publicación donde se han optimizado con éxito algunas estructuras de hormigón como muros, pórticos o marcos de carretera: (González et al, 2008).

Desde los primeros años de la década de los 80, la investigación de los problemas de optimización combinatoria se centra en el diseño de estrategias generales que sirvan para guiar a las heurísticas. Se les ha llamado metaheurísticas. Se trata de combinar inteligentemente diversas técnicas para explorar el espacio de soluciones. Osman y Kelly (1996) nos aportan la siguiente definición: “Los procedimientos metaheurísticos son una clase de métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria, en los que los heurísticos clásicos no son ni efectivos ni eficientes. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y la mecánica estadística”.

Aunque existen diferencias apreciables entre los distintos métodos desarrollados hasta el momento, todos ellos tratan de conjugar en mayor o menor medida la intensificación en la búsqueda –seleccionando movimientos que mejoren la valoración de la función objetivo-, y la diversificación –aceptando aquellas otras soluciones que, aun siendo peores, permiten la evasión de los óptimos locales-.

Las metaheurísticas son susceptibles de agruparse de varias formas. Algunas clasificaciones recurren a cambios sucesivos de una solución a otra en la búsqueda del óptimo, mientras otras se sirven de los movimientos aplicados a toda una población de soluciones. El empleo, en su caso, de memoria que guíe de la exploración del espacio de elecciones posibles permite otro tipo de agrupamiento. En otras circunstancias se emplean perturbaciones de las opciones, de la topología del espacio de soluciones, o de la función objetivo. En la Figura se recoge una propuesta de clasificación de las heurísticas y metaheurísticas empleadas en la optimización combinatoria (Yepes, 2002), teniendo en común todas ellas la necesidad de contar con soluciones iniciales que permitan cambios para alcanzar otras mejores. Es evidente que existen en este momento muchas más técnicas de optimización, pero puede ser dicha clasificación un punto de partida para una mejor taxonomía de las mismas.

Taxonomía de estrategias empleadas en la resolución aproximada de problemas de optimización combinatoria sobre la base de soluciones iniciales. — Figura. Taxonomía de estrategias empleadas en la resolución aproximada de problemas de optimización combinatoria sobre la base de soluciones iniciales (Yepes, 2002)

Las metaheurísticas empleadas en la optimización combinatoria en podrían clasificarse en tres grandes conjuntos. Las primeras generalizan la búsqueda secuencial por entornos de modo que, una vez se ha emprendido el proceso, se recorre una trayectoria de una solución a otra vecina hasta que éste concluye. En el segundo grupo se incluyen los procedimientos que actúan sobre poblaciones de soluciones, evolucionando hacia generaciones de mayor calidad. El tercero lo constituyen las redes neuronales artificiales. Esta clasificación sería insuficiente para aquellas metaheurísticas híbridas que emplean, en mayor o menor medida, estrategias de unos grupos y otros. Esta eventualidad genera un enriquecimiento deseable de posibilidades adaptables, en su caso, a los diferentes problemas de optimización combinatoria.

Referencias

GONZÁLEZ-VIDOSA-VIDOSA, F.; YEPES, V.; ALCALÁ, J.; CARRERA, M.; PEREA, C.; PAYÁ-ZAFORTEZA, I. (2008) Optimization of Reinforced Concrete Structures by Simulated Annealing. TAN, C.M. (ed): Simulated Annealing. I-Tech Education and Publishing, Vienna, pp. 307-320. (link)

OSMAN, I.H.; KELLY, J.P. (Eds.) (1996). Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers.

Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.