Guión Vídeo 2 :] Redes de Optimización

	Imágenes a colocar	Texto a colocar	Sonidos o efectos	Narración	Segundos
Introducción		Redes de optimización Explicación locutor 1	James Horner A Beautiful Mind	Dentro de las redes de optimización se puede hallar la ruta más corta entre dos nodos. La longitud mínima de una ruta o camino se llama ruta más corta. Se puede plantear en MPL y red. Para que un problema tenga solución debe existir por lo menos un camino de S a T,y no haber circuitos negativos  pues de no ser así podría presentarse una solución no acotada en el problema.El algoritmo de Dijkstra funciona para redes dirigidas  con costos no negativos, tiene dos etapas: etiquetado temporal y etiquetado permanente, este algoritmo fue creado por Edsger Wybe Dijkstra en la década de los 90’s.	35 seg
Planteamiento		Planteamiento del problema Planeación de producción.		Una empresa vende un artículo cuya demanda en los 4 meses siguientes serán de 100, 140, 210 y 180 respectivamente. La empresa puede almacenar la cantidad justa para cada mes o puede almacenar más y cumplir con la demanda de 2 o más meses consecutivos, en este caso se tendrá un costo adicional  de retención de 1.20 por unidad en exceso por mes. Los precios unitario de compra durante los 4 siguientes meses serán 15, 12, 10 y 14 pesos respectivamente, cada vez que se surte la demanda se tendrá un costo de preparación de 200. La empresa desea desarrollar un plan de compras que minimice los costos totales.	15 seg
Solución		Explicación locutor 2		1 Se plantea la red. 2 Al nodo de inicio se etiqueta temporalmente, es decir se pone en corchetes costo y nodo antecesor. 3 A los nodos adyacentes de este nodo se etiquetan temporalmente, es decir se pone en paréntesis costo y nodo antecesor. 4 Al nodo con la etiqueta de menor costo se le etiqueta permanente. - Repetimos paso 3 sumando costo de nodo con costo del arco, si el costo total se mayor al que tenia se deja con el original. - Se repite  paso 4 y 3 hasta que todas las etiquetas sean permanentes. Para hacer la ruta del nodo final se regresa al nodo antecesor que tiene la etiqueta y así sucesivamente hasta llegar al nodo inicial.	1 min
Interpretación		Explicación locutor 3		En el año 0 se produce 100 unidades para año 1. En el año 1 se produce 140 unidades para el año 2. En el año 2 se produce 390 unidades para los años 3 y 4. En el año 3 no se produce. Con un costo total de 8096.	15 seg
Créditos		Explicación locutor 3 Voces: Hernández Mateos Karina Méndez Mares Liliana Selene Reyes Lucas Dulce María Música: James Horner A Beautiful Mind Unam Fes Acatlán Octubre 2011		Voces y producción: Hernández Mateos Karina Méndez Mares Liliana Selene Reyes Lucas Dulce María Música: James Horner A Beautiful Mind Unam Fes Acatlán Octubre 2011	10 seg

Biografias Lester Randolph Ford y 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

Lester Randolph Ford

Nació: 23 de Septiembre de 1927, de 84 años de edad.

Lester Randolph Ford Jr. es un matemático americano, uno de los pioneros en el campo de la programación de flujos en grafos. Es el hijo de L.R. Ford Sr. (quién también es un matemático distinguido) y nació el 23 de septiembre de 1927,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 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

Participación 3 :D

Unidad 2 Redes de Optimización

Participación 3

Ruta más Corta de Problemas No Clásicos

Se tiene una red de comunicaciones entre dos estaciones 1 y 7. Las probabilidades de que un enlace de la red funcione sin fallar se muestran en la siguiente tabla. Los mensajes se mandan de la estación 1 a la estación 7 y el objetivo es determinar la ruta que maximice la probabilidad de una buena transmisión.

Estaciones	probabilidad	Estaciones	Probabilidad
1,2	0.8	1,4	0.65
1,3	0.3	2,5	0.5
2,4	0.9	3,6	0.95
4,5	0.7	4,6	0.6
4,3	0.85	5,7	0.8
5,6	0.5	6,7	0.9

Plantear la red y resolver como un problema de ruta más corta.

Aplicando el Método de Dijkstra se tiene lo siguiente:

La probabilidad que maximiza una buena transmisión es de .52326

Participación 2 :P

Unidad 2 Redes de Optimización

Participación 2

Problemas de Ruta más Corta

Encuentre la trayectoria más corta del nodo 1 al nodo 6.
Utilizando el método de Dijkstra se tiene lo siguiente:

Se tendrá un costo mínimo de 31.

Participación 1 :D

Unidad 2 Redes de Optimización

Participación 1

Problemas de árbol de expansión mínima

1.    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?

	Gary	Fort Wayne	Evansville	Terre Haute	South Bend
Gary	--	132	217	164	58
Fort Wayne	132	--	290	201	79
Evansville	217	290	--	113	303
Terre Haute	164	201	113	--	196
South Bend	58	79	303	196	--

Por el método de Kruskal,se tiene lo siguiente:

Iteración	Aristas Ordenadas	K	Costo
1	(1,5)	1	58
2	(2,5)	2	137
3	(4,3)	3	250
4	(1,2)	3	250
5	(1,4)	4	414
6	(5,4)	4	414
7	(2,4)	4	414
8	(1,3)	4	414
9	(2,3)	4	414
10	(5,3)	4	414

La distancia mínima entre las carreteras será de 414 millas.