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)
Instituto de Ciencia y Tecnología del Hormigón (ICITECH)
Creo interesante comentar en este post los resultados que estamos obteniendo de un Proyecto de Investigación financiado por el Ministerio de Ciencia e Innovación que nuestro grupo de investigación llama HORSOST. Su nombre completo describe el contenido del trabajo que estamos desarrollando: “Diseño eficiente de estructuras con hormigones no convencionales basados en criterios sostenibles multiobjetivo mediante el empleo de técnicas de minería de datos“.
Se trata de un proyecto que empezamos en el año 2012 y que tiene prevista su finalización a finales del 2014. Nuestro grupo de investigación está formado por seis profesores y varios becarios de investigación del Instituto de Ciencia y Tecnología del Hormigón (ICITECH) de la Universidad Politécnica de Valencia. En dicho grupo me corresponde el papel de investigador principal. Espero que esta breve descripción os oriente sobre lo que estamos haciendo.
Este proyecto de investigación se encuentra relacionado con otros ya finalizados y otros en marcha, tanto de convocatorias competitivas como de convenios de transferencia tecnológica con empresas (constructoras, empresas de prefabricados, consultoras, etc.).
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:
Toda actividad necesita recursos para ejecutarse. La programación de los recursos disponibles constituye un tema crucial para lograr que la obra esté finalizada en los plazos y costes establecidos. Consiste en asociar los recursos a sus tareas respectivas y ver cómo se ensamblan en el conjunto de la obra.
La limitación de recursos en la realización de una obra provoca conflictos que pueden resolverse mediante métodos de nivelación y de asignación. Los primeros laminan el diagrama de cargas sin producir retrasos en el plazo programado. Los métodos de asignación, por otra parte, pretenden que los recursos necesarios no superen los disponibles, pero con la condición de que el retraso provocado sea el mínimo posible. Con ayuda de las diversas técnicas de redes, se habrá establecido un camino crítico y unas holguras para cada una de las actividades. La prioridad en la asignación de los recursos será mayor cuanto menor sea la holgura disponible para cada una de las actividades.
Para aclarar este tema, os dejo un Polimedia de Alberto Palomares. Espero que os guste.
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.
El tiempo disponible para realizar cada tarea lo determinan las fechas en que se produce su inicio y su terminación. La duración de una actividad puede reducirse añadiendo recursos adicionales que, desgraciadamente, incrementan su coste. Existe la posibilidad de modificar los recursos asignados a cada tarea para ajustarse a las condiciones más convenientes, según las contingencias que se presenten durante la ejecución de la obra. Estos cambios producen una aceleración o deceleración en la realización de ciertas actividades con el consiguiente aumento o disminución de su coste directo. Se produce, por tanto, una correspondencia entre el coste directo de cada actividad y el tiempo invertido en su ejecución que proporciona la posibilidad de un ajuste costes-tiempos, adaptable a las necesidades de plazo o a la inversión económica del momento.
La duración “normal” de una tarea es aquella que minimiza su coste. En ocasiones, una programación basada en la duración normal puede prolongar excesivamente el trabajo, incrementando la repercusión de los gastos generales de la empresa en la obra. Del mismo modo, es probable exceder el plazo contractual si se programa exclusivamente con duraciones normales. En ambos casos, el jefe de obra tiene la posibilidad de reducir la duración de algunas o todas las actividades para disminuir el plazo total.
Otra aproximación a la estimación de la duración de las tareas es la que propugna el método PERT, y que ya tuvimos la ocasión de explicar en un artículo anterior. No obstante todo lo anterior, y para evitar una estimación “ad hoc” de las duraciones (es decir, la que más convenga), deberíamos fijar la duración de cada tarea en función de los recursos reales que tengamos para acometerlas. Esta práctica nos llevará a estimaciones realistas y deberíamos hacerla en el momento de la confección de la Estructura de Desglose de Trabajos.
Una pequeña introducción a estos conceptos la vamos a ver en el siguiente Polimedia de Alberto Palomares. Espero que os guste.
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.
Usualmente, como primer paso de la planificación, se utiliza la técnica denominada “Estructura de Descomposición del Trabajo” (EDT) que permite dividir sucesivamente una obra en actividades con el fin de gestionarla adecuadamente. La EDT consiste en la identificación y la subdivisión jerárquica en tareas. El fraccionamiento sucesivo de la EDT se lleva a cabo en etapas que presentan un nivel de detalle cada vez mayor. El escalonamiento se visualiza en forma de diagrama de árbol; de este modo se reduce la complejidad de la obra al descomponerlo en conjuntos de actividades. Puede llegarse al nivel de descomposición que se estime más adecuado. El nivel más bajo de descomposición que define una actividad depende de factores tales como la tipología, la magnitud y la duración de la obra, la finalidad de la programación y los requisitos de control exigidos.
El propósito de una EDT es organizar y definir el alcance total aprobado del proyecto según lo declarado en la documentación vigente. Su forma jerárquica permite una fácil identificación de los elementos finales, llamados “Paquetes de Trabajo”. Se trata de un elemento exhaustivo en cuanto al alcance del proyecto, la EDT sirve como la base para la planificación del proyecto. Todo trabajo a ser hecho en el proyecto debe poder rastrear su origen en una o más entradas de la EDT.
Pero para que el concepto quede más claro, os dejo un Polimedia del profesor Alberto Palomares. Espero que os guste.
Os dejo algunos vídeos explicativos adicionales:
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.
¿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.
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)
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)
Un cronograma no puede planificarse si antes no se han secuenciado las tareas de un proyecto. Se trata de establecer el orden en que cada tarea debe ser ejecutada y qué dependencia existe entre esta tarea y el resto.
Para aclarar este tema, os dejo un Polimedia del profesor Alberto Palomares donde se explica la secuenciación. Espero que os guste.
A continuación dejo en esta entrada un par de vídeos, que en nuestra universidad denominamos “Polimedias“, donde se explica de forma breve y concisa el uso de las redes de flechas en la programación de proyectos. Es evidente que existen programas comerciales que permiten automatizar y gestionar de forma eficiente los proyectos. Estos vídeos sólo pretenden recordar y difundir los aspectos básicos sobre los que se fundamentan estos programas. Espero que sea de interés.
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.
