Interpretación de las holguras de una actividad en la planificación de un proyecto

En un artículo anterior ya vimos los errores que suelen cometerse en el cálculo de las holguras, especialmente cuando se está trabajando con un diagrama de precedencias. El concepto de holgura se emplea en la planificación para describir la libertad de desplazamiento que, dentro de un cierto intervalo de tiempo, puede tener un suceso o una actividad. También suelen llamarse juegos o tiempos flotantes. En esta entrada vamos a interpretar qué significa cada una de las holguras que existen en una actividad. Esta interpretación es fundamental para el responsable de la tarea, pues debe comprender qué implica el retraso de su actividad en el contexto del proyecto o de la obra que está realizando.

En la Figura 1 se muestra cómo una actividad aij se representa como una flecha orientada desde parte del nodo i y llega al nodo j. A los nodos se les denomina “sucesos” o “acontecimientos“.

Figura 1. Definición de los tiempos disponibles de una actividad

Estos nodos presentan una holgura de suceso o margen de etapa que, en el caso del nodo i, se calcula de la siguiente forma:

En esta expresión, Ei representa la fecha más temprana del acontecimiento i, mientras que Li representa la fecha más tardía.

Con los conceptos anteriores, es fácil demostrar que el margen de etapa en un determinado nudo es igual a la diferencia entre los tiempos “disponible total” y “disponible libre” de cualquier actividad que termine en dicho nudo. En efecto, para una actividad aij, se tiene:

Pues bien, cualquier actividad, como la aij, debe transcurrir entre sus nodos de inicio y de final. Como cada nodo presenta dos fechas, una más temprana y otra más tardía, los nodos de entrada y salida de una actividad dan lugar a cuatro fechas que definen cuatro posibles tiempos disponibles para la actividad (ver Figura 1).

Se define como holgura o margen de una actividad como el tiempo disponible que queda después de descontar la duración de dicha tarea. Como existen cuatro posibles tiempos disponibles, se podrán definir cuatro tipos de holguras para las actividades. Es evidente que si una actividad pertenece a un camino crítico, no tiene holguras.

Recordemos que la fecha más tardía para que la actividad aij pueda empezar, se calcula como Ljtij. Esta fecha no tiene por qué coincidir con Li, tal y como ya discutimos en un artículo anterior.

Si dibujamos la actividad aij en un diagrama de barras, podríamos representar la actividad empezando lo antes posible, es decir, en el instante Ei. Otra opción sería dibujar la actividad empezando en el instante más tardío del acontecimiento i (volvemos a recordar que no es la fecha más tardía en que puede empezar la actividad aij). De esta forma, podemos visualizar las holguras que presenta la actividad en la Figura 2. Se puede ver una quinta holgura, que es la holgura interferente, como diferencia entre la holgura total y la holgura libre.

Figura 2. Representación de las holguras de una actividad

Vamos a analizar cada una de estas holguras para poder interpretar lo que significan. Ya os adelanto que las holguras más empleadas son la total y la libre. Pero hay más.

Holgura total

La holgura total se define como la diferencia entre el tiempo disponible total y la duración de la actividad. Es una holgura que es mayor o igual a cero y se calcula de la siguiente forma:

Es el margen en que una actividad puede atrasar su inicio más temprano, su término más temprano o su duración, sin atrasar el término programado del proyecto. Si se consume esta holgura, la actividad y el suceso siguiente se hacen críticos. Este es el valor menos probable de todas las holguras, pues está condicionado al hecho de que la actividad comience en el tiempo más optimista y que la actividad no sufra desviación alguna.

La holgura total pertenece al camino del que forma parte la actividad. Es decir, que dicha holgura se puede consumir completamente en una de las tareas del camino o distribuir el margen entre distintas actividades de dicho camino. Es por ello que a la holgura total también suele llamarse “margen de camino“.

Holgura libre

La holgura libre se define como la diferencia entre el tiempo disponible libre y la duración de la actividad, siendo un valor mayor o igual a cero. Se calcula de la siguiente forma:

Se trata de la cantidad de tiempo en que una actividad puede atrasar su inicio más temprano, su término más temprano o aumentar su duración, sin atrasar el inicio más temprano de sus actividades subsecuentes. Esta holgura es muy importante para el gestor de la actividad, pues si mantengo el retraso dentro de este límite, no afectaré a las actividades que vengan después. Si se consume esta holgura, la red permanece inalterada. Por eso se llama a esta holgura “margen de actividad“.

La holgura total se puede obtener sumando a la holgura libre el margen de la etapa de llegada. En efecto,

Como se puede comprobar, la holgura libre no puede ser mayor a la holgura total. Además, la condición necesaria (pero no suficiente) para que exista es que llegue más de una actividad al nodo de terminación de la actividad que estamos analizando.

Holgura interferente

La holgura interferente se define como la diferencia entre la holgura total y la holgura libre. Se interpreta como la cantidad de tiempo que se puede demorar la terminación de una actividad, sin demorar la terminación del proyecto, pero cuyo uso retrasará el inicio de alguna de las actividades siguientes. La holgura interferente es exactamente el margen de etapa del nodo de llegada de la actividad. Se puede calcular de la siguiente forma:

