Planteamientos de problemas de optimización dinamica
https://sites.google.com/site/redesdeoptimizacionmac/home
lunes, 22 de octubre de 2012
miércoles, 10 de octubre de 2012
Biografia Ford y Fulkerson
Ford y Fulkernson
Lester Randolph Ford Jr. es un matemático americano, nació: 23 de Septiembre de 1927, de 84 años de edad, 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.
Delbert Ray Fulkerson (14/08/1924 - 01/10/1976)
Fue
un matemático que co-desarrolló el algoritmo de Ford-Fulkerson, uno de
los más conocidos algoritmos para resolver el problema de flujo máximo
en redes .
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 en 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.
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.
FUENTES
-Lester R. Ford. Recuperado el 23 de Septiembre de 2012. Disponible en: http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford
-Fulkerson. Recuperado el 23 de Septiembre de 2012. Disponible en: http://en.wikipedia.org/wiki/D._R._Fulkerson
FUENTES
-Lester R. Ford. Recuperado el 23 de Septiembre de 2012. Disponible en: http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford
-Fulkerson. Recuperado el 23 de Septiembre de 2012. Disponible en: http://en.wikipedia.org/wiki/D._R._Fulkerson
Biografía Floyd
Robert W. Floyd
Nació el 8 de Junio de 1936 en Nueva York, Estados Unidos de América. Floyd culminó bachillerato a los 14 años. Se graduó en laUniversidad 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.
FUENTE
-Robert Floyd. Recuperado el 23 de Septiembre del 2012. Disponible en: http://biografía.cine.hispavista.com/206240-robert-floyd.
-Robert Floyd. Recuperado el 23 de Septiembre del 2012. Disponible en: http://es.wikipedia.org/wiki/Robert_W._Fl
Biografia Dijkstra
Edsger Wybe Dijkstra
Dijkstra nació el 11 de mayo de 1930 en Rotterdam, Holanda, hijo
de un químico y una matemática. Estudió física
y matemáticas en la Universidad de Leyden, terminando en 1951.
Más tarde, realizó un doctorado en física teórica en la misma
universidad en 1956, seguido de un Ph.D. en 1959 en la Universidad de Amsterdam.
En 1952 comenzó a trabajar en el Centro Matemático de Amsterdam
donde aprendió a programar, siendo el primer programador en Holanda.
En 1962 pasó a ser profesor en la Universidad Tecnológica de Eindhoven hasta 1984. En paralelo, desde 1973
a 1984 fue investigador para Burroughs. Finalmente, en 1984
aceptó la cátedra Schlumberger en la Universidad de Texas en
Austin, hasta que se jubiló en 1999. Dijkstra
se casó en 1957 con Maria Debets (más conocida como Ria)
y tuvo tres hijos: Marcus, Femke y Rutger, el único que siguió
sus pasos en la computación.
Murió en Nuenen, Holanda, el 8 de Agosto de 2002, a causa de cáncer.
El trabajo de Dijkstra siempre se caracterizó por su elegancia
y simplicidad, sin comprometer el rigor de su investigación con
consideraciones económicas, políticas o administrativas.
Contaba el mismo que al preguntarle a su madre cuán difícil
eran las matemáticas, ella le contestó: "aprende todas las
fórmulas y que si alguna vez necesitaba
más de cinco líneas para demostrar algo, estaba en el
camino equivocado". En 1972 recibió el premio Turing, y su discurso
fue publicado en un artículo titulado The
Humble Programmer (el programador humilde) ese mismo año en
Communications of the ACM. >
>Sus Contribuciones
Dijkstra escribió más de 1300
artículos, pero indudablemente hay tres contribuciones cuyo
impacto está presente en numerosos ámbitos de la computación
moderna:
- Algoritmo para encontrar el camino más corto en un grafo: este fue
el primer problema de grafos que resolvió Dijkstra en 1956 y publicado
en 1959 por que en esa época un algoritmo era difícilmente
considerado un logro científico. Hoy en día, este algoritmo
ha sido usado como la base para protocolos de enrutamiento en Internet,
sistemas de posicionamiento global o simplemente para itinerarios de viaje.>
- El concepto de abrazo mortal (deadlock) y su solución a través
de semáforos y regiones de código con acceso exclusivo. Dijkstra
describió el problema con la cena de los famosos cinco filósofos
que sólo tenían cinco palillos para comer arroz (ver figura).
Si ellos no se ponían de acuerdo y tomaban un palillo cada uno,
creaban un deadlock
y morían de hambre pues se necesitaban
dos palillos para comer. Esta es la base de la programación concurrente
y una parte fundamental de cualquier sistema operativo.
- Su aporte a la programación estructurada. Dijkstra participó
en el comité que diseño Algol 60, el primer lenguaje de programación
estructurado, y lo promovió intensamente fomentando la verificación
formal de programas y la eliminación del goto. En este tema
fue autor y coautor de varios libros, además de su artículo
corto Go To statement considered
harmful (La instrucción go to es considerada dañina) publicado en Communications
of ACM en 1968, que es legendario.
FUENTE
-Dijkstra. Recuperado el 17 de Septiembre de 2012. Disponible en: http://users.dcc.uchile.cl/~rbaeza/inf/dijkstra.html
-Dijkstra. Recuperado el 17 de Septiembre de 2012. disponible en: http://miriamherz.blogspot.mx/2011/09/participacion-biografia-de-dijkstra.html
Participacion 2.7
Flujo Máximo
1.Para las redes de las siguientes figuras determine el flujo máximo de la fuente del sumidero. También encuentre un corte cuya capacidad mínima es igual al flujo máximo en la red.
Flujo Máximo = 45 Flujo Máximo =9 De S a 1: 20 De S a 1: 6
De S a 2: 10 De S a 2: 3
De S a 3: 15 De 1 a 2: 1
De 1 a t: 20 De 1 a 3: 5
De 2 a t: 10 De 2 a 4: 7 De 4 a t: 15 De 3 a 2: 3
De 3 a t: 2
De 4 a t: 7
2. Cinco camiones entregan siete tipos de paquetes. Hay tres paquetes de cada tipo, y las capacidades de los cinco camiones son 6, 4, 5, 4 y 3 paquetes, respectivamente. Prepare un problema de flujo máximo que se puede usar para determinar si pueden cargarse los paquetes de modo que ningún camión lleve dos paquetes del mismo tipo.
jueves, 4 de octubre de 2012
Participacion 2.6
Método de Floyd
a) Ruta más corta ¿Qué problemática tiene el problema? Ubica al menos una ruta
para k=1 no hay valores para "i", asi que pasamos al siguiente
k=2
i=1, 3 j= 4, 5
C14=min{infinito,3+4}=7 Z14=Z24
C15=min{infinito,3+1}=4 Z15=Z25
C34=min{infinito,2+4}=6 Z34=Z34
C35=min{infinito,2+1}=3 Z35=Z35
k=3
i= 1,4 j=2,4,5
C12=min{3,-2+2}=0 Z12=Z32
C14=min{7,-2+6}=4 Z14=Z34
C15=min{4,-2+3}=1 Z15=Z35
C42=min{infinito,3+2}=5 Z42=Z32
C44=min{0,3+6}=---
C45=min{}0,3+3=---
z=4
i=1,2,3 j=2,3
C12=min{0,4+5}=---
C13=min{-2,4+3}=---
C22=min{0,4+5}=---
C23=min{7,4+3}=---
C32=min{2,6+5}=---
C33=min{0,6+3}=---
para k=5 no hay valores para "i", asi que ya tenemos nuestras matrices:
Participacion 2.4
Problema de Ruta Más Corta
(problema tipo mochila)
4) La NASA quiere saber cuantos de los tres tipos de objetos deben ser traídos a bordo del
trasbordador espacial. El peso y beneficio se muestra en la siguiente tabla. Puede llevar un
máximo de 15 libras.
trasbordador espacial. El peso y beneficio se muestra en la siguiente tabla. Puede llevar un
máximo de 15 libras.
| Objeto | Beneficio | Peso (libras) |
| 1 | 10 | 3 |
| 2 | 15 | 4 |
| 3 | 17 | 5 |
Aplicando el algoritmo de Dijkstra, tenemos que la solución es: (1,15)-(2,12)-(3,0)-(4,0)-(t)
Lo cual nos dice que llevará 1 objeto1 y 3 objetos2, obteniendo, así, un beneficio de 55.
miércoles, 3 de octubre de 2012
Participación 2.2
Problema de árbol de peso mínimo
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?
¿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 | -- |
Suscribirse a:
Entradas (Atom)