Conceptos basicos

CONCEPTOS BASICOS

 En Investigación de Operaciones hay un montón de situaciones que se pueden modelar y resolver como redes (nodos conectados por ramas).

Aplicaciones posibles de Redes:

1.- Modelo de  minimización  del costo de construcción de un gasoducto.

2.- Determinación de la ruta más corta entre dos ciudades.

3.- Determinación de la capacidad máxima (en toneladas) de una tubería.

4.- Determinación del programa de Flujo con costo mínimo.

5.- Determinación del cronograma (Fechas de inicio y terminación) de actividades.

Algunos algoritmos de optimización de redes (Formas de resolver los problemas):

1.- Árbol de Expansión mínima.

2.- Algoritmo de la Ruta Más Corta.

3.- Algoritmo del Flujo Máximo.

4.- Algoritmo de red capacitada con costo mínimo.

5.- Algoritmo de la Ruta Crítica.

Definición de Red: 

Una red consiste en una serie de nodos enlazados con arcos (o ramas). La notación para describir una red es (N, A), donde N es el conjunto de Nodos y A es el conjunto de Arcos.

Ejemplo:

N= {1, 2, 3, 4, 5}

A= {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}

 Figura 2. Ejemplo de Red (N, A).

–          Cada red se asocia a un flujo.

–          El flujo en  una red está limitado por la capacidad de sus arcos (finitos o infinitos).

–          Un arco es orientado o dirigido si permite un flujo positivo en una dirección y flujo cero en la dirección opuesta.

–          Una red dirigida tiene todos sus arcos dirigidos.

–          Una ruta es una sucesión de arcos distintos que unen dos nodos pasando por otros nodos, independientemente de la dirección de flujo de cada arco.

–          Una ruta forma un ciclo si conecta un nodo consigo mismo pasando por otros nodos.

–          Un ciclo es dirigido si consiste en una ruta dirigida.

–          Una red conectada es aquella en que cada dos nodos distintos están enlazados al menos por una ruta.

–          Un árbol es una red conectada que puede consistir solo en un subconjunto de todos los nodos en ella, donde no se permiten ciclos.

    Figura 3. Árbol de la Red de la figura 2.

–         Un árbol de expansión es un árbol que enlaza todos los nodos de la red, también sin permitir ciclos. 

Figura 4. Árbol de expansión de la Red de la figura 2.