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.