Modelo de flojo Maximo y Minimo
Páginas: 6 (1446 palabras)
Publicado: 3 de diciembre de 2013
Modelo de Flujo Máximo
Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino.
[pic]
Características:
1. Todo el flujo a través de la red que se origina un nodo, llamado origen y termina en otro nodollamado destino.
2. Todos los nodos restantes son nodos de transbordo.
3. Solo está permitido el flujo a través de un arco en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad de ese arco.
4. El objetivo es maximizar la cantidad total del flujo del origen al destino. Esta cantidad esta medida en una de 2 formas equivalentes, que sonla cantidad que sale del origen o la cantidad que entra en el destino.
5. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:
a. El flujo es siempre positivo y con unidades enteras.
b. El flujo a través de un arco es menor o igual que la capacidad.
c. El flujo queentra en un nodo es igual al que sale de él.
En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:
[pic]
DIFERENCIAS ENTRE COSTO MINIMO Y COSTO MAXIMO
El origen y el destino de un problema de flujo máximo son análogos a los nodos de recursos y demanda en elproblema del flujo del costo mínimo. Estos son los únicos nodos que no cuentan con conservación de flujo (flujo de salida igual a flujos de entrada).Igual que los nodos de recursos, el origen genera el flujo. Igual que los nodos de demanda, el destino absorbe el flujo.
• En el de flujo máximo en objetivo es maximizar el flujo que sale del origen y entra en el destino en lugar de esacantidad.
• La segunda diferencia es que, mientras que el numero de nodos de recursos y el numero de nodos de demanda en un problema de costo mínimo pueden ser más que uno, puede haber solo un origen y solo un destino en un problema de flujo máximo.
Problema del Flujo Máximo
En una red con flujo de capacidades en los arcos, el problema es determinar el flujo máximo posible proveniente delos orígenes de forma tal de ahogar las capacidades de flujos de los arcos. Considere una red con m nodos y n arcos con un flujo simple de bienes. Denote el arco de flujo (i a j) como Xij. Asociamos cada arco a una capacidad de flujo, kij. En esta red, deseamos encontrar el flujo total máximo en la red, F, del nodo 1 al nodo m.
[pic]
Luego de resolver este problema de PL mediante el uso de LINDO(entre otros software), obtenemos los siguientes resultados:
Enviar 10 unidades de 1 a 2
Enviar 7 unidades de 1 a 3
Enviar 3 unidades de 2 a 6
Enviar 7 unidades de 2 a 4
Enviar 4 unidades de 3 a 6
Enviar 6 unidades de 3 a 5
Enviar 7 unidades de 4 a 7
Enviar 8 unidades de 5 a 7
Enviar 3 unidades de 6 a 3
Enviar 2 unidades de 6 a 5
Enviar 2 unidades de 6 a 7
El flujo máximo es F= 17unidades.
El Problema Dual de Flujo Máximo:
El problema dual para el ejemplo numérico anterior es:
Min 10Y12 + 10Y13 + Y23 + Y32 + 6Y26 + 4Y36 + 4Y63 + 8Y24
3Y64 + 3Y46 + 12Y35 + 2Y65 + 2Y56 + 8Y75 + 7Y47 + 2Y67
sujeto a:
X2 - X1 + Y12 ³ 0, X3 - X1 + Y13 ³ 0, X3 - X2 + Y23 ³ 0,
X3 - X2 + Y32 ³ 0, X6 - X2 + Y26 ³ 0, X6 - X3 + Y36 ³ 0,
X3 - X6 + Y63 ³ 0, X4 - X2 + Y24 ³ 0, X4 - X6 + Y64 ³ 0X6 - X4 + Y46 ³ 0, X5 - X3 + Y35 ³ 0, X5 - X6 + Y65 ³ 0,
X6 - X5 + Y56 ³ 0, X5 - X7 + Y75 ³ 0, X7 - X4 + Y47 ³ 0,
X7 - X6 + Y67 ³ 0, X1 - X7 ³1, y
Yij ³ 0, y todos los Xi son variables
Flujo Costo Mínimo
Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redes de transporte, redes de comunicación, sistema de vuelos de los aeropuertos, rutas de...
Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino.
[pic]
Características:
1. Todo el flujo a través de la red que se origina un nodo, llamado origen y termina en otro nodollamado destino.
2. Todos los nodos restantes son nodos de transbordo.
3. Solo está permitido el flujo a través de un arco en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad de ese arco.
4. El objetivo es maximizar la cantidad total del flujo del origen al destino. Esta cantidad esta medida en una de 2 formas equivalentes, que sonla cantidad que sale del origen o la cantidad que entra en el destino.
5. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:
a. El flujo es siempre positivo y con unidades enteras.
b. El flujo a través de un arco es menor o igual que la capacidad.
c. El flujo queentra en un nodo es igual al que sale de él.
En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:
[pic]
DIFERENCIAS ENTRE COSTO MINIMO Y COSTO MAXIMO
El origen y el destino de un problema de flujo máximo son análogos a los nodos de recursos y demanda en elproblema del flujo del costo mínimo. Estos son los únicos nodos que no cuentan con conservación de flujo (flujo de salida igual a flujos de entrada).Igual que los nodos de recursos, el origen genera el flujo. Igual que los nodos de demanda, el destino absorbe el flujo.
• En el de flujo máximo en objetivo es maximizar el flujo que sale del origen y entra en el destino en lugar de esacantidad.
• La segunda diferencia es que, mientras que el numero de nodos de recursos y el numero de nodos de demanda en un problema de costo mínimo pueden ser más que uno, puede haber solo un origen y solo un destino en un problema de flujo máximo.
Problema del Flujo Máximo
En una red con flujo de capacidades en los arcos, el problema es determinar el flujo máximo posible proveniente delos orígenes de forma tal de ahogar las capacidades de flujos de los arcos. Considere una red con m nodos y n arcos con un flujo simple de bienes. Denote el arco de flujo (i a j) como Xij. Asociamos cada arco a una capacidad de flujo, kij. En esta red, deseamos encontrar el flujo total máximo en la red, F, del nodo 1 al nodo m.
[pic]
Luego de resolver este problema de PL mediante el uso de LINDO(entre otros software), obtenemos los siguientes resultados:
Enviar 10 unidades de 1 a 2
Enviar 7 unidades de 1 a 3
Enviar 3 unidades de 2 a 6
Enviar 7 unidades de 2 a 4
Enviar 4 unidades de 3 a 6
Enviar 6 unidades de 3 a 5
Enviar 7 unidades de 4 a 7
Enviar 8 unidades de 5 a 7
Enviar 3 unidades de 6 a 3
Enviar 2 unidades de 6 a 5
Enviar 2 unidades de 6 a 7
El flujo máximo es F= 17unidades.
El Problema Dual de Flujo Máximo:
El problema dual para el ejemplo numérico anterior es:
Min 10Y12 + 10Y13 + Y23 + Y32 + 6Y26 + 4Y36 + 4Y63 + 8Y24
3Y64 + 3Y46 + 12Y35 + 2Y65 + 2Y56 + 8Y75 + 7Y47 + 2Y67
sujeto a:
X2 - X1 + Y12 ³ 0, X3 - X1 + Y13 ³ 0, X3 - X2 + Y23 ³ 0,
X3 - X2 + Y32 ³ 0, X6 - X2 + Y26 ³ 0, X6 - X3 + Y36 ³ 0,
X3 - X6 + Y63 ³ 0, X4 - X2 + Y24 ³ 0, X4 - X6 + Y64 ³ 0X6 - X4 + Y46 ³ 0, X5 - X3 + Y35 ³ 0, X5 - X6 + Y65 ³ 0,
X6 - X5 + Y56 ³ 0, X5 - X7 + Y75 ³ 0, X7 - X4 + Y47 ³ 0,
X7 - X6 + Y67 ³ 0, X1 - X7 ³1, y
Yij ³ 0, y todos los Xi son variables
Flujo Costo Mínimo
Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redes de transporte, redes de comunicación, sistema de vuelos de los aeropuertos, rutas de...
Leer documento completo
Regístrate para leer el documento completo.