UPV



investigación operativa


Publicada By  Víctor Yepes Piqueras - algoritmo, Docencia, investigación operativa, optimización, ordenadores, Polimedia, programación    

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: https://www.youtube.com/watch?v=wtw_B_3lrjE

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)

Publicada By  Víctor Yepes Piqueras - ciclo de vida, costes, estructuras, hormigón, investigación operativa, optimización, Puentes, sostenibilidad    

Nos acaban de publicar en línea en la revista Structural and Multidisciplinary Optimization (revista indexada en JCR en el primer cuartil) un trabajo de investigación en el que utilizamos las redes neuronales artificiales junto para el diseño multiobjetivo de puentes postesados de carreteras. Os paso a continuación el resumen y el enlace al artículo por si os resulta de interés. El enlace del artículo es el siguiente: http://link.springer.com/article/10.1007%2Fs00158-017-1653-0

Referencia:

García-Segura, T.; Yepes, V.; Frangopol, D.M. (2017). Multi-objective design of post-tensioned concrete road bridges using artificial neural networks. Structural and Multidisciplinary Optimization, doi:10.1007/s00158-017-1653-0

Abstract:

In order to minimize the total expected cost, bridges have to be designed for safety and durability. This paper considers the cost, the safety, and the corrosion initiation time to design post-tensioned concrete box-girder road bridges. The deck is modeled by finite elements based on problem variables such as the cross-section geometry, the concrete grade, and the reinforcing and post-tensioning steel. An integrated multi-objective harmony search with artificial neural networks (ANNs) is proposed to reduce the high computing time required for the finite-element analysis and the increment in conflicting objectives. ANNs are trained through the results of previous bridge performance evaluations. Then, ANNs are used to evaluate the constraints and provide a direction towards the Pareto front. Finally, exact methods actualize and improve the Pareto set. The results show that the harmony search parameters should be progressively changed in a diversification-intensification strategy. This methodology provides trade-off solutions that are the cheapest ones for the safety and durability levels considered. Therefore, it is possible to choose an alternative that can be easily adjusted to each need.

Keywords:

Multi-objective harmony search; Artificial neural networks; Post-tensioned concrete bridges; Durability; Safety.

Publicada By  Víctor Yepes Piqueras - algoritmo, Docencia, hormigón, investigación operativa, optimización    

La programación lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones lineales, optimizando la función objetivo, también lineal. Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

Os dejo un vídeo tutorial donde se explica la programación lineal y se avanzan las ideas básicas del método Simplex.

Existen páginas web, como PHPSimplex, donde puedes solucionar on-line problemas sencillos. También puede resolverse este tipo de problemas con las herramientas de MATLAB: Optimization Toolbox.

A continuación os dejo un vídeo donde se explica cómo resolver un problema de Programación Lineal mediante MS Excel 2007. Es importante que aprendáis a utilizar el Solver. Espero que os guste el vídeo.

También os dejo el siguiente enlace del canal FdeT donde podéis aprender más sobre programación lineal: https://www.youtube.com/playlist?list=PL0_FimzlChzLfAeFbjv0S2nnj8fAi82wB

¿Seríais capaces de resolver los siguientes problemas, donde el objetivo es maximizar el beneficio?:

  1. Una empresa produce hormigón usando los ingredientes A y B. Cada kilo de ingrediente A cuesta 60 unidades monetarias y contiene 4 unidades de arena fina, 3 unidades de arena gruesa y 5 unidades de grava. Cada kilo de ingrediente B cuesta 100 unidades monetarias y contiene 3 unidades de arena fina, 6 unidades de arena gruesa y 2 unidades de grava. Cada amasada debe contener, por lo menos, 12 unidades de arena fina, 12 unidades de arena gruesa y 10 unidades de grava. Formule un modelo de programación lineal y resuélvalo gráficamente.
  2. Una empresa especializada en la construcción de estructuras de edificios tiene patentes de tres tipos de forjados F1, F2 y F3. Los beneficios que consigue por metro cuadrado de forjado construido son 100, 90 y 120 unidades monetarias respectivamente. Por razones de almacenamiento y financiación, diariamente sólo se dispone de dos toneladas de acero, 200 m3 de hormigón y 8 m3 de madera para encofrados. Las cantidades de acero, hormigón y madera que se necesitan por m2 en cada uno de los forjados son:

Tipo de forjado

Materia prima

Cantidad

F1

Acero

0,2 kg/m2

Hormigón

80 dm3/m2

Madera

0,001 m3/m2

F2

Acero

0,25 kg/m2

Hormigón

37,5 dm3/m2

Madera

0,00125 m3/m2

F3

Acero

0,225 kg/m2

Hormigón

35 dm3/m2

Madera

0,0015 m3/m2

 

13 febrero, 2016
 

Publicada By  Víctor Yepes Piqueras - algoritmo, investigación operativa, optimización, ordenadores, Planificación, programación, proyectos    

Henry Laurence Gantt (1861-1919)