Cuando se representa en un diagrama de barras una actividad, empezando lo antes posible, si existe holgura total, debe diferenciarse con un trazo vertical qué parte es holgura libre y qué parte es interferente. En la Figura 3 se muestra cómo debe hacerse.

Figura 3. Representación de la holgura total, libre e interferente en un diagrama de barras

Holgura independiente

La holgura independiente es la diferencia entre el tiempo disponible independiente y la duración de la actividad. También se llama “holgura mínima“. Suele ser un valor muy pequeño, incluso negativo. Además, siempre es menor o igual a la holgura libre (Figura 2). Se calcula de la siguiente forma:

Esta holgura es el retraso que puede sufrir una actividad con su inicio demorado al máximo por las actividades precedentes, sin que ese retraso ocasione aplazamientos en el comienzo de cualquier actividad posterior. Al igual que la holgura libre, la independiente no se comparte con ninguna otra actividad.

En la práctica no se suele emplear esta holgura, aunque puede ser útil como parámetro representativo de las condiciones más desfavorables en que puede desarrollarse una actividad.

La holgura independiente se puede calcular como la holgura total menos la suma de los márgenes de las etapas inicial y final de la actividad. También como la diferencia entre la holgura libre y el margen de la etapa inicial de la actividad. Por dicho motivo, la holgura independiente no puede superar a la holgura libre, al igual que la holgura libre no podía ser mayor a la holgura total.

Holgura condicionada

La holgura condicionada, también llamada “holgura intermedia“, es el margen en que una actividad puede atrasar su inicio demorado al máximo por las actividades precedentes, su término más temprano o su duración, sin atrasar el término programado del proyecto. Se puede calcular de la siguiente forma:

Como se puede observar, su interpretación es similar a la holgura total, pero suponiendo que el inicio se ha retrasado al máximo posible por las actividades precedentes.

Si observamos la Figura 2, es fácil deducir que la holgura condicionada es la suma de la holgura independiente y la interferente. O lo que es lo mismo, la holgura condicionada es la holgura independiente, menos la diferencia de la holgura total y la libre.

A modo de ejemplo, vamos a analizar las holguras de la actividad E perteneciente al siguiente proyecto:

Como se puede observar, la actividad E podría empezar, como muy pronto, en la etapa 10, y como muy tarde, en la etapa 15. Asimismo, podría terminar, como muy pronto, en la etapa 15, y como muy tarde, en la etapa 20.

El cálculo de las holguras sería el siguiente:

Holgura total: L5 – E3 – t35 = 20 – 10 – 5 = 5

Holgura libre: E5 – E3 – t35 = 17 – 10 – 5 = 2

Holgura interferente: L5 – E5 = 20 – 17 = 3

Holgura independiente: E5 – L3 – t35 = 17 – 12 – 5 = 0

Holgura condicionada: L5 – L2 – t35 = 20 – 12 – 5 = 3

Referencias:

YEPES, V.; MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F.; ALCALÁ, J. (2012). Técnicas de planificación y control de obras. Editorial de la Universitat Politècnica de València. Ref. 189. Valencia, 94 pp. Depósito Legal: V-423-2012.

YEPES, V. (2022). Gestión de costes y producción de maquinaria de construcción. Colección Manual de Referencia, serie Ingeniería Civil. Editorial Universitat Politècnica de València, 243 pp. Ref. 442. ISBN: 978-84-1396-046-3

YEPES, V. (2023). Maquinaria y procedimientos de construcción. Problemas resueltos. Colección Académica. Editorial Universitat Politècnica de València, 562 pp. Ref. 376. ISBN 978-84-1396-174-3

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

Errores que se comenten en el cálculo de holguras con los diagramas de precedencias

Figura 1. Programación de proyectos

Las técnicas de programación de proyectos basadas en el cálculo de redes se explican normalmente en los grados de ingeniería civil. Los estudiantes automatizan el cálculo de estas redes de forma sencilla, tanto en el caso de las redes de flechas como en el de las redes de precedencias. Sin embargo, muchas veces no comprenden o les resulta confuso la idea de holgura de un suceso o de una actividad. Incluso en algunos libros de texto confunden los conceptos. Quiero en este artículo aclarar mediante un ejemplo dónde están los problemas asociados al cálculo de las holguras.

Por cierto, podéis repasar en cálculo de una red de flechas o una red de precedencias en alguno de los artículos y vídeos que grabé en su momento. Basta que pulséis el enlace correspondiente.

Sea un proyecto compuesto por seis actividades cuyas relaciones de precedencia y duración se muestran en la Tabla 1. En dicha tabla, una actividad situada en una línea precede a la actividad de una columna si la casilla se encuentra marcada. Así, por ejemplo, la actividad A precede tanto a la actividad B como a la C. Para simplificar, las relaciones son final-principio, es decir, la actividad subsecuente no puede iniciarse hasta que se hayan terminado las actividades que le preceden.

Tabla 1. Relación de precedencias entre las actividades.

Es fácil representar y calcular el diagrama de flechas correspondiente. Este proyecto tiene un plazo de 35 etapas, siendo el camino crítico el representado por las actividades A, B, D y F (ver Figura 2).

Figura 2. Representación y cálculo del diagrama de flechas

Este mismo proyecto se podría haber calculado usando un diagrama de precedencias, cuya resolución puede verse en la Figura 3. Observe que las fechas más tempranas de inicio de cada actividad tienen un color azul, mientras que las más tardías están en verde. Estas fechas se pueden ver también en la Figura 2.

