Modelos de redes

MODELOS DE REDES

Modelos de redes son utilizados porque pueden aplicarse de forma rápida.

Problemas de programación entera pueden formularse como modelo de redes obteniendo soluciones enteras sin necesidad de restricciones adicionales, aumentando la eficiencia y reduciendo el tiempo consumido por los algoritmos clásicos de programación lineal

No importando el tamaño del problema planteando según su estructura matemática se pueden resolver por pequeños algoritmos.

Terminología

Una red es un conjunto de puntos y líneas que conectan pares de puntos. Los puntos se llaman nodos o vértices y las líneas se llaman arcos o aristas, estos pueden tener una dirección asociada, en este caso se denominan arcos dirigidos.

Flujo es el valor que se le asigna a un arco que conecta dos nodos.

Para nombrar el arco se pone primero el nodo de donde viene y luego el nodo hacia dónde va.

Por ejemplo, si el flujo sólo va desde el nodo C hacia el nodo D, entonces el arco se llama CD y no DC.

Una trayectoria entre 2 nodos es una sucesión de arcos distintos que conectan estos nodos.

Por ejemplo, una trayectoria que conecta al nodo A con el nodo G es AC-CE-EG.

Una trayectoria dirigida desde el nodo i al nodo j es una sucesión de arcos cuya dirección es hacia el nodo j, de manera que el flujo del nodo i al nodo j a través de esta trayectoria es factible

Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección ( si la tiene) puede ser hacia o desde el nodo j.

Ciclo es una trayectoria que comienza y termina en un mismo nodo.

Ciclo dirigido cuando está formado por una trayectoria dirigida.

Ciclo no dirigido cuando la trayectoria que lo conforma es no dirigida.

La cantidad máxima de flujo que puede circular en un arco dirigido es llamada capacidad del arco.

El nodo que tiene la propiedad de que su flujo que sale es mayor que el flujo que entra en el se le llama nodo fuente o nodo de origen. Por el contrario, si su flujo que sale es menor que el flujo que entra a él se le llama nodo demanda o nodo destino. Si el flujo que entra es igual al flujo que sale, entonces se le llama nodo de trasbordo o nodo intermedio.

Árbol es una serie de nodos conectados que no contiene ciclos.

Árbol de expansión es un árbol que conecta todos los nodos de la red contiene n-1 arcos, donde n es el número de nodos.

REDES DE PETRI

Las PN se componen de cuatro partes:

• Un conjunto de nodos.

• Un conjunto de transiciones.

• Una función de entrada y

• Una función de salida.

Las funciones de entrada y salida relacionan a los nodos y a las transiciones. La función de entrada es un mapeo de una transición tj a una colección de nodos conocidos como los nodos de entrada de una transición. La estructura de una PN es definida por los nodos, las transiciones, la función de entrada y la función de salida.

Definición: La estructura de la PN P=(P,T,I,O) donde:}

P={p1,p2,…,pn} es un conjunto finito de nodos, con n³ 0.

T={t1,t2,…,tm} es un conjunto finito de transiciones con m³ 0.

PÇ T= Æ

I,O: T ® P

Una marca U es una característica de la PN, marca U es una asignación de tokens a la PN. Un token es un concepto primitivo de una PN, un número de ellos reside en los nodos y se mueve entre ellos; los tokens son la parte dinámica de la PN, su número puede variar entre nodos y son los que determinan la situación de la red en un momento determinado.

Definición: Una marca U de una PN P= (P, T, I, O) es una función U: P ® N.

Es decir el nodo pi tiene U (pi) tokens.

La PN puede ser considerada también como un modelo de flujo de información, en donde el comportamiento dinámico de los tokens representan el flujo. Dicho de otra manera la información depende de lo que la PN esta modelando.

Representación gráfica de una red de Petri.

La representación gráfica de una PN es importante porque al observar el modelo del sistema en forma gráfica y observar cómo cambia de un estado a otro puede mantener la atención y dar una perspectiva más clara a quién esté analizando el problema.

Definición: Una gráfica G de una PN P=(P,T,I,O) es una gráfica múltiple bipartita dirigida G=(V,A) donde V={ v1, v2, …, vn} es

...