TEORIA DE COLAS

TEORÍA DE COLAS

         

 -Las colas son frecuentes en nuestra vida cotidiana:

—En un banco

—En un restaurante de comidas rápidas

—Al matricular en la universidad

—Los autos en un lavacar

-En general, a nadie le gusta esperar

Cuando la paciencia llega a su límite, la gente se va a otro lugar

Sin embargo, un servicio muy rápido tendría un costo muy elevado

Es necesario encontrar un balance adecuado

Teoría de colas

¢Una cola es una línea de espera

¢La teoría de colas es un conjunto de modelos matemáticos que describen sistemas de líneas de

espera particulares

¢El objetivo es encontrar el estado estable del sistema y determinar una capacidad de servicio

apropiada

¢Existen muchos sistemas de colas distintos

¢Algunos modelos son muy especiales

Modelos de una cola y un servidor

M/M/1: Un servidor con llegadas de Poisson y tiempos de servicio exponenciales

Ejemplo:

Un lavacar puede atender un auto cada 5 minutos y la tasa media de llegadas es de 9 autos por hora. Obtenga las medidas de desempeño de acuerdo con el modelo M/M/1.Además la probabilidad de tener 0 clientes en el sistema, la probabilidad de tener una cola de más de 3 clientes y la probabilidad de esperar más de 30 min. en la cola y en el sistema.

 SOLUCION:

   

Modelo M/G/1:

 

Un lavacar puede atender un auto cada 5 min. y la tasa media de llegadas es de 9 autos/hora, s = 2 min.

Obtenga las medidas de desempeño de acuerdo con el modelo M/G/1

Además la probabilidad de tener 0 clientes en el sistema y la probabilidad de que un cliente tenga que esperar por el servicio.

 

 

 Modelo M/D/1:

 

 Un lavacar puede atender un auto cada 5 min.

La tasa media de llegadas es de 9 autos/hora.

Obtenga las medidas de desempeño de acuerdo con el modelo M/D/1

 

 

 

 Modelo M/Ek/:

 

Un lavacar puede atender un auto cada 5 min.

La tasa media de llegadas es de 9 autos/hora. Suponga s = 3.5 min (aprox.)

Obtenga las medidas de desempeño de acuerdo con el modelo M/Ek/1

 

 

 

 

PERT/CPM RUTA CRITICA

PERT/ CPM RUTA CRITICA

El Método CPM (Critical Path Method), fue desarrollado en 1957 en los Estados Unidos de América, por un centro de investigación de operaciones para las firmas Dupont y Remington Rand, buscando el control y la optimización de los costos mediante la planeación y programación adecuadas de las actividades componentes del proyecto. En administración y gestión de proyectos, una ruta crítica es la secuencia de los elementos terminales de la red de proyectos con la mayor duración entre ellos, determinando el tiempo más corto en el que es posible completar el proyecto. La duración de la ruta crítica determina la duración del proyecto entero. Cualquier retraso en un elemento de la ruta crítica afecta a la fecha de término planeada del proyecto, y se dice que no hay holgura en la ruta crítica.

Un proyecto puede tener varias rutas críticas paralelas. Una ruta paralela adicional a través de la red con las duraciones totales menos cortas que la ruta crítica es llamada una sub-ruta crítica.

Originalmente, el método de la ruta crítica consideró solamente dependencias entre los elementos terminales. Un concepto relacionado es la cadena crítica, la cual agrega dependencias de recursos. Cada recurso depende del manejador en el momento donde la ruta crítica se presente.

A diferencia de la técnica de revisión y evaluación de programas (PERT), el método de la ruta crítica usa tiempos ciertos (reales o determinísticos). Sin embargo, la elaboración de un proyecto basándose en redes CPM y PERT son similares y consisten en:

• Identificar todas las actividades que involucra el proyecto, lo que significa, determinar relaciones de precedencia, tiempos técnicos para cada una de las actividades.

• Construir una red con base en nodos y actividades (o arcos, según el método más usado), que implican el proyecto.

• Analizar los cálculos específicos, identificando las rutas críticas y las holguras de los proyectos.

En términos prácticos, la ruta crítica se interpreta como la dimensión máxima que puede durar el proyecto y las diferencias con las otras rutas que no sean la crítica, se denominan tiempos de holgura. 

REDES (FLUJO MAXIMO)

Modelo de Flujo Máximo

Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino.

Características:

1. Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.
2. Los nodos restantes son nodos de trasbordo.
3. Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dad por la capacidad del arco. En la fuente, todos los arcos señalan hacia fuera. En el destino, todos señalan hacia el nodo.
4. El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.

El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método símplex y usar cualquiersoftware. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficientes. El algoritmo se basa en dos conceptos intuitivos, el de red residual y el de trayectoria aumentada.

Algoritmo de la trayectoria de aumento para el problema de flujo máximo:

1. Se identifica una trayectoria de aumento encontrando alguna trayectoria dirigida del origen al destino en la red residual, tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva. (Si no existe una, los flujos netos asignados constituyen un patrón del flujo óptimo).
2. Se identifica la capacidad residual c* de esta trayectoria de aumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria.
3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa la paso 1.