Figura 3. Representación y cálculo del diagrama de precedencias

Si representamos el proyecto en un diagrama de barras, se obtiene la Figura 4. Se observa que en este diagrama se ha representado el inicio de cada actividad lo antes posible. Además, se han dibujado la holgura total y libre, separadas ambas por una línea vertical. La actividad C no tiene holgura libre, mientras que en la actividad E, la holgura total y libre coinciden.

Figura 4. Diagrama de barras o de Gantt, con las actividades empezando lo antes posible

Pues veamos ahora dónde están los problemas con las holguras. Previamente, vamos a definir la holgura de una actividad como la diferencia entre el tiempo disponible para realizarla y su duración.

Las holguras se definen en función de los nodos de entrada y salida de la actividad, según se representa en la Figura 5. Existen cinco tipos de holgura: total, libre, independiente, condicional e interferente. Esta última es la diferencia entre la holgura total y la holgura libre.

Figura 5. Definición de los tiempos disponibles de una actividad

El primer error conceptual que se comete es definir las fechas de los nodos de entrada y salida de una actividad como las fechas más tempranas y tardías de inicio o terminación de dicha actividad. Solo Ei y Lj son la fecha más temprana de inicio y la más tardía de finalización de la actividad. Las fechas Li y Ej corresponden a los nodos correspondientes. En efecto, la fecha más tardía de inicio sería Lj -tij; mientras que la fecha más temprana de terminación sería Ei+tij. Se pueden ver ambas fechas en las barras verdes de la Figura 5. Únicamente en el caso de las fechas representadas dentro de la caja de la actividad de un diagrama de precedencias, tenemos las fechas más tempranas y tardías de inicio y terminación de la actividad correspondiente (Figura 6).

Figura 6. Notación y forma de representación de una actividad en un diagrama de precedencias

El segundo error conceptual está en algunos libros cuando dicen lo siguiente “El concepto y cálculo de las holguras usando el diagrama de precedencias en nada difiere del introducido para el diagrama de flechas“. En sí misma, esta frase es correcta. El error viene cuando se confunde el comienzo más tardío de la actividad con Li y el final más temprano de la actividad con Ej.

Es por todo lo anterior que, en el caso del cálculo de la holgura total, no hay ningún problema en su cálculo con el diagrama de flechas o de precedencias. Pero el resto de holguras puede ser erróneo si utilizamos un diagrama de precedencias. Veamos qué ocurre con la actividad C de este proyecto.

Holgura total: L4 – E2 – t24 = 20 – 5 – 5 = 10

Holgura libre: E4 – E2 – t24 = 10 – 5 -5 = 0

Holgura independiente: E4 – L2 – t24 = 10 – 5 – 5 = 0

Holgura condicionada: L4 – L2 – t24 = 20 – 5 – 5 = 10

Fíjese que el comienzo más tardío de la actividad C sería 15, que es un valor diferente a L2 = 5. En este caso, la terminación más temprana de la actividad C sería 10, que coincide en este caso con E4 = 10.

Conclusión: Si se usa el diagrama de precedencias, hay que tener mucho cuidado en calcular holguras de una actividad, excepto para el caso de la holgura total. En el diagrama de flechas no existe ningún problema. No confundir las fechas de comienzo más tardío y final más temprano de una actividad con los correspondientes a los nodos de entrada y salida de dicha actividad.

Referencias:

YEPES, V.; MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F.; ALCALÁ, J. (2012). Técnicas de planificación y control de obras. Editorial de la Universitat Politècnica de València. Ref. 189. Valencia, 94 pp. Depósito Legal: V-423-2012.

YEPES, V. (2022). Gestión de costes y producción de maquinaria de construcción. Colección Manual de Referencia, serie Ingeniería Civil. Editorial Universitat Politècnica de València, 243 pp. Ref. 442. ISBN: 978-84-1396-046-3

YEPES, V. (2023). Maquinaria y procedimientos de construcción. Problemas resueltos. Colección Académica. Editorial Universitat Politècnica de València, 562 pp. Ref. 376. ISBN 978-84-1396-174-3

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

ESRA, un software educativo para introducir a los estudiantes de ingeniería civil en la programación de proyectos estocástica

https://www.piqsels.com/es/public-domain-photo-sucqz

Las técnicas clásicas de programación son herramientas comúnmente empleadas en las escuelas de ingeniería civil de todo el mundo para la enseñanza de la planificación y gestión de proyectos. Técnicas como el método del camino crítico (CPM), el método del diagrama de precedencias (PDM), el diagrama de Gantt o la técnica de evaluación y revisión de programas (PERT) presentan la ventaja de su sencillez, facilidad de comprensión y que se implementan en los programas informáticos de gestión de proyectos más aceptados, como Ms Project o Primavera P6. Sin embargo, estas técnicas de programación presentan importantes limitaciones a la hora de tratar la incertidumbre inherente a la gestión de proyectos de construcción. Por un lado, el enfoque determinista del CPM para el aprendizaje de la planificación del proyecto reduce la sensibilidad y la comprensión de los factores que alteran y desafían significativamente el éxito de un proyecto, y por otro lado, el CPM no es capaz de gestionar la incertidumbre. y desafían el éxito de un proyecto, mientras que, por otro lado, el PERT muestra unas capacidades demasiado limitadas en modelización de la incertidumbre y subestima la desviación estándar de la duración del proyecto.

