Problema de Reemplazo (esquema, guión de video)

https://docs.google.com/document/d/1zzV6xCXKm2flq_l5blLBf00HaC5iunyv04yyOj9P9eI/edit?usp=sharing

Biografía de Delbert Ray Fulkerson

Delbert Ray Fulkerson

Nacimiento: 14 de agosto de 1924, Tamms, Illinois, EE.UU

Murió: 10 de enero de 1976, Ithaca, Nueva York, EE.UU

Pionero en los campos de los flujos de la red, a gran escala de programación lineal y combinatoria y optimización.

Educación: B.A. en Matemáticas, en el sur Illinois University, 1947; M.S. en Matemáticas,Universidad de Wisconsin, 1948; Ph.D. en Matemáticas de la Universidad de Wisconsin, 1951.

Posiciones principales: Rand Corporation, Departamento de Matemáticas, 1951-1971; Maxwell M.Profesor de Ingeniería y el profesor de Investigación Operativa y Matemática Aplicada, Universidad de Cornell, 1971-1976.Trabajo seminal de Delbert Ray Fulkerson en los flujos de la red, a gran escala de programación lineal, y optimización combinatoria.

Ray, como le llamaban sus amigos, fue un matemático en el corazón. Le encantaba la elegancia y la gracia de las matemáticas, y amaba las matemáticas bueno para su propio bien. Gran parte de los más influyentes, comenzó a trabajar con una aplicación, un rompecabezas, o un obstáculo computacional específicos. La búsqueda de laestructuras matemáticas subyacentes llevó Ray y sus colaboradores profundamente a ampliasinnovaciones metodológicas, que incluye los planos de corte, la generación de columnas, y elfundamento de la teoría de flujo de red. 

Premios: Premio Lester R. Ford, la Asociación Matemática de América, por su trabajo''Las redes de flujo y''Combinatoria Investigación de Operaciones, 1967; del Sur de IllinoisPremio Universidad de notables logros profesionales, 1972; profesor visitante:U.C. Berkeley, la Universidad de Stanford, la Universidad de Waterloo.

 Su padre, Elbert Fulkerson, fue un educador muy conocido en la ciudad, y más tarde se convirtió en el director de la escuela. Su madre, Emma, era una mujer profundamente religiosa que en algún momento también había sido un profesor. Ray tuvo de hermanos y tres hermanas todos se convirtieron en educadores. Por otra parte, los tres hermanos obtuvierón el doctorado.

En 1942, Ray entró en la Southern Illinois University, habiéndose graduado con honores de clase de la escuela a la edad de 16 años. Dejó SIU en 1944 con el fin de servir en los EE.UU.

Cuerpo Aéreo del Ejército Ray volvió a SIU en 1946, y se graduó en 1947, una vez más en la parte superior de su clase. A continuación, pasó a la Universidad de Wisconsin para realizar un doctorado en las matemáticas. Él escribió una tesis titulada''formas QuasiHermite de filas finitas  de  matrices'', bajo la supervisión de Colton MacDuffee Cyrus.

Tras completar su doctorado en 1951, Ray se unió al Departamento de Matemáticas de la Rand Corporación, por invitación del jefe del departamento, John Williams. La Rand Corporation había comenzado tres años antes como una consecuencia de un proyecto especial entre la Fuerza Aérea de los EE.UU. y la Douglas Aircraft Company. Muchos de los colegas de Ray en el Departamento de Matemáticas también se convirtierón  en personajes célebres en el desarrollo de los fundamentos matemáticos de la investigación de operaciones, incluyendo Richard Bellman, George Dantzig, Merrill Flood, Les Ford, Johnson y Lloyd Selmer Shapley. Ray también ha trabajado extensivamente con Herb Ryser, uno de los consultores regulares de departamento, y un amigo y un compañero estudiante de posgrado con Ray en Wisconsin. Además, colaboró con varios jóvenes investigadores que trabajaron en o visitado, Rand, sobre todo Jon Folkman y Edmonds Jack. Ray se sintió muy orgulloso de los logros de las matemáticas. En 1971, se unió al Departamento o la Universidad de Cornell, y permaneció allí hasta su muerte en 1976.Antes de llegar a Rand, Ray no había estudiado ni programación lineal o la teoría de grafos. Élse introdujo en estos dos ámbitos a través de sus primeras asignaciones de Rand, que se traducen a T.S. Motzkin tesis sobre desigualdades lineales, y para escribir notas sobre la base de clases de teoría gráfica dada por A.W. Tucker. Poco después de llegar a Rand, Ray hizo importantes contribuciones a estos dos campos de estudio.Una de las primeras publicaciones de Ray y su contribución más duradera surgió de un rompecabezas, un desafío computacional sobre el problema del viajante (TSP): encontrar un menor viaje  a través de las capitales de los (entonces) 48 estados y en Washington, DC. Sucolaboradores en este esfuerzo fueron George Dantzig y Johnson Selmer. Ray había trabajado previamente con los dos, pero en circunstancias muy diferentes. Primera publicación de Ray fue conjuntamente con Dantzig (1954), que se refería al uso de programación lineal para resolver un problema petrolero-programación.Ray había aprendido la meteorología de Selmer Johnson durante la guerra de EE.UU. en una base del Cuerpo Aéreo del Ejército en Illinois.Dantzig, Fulkerson y Johnson (1954) fueron capaces de encontrar un recorrido y establecer su óptimo uso de Simple método de Dantzig y planos de corte, una nueva técnica que han desarrollado específicamente para con este fin. Su enfoque global, que engendró el área de la combinatoria poliédrica, fue muy innovador: considerar la envolvente convexa de los puntos enteros en la región factible de lo que ahora llamamos una relajación de programación lineal del TSP. 

