{"id":131798,"date":"2010-05-23T09:30:01","date_gmt":"2010-05-23T08:30:01","guid":{"rendered":"http:\/\/www.madrimasd.org\/blogs\/matematicas\/?p=131798"},"modified":"2010-05-23T10:05:32","modified_gmt":"2010-05-23T09:05:32","slug":"la-conjetura-de-hirsch-refutada-por-francisco-santos","status":"publish","type":"post","link":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798","title":{"rendered":"La Conjetura de Hirsch, refutada por Francisco Santos"},"content":{"rendered":"

Nos hacemos eco en Matem\u00e1ticas y sus fronteras de un importante resultado obtenido por nuestro compa\u00f1ero Francisco Santos, Catedr\u00e1tico de la Universidad de Cantabria.<\/p>\n

\"preview26\"<\/p>\n

La Programaci\u00f3n Lineal y el m\u00e9todo del s\u00edmplex<\/span><\/p>\n

En el a\u00f1o 2000 la revista Computing in Science and Engineering<\/em> pidi\u00f3 a Jack Dongarra y a Francis Sullivan que eligieran los \u00ab10 algoritmos del Siglo XX\u00bb; es decir, los algoritmos m\u00e1s influyentes en el desarrollo de la ciencia y la ingenier\u00eda del pasado siglo. Uno de los diez elegidos fue el m\u00e9todo del s\u00edmplex en programaci\u00f3n lineal.<\/p>\n

La programaci\u00f3n lineal naci\u00f3 hacia 1939 con los trabajos del ruso L. V. Kantorovich (1912-1986), quien en 1975 recibi\u00f3 el Premio Nobel de Econom\u00eda por ello. Pero su desarrollo se mantuvo en secreto durante la segunda guerra mundial. No en vano se trata de la teor\u00eda de c\u00f3mo organizar de la mejor manera posible una cantidad limitada de recursos (o defensas) para obtener de ellos al mayor rendimiento (o conseguir los m\u00ednimos da\u00f1os).<\/p>\n

\"Kantorovich_6\"<\/p>\n

L. V. Kantorovich<\/p>\n

\n

Dicho en lenguaje t\u00e9cnico, la programaci\u00f3n lineal es el problema de encontrar el m\u00e1ximo (o m\u00ednimo) de una funci\u00f3n lineal en un dominio definido por desigualdades tambi\u00e9n lineales. Su relevancia queda expresada en la rese\u00f1a que SIAM News <\/em>public\u00f3 a prop\u00f3sito del 80 cumplea\u00f1os de George Dantzig, mediante una cita de Eugene Lawler y otra de Laszlo Lovasz, actual presidente de la Uni\u00f3n Matem\u00e1tica Internacional. El primero dijo que la programaci\u00f3n lineal \u00abse usa para asignar recursos, planificar producci\u00f3n o carteras de inversi\u00f3n, organizar horarios, formular estrategias de mercado, o militares, etc. La versatilidad e impacto econ\u00f3mico de la programaci\u00f3n lineal en el mundo industrial de hoy es verdaderamente incre\u00edble\u00bb. El segundo: \u00abSi hici\u00e9ramos estad\u00edsticas sobre qu\u00e9 problema matem\u00e1tico est\u00e1 usando m\u00e1s tiempo de computaci\u00f3n en este momento en el mundo (excluyendo problemas de manejo de bases de datos, como b\u00fasqueda u ordenaci\u00f3n) la respuesta ser\u00eda probablemente programaci\u00f3n lineal\u00bb.<\/p>\n

\"Dantzig_George\"<\/p>\n

G. Dantzig<\/p>\n

El m\u00e9todo del s\u00edmplex fue publicado en 1947 por George Dantzig (1914-2005), que por entonces trabajaba en la Oficina de Control Estad\u00edstico del ej\u00e9rcito estadounidense. Durante m\u00e1s de 30 a\u00f1os el m\u00e9todo del s\u00edmplex fue el \u00fanico m\u00e9todo practicable para resolver grandes problemas de programaci\u00f3n lineal y, sin embargo, a\u00fan a fecha de hoy no sabemos si es un algoritmo polin\u00f3mico, en el sentido de la teor\u00eda de la complejidad. Es decir, no sabemos si un problema de programaci\u00f3n lineal con un n\u00famero d<\/em> de variables y un n\u00famero n<\/em> de restricciones puede ser resuelto mediante el m\u00e9todo del s\u00edmplex en un tiempo que dependa de manera polin\u00f3mica de los par\u00e1metros n<\/em> y d.<\/em><\/p>\n

La raz\u00f3n fundamental de ese desconocimiento es que no sabemos, dada una regi\u00f3n poli\u00e9drica de dimensi\u00f3n d <\/em>y definida por n<\/em> desigualdades lineales, si su grafo tiene di\u00e1metro polin\u00f3mico en los par\u00e1metros n<\/em> y d<\/em>. El m\u00e9todo del s\u00edmplex funciona en dos etapas: primero busca un v\u00e9rtice arbitrario del dominio definido por las restricciones y despu\u00e9s va movi\u00e9ndose de un v\u00e9rtice a otro en el que el funcional a maximizar aumenta, recorriendo en cada paso una arista del politopo. Hacer esto \u00faltimo computacionalmente es relativamente sencillo. El m\u00e9todo del s\u00edmplex tiene cierta libertad a la hora de elegir a qu\u00e9 v\u00e9rtice vecino del actual dirigirse y el criterio utilizado para la elecci\u00f3n de uno u otro se llama la \u00abregla de pivote\u00bb. Pero el n\u00famero de veces que hay que hacerlo ser\u00e1, como m\u00ednimo, la distancia del v\u00e9rtice original al v\u00e9rtice \u00f3ptimo en el grafo del poliedro.\u00a0 Es decir, para poder acotar la complejidad del m\u00e9todo del s\u00edmplex es necesario ser capaces primero de acotar el di\u00e1metro de los grafos de poliedros, aunque el rec\u00edproco no es cierto; incluso si supi\u00e9ramos que el di\u00e1metro es peque\u00f1o, quedar\u00eda el problema de c\u00f3mo hacer que el m\u00e9todo del s\u00edmplex encuentre un camino corto.<\/p>\n

Hay que decir que, aunque se conocen otros algoritmos para programaci\u00f3n lineal que s\u00ed son polin\u00f3micos en el modelo bit de complejidad (m\u00e1quina de Turing), una \u00abregla de pivote\u00bb polin\u00f3mica para el m\u00e9todo de s\u00edmplex probar\u00eda que el mismo es fuertemente polin\u00f3mico<\/em>, es decir, polin\u00f3mico tanto en el modelo de bit como en el modelo real. La pregunta sobre la existencia de un algoritmo polin\u00f3mico para programaci\u00f3n lineal en el modelo real fue incluida en el a\u00f1o 2000 por Steven Smale en su lista de Problemas matem\u00e1ticos para el siglo que viene<\/em>.<\/p>\n

<\/span><\/p>\n

La conjetura de Hirsch<\/span><\/p>\n

La conjetura de Warren M. Hirsch (1918-2007), en una carta dirigida a Dantzig en 1957, afirma que el di\u00e1metro (combinatorio) del grafo de un poliedro de dimensi\u00f3n d<\/em> y\u00a0 definido por n<\/em> desigualdades no puede ser nunca mayor que n-d<\/em>.<\/p>\n

\n

\"hirshc\"<\/p>\n

W. M. Hirsch<\/p>\n

Dantzig la incluy\u00f3 en su libro \u00abLinear programming and extensions’<\/em>‘ (1963), considerado la \u00abBiblia\u00bb de la programaci\u00f3n lineal. Desde entonces ha atra\u00eddo la atenci\u00f3n de matem\u00e1ticos tanto puros como aplicados. Sin embargo, m\u00e1s de 50 a\u00f1os despu\u00e9s nuestro conocimiento sobre el problema sigue siendo humillantemente escaso: no se conoce ninguna cota superior polin\u00f3mica para el di\u00e1metro que se conjetura lineal!<\/p>\n

\"photoSmall\"<\/p>\n

V. Klee<\/p>\n

En 1967, Klee y Walkup demostraron la conjetura para n <\/em>\u2264 d<\/em>+5 y, hace apenas dos a\u00f1os, el caso n <\/em>= d<\/em>+6 ha sido verificado por Bremmer y Schewe\u2026 La demostraci\u00f3n usa el llamado \u00abTeorema de los d<\/em> pasos\u00bb, que dice que si la conjetura de Hirsch es cierta para politopos de dimensi\u00f3n k <\/em>con 2k<\/em> caras, para un cierto valor de k<\/em>, entonces tambi\u00e9n es cierta para politopos de dimensi\u00f3n n<\/em>–k<\/em> con n<\/em> caras, sea quien sea n<\/em>. N\u00f3tese que el teorema de los d <\/em> pasos no afirma que la conjetura de Hirsch sea cierta, s\u00f3lo que el caso general es equivalente al caso particular n = 2d<\/em>, en cuyo caso el n\u00famero de pasos conjeturado es d<\/em> (de ah\u00ed el nombre).<\/p>\n

Y esta era la situaci\u00f3n hasta\u2026 el 10 de Mayo de 2010. Ese d\u00eda, el catedr\u00e1tico de Geometr\u00eda de la Universidad de Cantabria, Francisco Santos Leal,\u00a0 envi\u00f3 el siguiente resumen de su pr\u00f3xima conferencia al congreso The Mathematics of Klee and Gr\u00fcnbaum: 100 years in Seattle<\/em>, anunciando que hab\u00eda encontrado un contraejemplo a la Conjetura de Hirsch:<\/p>\n

\u00abHe estado en Seattle s\u00f3lo una vez, en enero de 2002, con motivo de una charla en la Universidad de Washington. Aunque Victor Klee ya estaba jubilado –ten\u00eda 76 a\u00f1os– vino al Departamento para charlar conmigo. Tuvimos una amena conversaci\u00f3n en el transcurso de la cual me pregunt\u00f3: \u00bfPor qu\u00e9 no intentas refutar la Conjetura de Hirsch?<\/em><\/p>\n

M\u00e1s tarde descubr\u00ed que Klee formulaba la misma pregunta a mucha gente, incluyendo a todos sus alumnos, pero la pregunta y la forma en que me la plante\u00f3 me hizo sentir especial en ese momento.\u00a0 Esta charla es la respuesta a esa pregunta. Describir\u00e9 la construcci\u00f3n de una politopo de dimensi\u00f3n 43 con 86 facetas y di\u00e1metro mayor que 43. La prueba se basa en una generalizaci\u00f3n del teorema de los <\/em>d-pasos de Klee y Walkup.\u00bb<\/em><\/p>\n

\u00abI have been in Seattle only once, in January 2002, when I visited to give a colloquium talk at UW. Although Victor Klee was already retired–he was 76 years old–he came to the Department of Mathematics to talk to me. We had a nice conversation during which he asked \u00abWhy don’t you try to disprove the Hirsch Conjecture?\u00bb<\/p>\n

I have later found out that he asked the same question to many people, including all his students, but the question and the way it was posed made me feel special at that time. This talk is the answer to that question. I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43. The proof is based on a generalization of the d-step theorem of Klee and Walkup.\u00bb<\/p>\n

Ese mismo d\u00eda, el insigne experto en combinatoria Gil Kalai public\u00f3 la noticia en su muy visitado blog ( http:\/\/gilkalai.wordpress.com ) y la entrada de \u00abHirsch conjecture\u00bb en la Wikipedia (http:\/\/en.wikipedia.org\/wiki\/Hirsch_conjecture<\/a>) fue actualizada para hacerse eco de ella.<\/p>\n

Como se dice en el resumen de la charla de F. Santos, su contraejemplo a la conjetura de Hirsch tiene dos ingredientes: una generalizaci\u00f3n del teorema de los d<\/em> pasos a unos politopos en forma de huso, y la construcci\u00f3n expl\u00edcita de cierto politopo de dimensi\u00f3n 5 y 48 facetas, usando en cierto modo para ello la bien conocida fibraci\u00f3n de Hopf<\/em> de la 3-esfera. La conjunci\u00f3n de ambas cosas demuestra la existencia de un politopo de dimensi\u00f3n 43, con 86 facetas y en el que el di\u00e1metro es mayor que 43!!<\/p>\n

La correcci\u00f3n del contrajemplo de Santos ha sido verficada por un grupo reducido de expertos colegas que incluye al propio Kalai. Parte del contraejemplo ha sido tambi\u00e9n comprobado por ordenador.<\/p>\n

\u00bfY ahora?<\/span><\/p>\n

<\/span><\/p>\n

En 1987 Klee y Kleinschmidt escribieron un survey sobre las conjeturas de Hirsch y de los d<\/em> pasos. Dicen en \u00e9l: \u00abEncontar un contrajemplo apenas constituir\u00e1 un peque\u00f1o primer paso en la l\u00ednea de investigaci\u00f3n relacionada con la conjetura\u00bb. <\/em>(\u00abFinding a counterexample will be merely a small first step in the line of investigation related to the conjecture\u00bb.) <\/em><\/p>\n

Aunque hayan sido necesarios\u00a0 para dar ese \u00abpeque\u00f1o paso\u00bb, 53 a\u00f1os desde el enunciado de la conjetura y 23 desde que se escribi\u00f3 esta frase,\u00a0 Santos subscribe\u00a0 totalmente estas palabras. Su contraejemplo, mediante construcciones cl\u00e1sicas de productos y pegados, se puede convertir, se\u00f1ala Santos,\u00a0 en una familia inifinita de contraejemplos a la conjetura de Hirsch en la que el di\u00e1metro de los poliedros construidos crece, b\u00e1sicamente, como 1.03 n<\/em>. Es decir, violan la conjetura, que era n-d,<\/em> pero sus di\u00e1metros no dejan de ser lineales y no dicen mucho sobre el problema de fondo. Quiz\u00e1, por tanto, seg\u00fan Santos,\u00a0 lo m\u00e1s significativo no es el contraejemplo en s\u00ed sino el Teorema generalizado de los d pasos<\/em> que ha tenido que desarrollar, y que puede abrir una nueva l\u00ednea de ataque al problema de encontrar cotas razonables al di\u00e1metro de un politopo y, en definitiva, a la complejidad de la programaci\u00f3n lineal.<\/p>\n

La versi\u00f3n detallada del contraejemplo de Santos est\u00e1 a\u00fan siendo redactada y ser\u00e1 enviada a una de las m\u00e1s prestigiosas revistas de investigaci\u00f3n matem\u00e1tica,\u00a0 donde aparecer\u00e1, esperamos,\u00a0 tras un riguroso proceso de revisi\u00f3n. Pero la comunidad matem\u00e1tica espa\u00f1ola podr\u00e1 beneficiarse de un avance de ese resultado en un pr\u00f3ximo n\u00famero de\u00a0 La Gaceta de la Real Sociedad Matem\u00e1tica Espa\u00f1ola. Ha sido, precisamente, extrayendo ideas y p\u00e1rrafos de un borrador inicial del\u00a0 manuscrito que Santos publicar\u00e1 alli, lo que nos ha permitido elaborar este apunte del blog Matem\u00e1ticas y sus fronteras.<\/p>\n

\u00a1Enhorabuena, Paco!<\/p>\n

___________________________<\/p>\n

Tom\u00e1s Recio<\/strong>, Universidad de Cantabria.<\/p>\n","protected":false},"excerpt":{"rendered":"

Nos hacemos eco en Matem\u00e1ticas y sus fronteras de un importante resultado obtenido por nuestro compa\u00f1ero Francisco Santos, Catedr\u00e1tico de la Universidad de Cantabria. La Programaci\u00f3n Lineal y el m\u00e9todo del s\u00edmplex En el a\u00f1o 2000 la revista Computing in Science and Engineering pidi\u00f3 a Jack Dongarra y a Francis Sullivan que eligieran los \u00ab10 algoritmos del Siglo XX\u00bb; es decir, los algoritmos m\u00e1s influyentes en el desarrollo de la ciencia y la ingenier\u00eda del pasado siglo. Uno de los diez elegidos fue el m\u00e9todo del s\u00edmplex en programaci\u00f3n lineal. La programaci\u00f3n lineal naci\u00f3 hacia 1939 con los trabajos del\u2026<\/p>\n","protected":false},"author":49,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0},"categories":[1],"tags":[],"blocksy_meta":{"styles_descriptor":{"styles":{"desktop":"","tablet":"","mobile":""},"google_fonts":[],"version":4}},"aioseo_notices":[],"yoast_head":"\nLa Conjetura de Hirsch, refutada por Francisco Santos - Matem\u00e1ticas y sus fronteras<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798\" \/>\n<meta property=\"og:locale\" content=\"es_ES\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"La Conjetura de Hirsch, refutada por Francisco Santos - Matem\u00e1ticas y sus fronteras\" \/>\n<meta property=\"og:description\" content=\"Nos hacemos eco en Matem\u00e1ticas y sus fronteras de un importante resultado obtenido por nuestro compa\u00f1ero Francisco Santos, Catedr\u00e1tico de la Universidad de Cantabria. La Programaci\u00f3n Lineal y el m\u00e9todo del s\u00edmplex En el a\u00f1o 2000 la revista Computing in Science and Engineering pidi\u00f3 a Jack Dongarra y a Francis Sullivan que eligieran los \u00ab10 algoritmos del Siglo XX\u00bb; es decir, los algoritmos m\u00e1s influyentes en el desarrollo de la ciencia y la ingenier\u00eda del pasado siglo. Uno de los diez elegidos fue el m\u00e9todo del s\u00edmplex en programaci\u00f3n lineal. La programaci\u00f3n lineal naci\u00f3 hacia 1939 con los trabajos del\u2026\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798\" \/>\n<meta property=\"og:site_name\" content=\"Matem\u00e1ticas y sus fronteras\" \/>\n<meta property=\"article:published_time\" content=\"2010-05-23T08:30:01+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2010-05-23T09:05:32+00:00\" \/>\n<meta property=\"og:image\" content=\"http:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/05\/preview261-300x225.jpg\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Escrito por\" \/>\n\t<meta name=\"twitter:data1\" content=\"Matem\u00e1ticas y sus fronteras\" \/>\n\t<meta name=\"twitter:label2\" content=\"Tiempo de lectura\" \/>\n\t<meta name=\"twitter:data2\" content=\"10 minutos\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#website\",\"url\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/\",\"name\":\"Matem\u00e1ticas y sus fronteras\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"es\"},{\"@type\":\"ImageObject\",\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#primaryimage\",\"inLanguage\":\"es\",\"url\":\"http:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/05\/preview261-300x225.jpg\",\"contentUrl\":\"http:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/05\/preview261-300x225.jpg\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#webpage\",\"url\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798\",\"name\":\"La Conjetura de Hirsch, refutada por Francisco Santos - Matem\u00e1ticas y sus fronteras\",\"isPartOf\":{\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#primaryimage\"},\"datePublished\":\"2010-05-23T08:30:01+00:00\",\"dateModified\":\"2010-05-23T09:05:32+00:00\",\"author\":{\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#\/schema\/person\/15722bca1b77eece37f4c192bd1b5230\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#breadcrumb\"},\"inLanguage\":\"es\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Portada\",\"item\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"La Conjetura de Hirsch, refutada por Francisco Santos\"}]},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#\/schema\/person\/15722bca1b77eece37f4c192bd1b5230\",\"name\":\"Matem\u00e1ticas y sus fronteras\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#personlogo\",\"inLanguage\":\"es\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/50eb6cc40d97cb9ad268a3471c7e2492?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/50eb6cc40d97cb9ad268a3471c7e2492?s=96&d=mm&r=g\",\"caption\":\"Matem\u00e1ticas y sus fronteras\"},\"description\":\"Manuel de Le\u00f3n es Profesor de Investigaci\u00f3n del CSIC, acad\u00e9mico de la Real Academia de Ciencias y su Tesorero, fundador del ICMAT (CSIC), acad\u00e9mico de la Real Academia Canaria de Ciencias y de la Real Academia Galega de Ciencias. Es adem\u00e1s Director del programa Estalmat.\",\"url\":\"https:\/\/www.madrimasd.org\/blogs\/matematicas\/author\/matematicas\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"La Conjetura de Hirsch, refutada por Francisco Santos - Matem\u00e1ticas y sus fronteras","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798","og_locale":"es_ES","og_type":"article","og_title":"La Conjetura de Hirsch, refutada por Francisco Santos - Matem\u00e1ticas y sus fronteras","og_description":"Nos hacemos eco en Matem\u00e1ticas y sus fronteras de un importante resultado obtenido por nuestro compa\u00f1ero Francisco Santos, Catedr\u00e1tico de la Universidad de Cantabria. La Programaci\u00f3n Lineal y el m\u00e9todo del s\u00edmplex En el a\u00f1o 2000 la revista Computing in Science and Engineering pidi\u00f3 a Jack Dongarra y a Francis Sullivan que eligieran los \u00ab10 algoritmos del Siglo XX\u00bb; es decir, los algoritmos m\u00e1s influyentes en el desarrollo de la ciencia y la ingenier\u00eda del pasado siglo. Uno de los diez elegidos fue el m\u00e9todo del s\u00edmplex en programaci\u00f3n lineal. La programaci\u00f3n lineal naci\u00f3 hacia 1939 con los trabajos del\u2026","og_url":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798","og_site_name":"Matem\u00e1ticas y sus fronteras","article_published_time":"2010-05-23T08:30:01+00:00","article_modified_time":"2010-05-23T09:05:32+00:00","og_image":[{"url":"http:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/05\/preview261-300x225.jpg"}],"twitter_card":"summary_large_image","twitter_misc":{"Escrito por":"Matem\u00e1ticas y sus fronteras","Tiempo de lectura":"10 minutos"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebSite","@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#website","url":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/","name":"Matem\u00e1ticas y sus fronteras","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"es"},{"@type":"ImageObject","@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#primaryimage","inLanguage":"es","url":"http:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/05\/preview261-300x225.jpg","contentUrl":"http:\/\/www.madrimasd.org\/blogs\/matematicas\/files\/2010\/05\/preview261-300x225.jpg"},{"@type":"WebPage","@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#webpage","url":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798","name":"La Conjetura de Hirsch, refutada por Francisco Santos - Matem\u00e1ticas y sus fronteras","isPartOf":{"@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#primaryimage"},"datePublished":"2010-05-23T08:30:01+00:00","dateModified":"2010-05-23T09:05:32+00:00","author":{"@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#\/schema\/person\/15722bca1b77eece37f4c192bd1b5230"},"breadcrumb":{"@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#breadcrumb"},"inLanguage":"es","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/2010\/05\/23\/131798#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Portada","item":"https:\/\/www.madrimasd.org\/blogs\/matematicas"},{"@type":"ListItem","position":2,"name":"La Conjetura de Hirsch, refutada por Francisco Santos"}]},{"@type":"Person","@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#\/schema\/person\/15722bca1b77eece37f4c192bd1b5230","name":"Matem\u00e1ticas y sus fronteras","image":{"@type":"ImageObject","@id":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/#personlogo","inLanguage":"es","url":"https:\/\/secure.gravatar.com\/avatar\/50eb6cc40d97cb9ad268a3471c7e2492?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/50eb6cc40d97cb9ad268a3471c7e2492?s=96&d=mm&r=g","caption":"Matem\u00e1ticas y sus fronteras"},"description":"Manuel de Le\u00f3n es Profesor de Investigaci\u00f3n del CSIC, acad\u00e9mico de la Real Academia de Ciencias y su Tesorero, fundador del ICMAT (CSIC), acad\u00e9mico de la Real Academia Canaria de Ciencias y de la Real Academia Galega de Ciencias. Es adem\u00e1s Director del programa Estalmat.","url":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/author\/matematicas"}]}},"_links":{"self":[{"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/posts\/131798"}],"collection":[{"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/comments?post=131798"}],"version-history":[{"count":11,"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/posts\/131798\/revisions"}],"predecessor-version":[{"id":131815,"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/posts\/131798\/revisions\/131815"}],"wp:attachment":[{"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/media?parent=131798"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/categories?post=131798"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madrimasd.org\/blogs\/matematicas\/wp-json\/wp\/v2\/tags?post=131798"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}