El Análisis de Riesgo de Programación (SRA) es un método estocástico idóneo para promover que los estudiantes empiecen a gestionar proyectos de forma más eficaz y eficiente. En este trabajo, empleamos un software educativo de SRA (ESRA) para ayudar a los estudiantes a entender el supuesto subyacente de la programación estocástica, así como para hacer explícitas las ventajas de la programación estocástica en comparación con los métodos clásicos como CPM o PERT. ESRA permite modelar tanto la incertidumbre en la duración de las actividades, como la relación entre estas incertidumbres, ampliando la gama de problemas de planificación, que los estudiantes pueden ahora evaluar. Esta investigación se llevó a cabo en cuatro etapas a través de un taller. En primer lugar, se introdujeron los fundamentos teóricos de la simulación de Montecarlo, el método en el que se basan la mayoría de los métodos de evaluación de la incertidumbre. En segundo lugar, los estudiantes emplearon el ESRA para ver cómo funciona este método. En tercer lugar, los alumnos trabajaron en torno a un caso práctico de gestión de proyectos de construcción y analizaron los resultados, comparando los de la evaluación estocástica con los de la evaluación determinista. Por último, se les pidió que respondieran a un cuestionario en el que debían abordar la toma de decisiones en el mundo real en relación con la programación de proyectos que requería tener en cuenta las incertidumbres del proyecto.

Referencia:

SALAS, J.; SIERRA, L.; YEPES, V. (2021). ESRA, an educational software for introducing stochastic scheduling to civil engineering students. 15th annual International Technology, Education and Development Conference (INTED 2021), 8th-9th March, 2021, pp. 5788-5798, Valencia, Spain. ISBN: 978-84-09-27666-0

Descargar (PDF, 694KB)

 

 

 

Conceptos básicos de teoría de grafos

Algunas herramientas que utilizamos en Programación de Proyectos, como las redes de flechas, se basan en la teoría de grafos. Conceptos como nodo, arco, flecha, camino, bucle, etc. son necesarios conocerlos de forma previa al estudio de las técnicas de programación. Os dejo a continuación unos Polimedias de la profesora Cristina Jordán donde se explican brevemente los conceptos básicos de esta teoría. Espero que os gusten.

Referencias:

PELLICER, E.; YEPES, V. (2007). Gestión de recursos, en Martínez, G.; Pellicer, E. (ed.): Organización y gestión de proyectos y obras. Ed. McGraw-Hill. Madrid, pp. 13-44. ISBN: 978-84-481-5641-1. (link)

YEPES, V.; PELLICER, E. (2008). Resources Management, in Pellicer, E. et al.: Construction Management. Construction Managers’ Library Leonardo da Vinci: PL/06/B/F/PP/174014. Ed. Warsaw University of Technology, pp. 165-188. ISBN: 83-89780-48-8.

YEPES, V.; MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F.; ALCALÁ, J. (2012). Técnicas de planificación y control de obras. Editorial de la Universitat Politècnica de València. Ref. 189. Valencia, 94 pp. Depósito Legal: V-423-2012

¿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)

¿Es fácil optimizar estructuras de hormigón?

Es más, ¿es posible que un ordenador sea capaz de diseñar de forma automática estructuras óptimas sin darle ninguna pista o información previa? Estoy convencido que a la vuelta de un par de años, todos los programas comerciales tendrán paquetes de optimización estructural que permitirán reducciones de coste en torno al 5-15% respecto a los programas actuales. Ya os adelanto que esta nueva tecnología va a traer consigo nuevas patologías en las estructuras de hormigón, que con la optimización se parecen más a las estructuras metálicas. Con el tiempo habrá que introducir capítulos o restricciones en las futuras versiones de la EHE o de los Eurocódigos. En este post vamos a continuar comentando aspectos relacionados con la modelización matemática, la optimización combinatoria, las metaheurísticas y los algoritmos.

Toda esta aventura la empezamos en el año 2002, con el primer curso de doctorado sobre optimización heurística en la ingeniería civil, que luego hemos ido ampliando y mejorando en el actual Máster Oficial en Ingeniería del Hormigón. Ya tenemos varias tesis doctorales y artículos científicos al respecto para aquellos de vosotros curiosos o interesados en el tema. Para aquellos que queráis ver algunas aplicaciones concretas, os recomiendo el siguiente capítulo de libro que escribimos sobre la optimización de distintas estructuras con un algoritmo tan simple como la cristalización simulada. Para aquellos otros que tengáis más curiosidad, os dejo algunas publicaciones de nuestro grupo de investigación en el apartado de referencias.

Os paso, para abrir boca, una forma sencilla de optimizar a través de este Polimedia. Espero que os guste.

