Estudio del problema de la ordenación lineal y asociación a digrafos

Abstract

[ES] En el Capítulo 1 de este documento introducimos conceptos básicos de la optimización, en particular, de la optimización combinatoria. A continuación, desarrollamos algunos de los ejemplos más relevantes de este tipo de problemas, para, a partir del Capítulo 2, centrarnos en el problema de la ordenación lineal ("Linear Ordering Problem" - LOP). En primer lugar desarrollamos y demostramos algunas de sus propiedades más relevantes. En segundo lugar, nombramos algunas de sus aplicaciones más comunes en el mundo actual, centrándonos en la aplicación económica. En el Capítulo 3, se introduce el concepto de "Landscape" del LOP, y para ello, se definen los dos entornos o vecindarios más utilizados para este problema. Se analizarán las características de los "landscapes" bajo estos dos vecindarios, relacionándolas con alguna de las familias de números más conocidas en el campo de la Matemática Discreta. En el Capítulo 4, introducimos conceptos básicos de la Teoría de Grafos y describimos una novedosa asociación entre nuestro problema y los digrafos. Además, formulamos y demostramos un teorema que relaciona los caminos hamiltonianos del digrafo asociado con los óptimos locales de nuestro problema para uno de los vecindarios descritos anteriormente. En el Capítulo 5, valiéndonos de los resultados obtenidos en el capítulo anterior, proponemos un algoritmo de resolución para este problema que aplicaremos a un caso real. La asociación entre el problema LOP y los grafos dirigidos no ha sido realizada en ningún trabajo anterior de la literatura, y por tanto, supone una propuesta completamente nueva. El algoritmo desarrollado en este trabajo es, por tanto, un trabajo original y nunca antes planteado. En el Capítulo 6, presentamos las conclusiones y, a partir de ellas, exponemos el trabajo futuro que puede desarrollarse tomando como base este proyecto.