Cadenas De Markov

INTRODUCCION

Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redes de transporte, redes de comunicación, sistema de vuelos de los aeropuertos, rutas de navegación de los cruceros, estaciones de bombeo que transportan fluidos a través de tuberías, rutas entre ciudades, redes de conductos y todas aquellas situaciones que puedan representarse mediante una red donde los nodos representan las estaciones o las ciudades, los arcos los caminos, las líneas aéreas, los cables, las tuberías y el flujo lo representan los camiones, mensajes y fluidos que pasan por la red. Con el objetivo de encontrar la ruta mas corta si es una red de caminos o enviar el máximo fluido si es una red de tuberías.

Cuando se trata de encontrar el camino más corto entre un origen y un destino, la técnica, algoritmo o el modelo adecuado es el de la ruta más corta; aunque existen otros modelos de redes como el árbol de expansión mínima, flujo máximo y flujo de costo mínimo cada uno abarca un problema en particular. En este trabajo se mencionan los modelos de redes existentes y los problemas que abarca cada uno de ellos, además se describen los algoritmos que aplican estos modelos para encontrar la solución optima al problema. Utilizando la terminología utilizada para representarlos como una red.

OPTIMIZACIÓN DE REDES

La importancia del análisis de flujo de redes, en los últimos años ha crecido de una manera progresiva en todos los campos de la planificación; de procesos tareas y recursos tanto económicos como físicos y del tiempo de los proyectos que requieren de este tipo de planificación.

La aplicación de estos tipos de modelos tiene infinidades campos de acción en los diferentes proyectos de inversión tales como:

⦁ En los proyectos de diseños de tuberías de acueducto, gas natural, electrificación, vías, tanto férreas como carrete hables.

⦁ En la determinación del camino más cortó entre dos lugares o ciudades de acuerdo a una red existente.

⦁ En la determinación de las capacidades máximas que deben fluir a través de una red, de un recurso especifico.

⦁ La determinación del programa de flujo de costo mínimo de los campos de origen a los centros de distribución de un recurso especial.

Un estudio de esta lista representativa, revela que los problemas de optimización de redes se pueden representar en términos generales a través de los siguientes modelos.

⦁ Modelo del flujo máximo

⦁ Modelo de la ruta más corta.

⦁ Modelo del árbol de extensión mínima.

⦁ Modelo de red de capacidad de costo mínimo.

⦁ Modelo de la ruta critica.