Referencias:

  • MOLINA-MORENO, F.; MARTÍ, J.V.; YEPES, V. (2017). Carbon embodied optimization for buttressed earth-retaining walls: implications for low-carbon conceptual designs. Journal of Cleaner Production, 164:872-884. https://authors.elsevier.com/a/1VLOP3QCo9NDzg 
  • GARCÍA-SEGURA, T.; YEPES, V.; FRANGOPOL, D.M.; YANG, D.Y. (2017). Lifetime Reliability-Based Optimization of Post-Tensioned Box-Girder Bridges. Engineering Structures, 145:381-391. DOI:10.1016/j.engstruct.2017.05.013 OPEN ACCESS
  • 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, 56(1):139-150. doi: 10.1007/s00158-017-1653-0
  • YEPES, V.; MARTÍ, J.V.; GARCÍA-SEGURA, T.; GONZÁLEZ-VIDOSA, F. (2017). Heuristics in optimal detailed design of precast road bridges. Archives of Civil and Mechanical Engineering, 17(4):738-749. DOI: 10.1016/j.acme.2017.02.006
  • MOLINA-MORENO, F.; GARCÍA-SEGURA; MARTÍ, J.V.; YEPES, V. (2017). Optimization of Buttressed Earth-Retaining Walls using Hybrid Harmony Search Algorithms. Engineering Structures, 134:205-216. DOI: 10.1016/j.engstruct.2016.12.042
  • GARCÍA-SEGURA, T.; YEPES, V. (2016). Multiobjective optimization of post-tensioned concrete box-girder road bridges considering cost, CO2 emissions, and safety. Engineering Structures, 125:325-336. DOI: 10.1016/j.engstruct.2016.07.012.
  • MARTÍ, J.V.; GARCÍA-SEGURA, T.; YEPES, V. (2016). Structural design of precast-prestressed concrete U-beam road bridges based on embodied energy. Journal of Cleaner Production, 120:231-240. DOI: 10.1016/j.jclepro.2016.02.024
  • GARCÍA-SEGURA, T.; YEPES, V.; ALCALÁ, J.; PÉREZ-LÓPEZ, E. (2015). Hybrid harmony search for sustainable design of post-tensioned concrete box-girder pedestrian bridges. Engineering Structures, 92:112-122. DOI: 10.1016/j.engstruct.2015.03.015 (link)
  • LUZ, A.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; MARTÍ, J.V. (2015). Diseño de estribos abiertos en puentes de carretera obtenidos mediante optimización híbrida de escalada estocástica. Informes de la Construcción, 67(540), e114. DOI: 10.3989/ic.14.089
  • MARTÍ, J.V.; YEPES, V.; GONZÁLEZ-VIDOSA, F. (2015). Memetic algorithm approach to designing of precast-prestressed concrete road bridges with steel fiber-reinforcement. Journal of Structural Engineering ASCE, 141(2): 04014114. DOI:10.1061/(ASCE)ST.1943-541X.0001058 (descargar versión autor)
  • YEPES, V.; GARCÍA-SEGURA, T.; MORENO-JIMÉNEZ, J.M. (2015). A cognitive approach for the multi-objective optimization of RC structural problems. Archives of Civil and Mechanical Engineering, 15(4):1024-1036. doi:10.1016/j.acme.2015.05.001
  • YEPES, V.; MARTÍ, J.V.; GARCÍA-SEGURA, T. (2015). Cost and CO2 emission optimization of precast-prestressed concrete U-beam road bridges by a hybrid glowworm swarm algorithm. Automation in Construction, 49:123-134. DOI: 10.1016/j.autcon.2014.10.013 (link)
  • GARCÍA-SEGURA, T.; YEPES, V.; MARTÍ, J.V.; ALCALÁ, J. (2014). Optimization of concrete I-beams using a new hybrid glowworm swarm algorithm. Latin American Journal of Solids and Structures,  11(7):1190 – 1205. ISSN: 1679-7817. (link)
  • MARTÍ, J.V.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; LUZ, A. (2013). Diseño automático de tableros óptimos de puentes de carretera de vigas artesa prefabricadas mediante algoritmos meméticos híbridos. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, DOI: http://dx.doi.org/10.1016/j.rimni.2013.04.010.
  • TORRES-MACHÍ, C.; YEPES, V.; ALCALA, J.; PELLICER, E. (2013). Optimization of high-performance concrete structures by variable neighborhood search. International Journal of Civil Engineering, 11(2):90-99 . ISSN: 1735-0522. (link)
  • MARTÍNEZ-MARTÍN, F.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2013). A parametric study of optimum tall piers for railway bridge viaducts. Structural Engineering and Mechanics45(6): 723-740. (link)
  • MARTINEZ-MARTIN, F.J.; GONZALEZ-VIDOSA, F.; HOSPITALER, A.; YEPES, V. (2012). Multi-objective optimization design of bridge piers with hybrid heuristic algorithms. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering, 13(6):420-432. DOI: 10.1631/jzus.A1100304. ISSN 1673-565X (Print); ISSN 1862-1775 (Online).  (link)
  • MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F.; YEPES, V.; ALCALÁ, J. (2013). Design of prestressed concrete precast road bridges with hybrid simulated annealing. Engineering Structures48:342-352. DOI:10.1016/j.engstruct.2012.09.014. ISSN: 0141-0296.(link)
  • YEPES, V.; GONZÁLEZ-VIDOSA, F.; ALCALÁ, J.; VILLALBA, P. (2012). CO2-Optimization Design of Reinforced Concrete Retaining Walls based on a VNS-Threshold Acceptance Strategy. Journal of Computing in Civil Engineering ASCE, 26 (3):378-386. DOI: 10.1061/(ASCE)CP.1943-5487.0000140. ISNN: 0887-3801. (link)
  • CARBONELL, A.; YEPES, V.; GONZÁLEZ-VIDOSA, F. (2011). Búsqueda exhaustiva por entornos aplicada al diseño económico de bóvedas de hormigón armado. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, 27(3):227-235.  (link) [Global best local search applied to the economic design of reinforced concrete vauls]
  • 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. (2011). Estudio paramétrico de pilas para viaductos de carretera. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, 27(3):236-250. (link)
  • MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; ALCALÁ, J. (2011). Design of tall bridge piers by ant colony optimization. Engineering Structures, 33:2320-2329.
  • PEREA, C.; YEPES, V.; ALCALÁ, J.; HOSPITALER, A.; GONZÁLEZ-VIDOSA, F. (2010). A parametric study of optimum road frame bridges by threshold acceptance. Indian Journal of Engineering & Materials Sciences, 17(6):427-437. ISSN: 0971-4588.  (link)
  • PAYÁ-ZAFORTEZA, I.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A. (2010). On the Weibull cost estimation of building frames designed by simulated annealing. Meccanica, 45(5): 693-704. DOI 10.1007/s11012-010-9285-0. ISSN: 0025-6455.  (link)
  • MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F. (2010). Design of prestressed concrete precast pedestrian bridges by heuristic optimization. Advances in Engineering Software, 41(7-8): 916-922. http://dx.doi.org/10.1016/j.advengsoft.2010.05.003
  • 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)
  • PAYÁ, I.; YEPES, V.; HOSPITALER, A.; GONZÁLEZ-VIDOSA, F. (2009). CO2-Efficient Design of Reinforced Concrete Building Frames. Engineering Structures, 31: 1501-1508. ISSN: 0141-0296. (link)
  • YEPES, V.; ALCALÁ, J.; PEREA, C.; GONZÁLEZ-VIDOSA, F. (2008). A Parametric Study of Optimum Earth Retaining Walls by Simulated Annealing. Engineering Structures, 30(3): 821-830. ISSN: 0141-0296.  (link)
  • PEREA, C.; ALCALÁ, J.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A. (2008). Design of Reinforced Concrete Bridge Frames by Heuristic Optimization. Advances in Engineering Software, 39(8): 676-688. ISSN: 0965-9978.  (link)
  • PAYÁ, I.; YEPES, V.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A. (2008). Multiobjective Optimization of Reinforced Concrete Building Frames by Simulated Annealing. Computer-Aided Civil and Infrastructure Engineering, 23(8): 596-610. ISSN: 1093-9687.  (link)
  • PAYÁ, I.; YEPES, V.; CLEMENTE, J.J.; GONZÁLEZ-VIDOSA, F. (2006). Optimización heurística de pórticos de edificación de hormigón armado. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería, 22(3): 241-259. [Heuristic optimization of reinforced concrete building frames]. (link)

