Estudio del algoritmo proyectivo de Karmarkar y sus aplicaciones en la ingeniería

Abstract

El estudio de la complejidad de problemas relativos a algoritmos de programación lineal es uno de los objetivos de estudio del presente trabajo. En particular, se estudia la resolubilidad de problemas con algoritmos de complejidad polinomial, donde el tiempo de ejecución de un algoritmo depende en general del tamaño del problema a ser resuelto. En este trabajo se considera el tiempo de ejecución T(n) como el peor caso de tiempo de ejecución de algún algoritmo sobre todos los problemas de tamaño n. Un algoritmo que sirve para encontrar una solución factible de un sistema de inecuaciones de números enteros de la forma Ax b es el llamado algoritmo del elipsoide, el cual es iterativo y converge en un tiempo de ejecución polinomial. Se estudia el algoritmo de Karmarkar y una variante de este, la principal motivación es resolver de manera rápida problemas de programación lineal donde el método del simplex tenga un comportamiento exponencial, la variante del método de Karmarkar es un algoritmo más sencillo y permite disminuir el volumen de los cálculos a realizar en cada iteración. Finalmente se exponen aplicaciones relativas al campo de la ingeniería, las cuales pueden ser resueltas empleando programación lineal. La primera aplicación está referida a la obtención del peso mínimo de una estructura aporticada, este es un problema de interés en la ingeniería estructural; la segunda aplicación está relacionada a la distribución de dotación de agua de cultivo, este último es un problema de interés tanto en la ingeniería hidráulica como agrícola.