4. Flujo máximo.

   Al obtener una red, si se desea hallar su flujo máximo, lo que hay que hacer, es seleccionar un inicio, y un fin.

   Por ejemplo para la siguiente red, tomaremos como inicio u origen el nodo 1, y como fin el nodo 5.

   

    

   Al ubicarnos en el nodo 1, lo siguiente por hacer es realizar una etiquetarlo de forma [ ,--], y estando ubicados en este nodo, lo que haremos es escoger cual de las aristas es la que tiene el mayor valor e irnos por este, sabemos que se irá por la arista de valor 30, que se dirigirá al nodo 3, estando en el nodo 3, lo etiquetaremos de la siguiente manera, [valor de envió, de que nodo viene], es decir [30,1], posteriormente se buscara el flujo máximo que parte de 3, es decir 20, que se dirige a 5, estando en 5 se etiquetara de la misma forma, [20,3].

   

     

   Ahora se declarara k_min,    cuyos valores serán los valores de los nodos por los que se viajo, es decir [30,10], el valor de menor  valor es el de 10, por lo tanto k_min será igual a 10.

   Ahora recorriendo este camino, lo que haremos es lo siguiente;

   C_ij, C_ji = [i-k , j+k]

   Donde i sera el valor de salida en la arista, y j el valor de llegada de la misma.

   Ahora aplicando esto en nuestra red.

   C₁₃, C₃₁ = [30-10, 0+10]

   C₃₅, C₅₃ = [20-10, 0+10]

   De esta forma:

   C₁₃, C₃₁ = [20, 10]

   C₃₅, C₅₃ = [10, 10]

   Se reemplazan estos valores en los nodos indicados, el primer numero sera la salida, y el Segundo la llegada.

   Después de reemplazar los valores en la red.

   Posteriormente haremos el mismo procedimiento de escoger desde el nodo de inicio, el valor máximo, y realizar su respectiva etiquetada.

   

     

   Luego haremos el mismo procedimiento de

   C_ij, C_ji = [i-k , j+k]

   
   

   Y se hallara mos k_min

   k_min = 5;

   Haremos su respectiva etiquetada.

   

   Esta es la red obtenida.

   
   

   Ahora repetiremos este procedimiento hasta dejar las conexiones saturadas, el decir que su salida es de 0,

   Para así finalmente después de obtenidas todas las k_min  realizar su sumatoria, para así obtener su flujo máximo.

   
   

REDES ( ARBOL DE EXPANSION MINIMA)

Modelo de minimización de redes

El modelo de minimización de redes o problema del árbol de mínima expansión tiene que ver con la determinación de los ramales que pueden unir todos los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos. No se deben incluir ciclos en al solución del problema.

Para crear el árbol de expansión mínima tiene las siguientes características:

1. Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red. (Las medidas alternativas para la longitud de una ligadura incluyen distancia, costo y tiempo.)
2. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un camino entre cada par de nodos.
3. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las ligaduras insertadas en la red.

Una red con n nodos requiere sólo (n-1) ligaduras para proporcionar una trayectoria entre cada par de nodos. Las (n-1) ligaduras deben elegirse de tal manera que la red resultante formen un árbol de expansión. Por tanto el problema es hallar el árbol de expansión con la longitud total mínima de sus ligaduras.

Algoritmo para construir el árbol de expansión mínima:

1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir, se agrega una ligadura) al nodo distinto más cercano.
2. Se identifica el nodo no conectado más cercano a un nodo conectado y se conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que todos los nodos están conectados.
3. Empates: los empates para el nodo más cercano distinto (paso 1) o para el nodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo debe llegar a una solución optima. No obstante, estos empates son señal de que pueden existir (pero no necesariamente)soluciones optimas múltiples. Todas esas soluciones se pueden identificar si se trabaja con las demás formas de romper los empates hasta el final.

EJEMPLO

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

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

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

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

REDES (RUTA MAS CORTA)

Modelo de la ruta más corta

Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino.

Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.

Algoritmo de la ruta más corta:

1. Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano sea el nodo destino.)
2. Datos para la n-ésima iteración: n-1 nodos más cercanos al origen (encontrados en las iteraciones previas), incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos.)
3. Candidatos para el n-ésimo nodo más cercano: Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta. (Los empates proporcionan candidatos adicionales.)
4. Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El candidato con la distancia total más pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia. 
5. Ejemplo:
6.  Se tiene una red de comunicaciones entre dos estaciones 1 y 7. Las probabilidades de que un enlace de la red funcione sin fallar se muestran en la siguiente tabla. Los mensajes se mandan de la estación 1 a la estación 7 y el objetivo es determinar la ruta que maximice la probabilidad de una buena transmisión.

7. Estaciones	probabilidad	Estaciones	Probabilidad
   1,2	0.8	1,4	0.65
   1,3	0.3	2,5	0.5
   2,4	0.9	3,6	0.95
   4,5	0.7	4,6	0.6
   4,3	0.85	5,7	0.8
   5,6	0.5	6,7	0.9

REDES

REDES

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 losalgoritmos que aplican estos modelos para encontrar la solución optima al problema. Utilizando la terminología utilizada para representarlos como una red.

MODELOS DE REDES

Los problemas de optimización de redes se pueden representar en términos generales a través de uno de estos cuatro modelos:

• Modelo de minimización de redes (Problema del árbol de mínima expansión).
• Modelo de la ruta más corta.
• Modelo del flujo máximo.
• Modelo del flujo del costo mínimo.