Flujo maximo y flujo minimo
Páginas: 7 (1558 palabras)
Publicado: 7 de diciembre de 2010
INSTITUTO TECNOLOGICO DE CIUDAD JUAREZ
EVALUACION UNIDAD 5
Problemas del flujo máximo y del costo mínimo
EQUIPO:
ARREOLA PONCE. LAURA ANGELICA
SOTO ARREOLA. MARGARITA
ORNELAS COLON. EDGAR DAMIAN
[pic]
CD. JUAREZ CHIHUAHUA A 29 DE NOVIEMBRE DEL 2010
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. Cadaarco 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 nodo llamado destino.
2. Todos los nodos restantes son nodos de transbordo.
3. Solo está permitido el flujo a travésde 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 son la cantidad que sale del origen o la cantidad que entra en el destino.
5. Los arcos tienen una capacidad máxima deflujo, 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 que entra 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, seañ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 el problema del flujo del costo mínimo. Estos son los únicos nodos que no cuentan con conservación de flujo (flujo de salidaigual 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 esa cantidad.
• La segunda diferencia es que, mientras que el numero de nodos de recursos y el numero de nodos de demanda en unproblema 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 de los orígenes de forma tal de ahogar las capacidades de flujos de los arcos. Considere una red con m nodos y n arcos con unflujo 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
Enviar3 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= 17 unidades.
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 ³ 0
X6 - X4 + Y46 ³ 0, X5 - X3 + Y35 ³ 0, X5 - X6 + Y65 ³ 0,
X6 - X5 + Y56 ³ 0, X5 - X7 + Y75 ³ 0, X7 - X4 + Y47 ³ 0,
X7 -...
EVALUACION UNIDAD 5
Problemas del flujo máximo y del costo mínimo
EQUIPO:
ARREOLA PONCE. LAURA ANGELICA
SOTO ARREOLA. MARGARITA
ORNELAS COLON. EDGAR DAMIAN
[pic]
CD. JUAREZ CHIHUAHUA A 29 DE NOVIEMBRE DEL 2010
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. Cadaarco 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 nodo llamado destino.
2. Todos los nodos restantes son nodos de transbordo.
3. Solo está permitido el flujo a travésde 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 son la cantidad que sale del origen o la cantidad que entra en el destino.
5. Los arcos tienen una capacidad máxima deflujo, 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 que entra 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, seañ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 el problema del flujo del costo mínimo. Estos son los únicos nodos que no cuentan con conservación de flujo (flujo de salidaigual 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 esa cantidad.
• La segunda diferencia es que, mientras que el numero de nodos de recursos y el numero de nodos de demanda en unproblema 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 de los orígenes de forma tal de ahogar las capacidades de flujos de los arcos. Considere una red con m nodos y n arcos con unflujo 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
Enviar3 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= 17 unidades.
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 ³ 0
X6 - X4 + Y46 ³ 0, X5 - X3 + Y35 ³ 0, X5 - X6 + Y65 ³ 0,
X6 - X5 + Y56 ³ 0, X5 - X7 + Y75 ³ 0, X7 - X4 + Y47 ³ 0,
X7 -...
Leer documento completo
Regístrate para leer el documento completo.