martes, 18 de octubre de 2011

U2. Participación 3


2. 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

Se brinda la solución del problema realizado por el método de Dijkstra.










La probabilidad de una buena transmisión es de 0.523 pasando por los nodos 1-2-4-3-6-7.

U2. Participación 2


4).- Determine la trayectoria más corta del nodo 1 al nodo 5.



Aplicando el algoritmo de Dijkstra:














La ruta mas corta obtenida es: 1,2,5 con un costo mínimo  de 14.



U2. Participación 1


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
--

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 es de 414 millas.

Actividad2. Hotpotatoes

Redes de Optimización.
Actividad basada en la unidad II.


https://docs.google.com/leaf?id=0B3HtoF2vEZdCYzY1MjIwZDAtMDMyOS00N2FjLTliNzMtYzJlZjQwNzAxZDE1&hl=en_US

Biografías de Ford y Fulkerson




Lester Randolph Ford, Jr.

Vida:
Nació el 23 de septiembre 1927, en Houston. Él es el hijo del matemático Lester R. Ford, Sr.

Educación y Trabajo:
Es un matemático estadounidense que se especializa en problemas de flujo de red. Se 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. 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. Trabajó en RAND CORPORATION.

Aportaciones:
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.
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, Con Richard Bellman , Ford también desarrolló el algoritmo de Bellman-Ford para encontrar los caminos más cortos en los gráficos que tienen bordes negativamente ponderado.

Referencias:
http://en.wikipedia.org/wiki/L._R._Ford,_Jr.
http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford


Delbert Ray Fulkerson


Vida:

Nació el 14 de agosto de 1924 en Estados Unidos  y murió el 10 de enero, 1976 USA.

Educación y trabajo:

Realizo sus estudios universitarios en la Universidad Southern Illinois fueron interrumpidos por el servicio militar durante la Segunda Guerra Mundial. Después de la guerra regresó para completar sus estudios en la SIU y se graduó en matemáticas en el estudio de la Universidad de Wisconsin. En 1951, al término de su doctorado, Ray se unió al departamento de matemáticas de la Rand Corporation. Allí, comenzó una carrera ilustre de la investigación y la erudición. Ray dejó Rand en 1971 y llegó a Cornell como el profesor Maxwell Upson de Ingeniería. Permaneció en Cornell hasta su muerte en 1976.En 1956, su importante artículo científico fue publicado. Desde 1979, la Sociedad de Programación Matemática (MPS) y la American Mathematical Society (AMS) otorgan cada tres años el Premio Fulkerson, para aquellos matemáticos que hayan creado artículos importantes en el área de la matemática discreta

Aportaciones:

En 1956, su importante artículo científico fue publicado. Desde 1979, la Sociedad de Programación Matemática (MPS) y la American Mathematical Society (AMS) otorgan cada tres años el Premio Fulkerson, para aquellos matemáticos que hayan creado artículos importantes en el área de la matemática discreta.
Desarrolló  junto con Lester Randolph Ford, Jr., el Algoritmo de Ford-Fulkerson, siendo éste uno de los algoritmos más utilizados para computar el flujo máximo en una red de flujo.

Refrencias:

http://es.wikipedia.org/wiki/D._R._Fulkerson http://www.orie.cornell.edu/orie/research/seminars/fulkerson/fulkerson-bio.cfm