Capítulo 4
Páginas: 21 (5027 palabras)
Publicado: 18 de noviembre de 2015
CAPÍTULO 4
4. ALGORITMO DE FLUJO DE COSTO MÍNIMO
4.1. Planteamiento del Problema de Flujo de Costo Mínimo
Sea G=(N,A) una red dirigida con un costo y una capacidad asociada con cada arco A. El problema que se plantea es:
Minimizar
sujeto a
Se representará con C la mayor magnitud de los costos asociados a los arcos y con U la mayor magnitud de la demanda u oferta dealgún arco o a la capacidad finita de dicho arco.
Se supondrá que el límite inferior de capacidad de cada arco , es cero. Además se harán las siguientes suposiciones:
1.-Todos los costos, ofertas, demandas y capacidades de los arcos son enteros.
2.-La red es dirigida
3.-Las ofertas y las demandas de los nodos satisfacen la condición y el problema de flujo de costo mínimo posee una soluciónfactible
4.- Supondremos que la red posee una ruta con una capacidad ilimitada entre cada par de nodos de los arcos que la componen.
5.-Todos los costos de los arcos son no negativos.
Los algoritmos a ser analizados emplean el concepto de redes residuales. En tales redes se ha reemplazado cada arco por dos arcos y . El arco posee un costo y una capacidad residual , y el arco tiene un costoy una capacidad residual . La red residual está compuesta de los arcos que posean una capacidad residual positiva.
4.2. Algoritmo de Descomposición de Flujo
En la formulación de problemas de flujo en redes existen dos formas de definir el flujo, la primera es definiendo el flujo sobre los arcos y la segunda definiendo el flujo sobre rutas y ciclos.
Para analizar la definición deflujo sobre arcos, empleamos el vector que satisface las siguientes restricciones:
donde,
Se observa que en este modelo hemos reemplazado la oferta/demanda , por el término , al que denominaremos como el desequilibrio del nodo i. Este término representa la diferencia entre el flujo que llega al nodo i y el flujo que sale del nodo. Por lo tanto si , se dice que i es un nodo de exceso. Casocontrario, si diremos que i es un nodo de déficit. Si afirmaremos que i es un nodo balanceado. La formulación del problema sobre flujos en rutas y ciclos, comienza con la enumeración de todas las rutas dirigidas P, entre algún par de nodos y de todos los ciclos dirigidos en la red. Al conjunto de todas las P, lo denotaremos con P y al conjunto de todos los ciclos W con W. Las variables dedecisión en esta formulación son el flujo sobre la ruta P, f(P) y el flujo sobre el ciclo W f(W). Estas variables están definidas para todos los elementos de P y W.
El flujo sobre el arco , es igual a la suma de los flujo f(P) y f(w) de todos las rutas y ciclos que contienen al arco . De manera formal definiremos a δij(P) igual a 1 si la ruta P contiene al arco y 0 sino lo contiene, y aδij(W) igual a 1 si el ciclo W contiene al arco y 0 sino lo contiene. Por lo tanto:
En relación a este razonamiento se establece el siguiente teorema:
4.2.1. Teorema de Descomposición de Flujo
Cada flujo en una ruta y en un ciclo tiene una única
representación como flujo no negativo sobre un arco. Inversamente cada flujo no negativo puede ser representadocomo un flujo sobre una ruta y un ciclo, aunque no necesariamente de manera única, con las siguientes propiedades:
a) Cada ruta dirigida con flujo positivo conecta un nodo de déficit con un nodo de exceso.
b) Siendo n el número de nodos de una red y m el número de arcos, a lo sumo n+m rutas y ciclos tiene un flujo no nulo, de tal cantidad, a lo sumo m ciclos tienen flujo no nulo.4.2.1.1. Prueba
La demostración consistirá en una prueba algorítmica de cómo descomponer un flujo sobre arcos en flujo sobre rutas y ciclos. Para lo cual supongamos la existencia de un arco que lleva una cantidad de flujo positiva desde un nodo de déficit i0, hacia otro nodo i1. Nos detenemos si i1 es un nodo de exceso, caso contrario existe otro arco con un flujo positivo. Este proceso es...
CAPÍTULO 4
4. ALGORITMO DE FLUJO DE COSTO MÍNIMO
4.1. Planteamiento del Problema de Flujo de Costo Mínimo
Sea G=(N,A) una red dirigida con un costo y una capacidad asociada con cada arco A. El problema que se plantea es:
Minimizar
sujeto a
Se representará con C la mayor magnitud de los costos asociados a los arcos y con U la mayor magnitud de la demanda u oferta dealgún arco o a la capacidad finita de dicho arco.
Se supondrá que el límite inferior de capacidad de cada arco , es cero. Además se harán las siguientes suposiciones:
1.-Todos los costos, ofertas, demandas y capacidades de los arcos son enteros.
2.-La red es dirigida
3.-Las ofertas y las demandas de los nodos satisfacen la condición y el problema de flujo de costo mínimo posee una soluciónfactible
4.- Supondremos que la red posee una ruta con una capacidad ilimitada entre cada par de nodos de los arcos que la componen.
5.-Todos los costos de los arcos son no negativos.
Los algoritmos a ser analizados emplean el concepto de redes residuales. En tales redes se ha reemplazado cada arco por dos arcos y . El arco posee un costo y una capacidad residual , y el arco tiene un costoy una capacidad residual . La red residual está compuesta de los arcos que posean una capacidad residual positiva.
4.2. Algoritmo de Descomposición de Flujo
En la formulación de problemas de flujo en redes existen dos formas de definir el flujo, la primera es definiendo el flujo sobre los arcos y la segunda definiendo el flujo sobre rutas y ciclos.
Para analizar la definición deflujo sobre arcos, empleamos el vector que satisface las siguientes restricciones:
donde,
Se observa que en este modelo hemos reemplazado la oferta/demanda , por el término , al que denominaremos como el desequilibrio del nodo i. Este término representa la diferencia entre el flujo que llega al nodo i y el flujo que sale del nodo. Por lo tanto si , se dice que i es un nodo de exceso. Casocontrario, si diremos que i es un nodo de déficit. Si afirmaremos que i es un nodo balanceado. La formulación del problema sobre flujos en rutas y ciclos, comienza con la enumeración de todas las rutas dirigidas P, entre algún par de nodos y de todos los ciclos dirigidos en la red. Al conjunto de todas las P, lo denotaremos con P y al conjunto de todos los ciclos W con W. Las variables dedecisión en esta formulación son el flujo sobre la ruta P, f(P) y el flujo sobre el ciclo W f(W). Estas variables están definidas para todos los elementos de P y W.
El flujo sobre el arco , es igual a la suma de los flujo f(P) y f(w) de todos las rutas y ciclos que contienen al arco . De manera formal definiremos a δij(P) igual a 1 si la ruta P contiene al arco y 0 sino lo contiene, y aδij(W) igual a 1 si el ciclo W contiene al arco y 0 sino lo contiene. Por lo tanto:
En relación a este razonamiento se establece el siguiente teorema:
4.2.1. Teorema de Descomposición de Flujo
Cada flujo en una ruta y en un ciclo tiene una única
representación como flujo no negativo sobre un arco. Inversamente cada flujo no negativo puede ser representadocomo un flujo sobre una ruta y un ciclo, aunque no necesariamente de manera única, con las siguientes propiedades:
a) Cada ruta dirigida con flujo positivo conecta un nodo de déficit con un nodo de exceso.
b) Siendo n el número de nodos de una red y m el número de arcos, a lo sumo n+m rutas y ciclos tiene un flujo no nulo, de tal cantidad, a lo sumo m ciclos tienen flujo no nulo.4.2.1.1. Prueba
La demostración consistirá en una prueba algorítmica de cómo descomponer un flujo sobre arcos en flujo sobre rutas y ciclos. Para lo cual supongamos la existencia de un arco que lleva una cantidad de flujo positiva desde un nodo de déficit i0, hacia otro nodo i1. Nos detenemos si i1 es un nodo de exceso, caso contrario existe otro arco con un flujo positivo. Este proceso es...
Leer documento completo
Regístrate para leer el documento completo.