¿Sirve la técnica del análisis del valor ganado (EVM)?

Una metodología adoptada con frecuencia para realizar un control efectivo de los costes es la del análisis del valor ganado. Permite un control económico-temporal del proyecto considerando las repercusiones económicas que produce un retraso en el plazo. Las variaciones, tanto de tiempo como de coste respecto de la planificación prevista deben ser corregidas, lo antes posible, de modo que el proyecto pueda cumplir los objetivos previstos. Para calcular estas variaciones se definen tres variables básicas (utilizando la nomenclatura propuesta por el Project Management Institute):

  • Coste presupuestado del trabajo planificado (PV).
  • Coste presupuestado del trabajo realizado (EV) o valor ganado.
  • Coste real del trabajo realizado (AC).

PV representa el coste previsto originalmente contra el cual se mide el rendimiento real. Desde el punto de vista del contrato, PV es el presupuesto contratado menos el beneficio previsto por la empresa. Para un período determinado, PV se determina sumando los costes de cada una de las tareas finalizadas y de la parte proporcional de las tareas en curso.

Usando las definiciones anteriores pueden obtenerse las siguientes variaciones (en las que los valores negativos indican un exceso sobre lo previsto):

  • CV (variación del coste) = EV – AC
  • SV (variación del tiempo) = EV – PV

Ambas pueden transformarse en porcentajes:

  • CVP (variación del coste) = (EV – AC) / EV
  • SVP (variación del tiempo) = (EV – PV) / PV

Y también en índices:

  • CPI (índice de coste consumido) = EV / AC
  • SPI (índice de tiempo consumido) = EV / PV

Si los índice son iguales a la unidad, el rendimiento es el previsto. Si son superiores a la unidad, el rendimiento es superior al planeado. Finalmente, si son inferiores a la unidad, su rendimiento es inferior al previsto. Estos índices se utilizan normalmente para predecir tendencias y llevar a cabo acciones correctivas, si fuese necesario.

 

Para entender mejor esta técnica y su formulación, os dejo unos vídeos explicativos sobre el tema. Espero que os gusten.

Referencias:

PELLICER, E.; YEPES, V. (2007). Gestión de recursos, en Martínez, G.; Pellicer, E. (ed.): Organización y gestión de proyectos y obras. Ed. McGraw-Hill. Madrid, pp. 13-44. ISBN: 978-84-481-5641-1. (link)

