Proyecto final

Ver Proyecto

Tarea 3-Aplicación de la Programación Entera

Ver Presentación

Tarea 2-Redes de Optimización

Delbert Ray Fulkerson (Biografía)

[Imagen de Delbert Fulkerson].Recuperada de https://en.wikipedia.org/wiki/D._R._Fulkerson

*Nació el 14 de agosto de 1924 

*Murió el 10 de enero de 1976*

* Fue un matemático estadounidense que desarrolló como co-autor, y junto con Lester Randolph Ford, Jr., el Algoritmo de Ford-Fulkerson, uno de los algoritmos más utilizados para computar el flujo máximo en una red de flujo.

*Fulkerson recibió su Ph.D. en la Universidad de Wisconsin-Madison en 1951. 

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

Referencias:

Wikipedia. Delbert Ray Fulkerson.  Recuperado el 21 de Abril de 2018, de Wikipedia Sitio web:https://en.wikipedia.org/wiki/D._R._Fulkerson

Robert W. Floyd (Biografía)

[Imagen de Robert W. Floyd].Recuperada de https://inteligencia2010.wordpress.com/historia/

*Nació el 8 de junio de 1936 en New York.

*Murió el 25 de septiembre de 2001

* Fue un prominente científico estadounidense en informática.

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

*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

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

*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

Referencias:

Wikipedia. Robert W. Floyd.  Recuperado el 19 de Abril de 2018, de Wikipedia Sitio web:https://es.wikipedia.org/wiki/Robert_W._Floyd

Lester Ford (Biografía)

[Imagen de Lester Ford].Recuperada de https://angelberh7.wordpress.com/2014/10/08/biografia-de-lester-randolph-ford-jr/

*Nacio el 14 de agosto de 1924 

*Murió el 10 de enero de 1976

* Fue un matemático estadounidense que desarrolló como co-autor, y junto con Lester Randolph Ford, Jr., el Algoritmo de Ford-Fulkerson, uno de los algoritmos más utilizados para computar el flujo máximo en una red de flujo.

*Fulkerson recibió su Ph.D. en la Universidad de Wisconsin-Madison en 1951. 

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

Referencias:

Grafos – software para la construcción, edición y análisis de grafos. Lester Randolph Ford Jr. Recuperado el 19 de Abril de 2018, de Sitio web: http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford

Edsger Wybe Dijkstra (Biografía)

[Imagen de Dijkstra].Recuperada de https://es.wikipedia.org/wiki/Edsger_Dijkstra

*Nació en Róterdam, Países Bajos el 11 de mayo de 1930

*Murió en Nuenen, Países Bajos el 6 de agosto de 2002

* Fue un científico de la computación de los Países Bajos.

*Entre sus contribuciones a las ciencias de la computación está la solución del problema del camino más corto, también conocido como el algoritmo de Dijkstra, la notación polaca inversa y el relacionado algoritmo shunting yard, el algoritmo del banquero y la construcción del semáforo para coordinar múltiples procesadores y programas.

*El algoritmo de Dijkstra es usado en la ruta más corta primero (SPF) que es usado en el protocolo de enrutamiento Open Shortest Path First (OSPF). 

*También se le debe la autoría de la expresión «Crisis del software», aparecida en su libro The Humble Programmer y usada ampliamente en la famosa reunión de la OTAN de 1968 sobre desarrollo del software. 

*Recibió el Premio Turing en 1972.

Referencias:

Wikipedia. Edsger Dijkstra. Recuperado el 19 de Abril de 2018, de http://es.wikipedia.org/wiki/Edsger_Dijkstra

Participación 11-Redes de Actividad

Unidad 2 Redes de Optimización

Participación 11

Redes de Actividad Subir el ejercicio 2 al blog.

2.- Considere la red de proyecto para cada actividad, se dan las estimaciones de a, b y m en la tabla 18. Determine la trayectoria crítica para esta red, el tiempo libre total para cada actividad, el tiempo libre para cada actividad y la probabilidad de que el proyecto se complete en 40 días. También prepare el PL que se pueda utilizar para encontrar la trayectoria crítica.

Tabla 18
actividad	a	b	m
(1,2)	4	8	6
(1,3)	2	8	4
(2,4)	1	7	3
(3,4)	6	12	9
(3,5)	5	15	10
(3,6)	7	18	12
(4,7)	5	12	9
(5,7)	1	3	2
(6,8)	2	6	3
(7,9)	10	20	15
(8,9)	6	11	9