Si tuviésemos que hablar de la historia de la planificación y control de las obras, deberíamos referirnos a la primera de las construcciones realizadas por el hombre y perdida en el origen de nuestra especie. Construcciones como las pirámides de Egipto no pudieron construirse sin un plan previo y una compleja organización de recursos. Sin embargo, si queremos utilizar las actuales técnicas de planificación, podríamos reducir significativamente nuestra historia y remontarnos apenas medio siglo en Estados Unidos, cuando tanto desde el ámbito militar como desde el civil, de forma independiente, se sentaron las bases de la técnicas basadas en el método del camino crítico (Critical Path Method, CPM) y en el método PERT (Program Evaluation and Review Technique). La planificación y programación de proyectos complejos, sobre todo grandes proyectos unitarios no repetitivos, comenzó a ser motivo de especial atención al final de la Segunda Guerra Mundial, donde el diagrama de barras de Henry Gantt  era la única herramienta de planificación de la que se disponía, que fue un método innovador en su momento, pero muy limitado. Gannt publicó en 1916 “Work, Wages, and Profits“, un texto donde discutía estos aspectos de planificación y otros relacionados con la productividad. De todos modos, para ser más exactos, Gantt no fue el pionero en el uso de esta herramienta. Otros autores como Joseph Priestley en 1765 o William Playfair en 1786, ya había sugerido ideas precursoras, que el ingeniero  Karol Adamiecki desarrolló en 1896 en lo que él llamó como “Harmonograma”. También deberíamos destacar aquí los primeros intentos desarrollados, entre 1955 y 1957 por la “Imperial Chemical Industries” y el “Central Electricity Generating Board”, en el Reino Unido, donde se desarrolló una técnica capaz de identificar la secuencia de estados más larga e irreductible para la ejecución de un trabajo, en línea con lo que después se llamaría CPM (Crítical Path Method). Estas empresas consiguieron ahorros de tiempo en torno al 40%, pero debido a que no se publicaron estas innovaciones, cayeron en la oscuridad, de la cual se despertó con los avances que se desarrollaron al otro lado del océano. (más…)

28 enero, 2015
 
|   Etiquetas: ,  ,  ,  ,  ,  ,  |  

Publicada By  Víctor Yepes Piqueras - algoritmo, hormigón, investigación operativa, logística, modelo matemático, optimización, ordenadores, transporte    

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 posts 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 afan 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. (más…)

Publicada By  Víctor Yepes Piqueras - algoritmo, investigación operativa, logística, modelo matemático, optimización, Polimedia, programación    

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)

Publicada By  Víctor Yepes Piqueras - algoritmo, competitividad, investigación operativa, logística, transporte    

La planificación y gestión de redes de distribución de baja demanda exige disponer de técnicas eficientes de optimización de rutas. El sistema de optimización de rutas disponible, no sólo afecta el desarrollo de operaciones sino, también las decisiones tácticas y estratégicas como el tamaño óptimo de flota, estimación de costes, políticas de publicidad y rotura de servicio, etc.  Por ejemplo, es habitual la venta de paquetes turísticos que incluyen el transporte; los precios se fijan mucho antes de que la demanda de transporte sea conocida, siendo frecuentes las cancelaciones de última hora y la llegada de nuevos clientes. Si  el número de pasajeros que debe ser transportado es pequeño, en comparación con la máxima capacidad de carga del vehículo óptimo a la distancia correspondiente, los beneficios o pérdidas generadas por el transporte dependen críticamente de la eficiencia del sistema de optimización de rutas. La Figura describe la influencia de la optimización de operaciones en la planificación y gestión de redes de distribución de baja demanda.

Redes de baja demanda

Planificación y Gestión de Redes de Distribución de Baja Demanda

Así pues, la planificación (más…)

6 agosto, 2014
 

Publicada By  Víctor Yepes Piqueras - algoritmo, investigación operativa, modelo matemático, optimización, programación    

George Bernard Dantzig

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:

 

(más…)

5 junio, 2014
 

Publicada By  Víctor Yepes Piqueras - algoritmo, economía, investigación, investigación operativa, logística, transporte    

Me ha parecido interesante rescatar una pequeña publicación, que ya tiene 10 años, donde se aplicaba un algoritmo de optimización heurística curioso: Old Bachelor Acceptance, o “algoritmo del solterón“. En este caso, aplicado a la optimización de redes de transporte con flotas heterogéneas. Resulta curioso ver cómo determinados comportamientos sociales (colonias de hormigas), principios naturales (teoría de la evolución) o recreaciones de nuestro cerebro (redes neuronales) son capaces de resolver problemas complejos de optimización.

Espero que os sea de interés.

20 marzo, 2014
 
|   Etiquetas: ,  ,  ,  |  

Publicada By  Víctor Yepes Piqueras - algoritmo, economía, investigación operativa, modelo matemático, optimización, Polimedia    

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.

 

 

18 diciembre, 2013
 

Página siguiente »

Universidad Politécnica de Valencia