martes, 13 de diciembre de 2011
viernes, 25 de noviembre de 2011
lunes, 14 de noviembre de 2011
domingo, 6 de noviembre de 2011
Unidad 3. Programación Entera
Biografías
Ralph E. Gomory
Fecha de nacimiento: 07 de mayo 1929, en Brooklyn Heights, Nueva York.
Se graduó del Williams College en 1950, estudió en la Universidad de Cambridge, y recibió su Ph.D. en matemáticas de la Universidad de Princeton en 1954. Gomory después sirvió en la Marina de Guerra (1954-57) y luego fue Profesor Higgins y profesor adjunto de matemáticas en Princeton antes de incorporarse a la recién creada División de Investigación de IBM en 1959 como investigador matemático.
En sus años de estudiantes y el estudiante graduado (Williams, Cambridge, Princeton), Gomory realizó investigaciones sobre ecuaciones diferenciales no lineales, pero sus años en la Marina volvió su atención a la matemática aplicada de la investigación de operaciones. De regreso en Princeton, obtuvo el primer plano de corte general de los algoritmos, que estableció el campo de la programación entera. Sigue siendo un área activa de investigación hoy en día.
En la investigación de IBM en la década de 1960, Gomory publicado trabajos con Paul Gilmore en el vendedor de la mochila, viajar y problemas de stock de corte, y con TC Hu sobre los flujos en redes multi-terminal y continua. A finales de la década de 1960, desarrolló la teoría asintótica de la programación entera e introdujo el concepto de la esquina de poliedros. A principios de la década de 1970, colaboró con Ellis Johnson en la investigación de las funciones relacionadas con los poliedros subaditiva esquina que también podrían desempeñar un papel en la producción de tecnología de los aviones.
Gomory se desempeñó como Presidente del Departamento de Matemática de Ciencias de Investigación de IBM 1965-67 y 1968-70 durante un período importante de su crecimiento y evolución. Este período se inicia el trabajo de Samuel Winograd sobre los límites de los algoritmos y de trabajo de Benoit Mandelbrot sobre los fractales.
Gomory se convirtió en Director de Investigación de IBM en 1970, con la responsabilidad de la línea de la División de Investigación de IBM. Durante sus 18 años como Director de Investigación de la División de Investigación realizó una amplia serie de contribuciones a los productos de IBM, a la industria de la computación y la ciencia. El Zurich Research Laboratory hizo el trabajo que dio lugar a dos sucesivos premios Nobel de física, Yorktown Heights investigación fue la cuna de lo que ahora se conoce como arquitectura RISC, y San José fue el lugar de nacimiento del concepto, la teoría y el primer prototipo de bases de datos relacionales.
Gomory, que se convirtió en el vicepresidente senior de IBM para la Ciencia y la Tecnología se retiró de IBM en 1989 y se convirtió en Presidente de la Fundación Alfred P. Sloan. Durante su mandato como presidente lideró la fundación en una larga lista de ámbitos relacionados con los grandes temas nacionales. La fundación fue pionera en el campo de la educación en línea apoyar este trabajo antes de que hubiera siquiera una Internet pública, y luego apoyó su crecimiento a más de tres millones de personas que toman cursos para obtener créditos. Se inició el programa ha extendido de estudios de la industria, y contrató a un importante programa aboga por un lugar de trabajo más flexible. La Fundación desarrolló un enfoque novedoso y exitoso para el problema de la producción de las minorías de doctorado en los campos científico y técnico. La fundación fue a principios de la percepción de la amenaza del bioterrorismo y participó activamente en esa área durante años antes de los acontecimientos del 9 / 11. En el lado científico de la Fundación apoyó la ampliamente reconocida Sloan Sky Survey, que ha hecho importantes contribuciones al problema de la energía oscura e inició un esfuerzo importante en todo el mundo para estudiar la vida en los océanos conocido como el Censo de Vida Marina. En diciembre de 2007, tras 18 años como presidente, Gomory se convirtió en Presidente Emérito.
Gomory ha servido en muchas de las organizaciones académicas, industriales y gubernamentales. Fue miembro del consejo de Hampshire College de 1977-1986 y de la Universidad de Princeton 1985 a 1989. Sirvió en el Consejo Presidencial de Asesores en Ciencia y Tecnología (PCAST) de 1984 a 1992, y nuevamente desde 2001 hasta la actualidad. Se desempeñó durante un número de términos en el Comité de la Academia Nacional de Ciencia, Ingeniería y Políticas Públicas (COSEPUP). Se ha incorporado recientemente a STEP, el Consejo de Ciencia, Tecnología y Política Económica de las Academias Nacionales.
Gomory ha sido director de varias compañías, incluyendo el Washington Post Company y el Banco de Nueva York. En la actualidad es director de Lexmark International, Inc., y de dos pequeñas empresas start-up. Fue nombrado uno de los diez mejores directores de Estados Unidos por la revista Alerta de Director en el año 2000.
Gomory ha sido elegido miembro de la Academia Nacional de Ciencias, la Academia Nacional de Ingeniería y la Sociedad Filosófica Americana. Fue elegido posteriormente a los Consejos de las tres sociedades. Ha sido galardonado con ocho doctorados honoris causa y numerosos premios incluyendo el Premio Lanchester en 1963, el Harry Goode Memorial Award de la Federación Americana de Sociedades de Procesamiento de la Información en 1984, John von Neumann, la teoría del Premio en 1984, la Medalla de la Sociedad de Investigación Industrial en 1985, el IEEE de Ingeniería de Liderazgo Premio de Reconocimiento en 1988, la Medalla Nacional de Ciencias otorgado por el Presidente en 1988, el Premio Arthur M. Bueche de la Academia Nacional de Ingeniería en 1993, el Premio Heinz para la Tecnología, la Economía y el Empleo en 1998 , la Medalla Madison de la Universidad de Princeton en 1999, la Beca de Sheffield de la Facultad de Ingeniería de la Universidad de Yale en 2000, la Federación Internacional de Sociedades de Investigación Operativa Salón de la Fama en 2005, y el Harold Larnder Premio de la Sociedad Canadiense de Investigación Operativa en el año 2006.
Al tiempo que continúa sus investigaciones sobre Gomory programación entera se ha escrito sobre la naturaleza del desarrollo tecnológico, la competitividad de la investigación en la industria, e industrial, y en los modelos de comercio internacional en relación con los cambios tecnológicos y las economías de escala. Él es el autor, con el profesor William Baumol, de la industria del libro Global intereses nacionales en conflicto (MIT Press, 2001).
Nació en Cluj, Rumania, el 13 de Junio de 1922, tiene la ciudadanía de Estados Unidos de América (emigró en 1967). Vive en Pittsburg, Pensilvania, EE UU.
Licenciado en Economía por la Universidad de Bolyai, Cluj, Rumania, Doctor en Economía (summa cum laude) por la Universidad de Bruselas y Doctor en Ciencias (Matemáticas) por la Universidad de París.
Desde 1968 el prof. Egon Balas es profesor de Administración Industrial y Matemática Aplicada en la Graduate School of Industrial Administration, en Carnegie Mellon University, Pittsburg, Pensilvania, EEUU.
El prof. Egon Balas es una de las figuras científicas más destacadas en programación matemática con especial énfasis en programación entera y discreta y optimización combinatoria. Ha publicado más de 180 trabajos científicos, y supervisado más de 25 tesis doctorales. Su investigación ha tenido una influencia extraordinaria en los avances teóricos y en los desarrollos computacionales de la matemática aplicada. Su prolífico trabajo de investigación incluye disciplinas teóricas y practicas, tales como programación disyuntiva, análisis poliédrico de diversos problemas de optimización combinatoria, problemas de redes y grafos, teoría de la localización, el problema del transporte, el problema del agente viajero, el problema de conjuntos de cubrimiento y particionamiento, el problema de la mochila, planificación de actividades, secuenciación y asignación, asignación de tráfico en comunicaciones vía satélite, planificación y optimización de la gestión de recursos forestales, etc.
La investigación del prof. Balas ha sido parcialmente financiada por la National Science Foundation, la US Office of Naval Research, la US Air Force Office of Scientific Research y la NATO. El prof. Balas ha sido consultor para el Dpto. de Energía de EEUU. Así mismo ha desarrollado y dirigido proyectos para el sector privado en la industria del acero, y en empresas tales como IBM, American Airlines, etc.
Su trabajo sobre el método aditivo para resolver problemas de programación lineal con variables 0-1 publicado en diversas entregas en el periodo 1964-1966 ha sido durante muchos años el trabajo más citado en las revistas, libros y otras publicaciones de Investigación-Operativa. Unos de sus últimos proyectos a lo largo de los años 90 ha sido el desarrollo del algoritmo “Lift-and-Project Cutting Plane” para la resolución de problemas lineales con variables 0-1 y continuas.
Desde hace muchos años el prof. Balas pertenece o ha pertenecido a los Comités Editoriales de las revistas más prestigiosas de Investigación-Operativa, tales como Operations Research, Discrete Applied Mathematics, Naval Logistics Research, The European Journal of Operations Research, Computational Optimization and Applications, Journal of Combinatorial Optimization, Annals of Operations Research, etc.
Reseñas del prof. Balas aparecen en “Who’s Who in the World”, Who’s Who in America”, “American Men and Woman of Science”. Tambien es citado en “Contemporary Classics in Engineering and Applied Science”
Recientemente, el prof. Balas ha publicado “Will to Freedom: A Perilous Journey through Fascim and Comunism”, Syracuse University Press, 2000, 469 pags., un recorrido sobre su vida hasta su llegada a EEUU.
Honores:
Medalla de Oro de EURO, la Asociación Europea de Sociedades de Investigación Operativa, 2001.
John von Neumann Theory Prize, concedido por INFORMS, la Sociedad de Investigación-Operativa de EEUU, 1995.
University Professor, Carnegie Mellon University, 1990.
The Thomas Lord Professorhip en Investigación-Operativa, Carnegie Mellon University, patrocinado por la Fundación Thomas Lord, 1996.
Senior US Scientific Award, concedido por la Fundación Alexander Humbodlt, Alemania, 1980-81.
Referencias:
http://www.sloan.org/bio/item/11
http://en.wikipedia.org/wiki/Ralph_E._Gomory
http://t3.gstatic.com/images?q=tbn:ANd9GcSj_0hiFjjk8ioHogL766cYGe7JQpaDbylspx7tPbu5Ye1KLcaK
http://blogs.umh.es/comunicacion/2002/09/25/biografa-de-d-egon-balas/
D. Egon Balas
Nació en Cluj, Rumania, el 13 de Junio de 1922, tiene la ciudadanía de Estados Unidos de América (emigró en 1967). Vive en Pittsburg, Pensilvania, EE UU.
Licenciado en Economía por la Universidad de Bolyai, Cluj, Rumania, Doctor en Economía (summa cum laude) por la Universidad de Bruselas y Doctor en Ciencias (Matemáticas) por la Universidad de París.
Desde 1968 el prof. Egon Balas es profesor de Administración Industrial y Matemática Aplicada en la Graduate School of Industrial Administration, en Carnegie Mellon University, Pittsburg, Pensilvania, EEUU.
El prof. Egon Balas es una de las figuras científicas más destacadas en programación matemática con especial énfasis en programación entera y discreta y optimización combinatoria. Ha publicado más de 180 trabajos científicos, y supervisado más de 25 tesis doctorales. Su investigación ha tenido una influencia extraordinaria en los avances teóricos y en los desarrollos computacionales de la matemática aplicada. Su prolífico trabajo de investigación incluye disciplinas teóricas y practicas, tales como programación disyuntiva, análisis poliédrico de diversos problemas de optimización combinatoria, problemas de redes y grafos, teoría de la localización, el problema del transporte, el problema del agente viajero, el problema de conjuntos de cubrimiento y particionamiento, el problema de la mochila, planificación de actividades, secuenciación y asignación, asignación de tráfico en comunicaciones vía satélite, planificación y optimización de la gestión de recursos forestales, etc.
La investigación del prof. Balas ha sido parcialmente financiada por la National Science Foundation, la US Office of Naval Research, la US Air Force Office of Scientific Research y la NATO. El prof. Balas ha sido consultor para el Dpto. de Energía de EEUU. Así mismo ha desarrollado y dirigido proyectos para el sector privado en la industria del acero, y en empresas tales como IBM, American Airlines, etc.
Su trabajo sobre el método aditivo para resolver problemas de programación lineal con variables 0-1 publicado en diversas entregas en el periodo 1964-1966 ha sido durante muchos años el trabajo más citado en las revistas, libros y otras publicaciones de Investigación-Operativa. Unos de sus últimos proyectos a lo largo de los años 90 ha sido el desarrollo del algoritmo “Lift-and-Project Cutting Plane” para la resolución de problemas lineales con variables 0-1 y continuas.
Desde hace muchos años el prof. Balas pertenece o ha pertenecido a los Comités Editoriales de las revistas más prestigiosas de Investigación-Operativa, tales como Operations Research, Discrete Applied Mathematics, Naval Logistics Research, The European Journal of Operations Research, Computational Optimization and Applications, Journal of Combinatorial Optimization, Annals of Operations Research, etc.
Reseñas del prof. Balas aparecen en “Who’s Who in the World”, Who’s Who in America”, “American Men and Woman of Science”. Tambien es citado en “Contemporary Classics in Engineering and Applied Science”
Recientemente, el prof. Balas ha publicado “Will to Freedom: A Perilous Journey through Fascim and Comunism”, Syracuse University Press, 2000, 469 pags., un recorrido sobre su vida hasta su llegada a EEUU.
Honores:
Medalla de Oro de EURO, la Asociación Europea de Sociedades de Investigación Operativa, 2001.
John von Neumann Theory Prize, concedido por INFORMS, la Sociedad de Investigación-Operativa de EEUU, 1995.
University Professor, Carnegie Mellon University, 1990.
The Thomas Lord Professorhip en Investigación-Operativa, Carnegie Mellon University, patrocinado por la Fundación Thomas Lord, 1996.
Senior US Scientific Award, concedido por la Fundación Alexander Humbodlt, Alemania, 1980-81.
Referencias:
http://www.sloan.org/bio/item/11
http://en.wikipedia.org/wiki/Ralph_E._Gomory
http://t3.gstatic.com/images?q=tbn:ANd9GcSj_0hiFjjk8ioHogL766cYGe7JQpaDbylspx7tPbu5Ye1KLcaK
http://blogs.umh.es/comunicacion/2002/09/25/biografa-de-d-egon-balas/
domingo, 23 de octubre de 2011
Paticipación 2 Unidad 2
3).- Encuentre la trayectoria más corta del nodo 1 al nodo 6.
Trayectoria más corta : 31
Partiipación 1 Unidad 2
Las distancias en millas entre ciudades de Indiana: Gary, Fort Wayne, Evansville, Terre Haute y South Bend, se muestran en la siguiente tabla. Es necesario construir un sistema estatal de carreteras que una todas estas ciudades. Suponga que por razones políticas no es necesario construir una carretera a Gary y Fort Evansville
¿Cuál es la longitud mínima de la carretera requerida?
R= 414
domingo, 16 de octubre de 2011
sábado, 15 de octubre de 2011
viernes, 7 de octubre de 2011
jueves, 22 de septiembre de 2011
Unidad 2: Redes de Optimización
Biografías
Edsger Wybe Dijkstra
Edsger Wybe Dijkstra (1930 – 2002) nació en 1930 en Rotterdam, Holanda. Era hijo de Wybe Douwe Dijkstra y Brechtje Cornelia Kruyper, y tenia tres hermanos más. Su padre era professor de fisica en la escuela secundaria de Rotterdam, mientras que su madre era matemática.
De joven, asistió a la escuela secundaria de Rotterdam. Djikstra quería estudiar Derecho y asi poder representar a los Paises Bajos en las Naciones Unidas. Pero, en 1948 realizó los exámenes finales de su etapa en la escuela secundaria y sacó notas excelentes en matematicas, física, química y biología, y tanto sus padres como sus profesores intentaron persuadirle para que se decantara por una carrera de ciencias. Finalmente, decidió estudiar física teórica en la universidad de Leyden.
Tres años después, en 1951, Dijkstra vio un anuncio de la Universidad de Cambridge sobre un curso de tres semanas que trataba la programación en computadores. Se interesó mucho por este curso y decidió apuntarse, ya que lo veía como una oportunidad esta actividad, que consideraba muy ligada a su campo, la física teórica.
De joven, asistió a la escuela secundaria de Rotterdam. Djikstra quería estudiar Derecho y asi poder representar a los Paises Bajos en las Naciones Unidas. Pero, en 1948 realizó los exámenes finales de su etapa en la escuela secundaria y sacó notas excelentes en matematicas, física, química y biología, y tanto sus padres como sus profesores intentaron persuadirle para que se decantara por una carrera de ciencias. Finalmente, decidió estudiar física teórica en la universidad de Leyden.
Tres años después, en 1951, Dijkstra vio un anuncio de la Universidad de Cambridge sobre un curso de tres semanas que trataba la programación en computadores. Se interesó mucho por este curso y decidió apuntarse, ya que lo veía como una oportunidad esta actividad, que consideraba muy ligada a su campo, la física teórica.
Aad van Wijngaarden, que era el director del Departamento de Ciencia de la Computación del Centro Matemático en Amsterdam, había hecho el mismo curso en Cambridge en el año anterior y cuando se enteró de que Dijkstra había terminado, le ofreció un puesto como programador del Centro de Matemáticas. Dijkstra aceptó el cargo desde marzo de 1952, pero sólo como una posición a tiempo parcial, ya que seguía siendo estudiante de física teórica en la Universidad de Leyden. A pesar de esto, Dijkstra empezaba a decantarse más por la programación que por la física teorica, ya que le suponía un reto mayor, al ser una rama del saber prácticamente nueva, con mucho por descubrir.
Después de haber tomado la decisión, Dijkstra completó sus estudios en física teórica en la universidad, graduándose en 1956. También en 1956, el Centro de Matemáticas de Amsterdam, en el que trabajaba completó la construcción de una nueva computadora y quería hacer una demostración pública. Para ello, Dijkstra, planteó el problema de encontrar el camino mas corto entre dos ciudades de los Países Bajos. Publicó su algoritmo, muy eficaz, que ha perdurado hasta nuestros días, y conocido popularmente como “el algoritmo de Djikstra” (o algoritmo de caminos mínimos). La idea de este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.
También en 1959 fue galardonado con el doctorado de la Universidad de Amsterdam por su tesis La comunicación con un equipo automático.
Como curiosidad, destacar que en 1957 se casó con María Debets , y tuvo dos hijos y una hija. Sin embargo, tuvo un problema en su boda porque el Juez de Paz no aceptaba “programador” como profesión para los registros, por lo que tuvo que decir que era “físico teórico” en el formulario.
Dijkstra también colaboró con el equipo de desarrollo del lenguaje de programación ALGOL-60. Hizo varias contribuciones importantes: la introducción explícita de la recursividad y la noción de ‘pila’. Dijkstra, junto con uno de sus colegas en el Centro de Matemáticas, escribió el primer compilador de ALGOL-60, que se completó en agosto de 1960.
Después de haber tomado la decisión, Dijkstra completó sus estudios en física teórica en la universidad, graduándose en 1956. También en 1956, el Centro de Matemáticas de Amsterdam, en el que trabajaba completó la construcción de una nueva computadora y quería hacer una demostración pública. Para ello, Dijkstra, planteó el problema de encontrar el camino mas corto entre dos ciudades de los Países Bajos. Publicó su algoritmo, muy eficaz, que ha perdurado hasta nuestros días, y conocido popularmente como “el algoritmo de Djikstra” (o algoritmo de caminos mínimos). La idea de este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.
También en 1959 fue galardonado con el doctorado de la Universidad de Amsterdam por su tesis La comunicación con un equipo automático.
Como curiosidad, destacar que en 1957 se casó con María Debets , y tuvo dos hijos y una hija. Sin embargo, tuvo un problema en su boda porque el Juez de Paz no aceptaba “programador” como profesión para los registros, por lo que tuvo que decir que era “físico teórico” en el formulario.
Dijkstra también colaboró con el equipo de desarrollo del lenguaje de programación ALGOL-60. Hizo varias contribuciones importantes: la introducción explícita de la recursividad y la noción de ‘pila’. Dijkstra, junto con uno de sus colegas en el Centro de Matemáticas, escribió el primer compilador de ALGOL-60, que se completó en agosto de 1960.
En 1972 recibió el premio Turing, y su discurso fue publicado en un artículo titulado “The Humble Programmer” (el programador humilde).
En 1984 se le ofreció un puesto en el Burroughs Research Center de Austin, Texas, donde permaneció hasta retirarse en 1999.
Finalmente murió en el año 2002 en Nuenen, Holanda, tras una larga enfermedad de cáncer.
Robert W. Floyd (8 de junio de 1936 - 25 de septiembre de 2001) fue un prominente científico estadounidense en informática.
Nacido en Nueva York, Floyd culminó bachillerato a los 14 años. Se graduó en la Universidad de Chicago en 1953 a los 17 años y como Físico en 1958.
Operador de computadoras en los años 60, publicó sus primeros artículos los cuales fueron de gran influencia y fue nombrado profesor asociado en la Universidad de Carnegie Mellon. Seis años más tarde fue nombrado profesor en la Universidad de Stanford.
Entre sus contribuciones se encuentran el diseño y análisis de algoritmos eficientes para encontrar el camino más corto en un grafo y para el problema de reconocimiento de frases, pero probablemente su logro más importante fue el ser pionero, con su artículo de 1967 «Assigning Meanings to Programs», en el área de verificación de programas utilizando aserciones lógicas, donde aparece la importante noción de invariante, esencial para demostrar propiedades de programas iterativos.
Floyd recibió el Premio Turing de la ACM en 1978 «por tener una clara influencia en las metodologías para la creación de software eficiente y confiable, y por haber contribuido a la fundación de las subáreas teoría del reconocimiento de frases, semántica de los lenguajes de programación, verificación automatizada de programas, síntesis automatizada de programas y análisis de algoritmos».
Fecha de nacimiento: 25 de octubre de 1886
Lugar de nacimiento: Missouri
El papel de Ford con DR Fulkerson en el problema de flujo máximo y el algoritmo de Ford-Fulkerson para resolverlo, publicado como un informe técnico en 1954 y en un diario en 1956, estableció el máximo de flujo min de corte teorema.
Con Richard Bellman, Ford también desarrolló el algoritmo de Bellman-Fordd para encontrar los caminos más cortoss en los gráficos que tienen bordes negativamente ponderado.
Fecha de nacimiento : 14 de agosto de 1924
Referencias :
http://histinf.blogs.upv.es/2010/10/28/dijkstra/
http://www.adeptis.ru/vinci/edsger_dijkstra5.jpg
http://es.wikipedia.org/wiki/Robert_W._Floyd
http://www.systemcomputing.org/turing%20award/robert_1978/Robert_files/image001.jpg
En 1984 se le ofreció un puesto en el Burroughs Research Center de Austin, Texas, donde permaneció hasta retirarse en 1999.
Finalmente murió en el año 2002 en Nuenen, Holanda, tras una larga enfermedad de cáncer.
Robert W. Floyd
Robert W. Floyd (8 de junio de 1936 - 25 de septiembre de 2001) fue un prominente científico estadounidense en informática.
Nacido en Nueva York, Floyd culminó bachillerato a los 14 años. Se graduó en la Universidad de Chicago en 1953 a los 17 años y como Físico en 1958.
Operador de computadoras en los años 60, publicó sus primeros artículos los cuales fueron de gran influencia y fue nombrado profesor asociado en la Universidad de Carnegie Mellon. Seis años más tarde fue nombrado profesor en la Universidad de Stanford.
Entre sus contribuciones se encuentran el diseño y análisis de algoritmos eficientes para encontrar el camino más corto en un grafo y para el problema de reconocimiento de frases, pero probablemente su logro más importante fue el ser pionero, con su artículo de 1967 «Assigning Meanings to Programs», en el área de verificación de programas utilizando aserciones lógicas, donde aparece la importante noción de invariante, esencial para demostrar propiedades de programas iterativos.
Floyd recibió el Premio Turing de la ACM en 1978 «por tener una clara influencia en las metodologías para la creación de software eficiente y confiable, y por haber contribuido a la fundación de las subáreas teoría del reconocimiento de frases, semántica de los lenguajes de programación, verificación automatizada de programas, síntesis automatizada de programas y análisis de algoritmos».
Lester Randolph Ford
Fecha de nacimiento: 25 de octubre de 1886
Lugar de nacimiento: Missouri
El papel de Ford con DR Fulkerson en el problema de flujo máximo y el algoritmo de Ford-Fulkerson para resolverlo, publicado como un informe técnico en 1954 y en un diario en 1956, estableció el máximo de flujo min de corte teorema.
Con Richard Bellman, Ford también desarrolló el algoritmo de Bellman-Fordd para encontrar los caminos más cortoss en los gráficos que tienen bordes negativamente ponderado.
Delbert Ray Fulkerson
Fecha de nacimiento : 14 de agosto de 1924
Fulkerson se crió en un pequeño pueblo del sur de Illinois y se convirtió en un estudiante en la Southern Illinois University. Su carrera académica se vio interrumpida por el servicio militar durante la Segunda Guerra Mundial. Habiendo vuelto a completar sus estudios después de la guerra pasó a hacer un doctorado en matemáticas en la Universidad de Wisconsin, bajo la supervisión de Ciro MacDuffee, un estudiante de LE Dickson.
Fulkerson recibió su doctorado en la Universidad de Wisconsin-Madison en 1951. Fue entonces, con el departamento de matemáticas de la Rand Corporation hasta 1971 cuando se trasladó a Cornell como el profesor Maxwell Upson de Ingeniería. Permaneció en Cornell hasta que se suicidó en 1976.
En 1956, publicó su documento con en el algoritmo de Ford-Fulkerson, junto con Lester Randolph Ford.
El Premio Fulkerson para los papeles destacados en el área de la matemática discreta está patrocinado conjuntamente por la Sociedad Matemática de Programación (MPS) y la American Mathematical Society (AMS). Este premio nace de la iniciativa de amigos de Fulkerson para fomentar la excelencia matemática en los campos de la investigación ejemplificada por su trabajo. Los premios están financiados por un fondo administrado por MPS.
Falleció el 10 de enero de 1976.Fulkerson recibió su doctorado en la Universidad de Wisconsin-Madison en 1951. Fue entonces, con el departamento de matemáticas de la Rand Corporation hasta 1971 cuando se trasladó a Cornell como el profesor Maxwell Upson de Ingeniería. Permaneció en Cornell hasta que se suicidó en 1976.
En 1956, publicó su documento con en el algoritmo de Ford-Fulkerson, junto con Lester Randolph Ford.
El Premio Fulkerson para los papeles destacados en el área de la matemática discreta está patrocinado conjuntamente por la Sociedad Matemática de Programación (MPS) y la American Mathematical Society (AMS). Este premio nace de la iniciativa de amigos de Fulkerson para fomentar la excelencia matemática en los campos de la investigación ejemplificada por su trabajo. Los premios están financiados por un fondo administrado por MPS.
Referencias :
http://histinf.blogs.upv.es/2010/10/28/dijkstra/
http://www.adeptis.ru/vinci/edsger_dijkstra5.jpg
http://es.wikipedia.org/wiki/Robert_W._Floyd
http://www.systemcomputing.org/turing%20award/robert_1978/Robert_files/image001.jpg
http://www.gap-system.org/~history/Biographies/Ford.html
http://www.gap-system.org/~history/Biographies/Ford.html
http://www.gap-system.org/~history/Biographies/Ford.html
http://en.wikipedia.org/wiki/D._R._Fulkerson
http://www.orie.cornell.edu/orie/research/seminars/fulkerson/fulkerson-bio.cfm
http://www.orie.cornell.edu/orie/research/seminars/fulkerson/fulkerson-bio.cfm
lunes, 19 de septiembre de 2011
martes, 13 de septiembre de 2011
PRIM
Se le conoce como algoritmo de Prim en honor a uno de sus desarrolladores Robert C. Prim
Algoritmo de Prim
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.
Referencia:http://es.wikipedia.org/wikiAlgoritmo_de_Prim
lunes, 12 de septiembre de 2011
Tarea 2
Aqui les dejo el enlace de nuestro guión:
https://docs.google.com/present/view?id=dcthbn88_0hrhxjmfj
https://docs.google.com/present/view?id=dcthbn88_0hrhxjmfj
jueves, 8 de septiembre de 2011
Participación 10
Suponga las siguientes redes, plantear los modelos de programación lineal y tabla de transporte:
a) Red
Modelo de Programación Lineal:
Modelo de Programación Lineal:
c) Red :
Modelo de Programación Lineal:
Tabla de transporte:
d) Red:
Modelo de Programación Lineal:
Min Z= 5X12+ 3X13+… +13X67
a) Red
Modelo de Programación Lineal:
Min Z= X13+ 6X35+… +8X46
X13+ X14= 100
X23+ X24=200
X34+ X35= X13+ X23+ X43
X43+ X45+ X46= X14+ X24+ X34
X35+ X45=150
X46+ X56=150
XIJ ≥ O XIJ ϵ Z
Tabla de transporte:
b) Red
Min Z= X14+ .5X15+… +1.9X58
X14+ X15= 900
X24+ X25= 1400
X34+ X35= 1000
X14+ X24 + X34 = X45+ X46 + X47 + X48
X15+ X25+ X35 = X56+ X57 + X58
X46+ X56= 1100
X47+ X57= 1000
X48+ X58= 1200
XIJ ≥ O XIJ ϵ Z
Tabla de trasnporte:c) Red :
Modelo de Programación Lineal:
Min Z= 3X16+ 2X12+… +8X72
X13+ X12= 50 000
X36+ X34= 60 000
X63+ X62 = X16+ X13 + X56
X56+ X57 + X54 = X63 + X75
X75+ X72= X57
X12+ X62 + X72 = 90 000
X14+ X24 = 20 000
XIJ ≥ O XIJ ϵ Z
Tabla de transporte:
Modelo de Programación Lineal:
Min Z= 5X12+ 3X13+… +13X67
X12+ X13=1
X24+ X24 + X25 = X12+ X32
X32+ X34 + X35 + X36= X13+ X23<span style="font-size: large;"> + X63
X45+ X47= X24+ X34 + X54
X54+ X56 + X57 = X25+ 3535 + X45
X63+ X67 = X36 + X65
X47+ X57 + X67= 1
XIJ ≥ O XIJ ϵ Z
Tabla de transporte:
Suscribirse a:
Comentarios (Atom)