Models and Algorithms for Deterministic and Stochastic Optimization Problems

Abstract

La optimización (también llamada programación maten ática (PM)) es la rama de las matemáticas que trata sobre encontrar aquella solución que proporcione el mayor beneficio para un problema dado, dicho de otro modo, trata de buscar, de entre todas las posibles soluciones a un problema, aquella que minimice una función dada (o equivalentemente, lamaximice, n¿otese quemax{f(x)}=min{¿f(x)}), generalmente se trata de una función real (f : Rn ¿ R) y se demomina funci¿on objetivo. El conjunto de soluciones factibles vendrá definido mediante ecuaciones matemáticas, llamadas restricciones, que las soluciones deben cumplir. Así pues, dado un problema cualquiera, se debe realizar un modelo matemático consistente en una serie de restricciones y una función objetivo a minimizar, para después resolverlo mediante alguno de los algoritmos proporcionados por el estado del arte. El modelado de un problema dado es de hecho un arte en sí mismo. Se trata de abstraer aquellos aspectos innecesarios, superfluos, y al mismo tiempo representar la realidad lo más fielmente posible, y ello teniendo en cuenta que, dependiendo del enfoque elegido, la resolución del modelo puede no ser viable en la práctica con los recursos computacionales de que dispone la humanidad en su actual estadio de desarrollo. Aspectos que pueden afectar drásticamente a la facilidad de resolución del modelo son: ¿ El tipo de modelo (fundamentalmente, si es lineal o no-lineal) ¿ Las variables que entran en juego (el número de variables, si son enteras, continuas o binarias) ¿ La elección de las restricciones adecuadas. En el trabajo de modelado puede jugar un papel fundamental la búsqueda de nuevas restricciones que permitan hacer el modelo más robusto desde el punto de vista matemático, o dicho de otro modo que cumpla ciertas condiciones que permitan a los algoritmos encontrar la solución más fácilmente. Dentro de la optimización matemática, en esta tesis vamos a transitar por dos ¿áreas que ocupan un lugar destacado, la Programación Lineal y la Programación Estocástica. La Programación Lineal trata de aquellos modelos cuyas restricciones y función objetivo son lineales. En general los modelos lineales se pueden resolver en menos tiempo que los no-lineales, especialmente si no tienen variables enteras, o tienen pocas, y cumplen ciertas condiciones. En esta tesis se aplica la programación lineal a los problemas de elusión de conflictos en el tráfico aéreo, mediante un enfoque distinto al habitual. El modo de tratar estos problemas hasta ahora se basaba principalmente en modelos no-lineales, lo que debido a las limitaciones computacionales mencionadas arriba, no permitía enfrentarse a casos en los que entren en juego muchos aviones o considerar un espacio aéreo amplio (generalmente los modelos tratan 2 o 3 aviones en un espacio limitado). El nuevo enfoque aplicado en esta tesis, en cambio, permite aplicar la programación lineal, lo cual a su vez facilita considerar el plan de vuelo de todos los aviones presentes en un espacio aéreo lo suficientemente amplio, y resolver los posibles conflictos aplicando cambios de velocidad o de altura, e incluso cambiando a rutas alternativas si ello fuera posible. Por otro lado nos adentramos en el ¿área de la Programación Estocástica. En muchos problemas reales la incertidumbre juega un papel importante y que por tanto debería tenerse en cuenta en el modelo resultante. Sin embargo la incertidumbre no se deja atrapar tan fácilmente, y el como modelarla es aun un problema que dista de estar cerrado, si bien se ha avanzado mucho y existe un enfoque ampliamente aceptado y para el que se han podido desarrollar varios algoritmos que explotan eficientemente sus características particulares.