Francisco Santos Leal, Catedrático de la Universidad de Cantabria, ha encontrado un contraejemplo que refuta la Conjetura de Hirsch.
En matemáticas, una conjetura es una afirmación hecha sin pruebas y supone, por tanto, un reto para los investigadores, que deben demostrar que es cierta o falsa.
La Conjetura de Warren M. Hirsch (1918-2007) fue enunciada en 1957 y, desde entonces, ha sido objeto de numerosos ataques sin éxito.
Esta Conjetura tiene que ver con un algoritmo de gran impacto en el ámbito industrial, el Algoritmo del Simplex. Éste se utiliza para optimizar recursos en numerosas aplicaciones, desde planificación de turnos, producción, diseño de redes ferroviarias, aéreas o de carreteras. Por todo ello, el algoritmo del método del simplex fue elegido en el año 2000, por la revista "Computing in Science and Engineering", como uno de los diez más influyentes en el desarrollo de la ciencia y la ingeniería del siglo XX.
La Conjetura de Hirsch, como se adelantaba en el párrafo anterior, surge motivada por el análisis del método simplex de programación lineal.
En matemáticas, una conjetura es una afirmación hecha sin pruebas y supone, por tanto, un reto para los investigadores, que deben demostrar que es cierta o falsa.
La Conjetura de Warren M. Hirsch (1918-2007) fue enunciada en 1957 y, desde entonces, ha sido objeto de numerosos ataques sin éxito.
Esta Conjetura tiene que ver con un algoritmo de gran impacto en el ámbito industrial, el Algoritmo del Simplex. Éste se utiliza para optimizar recursos en numerosas aplicaciones, desde planificación de turnos, producción, diseño de redes ferroviarias, aéreas o de carreteras. Por todo ello, el algoritmo del método del simplex fue elegido en el año 2000, por la revista "Computing in Science and Engineering", como uno de los diez más influyentes en el desarrollo de la ciencia y la ingeniería del siglo XX.
La Conjetura de Hirsch, como se adelantaba en el párrafo anterior, surge motivada por el análisis del método simplex de programación lineal.
Dicha conjetura indica que el grafo arista-vértice de un politopo de n-caras en un espacio euclidiano d-dimensional tiene un diámetro no mayor que n − d. Es decir, que cualquiera dos vértices del politopo deben estar conectados el uno con el otro por una trayectoria de longitud n − d como máximo.
Un poco más en cristiano, la conjetura está relacionada con la complejidad del citado algoritmo, aspecto, sin duda, importante de cara a sus aplicaciones. La conjetura establece un límite a dicha complejidad y lo que se ha demostrado es que este límite es falso, es decir, hay casos en los que el algoritmo es más complejo que el máximo que expresa la conjetura.
Más información en el artículo de Gaussianos.com
No hay comentarios:
Publicar un comentario