optimizacion


CONFERENCIAS DE CLASES
INVESTIGACIÓN DE OPERACIONES II







TEMA: MODELOS DE REDES







PREPARO: PROFESOR
RODRIGO PEREZ PEÑA


















UNIVERSIDAD COOPERATIVA DE COLOMBIA
FACULTADAD DE ADMINISTRACIÓN DE EMPRESAS


marzo de 2001




MODELO DE REDES

La importancia del análisis de flujo de redes, en los últimos años ha crecidode 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 corto 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 recursoespecial.
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 deproyectos (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 uncamino 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 flujopositivo 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ÁXIMOEste 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 tipode modelos se presentan los siguientes métodos.
1. Formulación de un problema de programación lineal.
2. 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.








Fuente destino


Cij XijEl flujo que circula por la red debe cumplir la siguiente restricción:


0 < Xij < Cij



Además debe cumplir la siguiente restricción de conservación de flujo.

 Xik -  Xkj = 0

Formulación de un problema de programación lineal

1. Se define la variable de decisión Xn.
XIJ = La cantidad de flujo que circula de la fuente i al destino j.
2. Se define la función...