Entradas etiquetadas como ‘Dantzig’

¿Qué tienen en común Francisco Santos y Benoit Mandelbrot?

 

Conjunto de Mandelbrot

En una primera aproximación se deduce fácilmente que los dos son matemáticos. Pero matemáticos hay muchos, afortunadamente, claro. Si uno analiza con más detenimiento la carrera de estos dos científicos, descubrirá que mientras Mandelbrot es asociado, principalmente, a unas estructuras matemáticas y maravillosas, conocidas como fractales, el nombre de Francisco Santos aparece muchas veces ligado a unas estructuras más rígidas y menos fotogénicas  conocidas como politopos.

Politopo

Ahora bien, como se dice en mi pueblo, con lo guapo no se come (que se lo pregunten a Naomi Campbell…) y aunque los politopos no sean tan espectaculares visualmente como los fractales, lo que no se les puede negar es que son mu apañaos.

¿Para qué puede servir estudiar politopos? Pues, por ejemplo, para poder acotar el tiempo máximo que necesitaríamos para resolver un problema de Programación Lineal usando el método del Simplex.

Ea, ya estamos, ¿qué es Programación Lineal, hija? ¿Cuál es el método del Simplex? 

En pocas palabras, la Programación Lineal se preocupa de cómo gestionar de la forma óptima una cantidad limitada de recursos para obtener de ellos al mayor rendimiento o minimizar los efectos adversos.

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.

 

Eugene Lawler

 

Sí, de esto sabe poco nuestro gobierno…

Fue el matemático ruso Leonid Kantoróvich, alrededor de 1939, el pionero en estudios de esta disciplina, estudios que le sirvieron para conseguir el Premio Nobel de Economía en 1975 (y es que como a los matemáticos no nos pueden dar el Nobel, tenemos que conseguirlo por otras vías, como también ha pasado con el último Nobel en la misma categoría…), aunque eso sí, tuvieron mucho cuidado en no ventilar los avances obtenido durante la Segunda Guerra Mundial, para evitar el uso por parte del enemigo de éstos en pro de optimizar sus recursos bélicos. Pero… ¡YA ESTÁN PUBLICADOS, DE GUINDOS!

Pues bien, unos años más tarde, un colega estadounidense, George Dantzig, que trabajaba para el ejército estadounidense, publicó el método Simplex para la resolución eficiente de problemas de Programación Lineal. Durante mucho tiempo ha sido el único método conocido para abordar grandes problemas de este tipo. De hecho, en el año 2000, en la revista Computing in Science and Engineering, en un sección dedicada a Lo mejor del siglo XX,  se publicó una lista con un  Top 10  de algoritmos de dicho siglo; es decir, los algoritmos más influyentes en el desarrollo de la ciencia y la ingeniería en ese período,  en la que el Método del Simplex de Dantzig aparece en segundo lugar (están en orden cronológico).

¿Qué tiene que ver todo esto con un politopo? En pocas palabras, la pega del método del simplex está en que no se puede, a priori, decidir cuánto tardará como máximo en encontrar la solución óptima. Podemos pensar que las soluciones posibles (con los recursos y limitaciones que tenemos) están representadas por lo vértices del politopo. El método empieza en uno de ellos, elegido arbitrariamente y se va moviendo por las aristas, visitando uno a uno los vértices del politopo hasta llegar al que representa a la solución óptima, ¿me explico? Pues bien, para saber cuál será  tiempo máximo necesario para llegar a la solución óptima, la mejor, del problema, habría que conocer cuál es la máxima distancia posible entre dos vértices del politopo, si medimos la distancia contando el número de aristas del poiltopo que tenemos que recorrer para llegar de uno a otro. Esto, esa máxima distancia posible, se conoce como diámetro.

