Flujo Máximo (Participación 6)

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).]

1.- Obtenemos el Flujo Máximo con el algoritmo de Ford y Fulkerson

 

Por lo tanto el Flujo Max=1500

Para resolver lo de la ganancia máxima hay 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 vuelvos constantes en los aeropuertos y así pagar menos lo de las pistas de los aeropuertos.

Ruta Más Segura (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

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

El enunciado habla claramente de un problema de Ruta Más Segura, así que la red nos queda de la siguiente forma: 

 

Ahora aplicaremos el método de Dijkstra el cuál se trata de etiquetar permanentemente los nodos hasta encontrar la ruta más segura, además como estamos maximizando la probabilidad de una buena trasmisión cambiamos los criterios del método tomando las probabilidades más grandes.

Solución:

Ruta: 1-2-4-3-6-7 

Con una probabilidad de 0.5233