Investigacion de operaciones

INVESTIGACION DE OPERACIONES
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).
Los arcos se etiquetan para dar nombres a los nodos en sus puntos terminales, por ejemplo, AB es el arco entre los nodos A Y B.
En unproblema de programación lineal, las redes pueden representar un conjunto de estaciones, campos petrolíferos, almacenes, fabricas, sucursales, ciudades, interconectadas entre sí 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 unacalle de un sentido). La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco.
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 AB.
Arcos No Dirigidos: Si el flujoa 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 endirecciones 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 1 es la sucesión de arcos OB-BD-DT (OBDT), y viceversa.
Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinción entre trayectorias dirigidas y trayectorias nodirigidas.
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 elnodo 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. Sedice que dos nodos están conectados si la red contiene al menos una trayectoria no dirigida entre ellos. Se debe resaltar que no es necesario que la trayectoria sea dirigida aun cuando la red sea dirigida. La figura 1 representa una red conexa.
Árbol de Expansión: es una red conexa para los n nodos, que contiene ciclos no dirigidos. Todo árbol de expansión tiene justo n-1 arcos, ya que este es elnúmero mínimo de arcos necesarios para tener una red conexa y el máximo número posible para que no haya ciclos no dirigidos.
Capacidad de Arco: Es la cantidad máxima de flujo (quizás infinito) que puede circular en un arco dirigido.
Nodo Fuente: (o nodo de origen) tiene la propiedad de que el flujo que sale del nodo excede al flujo que entra a él.
Nodo Demanda: (o nodo destino) es el casocontrario al nodo fuente, donde el flujo que llega excede al que sale de él.
Nodo de Trasbordo: (o nodo intermedio) satisface la conservación del flujo, es decir, el flujo que entra es igual al que sale.
Red Dirigida: Es una red que tiene solo arcos dirigidos.
Red No Dirigida: Es una red donde todos sus arcos son no dirigidos. La figura 10 representa una red no dirigida.
VISTA GENERAL DE ALGUNAS...