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)
¿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.
Algunas de las críticas más importantes que se hacen a la planificación de las obras es aquella que dice que es imposible saber a ciencia cierta cuanto van a durar los trabajos y las tareas que componen el proyecto que vamos a ejecutar. Parte de razón se tiene, puesto que las inclemencias meteorológicas, los retrasos en la entrega de materiales, la motivación de los trabajadores, el estado de conservación y mantenimiento de la maquinaria y otros imprevistos hacen que nuestras previsiones se arruinen incluso antes de empezar nuestra obra.
Entonces, ¿es imposible planificar una obra? Definitivamente, no. Afortunadamente, existen técnicas que, bien empleadas, suponen una ayuda inestimable en la labor de planificar y controlar nuestras obras. Entre ellas se encuentra el PERT, acrónimo de “Program Evaluation and Review Technique”. Se trata de una técnica que ayuda al gestor en su toma de decisiones y que permite introducir la probabilidad en los cálculos de los plazos de terminación de los proyectos. Para los que estéis interesados podéis ver en este artículo cuáles fueron los orígenes del PERT.
A continuación os dejo un vídeo donde, de forma muy resumida, se explican los conceptos básicos en los que se basa la técnica. Espero que os guste.
Referencias:
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.; 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.
Me gustaría compartir con vosotros una herramienta de gran interés en la docencia en red. Se trata de “pequeñas píldoras” de conocimiento que llamamos en la Universidad Politécnica de Valencia como “objetos de aprendizaje”. Nuestros alumnos, o bien cualquier persona en cualquier parte del mundo puede acceder a explicaciones sobre conceptos muy concretos. Os paso como ejemplo un Polimedia sobre el método PERT.