PELLICER, E.; YEPES, V.; TEIXEIRA, J.C.; MOURA, H.P.; CATALÁ, J. (2014). Construction Management. Wiley Blackwell, 316 pp. ISBN: 978-1-118-53957-6.

YEPES, V.; PELLICER, E. (2008). Resources Management, in Pellicer, E. et al.: Construction Management. Construction Managers’ Library Leonardo da Vinci: PL/06/B/F/PP/174014. Ed. Warsaw University of Technology, pp. 165-188. ISBN: 83-89780-48-8.

YEPES, V.; MARTÍ, J.V.; GONZÁLEZ-VIDOSA, F.; ALCALÁ, J. (2012). Técnicas de planificación y control de obras. Editorial de la Universitat Politècnica de València. Ref. 189. Valencia, 94 pp. Depósito Legal: V-423-2012.

¿Las hormigas nos pueden enseñar a optimizar puentes?

A veces la Naturaleza nos sorprende cada día más. ¿Es posible que el comportamiento de las hormigas pueda servirnos para optimizar estructuras complejas, como por ejemplo un puente? Pues vamos a ver que sí. Este post es continuación de otros anteriores donde hablamos de la posibilidad de optimizar estructuras de hormigón. La optimización por colonia de hormigas (ant colony optimization) va a ser una metaheurística que nos va a permitir realizar este tipo de operaciones. A continuación vamos a contar los fundamentos básicos y en las referencias os dejo, incluso, algunos artículos donde hemos podido utilizar esta técnica de forma exitosa.

Colorni, Dorigo y Maniezzo (1991) sugirieron la idea de imitar el comportamiento de los insectos para encontrar soluciones a los problemas de optimización combinatoria. El principio de la metaheurística denominada como “Ant System Optimization, ACO” se basa en el comportamiento colectivo de las hormigas en la búsqueda de alimentos para su subsistencia, que son capaces de encontrar el camino más corto entre una fuente de comida y su hormiguero. Primero las hormigas exploran el entorno de su hormiguero de forma aleatoria. Tan pronto como un individuo encuentra una fuente de comida, evalúa su cantidad y calidad y transporta un poco al hormiguero. Durante el regreso, la hormiga deja por el camino una señal odorífera, depositando una sustancia denominada feromona, para que las demás puedan seguirla. Después de un tiempo, el camino hacia el alimento se indicará por un rastro oloroso que crece con el número de hormigas que pasen por él, y que va desapareciendo en caso contrario. El resultado final es la optimización del trabajo de todo el hormiguero en su búsqueda de comida.

En la Figura se muestra cómo las hormigas encuentran el camino más corto. En a) las hormigas deben decidir un camino; en b) se toma uno al azar; en c), dado que la velocidad de una hormiga se considera aproximadamente constante, las que llegan antes vuelven eligiendo el camino con más acumulación de feromona. En d), se circula por el camino más corto, desapareciendo por evaporación el rastro en el camino más largo.

Las hormigas y el camino más corto

La analogía a una metaheurística de optimización puede establecerse de la siguiente forma:

  • La búsqueda de alimento por las hormigas es equivalente a la exploración de soluciones factibles de un problema combinatorio.
  • La cantidad de alimento hallada en un lugar es similar al valor de la función objetivo.
  • El rastro de feromona es la memoria adaptativa del método.

Un esquema básico de la metaheurística sería el siguiente:

  1. Iniciar un rastro de feromona.
  2. Mientras no se encuentre un criterio de parada:
    1. Para cada hormiga artificial, construir una nueva solución usando el rastro actual y evaluar la solución que está siendo construida.
    2. Actualizar el rastro de feromona.

El componente más importante de un Sistema de Hormigas es la gestión de las huellas odoríferas. En su versión estándar, los rastros se usan en relación con la función objetivo para construir nuevas soluciones. Una vez se ha construido, éstos se actualizan de la siguiente forma: primero todos los rastros se debilitan para simular la evaporación del feronoma; después aquellos que corresponden a los elementos que se han empleado para la construcción, se refuerzan teniendo en cuenta la calidad de la solución.

El siguiente vídeo os puede ayudar a comprender el comportamiento de las hormigas. Espero que os guste.

Referencias:

COLORNI, A.; DORIGO, M.; MANIEZZO, V. (1991). Distributed optimization by ant colonies, in VARELA, F.J.; BOURGINE, P. (eds.) Proceedings of the First European Conference on Artificial Life (ECAL-91). The MIT Press: Cambrige, MA, 134-142.