Ray y  Fulkerson son probablemente mejor conocidos por su trabajo en los flujos de la red.

Su colaboración con Lester R. Ford, Jr. puso los cimientos de toda la materia. Todo comenzó con una específica aplicación a las operaciones militares trajeron a su atención durante el almuerzo en Rand por FS Ross.Ross y Harris TE estaban trabajando en un proyecto para evaluar la capacidad de la Europa del Este la red ferroviaria para apoyar una guerra convencional. Ford y Fulkerson (1956, 1962) colaboraron en este problema, llevando su primer trabajo (1956) sobre los flujos de la red, en la que demostró el ahora flujo famoso teorema de flujo max min.

 El papel de Ray(1966) en las redes de flujo y la investigación de operaciones combinatorias fue reconocido por su exposición excelencia con el Premio Lester R. Ford de la Asociación Matemática de América. El premio lleva el nombre de Lester R. Ford, Sr., un ex presidente de la AMA, y el padre de Ray colaborador frecuente.

Su muerte en 1976, fue llorada por todos los que le conocían, y se destacó por las declaraciones de monumento envarias revistas, un volumen especial de la investigación de operaciones matemáticas, y el establecimiento de la D.R. Fulkerson Premio en Matemáticas Discretas por la Sociedad Matemática Americana y La Sociedad Matemática de programación.

Referencias:

http://es.wikipedia.org/wiki/D._R._Fulkerson
http://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2005.00506.x/pdf
http://www.deepdyve.com/lp/informs/delbert-ray-fulkerson-august-14-1924-january-10-1976-ivA88ywFg9

Biografía de Lester Randolph Ford Jr.

Lester Randolph Ford Jr.

Lester Randolph Ford Jr. es un matemático americano, uno de los pioneros en el campo de la programación de flujos en grafos. Nació el 23 de septiembre de 1927 y es el hijo de L.R. Ford Sr. (quién también es un matemático distinguido) ,su madre  Margarita E. John y esposa Janet Lux.

         

L. R. Ford Sr es elogiado por su ejemplar trabajo en matemáticas al inventar una interpretación geométrica absolutamente maravillosa de la serie de Farey. También le acredita su trabajo 'Pointwise Discontinuous Functions' que era la base de su trabajo para un grado de M.S. del departamento de matemáticas en la universidad de Missouri-Colombia en 1912. Tal fue su contribución a las matemáticas, que en 1964 se estableció el Lester R. Ford Award para reconocer la contribución a las matemáticas de excelentes autores matemáticos publicados en The American Mathematical Monthly o Mathematics Magazine. Fue redactor de American Mathematical Monthly, de 1942-1946, y el presidente de Mathematical Association of America, 1947-1948. Ford Sr. y Ford Jr. son co-autores de Automorphic Functions cuál fue publicado cerca por McGraw-Hill en 1963.

Mientras trabajó en RAND CORPORATION, Ford Jr publicó numerosos artículos que no solo establecieron la base de los flujos de red sino también la futura investigación en este campo. En 1962 Priceton University Press publicó su libro Flow in Networks con D. R. Fulkerson como co-autor. Este libro contiene todo su trabajo sobre redes.

Junto con Richard E. Bellman (26 de agosto 1920 – 19 marzo de 1984) desarrollaron el algoritmo de 'corrección de etiquetas' que calcula el camino más corto en un digrafo ponderado (donde incluso y a diferencia de Dijkstra, los pesos de los arcos pueden ser negativos).

El papel de Ford con el 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 .

La mayoría del trabajo de Ford lo hizo en la colaboración con Fulkerson, al parecer los dos hacían una buena asociación. Sin embargo, en 1956 presentó varios artículos firmados por él sólo. Ha sido el autor de diversos algoritmos que se han refinado con los años y que todavía se utilizan para solucionar la mayoría de problemas de grafos.

Referencias: 

http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford
http://www.tangrammit.com/barbara.html

Tarea 1 (Nube de palabras y Planteamiento de problema de Asignación)

Tarea 1 (Nube de palabras y Planteamiento de problema de Asignación)

Consultar PDF aquí.
https://docs.google.com/file/d/0B4nbJuWXL68mX091c2IxS1VlUHc/edit?usp=sharing