Redes De Petri
Páginas: 4 (834 palabras)
Publicado: 3 de junio de 2012
Índice
Modelos de redes de Petri: 2
Algoritmo de flujo máximo: 3
Teorema de flujo máximo y corte mínimo 3
Acoplamiento 4
Redes de petri: 5
Modelos de redes de Petri:
La RTPconsiste de un número (n) de sub-redes a cíclicas que modelan las relaciones de precedencia de los n trabajos asignados al sistema de manufactura. Los recursos se añaden como plazas que representancondiciones para el procesamiento de dichos trabajos. La RdP contiene plazas temporizadas y no temporizadas: las primeras modelan las operaciones de los trabajos, mientras que las segundas lo hacen conlas colas de almacenamiento temporal (buffers) localizadas antes de las estaciones
Algoritmo de flujo máximo:
Sea P una trayectoria del vértice a al z en una red G que satisface las siguientescondiciones:
a) Para cada arista (i, j) con orientación apropiada en P,
Fij<Cij.
b) Para cada artista ( i, j) con orientación inadecuada en P,
0<fij.
Sea
Δ= min X,
Donde Xconsiste en los números Cij-Fij, para aristas (i, j) con orientación apropiada en
PyFij, para aristas (i, j) con orientación inapropiada en P. defina
F*ij = Fi, j si (i, j) no está en P
Fi, j + Δsi (i, j) tiene orientación apropiada en P
Fi, j - Δ si (i, j) no tiene la orientación apropiada en P.
Entonces F* es un flujo cuyo valor es Δ mayor que el valor de F
Teorema de flujo máximoy corte mínimo
Un corte T es una selección cualquiera de nodos de una red tal que la fuente F está en T y el sumidero S no está en T. Vemos por lo tanto que S ∈ Tc.
Definición: Decimos que uncorte es mínimo si la capacidad tiene un valor mínimo.
Ejemplo. La capacidad del corte del ejemplo 1 es w (F, e) + w (f, h) + w(c, d) = 3 + 6 +5 = 14
Teorema. Si tenemos una red R con flujo f yun corte T.
Entonces si la igualdad del teorema anterior se cumple se tiene un flujo máximo y un corte mínimo. En este caso se tiene: f (i, j) = w (i, j) si i ∈ T, j NO∈ T y también f (i, j) = 0...
Modelos de redes de Petri: 2
Algoritmo de flujo máximo: 3
Teorema de flujo máximo y corte mínimo 3
Acoplamiento 4
Redes de petri: 5
Modelos de redes de Petri:
La RTPconsiste de un número (n) de sub-redes a cíclicas que modelan las relaciones de precedencia de los n trabajos asignados al sistema de manufactura. Los recursos se añaden como plazas que representancondiciones para el procesamiento de dichos trabajos. La RdP contiene plazas temporizadas y no temporizadas: las primeras modelan las operaciones de los trabajos, mientras que las segundas lo hacen conlas colas de almacenamiento temporal (buffers) localizadas antes de las estaciones
Algoritmo de flujo máximo:
Sea P una trayectoria del vértice a al z en una red G que satisface las siguientescondiciones:
a) Para cada arista (i, j) con orientación apropiada en P,
Fij<Cij.
b) Para cada artista ( i, j) con orientación inadecuada en P,
0<fij.
Sea
Δ= min X,
Donde Xconsiste en los números Cij-Fij, para aristas (i, j) con orientación apropiada en
PyFij, para aristas (i, j) con orientación inapropiada en P. defina
F*ij = Fi, j si (i, j) no está en P
Fi, j + Δsi (i, j) tiene orientación apropiada en P
Fi, j - Δ si (i, j) no tiene la orientación apropiada en P.
Entonces F* es un flujo cuyo valor es Δ mayor que el valor de F
Teorema de flujo máximoy corte mínimo
Un corte T es una selección cualquiera de nodos de una red tal que la fuente F está en T y el sumidero S no está en T. Vemos por lo tanto que S ∈ Tc.
Definición: Decimos que uncorte es mínimo si la capacidad tiene un valor mínimo.
Ejemplo. La capacidad del corte del ejemplo 1 es w (F, e) + w (f, h) + w(c, d) = 3 + 6 +5 = 14
Teorema. Si tenemos una red R con flujo f yun corte T.
Entonces si la igualdad del teorema anterior se cumple se tiene un flujo máximo y un corte mínimo. En este caso se tiene: f (i, j) = w (i, j) si i ∈ T, j NO∈ T y también f (i, j) = 0...
Leer documento completo
Regístrate para leer el documento completo.