En 1957, Warren M. Hirsch escribió una carta al mismo Dantzig en el que conjeturaba (es decir, afirmaba sin que lo hubiese demostrado) que ese diámetro estaba acotado, no podía ser mayor, que el número de restricciones  del problema menos la dimensión del politopo. No vamos a entrar en mucho más detalles sobre este particular para no espantar al lector menos familiarizado con estos temas (os recomiendo esta entrada de Gaussianos para saber más) , pero lo sorprendente de esta historia, es que esta conjetura de Hirsch estuvo más de 50 años sin ser demostrada o refutada, a pesar del esfuerzo y dedicación de muchos matemáticos de reconocido prestigio sin saber que:

The answer, my friend, is blowing in the wind

Bob Dylan

 

Efectivamente, Francisco Santos Leal (Paco para sus amigos, muchos) es profesor de la Universidad de Cantabria y volaba desde Bilbao camino de Paris leyendo On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra (de Fogel et al.) cuando se le ocurrió cómo construir el contraejemplo que desmontaría la famosa conjetura de Hirsch. Afortunadamente, anotó las ideas en un cuaderno que llevaba y no en el margen de la citada revista porque la dejó olvidada en el avión y se hubiese repetido la historia de Fermat…

En Mayo de 2010, la noticia de que Paco había refutado la conjetura de Hirsch no solo nos llenó de orgullo y satisfacción a todos sus colegas y amigos, sino que fue recogida en numerosos medios de comunicación que se lanzaron a conseguir una entrevista con Paco. De entre todo lo publicado alrededor de este hecho, me resulta especialmente emotivo este artículo publicado en Lastampa el pasado 27 de Abril de 2011, en el que el profesor Bernd Sturmfels reconoce honestamente que Paco resolvió con brillantez el problema que él abandonó después de un año por encontrarlo demasiado complicado.

Ahora sí, volviendo al título de esta entrada, ¿por qué me dio esta mañana por relacionar a Francisco Santos con Benoit Mandelbrot?

Pues porque la semana pasada se conoció la noticia de que nuestro profesor e investigador cántabro, igual que el papá de la Geometría Fractal, acaba de ser galardonado con el Premio Humboldt de Investigación por su labor docente y científica. La importancia y relevancia de este premio, entre otras cosas, queda patente en el hecho de que entre sus galardonados anteriormente, podemos encontrar casi 50 premios Nobel… ¿Quién sabe? ¿No?

Hoy tenemos motivo para sentirnos orgullosos, pero orgullosos de verdad, porque mientras nuestro Ministro de Educación se preocupa de impregnar la educación de nuestros hijos con religión y otras opciones políticas e ideológicas, desde la Universidad Libre de Berlín, uno de los más destacados investigadores a nivel mundial, Günter M. Ziegler, dice públicamente que la Fundación Humboldt trae a a Berlín, desde España, a una estrella de la Geometría que  acelerará la investigación en la Universidad Libre.

Enhorabuena, Paco, y ¡gracias! Y quién sabe… también uno de los galardonados este año con el Nobel de Física, Serge Haroche, tuvo su Premio Humboldt en 1992 y la Física también te gusta 😉

P.S.1:  Por cierto, si lo que ha llevado a Paco Santos a las portadas de los medios ha sido su refutación de la conjetura de Hirsch, dejadme que presuma de que yo también fui refutada por el Dr. Santos. Sí, tengo el honor de llevar en mi tesis doctoral un contraejemplo que se le ocurrió hace algunos años, 15, durante un congreso en Barcelona,  al día siguiente de la cena del congreso, por cierto. Fue un banquete el que nos ofrecieron tan espectacular como delicioso, pero excesivo. Como consecuencia, nadie pudo dormir aquella noche, tratando de hacer la digestión. Los había que paseaban por los pasillos, otros leían, matemáticas y/o ficción, otros veían la tele…pero nuestro desvelado de Santander encontró un contraejemplo que aparecería en mi tesis Geometría Computacional en Superficies y posteriormente en nuestro libro.

P.S.2: Cuando, hace un año,  le dije que escribiría sobre él en mi blog personal, me pidió que os rogara que cada vez que volarais en Air France, miraseis en los bolsillos de los asientos por si encontráis un ejemplar del volumen 42 de Discrete and Computational Geometry, porque aunque no esté descrito el contraejemplo en el margen, le gustaría tenerla de recuerdo.