Problema De Flujo De Costo Mínimo
Páginas: 3 (568 palabras)
Publicado: 7 de mayo de 2012
EL MODELO DE FLUJO DE COSTO MINIMO EN UNA RED (MCNFP)
El modelo de Flujo de Costo Mínimo en una Red se plantea de la manera siguiente
bi>0 si i es un nodo origen
bi<0 si i es un nododestino
bi=0 si i es un nodo de transbordo
Una condición necesaria para que el modelo tenga solución factible es que
bi=0, es decir, que el flujo total generado en los nodos origen sea igualal flujo total absorbido por los nodos destino.
Cuando esta condición no se cumple (problemas de transporte no balanceado en los que la oferta es diferente a la demanda) se generan nodosficticios que generen o que absorban flujo. Los costos asociados a los arcos que parten o llegan a estos nodos es cero.
Con frecuencia bi y uij son valores enteros. Las variables xij son variables enterasy no se requiere agregar esta condición al modelo (unimodularidad).
Con este modelo es posible plantear un problema de transporte, de transbordo, de flujo máximo y de camino más corto.
ELPROBLEMA DEL CAMINO MÁS CORTO EN UNA RED
El origen es un nodo con b1=1
El destino es un nodo con bn= -1
Los nodos restantes son nodos de transbordo
Como la red es no-dirigida cada arco sesustituye por un par de arcos dirigidos en dirección opuesta, excepto para el nodo origen y el nodo destino.
El costo cij es la distancia del arco (i,j)
Las variables tomarán valores 0 y 1dependiendo si se asignan al camino o no.
Veamos un ejemplo: la siguiente red indica los caminos posibles para llegar del nodo 1 al nodo 7. Los valores en los arcos indican la distancia entre cada nodo.15
5
8
2
10
18
50000
11
19
8
3
2664
10
4
6
1
7
min10x12+15x27+19x67+26x13+8x23+8x32+18x24+18x42+10x35+10x53+
+8x56+8x65+5x45+5x54+11x47
s.t.
x12+x13=1
-x27-x47-x67=-1
x27+x24+x23-x32-x42-x12=0
x32+x35-x23-x53-x13=0
x42+x47+x45-x24-x54=0
x53+x54+x56-x35-x45-x65=0...
El modelo de Flujo de Costo Mínimo en una Red se plantea de la manera siguiente
bi>0 si i es un nodo origen
bi<0 si i es un nododestino
bi=0 si i es un nodo de transbordo
Una condición necesaria para que el modelo tenga solución factible es que
bi=0, es decir, que el flujo total generado en los nodos origen sea igualal flujo total absorbido por los nodos destino.
Cuando esta condición no se cumple (problemas de transporte no balanceado en los que la oferta es diferente a la demanda) se generan nodosficticios que generen o que absorban flujo. Los costos asociados a los arcos que parten o llegan a estos nodos es cero.
Con frecuencia bi y uij son valores enteros. Las variables xij son variables enterasy no se requiere agregar esta condición al modelo (unimodularidad).
Con este modelo es posible plantear un problema de transporte, de transbordo, de flujo máximo y de camino más corto.
ELPROBLEMA DEL CAMINO MÁS CORTO EN UNA RED
El origen es un nodo con b1=1
El destino es un nodo con bn= -1
Los nodos restantes son nodos de transbordo
Como la red es no-dirigida cada arco sesustituye por un par de arcos dirigidos en dirección opuesta, excepto para el nodo origen y el nodo destino.
El costo cij es la distancia del arco (i,j)
Las variables tomarán valores 0 y 1dependiendo si se asignan al camino o no.
Veamos un ejemplo: la siguiente red indica los caminos posibles para llegar del nodo 1 al nodo 7. Los valores en los arcos indican la distancia entre cada nodo.15
5
8
2
10
18
50000
11
19
8
3
2664
10
4
6
1
7
min10x12+15x27+19x67+26x13+8x23+8x32+18x24+18x42+10x35+10x53+
+8x56+8x65+5x45+5x54+11x47
s.t.
x12+x13=1
-x27-x47-x67=-1
x27+x24+x23-x32-x42-x12=0
x32+x35-x23-x53-x13=0
x42+x47+x45-x24-x54=0
x53+x54+x56-x35-x45-x65=0...
Leer documento completo
Regístrate para leer el documento completo.