Resolviendo el problema

Obteniendo la media y la desviación estándar:

actividad	a	b	m	t	Desv.
(1,2)	4	8	6	6	0.67
(1,3)	2	8	4	4.3	1
(2,4)	1	7	3	3.3	1
(3,4)	6	12	9	9	1
(3,5)	5	15	10	10	1.67
(3,6)	7	18	12	12.2	1.83
(4,7)	5	12	9	8.83	1.16
(5,7)	1	3	2	2	.3
(6,8)	2	6	3	3.3	.67
(7,9)	10	20	15	15	1.67
(8,9)	6	11	9	8.83	.83

Realizando el método de revisión hacia adelante y hacia atras:

 

Resultados:

*Tiempo total del proyecto (media) = 37.1
*La ruta crítica queda : 1-3-4-7-9
*Desviación de: 4.83
Los tiempos libres para cada actividad son:
(1,2) tiene un tiempo libre de 4                      (5,7) tiene un tiempo libre de 5.8
(2,4) tiene un tiempo libre de 4                      (6,8) tiene un tiempo libre de 8.5
(3,5) tiene un tiempo libre de 5.8                   (8,9) tiene un tiempo libre de8.5
(3,6) tiene un tiempo libre de 8.5

Obteniendo la probabilidad de que el proyecto se termine en 40 días:
Z= (40-37.1) / 4.83 = 0.60
P(x < 0.60) = 72.5%

*El Modelo de Programación Lineal es:
Min Z = X9 - X₁
s.a.       X2 ≥ X1 + 6
            X3 ≥ X1 + 4.3
            X4 ≥ X2 + 3.3
            X4 ≥ X3 + 9
            X5 ≥ X3 + 10
            X6 ≥ X3 + 12.1
            X7 ≥ X4 + 8.8
            X7 ≥ X5 + 2
            X8 ≥ X6 + 3.3
            X9 ≥ X7 + 15
            X9 ≥ X8 + 8.8
         X_i ≥ 0

Participación 6-Flujo máximo

Unidad 2 Redes de Optimización

Participación 6

Flujo Máximo Resuelve el 1 ejercicio y súbelo a tu blog

1.    La aerolínea Fly-by-Night está considerando realizar tres vuelos. Los ingresos de cada vuelo y los aeropuertos utilizados por cada vuelo se muestran en la siguiente tabla:

Vuelo	Ingreso ($)	Aeropuerto utilizado
1	900	1 y 2
2	600	2
3	800	2 y 3

     Cuando Fly-by-Night utiliza un aeropuerto, la compañía debe pagar las siguientes cuotas de aterrizaje (sin importar el número de vuelos que usen el aeropuerto): aeropuerto 1, $300; aeropuerto 2, $700; aeropuerto 3, $500. Así, si se hacen los vuelos 1 y 3, se obtendrá una ganancia de 900 + 800 – 300 -700 -500= $200. Muestre que la siguiente red

(ganancia máxima)=(ingresos totales de los vuelos) – (capacidad de corte mínimo). Explique cómo se podría usar este resultado para ayudar a Fly-by-Night a maximizar las ganancias (incluso si tiene cientos de vuelos posibles. [Sugerencia: considere cualquier conjunto de vuelos F (digamos, vuelos 1 y 3). Considere el corte que corresponde al sumidero, los nodos asociados con los vuelos que no están en F y los nodos asociados con los vuelos que no están en F y los nodos asociados con los aeropuertos que no utiliza F. Muestre que (capacidad de este corte) = (ingresos de los vuelos que no están en F)+(Costos asociados en los aeropuertos utilizados por F).]

Aplicando Flujo máximo

z=1500

Por lo tanto el Flujo Max=1500

Para resolver lo de la ganancia máxima se tiene que encontrar un corte que sea igual al flujo máximo.

N={A1,A2,A3,SO,F1,F2,F3}

Ñ={Si}

C(N,Ñ)=1500

Ganancia Max=Ingresos totales de vuelos-Capacidad de corte mínima

Ganancia Max=2300-1500

Ganancia Max=800

Este resultado implica que por cada vuelo las ganancias obtenidas son de 800 claro podría mantenerlas siempre y cuando se hagan vuelos constantes en los aeropuertos y así pagar menos lo de las pistas de los aeropuertos.