MARTÍNEZ, F.J.; GONZÁLEZ-VIDOSA, F.; HOSPITALER, A.; ALCALÁ, J. (2011). Design of tall bridge piers by ant colony optimization. Engineering Structures, 33:2320-2329.

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. (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.

Los orígenes del PERT y del CPM

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. No obstante, al emplear las técnicas de planificación actuales, podemos acortar nuestra retrospectiva a aproximadamente medio siglo atrás en Estados Unidos. Tanto en el ámbito militar como en el civil, de manera independiente, se establecieron los fundamentos de las 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.

Si bien al principio PERT y CPM tenían algunas diferencias importantes, con el tiempo, ambas técnicas se han fusionado, de modo que hoy día se habla de estos procedimientos como PERT/CPM. El PERT supone que el tiempo para realizar cada una de las actividades es una variable aleatoria descrita por una distribución de probabilidad. El CPM, por otra parte, infiere que los tiempos de las actividades se conocen en forma determinística y se pueden variar cambiando el nivel de recursos utilizados. Ambos métodos aportaron los elementos necesarios para conformar el método del camino crítico actual, empleando el control de los tiempos de ejecución y los costes de operación, para ejecutar un proyecto en el menor tiempo y coste posible. PERT/CPM se basan en diagramas de redes capaces de identificar las interrelaciones entre las tareas y establecen el momento adecuado para su realización. Además, permiten preparar el calendario del proyecto y determinar los caminos críticos. El camino crítico es, en esencia, la ruta que representa el cuello de botella de un proyecto. La reducción del plazo total de ejecución será solo posible si se encuentra la forma de abreviar las actividades situadas en dicho camino, pues el tiempo necesario para ejecutar las actividades no críticas no incide en la duración total del proyecto. La principal diferencia entre PERT y CPM es la manera en que se realizan los estimados de tiempo. En artículos anteriores hemos explicado mediante sendos vídeos las mecánicas de cálculo de los diagramas de flechas y del propio PERT.

El origen del CPM se sitúa entre diciembre de 1956 y febrero de 1959. En aquellos momentos, la compañía norteamericana E.I. du Pont (DuPont) estaba buscando cómo utilizar uno de los primeros ordenadores comerciales, el “UNIVAC1”. Los gestores de DuPont se dieron cuenta de que planificar, estimar y programar parecía ser el mejor uso que la empresa podría darle a este ordenador. Este trabajo se asignó a Morgan Walker, de la Engineering Services Division de Du Pont, que junto con el matemático James E. Kelley, Jr, que trabajaba en Remington Rand, consiguieron poner a punto el método, con el objetivo de controlar el mantenimiento de los proyectos de plantas químicas de DuPont. A mediados de 1957, esta empresa estaba interesada en ampliar cerca de 300 fábricas, lo cual implicaba un gran número de actividades (por lo menos unas 30000) lo cual no se podía abordar con los diagramas de Gantt. El objetivo era controlar y optimizar los costos de operación de las actividades de un proyecto. En este método, cada una de las tareas tenía una duración exacta, conocida de antemano.

Ordenador digital UNIVAC1. https://museo.inf.upv.es/univac2/
William Francis Raborn (1905-1990) Militar estadounidense.

El origen de los trabajos de la técnica PERT empezaron formalmente en enero de 1957, siendo paralelo al del CPM, pero su origen fue en el ámbito militar. Se desarrolló en la Oficina de Proyectos Especiales de la Armada de los EEUU, al reconocer el almirante William. F. Raborn que se necesitaba una planificación integrada y un sistema de control fiable para el programa de misiles balísticos Polaris. Con su apoyo se estableció un equipo de investigación para desarrollar el PERT o “Program Evaluation Research Task”. Así, la Oficina de Proyectos Especiales de la Marina de los Estados Unidos de América, en colaboración con la división de Sistemas de Misiles Lockheed (fabricantes de proyectiles balísticos) y la consultora Booz, Allen & Hamilton (ingenieros consultores), se plantean un nuevo método para solucionar el problema de planificación, programación y control del proyecto de construcción de submarinos atómicos armados con proyectiles «Polaris». Este proyecto involucra la coordinación y supervisión de 250 empresas, 9,000 subcontratistas y numerosas agencias gubernamentales a lo largo de cinco años. En julio de 1958 se publica el primer informe del programa al que denominan “Program Evaluation and Review Technique”, decidiendo su aplicación en octubre del mismo año y consiguiendo un adelanto de dos años sobre los cinco previstos. D. G. Malcolm, J. H. Roseboom, C. E. Clark y W. Fazar, todos del equipo de investigación patrocinado por la Armada, fueron los autores del primer documento publicado sobre el PERT (Malcolm et al., 1959). Este método se basa en la probabilidad de la duración de las actividades. Hoy día se sigue utilizando este método, si bien, tal y como apuntan algunos autores (ver Ahuja et al., 1995), la estimación calculada por PERT suele subestimar la duración real de los proyectos.

REFERENCIAS

AHUJA, H; DOZZI, S.P.; ABOURIZK, S.M. (1995). Project management techniques in planning and controlling construction projects. 2nd edition, Wiley, N.Y.

CLARK, C.E. (1962). The PERT model for the distribution of an activity time. Operations Research, 10(3):405-406.

MALCOLM, D.G.; ROSEBOOM, J.H.; CLARK, C.E.; FAZAR, W. (1959). Application of a technique for research and development program evaluation. Operations Research, 11(5):646-669.

WEAVER, P. (2006).  A brief story of scheduling -back to the future- http://www.mosaicprojects.com.au/PDF_Papers/P042_History%20of%20Scheduing.pdf

YEPES, V.; PELLICER, E. (2008). Resources Management, in Pellicer, E. et al.: Construction Management. Construction Managers’ Library Leonardo da Vinci: PL/06/B/F/PP/174014. Ed. Warsaw University of Technology, pp. 165-188. ISBN: 83-89780-48-8.

PELLICER, E.; YEPES, V.; TEIXEIRA, J.C.; MOURA, H.P.; CATALÁ, J. (2014). Construction Management. Wiley Blackwell, 316 pp. ISBN: 978-1-118-53957-6.

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

¿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)