⦁ Modelo de la técnica de evaluación y revisión de proyectos (PERT.

Para la comprensión de los diferentes modelos, se deben tener en cuenta las siguientes definiciones.

DEFINICIÓN DE RED. Es un conjunto de nodos conectados por arcos o ramas, a veces los nodos reciben el nombre de “vértices” y los ramales de “arcos”.

CADENA:Una cadena es una secuencia de ramales que conectan dos nodos que al especificarles dirección forman lo que se llama un camino o ruta.

RED SIMÉTRICA: Significa que un vértice “x” esta conectado a uno “y”; entonces “y”, esta conectado a “x”.

RED ASIMÉTRICA: Significa que un vértice “x” esta conectado a uno “y”; entonces “y”, no esta conectado a “x”.

CAPACIDAD: Es el flujo que circula por una determinada red y puede ser finita o infinita.

RAMA DIRIGIDA U ORIENTADA: Cuando se permite el paso de un flujo positivo en una determinada dirección y cero en la dirección opuesta.

TRAYECTORIA: Es una secuencia de ramas que conectan dos nodos sin considerar su orientación de las demás ramas individuales.

LASO O CICLO: Se presenta cuando un nodo se conecta consigo mismo.

LASO DIRIJIDO U CIRCUITO: Es un lazo donde todas las ramas tienen las mismas dirección u orientación.

PROBLEMA DEL FLUJO MÁXIMO

Este problema determina el estado factible de flujos a través de la red, que maximiza el flujo total desde el origen hasta el destino en forma tal, que la capacidad de cada rama en esta trayectoria sea mínima.

El flujo máximo a lo largo de esta trayectoria debe ser igual a la capacidad mínima, de todas las ramas que constituyen la trayectoria.

FORMULACION DEL MODELO

Para resolver este tipo de modelos se presentan los siguientes métodos.

⦁ Formulación de un problema de programación lineal.

⦁ Algoritmo del flujo máximo.

El primer método de plantea de la siguiente manera:

Supongamos que existen “n” nodos, donde los nodos 1 y n son el origen y el destino respectivamente como se representa en la red.

TERMINOLOGIAS

Una red o grafo consiste de puntos, y líneas que conectan pares de puntos. Los puntos se llaman nodos o vértices. Las líneas de llaman arcos. Los arcos pueden tener una dirección asociada, en cuyo caso se denominan arcos dirigidos. Si un arco no tiene dirección normalmente se le denomina rama. Si todos los arcos en la red son dirigidos, la red se denomina una red dirigida. Si todos los arcos son no-dirigidos, la red es una red no-dirigida.

Dos nodos pueden estar conectados por un conjunto de arcos. Una trayectoria (path en inglés) es una secuencia de arcos distintos (con nodos no repetidos) conectando a los nodos. Una trayectoria dirigida desde nodo i al nodo j es una secuencia de arcos, cada uno de los cuales apunta al nodo j (si es que hay dirección). Una trayectoria no dirigida puede incluir arcos dirigidos apuntando en cualquiera de dirección.

Una trayectoria que comienza y que termina en el mismo nodo se denomina ciclo y puede ser ya sea dirigida o no-dirigida.

Una red está conectada si existe una trayectoria no-dirigida entre cualquier par de nodos. Una red conectada que no tiene ciclos se denomina árbol.

Optimización de redes es un tipo especial de modelo en programación lineal. Los modelos de redes tienen tres ventajas importantes con respecto a la programación lineal.

NOTACIÓN Y TERMINOLOGÍA

Red: Una red consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos. Los puntos se llaman nodos (o vértices). Las líneas se llaman arcos (o ligaduras, aristas o ramas).

Representación de una Red

Los arcos se etiquetan para dar nombres a los nodos en sus puntos terminales, por ejemplo, AB es el arco entre lo nodos A Y B.

En un problema de programación lineal, las redes pueden representar un conjunto de estaciones, campos petrolíferos, almacenes, fabricas, sucursales, ciudades, interconectadas entre si a través de caminos, conductos, tuberías que permiten fluir productos para la comercialización o la distribución.

Arcos Dirigidos: Se dice que un arco es dirigido cuando el arco tiene flujo en una dirección (como en una calle de un sentido). La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco.

Representación de un Arco Dirigido

Al etiquetar un arco dirigido con el nombre de los nodos que une, siempre se coloca primero al nodo de donde viene y después el nodo a donde va, esto es, un arco dirigido del nodo A al nodo B debe etiquetarse como AB y no como BA. Otra Manera es A B.

Arcos No Dirigidos: Si el flujo a través de un arco se permite en ambas direcciones (como una tubería que se puede usar para bombear fluido en ambas direcciones), se dice que es un arco no dirigido.

También se les llama ligadura. Aunque se permita que el flujo a través de un arco no dirigido ocurra en cualquier dirección, se supone que ese flujo será en una dirección, en la seleccionada, y no se tendrá flujos simultáneos en direcciones opuestas.

Trayectoria: Una trayectoria entre dos nodos es una sucesión de arcos distintos que conectan estos nodos. Por ejemplo, una de las trayectorias que conectan los nodos O y T en la figura 4 es la sucesión de arcos OB-BD-DT (O B D T), y viceversa.

Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinción entre trayectorias dirigidas y trayectorias no dirigidas.

Trayectoria Dirigida: Una trayectoria dirigida del nodo i al nodo j, es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j, a través de esta trayectoria es factible.

Trayectoria No Dirigida: Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) pueden ser hacia o desde el nodo j. Con frecuencia alguna trayectoria no dirigida tendrá algunos arcos dirigidos hacia el nodo j y otros desde él (es decir, hacia el nodo i).

Ciclo: Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En la red no dirigida que se muestra en la figura 5 existen muchos ciclos, OA-AB-BC-CO.

Red Conexa: Una red conexa es una red en la que cada par de nodos está conectado. Se dice que dos nodos están conectados si la red contiene al menos una trayectoria no dirigida entre ellos.

...