La conjetura de Hirsch, Francisco Santos y la programación lineal

A veces cuando en clase explicas determinados contenidos matemáticos a los alumn@s es difícil hacerles ver cómo esas fórmulitas que escriben o esas derivadas que calculan se pueden usar en la vida real, incluso cuesta que imaginen las dificultades y el tiempo que llevó conseguir determinados resultados que ellos asumen como cierto sin más.

Así que, noticias como las que nos encontramos el pasado 26 de mayo en el periódico "Un español resuelve la llamada conjetura de Hirsch, luz en los problemas de programación lineal" pueden ayudar a hacerles ver la importancia que tienen las matemáticas en nuestro día a día.

La programación lineal (que se estudia en el sistema educativo español en las Matemáticas aplicadas a las Ciencias Sociales de 2º de Bachillerato) nació hacia 1939 con los trabajos del ruso L. V. Kantorovich (1912-1986), quien en 1975 recibió el Premio Nobel de Economía por ello. Pero su desarrollo se mantuvo en secreto durante la segunda guerra mundial. No en vano se trata de la teoría de cómo organizar de la mejor manera posible una cantidad limitada de recursos (o defensas) para obtener de ellos al mayor rendimiento (o conseguir los mínimos daños). Dicho en lenguaje técnico, la programación lineal es el problema de encontrar el máximo (o mínimo) de una función lineal en un dominio definido por desigualdades también lineales.

De la programación lineal se han dicho cosas como...

"La programación lineal se usa para asignar recursos, planificar producción o carteras de inversión, organizar horarios, formular estrategias de mercado, o militares, etc. La versatilidad e impacto económico de la programación lineal en el mundo industrial de hoy es verdaderamente increíble"

"Si hiciéramos estadísticas sobre qué problema matemático está usando más tiempo de computación en este momento en el mundo (excluyendo problemas de manejo de bases de datos, como búsqueda u ordenación) la respuesta sería probablemente programación lineal"

Durante más de 30 años el método del simplex, ideado por George Dantzig en 1947 ha sido el único método practicable para resolver grandes problemas de programación lineal. Su importancia ha sido tal que en el año 2000 fue incluido entre los 10 principales algoritmos más trascendentales del siglo XX en el "top ten" que elaboró la revista 'Computing in Science and Engineering'.

La Conjetura de Hirsch, formulada hace ya más de 50 años, y que ha resuelto el español Francisco Santos, está relacionada con la complejidad de este algoritmo. La complejidad implica, por ejemplo, más tiempo de cálculo -caro y escaso- en ordenadores. Lo que dice la conjetura a grandes rasgos es que hay un límite determinado para la complejidad del algoritmo del símplex.

En matemáticas, una conjetura es una afirmación que se supone cierta, pero que no ha sido probada ni refutada hasta la fecha. Franciso Santos lo que ha demostrado es que esto es falso encontrado un contraejemplo para dicha conjetura que supera el límite dado por Hirsh.