domingo, 8 de junio de 2014

MODELOS DE COLAS CON DOS SERVIDORES (M/M/2)



Estas relaciones son fundamentales pues permiten determinar las cuatro cantidades fundamentales L, W, Lq, Wq, en cuanto se encuentra analíticamente el valor de una de ellas.
Características claves.
Existen dos clases básicas de tiempo entre llegadas:
Determinístico, en el cual clientes sucesivos llegan en un mismo intervalo de tiempo, fijo y conocido. Un ejemplo clásico es el de una línea de ensamble, en donde los artículos llegan a una estación en intervalos invariables de tiempo (conocido como ciclos de tiempo)

Probabilístico, en el cual el tiempo entre llegadas sucesivas es incierto y variable. Los tiempos entre llegadas probabilísticos se describen mediante una distribución de probabilidad.

En el caso probabilístico, la determinación de la distribución real, a menudo, resulta difícil. Sin embargo, una distribución , la distribución exponencial, ha probado ser confiable en muchos de los problemas prácticos. La función de densidad, para una distribución exponencial depende de un parámetro, digamos l (letra griega lambda), y está dada por:

f(t)=(1/ l )e- l t
en donde l (lambda) es el número promedio de llegadas en una unidad de tiempo.

Con una cantidad, T, de tiempo se puede hacer uso de la función de densidad para calcular la probabilidad de que el siguiente cliente llegue dentro de las siguientes T unidades a partir de la llegada anterior, de la manera siguiente:
P(tiempo entre llegadas <=T)=1-e- l t
El proceso de servicio.

El proceso de servicio define cómo son atendidos los clientes. En algunos casos, puede existir más de una estación en el sistema en el cual se proporcione el servicio requerido. Los bancos y los supermercados, de nuevo, son buenos ejemplos de lo anterior. Cada ventanilla y cada registradora son estaciones que proporcionan el mismo servicio. A tales estructuras se les conoce como sistemas de colas de canal múltiple. En dichos sistemas, los servidores pueden ser idénticos, en el sentido en que proporcionan la misma clase de servicio con igual rapidez, o pueden no ser idénticos. Por ejemplo, si todos los cajeros de un banco tienen la misma experiencia, pueden considerarse como idénticos.

Al contrario de un sistema de canal múltiple, considere un proceso de producción con una estación de trabajo que proporciona el servicio requerido. Todos los productos deben pasar por esa estación de trabajo; en este caso se trata de un sistema de colas de canal sencillo. Es importante hacer notar que incluso en un sistema de canal sencillo pueden existir muchos servidores que, juntos, llevan a cabo la tarea necesaria. Por ejemplo, un negocio de lavado a mano de automóviles, que es una sola estación, puede tener dos empleados que trabajan en un auto de manera simultánea

Otra característica del proceso de servicio es el número de clientes atendidos al mismo tiempo en una estación. En los bancos y en los supermercados (sistema de canal sencillo), solamente un cliente es atendido a la vez. Por el contrario, los pasajeros que esperan en una parada de autobús son atendidos en grupo, según la capacidad del autobús que llegue.

Otra característica más de un proceso de servicio es si se permite o no la prioridad, esto es ¿puede un servidor detener el proceso con el cliente que está atendiendo para dar lugar a un cliente que acaba de llegar?. Por ejemplo, en una sala de urgencia, la prioridad se presenta cuando un médico, que está atendiendo un caso que no es crítico es llamado a atender un caso más crítico. Cualquiera que sea el proceso de servicio, es necesario tener una idea de cuánto tiempo se requiere para llevar a cabo el servicio. Esta cantidad es importante debido a que cuanto más dure el servicio, más tendrán que esperar los clientes que llegan. Como en el caso del proceso de llegada, este tiempo pude ser determinístico o probabilístico . Con un tiempo de servicio determinístico, cada cliente requiere precisamente de la misma cantidad conocida de tiempo para ser atendido. Con un tiempo de servicio probabilístico, cada cliente requiere una cantidad distinta e incierta de tiempo de servicio. Los tiempos de servicio probabilísticos se describen matemáticamente mediante una distribución de probabilidad. En la práctica resulta difícil determinar cuál es la distribución real, sin embargo, una distribución que ha resultado confiable en muchas aplicaciones , es la distribución exponencial .En este caso, su función de densidad depende de un parámetro, digamos (la letra griega my) y esta dada por

s(t)=(1/ m )e-m t
en la que:
m = número promedio de clientes atendidos por unidad de tiempo,
de modo que:

1/ m = tiempo promedio invertido en atender a un cliente
En general, el tiempo de servicio puede seguir cualquier distribución, pero, antes de que pueda analizar el sistema, se necesita identificar dicha distribución.
Medidas de rendimiento para evaluar un sistema de colas

El objetivo último de la teoría de colas consiste en responder cuestiones administrativas pertenecientes al diseño y a la operación de un sistema de colas. El gerente de un banco puede querer decidir si programa tres o cuatro cajeros durante la hora de almuerzo. En una estructura de producción, el administrador puede desear evaluar el impacto de la compra de una nueva máquina que pueda procesar los productos con más rapidez.

Cualquier sistema de colas pasa por dos fases básicas. Por ejemplo, cuando el banco abre en la mañana, no hay nadie en el sistema, de modo que el primer cliente es atendido de forma inmediata. Conforme van llegando más clientes, lentamente se va formando la cola y la cantidad de tiempo que tienen que esperar se empieza a aumentar. A medida que avanza el día, el sistema llega a una condición en la que el efecto de la falta inicial de clientes ha sido eliminado y el tiempo de espera de cada cliente ha alcanzado niveles bastante estables.


- ?n = Tasa media de llegadas de nuevos clientes cuando hay n clientes en el sistema (número promedio de llegadas por unidad de tiempo).

- 1/? = Tiempo promedio entre llegadas.

- µn = Tasa media de servicio de nuevos clientes cuando hay n clientes en el sistema (número promedio de clientes al cual puede dar servicio la instalación en una unidad de tiempo, suponiendo que no hay escasez de clientes).

- 1/µ = Tiempo promedio servicio.

- Lq = Número esperado de clientes en la cola (excluye los clientes que están en servicio).

- L = Número esperado de clientes que se atienden y/o esperan en el sistema.

- Wq = Tiempo estimado que emplea un cliente esperando en la cola.

- W = Tiempo estimado que emplea un cliente esperando más el que emplea siendo atendido (tiempo esperado en el sistema).

- Po = Probabilidad de encontrar el sistema vacío u ocioso.

- Pn = Probabilidad de encontrar exactamente n clientes en el sistema.

- ? = Fracción esperada de tiempo que los servidores individuales están ocupados.

Modelo de la Cola Infinita, Fuente Infinita y una Unidad de Servicio Múltiple.

Para este modelo de considera lo siguiente:

1.- Las llegadas son aleatorias y provienen de una distribución de probabilidad de Poisson o de Markov.

2.- Se supone que el tiempo de servicio es también una variable aleatoria que sigue una distribución exponencial o de Markov. Se supone además que los tiempos de servicios son independientes entre sí e independiente del proceso de llegada.

3.- Hay varias unidades de servicio.

4.- La disciplina de cola se basa en el principio FIFO (primero en llegar primero en salir) y no hay un límite para el tamaño de la cola.



5.- Las tasas de llegadas y de servicio no cambian con el tiempo. El proceso ha estado en operación el tiempo suficiente para eliminar los efectos de las condiciones iniciales.

La siguiente notación supone la condición de estado estable:

• Pn : Probabilidad de que haya exactamente n clientes en el sistema

• L: Número esperado de clientes en el sistema.

• Lq : Longitud esperada de la cola (excluye los clientes que están en servicio).

• W : Tiempo de espera en el sistema para cada cliente

• W : E(W )

• W q: Tiempo de espera en la cola para cada cliente.

• Wq: E (Wq )

Relaciones entre L , W , Lq y Wq

Supongamos que ln es una constante l para toda n:

L = l W Lq = l Wq

Supongamos que el tiempo medio de servicio es una constante 1/m para toda n ³ 1

W = Wq + 1/m L = Lq+r














TEORÍA DE COLAS (M/M/1)


El matemático danés Agner Krarup Erlang, trabajador de la Copenhagen Telephone Exchange, publicó el primer artículo sobre la teoría de colas en 1909.1 Específicamente se preocupó del estudio del problema de dimensionamiento de líneas y centrales de conmutación telefónica para el servicio de llamadas.

Diagrama que muestra dos colas y múltiples nodos servidores. La teoría de colas estudia los tiempos de espera y capacidad del sistema.

La teoría de colas es el estudio matemático de las colas o líneas de espera dentro de un sistema. Ésta teoría estudia factores como el tiempo de espera medio en las colas o la capacidad de trabajo del sistema sin que llegue a colapsarse. Dentro de las matemáticas, la teoría de colas se engloba en la investigación de operaciones y es un complemento muy importante a la teoría de sistemas y la teoría de control. Se trata así de una teoría que encuentra aplicación en una amplia variedad de situaciones como negocios, comercio, industria,ingenierías, transporte y logística o telecomunicaciones.

En el caso concreto de la ingeniería, la teoría de colas permite modelar sistemas en los que varios agentes que demandan cierto servicio o prestación confluyen en un mismo servidor y, por lo tanto, pueden registrarse esperas desde que un agente llega al sistema y el servidor atiende sus demandas. En este sentido, la teoría es muy útil para modelar procesos tales como la llegada de datos a una cola enciencias de la computación, la congestión de red de computadoras o de telecomunicación, o la implementación de una cadena productivaen la ingeniería industrial.

En el contexto de la informática y de las tecnologías de la información y la comunicación las situaciones de espera dentro de una red son más frecuentes. Así, por ejemplo, los procesos enviados a un servidor para su ejecución forman colas de espera mientras no son atendidos; la información solicitada, a través de Internet, a un servidor Web puede recibirse con demora debido a la congestión en la red; también se puede recibir la señal de línea de la que depende nuestro teléfono móvil ocupada si la central está colapsada en ese momento, etc.

LA FORMACIÓN DE COLAS

Se forman debido a un desequilibrio temporal entre la demanda del servicio y la capacidad del sistema para suministrarlo.

En las formaciones de colas se habla de clientes, tales como máquinas dañadas a la espera de ser rehabilitadas. Los clientes pueden esperar en cola debido a que los medios existentes sean inadecuados para satisfacer la demanda del servicio; en este caso, la cola tiende a ser explosiva, es decir, a ser cada vez más larga a medida que transcurre el tiempo. Los clientes puede que esperen temporalmente, aunque las instalaciones de servicio sean adecuadas, porque los clientes llegados anteriormente están siendo atendidos.

Los objetivos de la teoría de colas consisten en:

· Identificar el nivel óptimo de capacidad del sistema que minimiza el coste del mismo.

· Evaluar el impacto que las posibles alternativas de modificación de la capacidad del sistema tendrían en el coste total del mismo.

· Establecer un balance equilibrado (“óptimo”) entre las consideraciones cuantitativas de costes y las cualitativas de servicio.

· Prestar atención al tiempo de permanencia en el sistema o en la cola de espera.

ELEMENTOS DE LAS TEORÍAS DE COLAS

Proceso básico de colas: Los clientes que requieren un servicio se generan en una fase de entrada. Estos clientes entran al sistema y se unen a una cola. En determinado momento se selecciona un miembro de la cola, para proporcionarle el servicio, mediante alguna regla conocida como disciplina de servicio. Luego, se lleva a cabo el servicio requerido por el cliente en un mecanismo de servicio, después de lo cual el cliente sale del sistema de colas.

Fuente de entrada o población potencial: Una característica de la fuente de entrada es su tamaño. El tamaño es el número total de clientes que pueden requerir servicio en determinado momento. Puede suponerse que el tamaño es infinito o finito.

Cliente: Es todo individuo de la población potencial que solicita servicio como por ejemplo una lista de trabajo esperando para imprimirse.

Capacidad de la cola: Es el máximo número de clientes que pueden estar haciendo cola (antes de comenzar a ser servidos). De nuevo, puede suponerse finita o infinita.

Disciplina de la cola: La disciplina de la cola se refiere al orden en el que se seleccionan sus miembros para recibir el servicio. Por ejemplo, puede ser:

· FIFO (first in first out) primero en entrar, primero en salir, según la cual se atiende primero al cliente que antes haya llegado.

· LIFO (last in first out) también conocida como pila que consiste en atender primero al cliente que ha llegado el último.

· RSS (random selection of service) que selecciona los clientes de manera aleatoria, de acuerdo a algún procedimiento de prioridad o a algún otro orden.

· Processor Sharing – sirve a los clientes igualmente. La capacidad de la red se comparte entre los clientes y todos experimentan con eficacia el mismo retraso.

Mecanismo de servicio: El mecanismo de servicio consiste en una o más instalaciones de servicio, cada una de ellas con uno o más canales paralelos de servicio, llamados servidores.

Redes de colas. Sistema donde existen varias colas y los trabajos fluyen de una a otra. Por ejemplo: las redes de comunicaciones o los sistemas operativos multitarea.

Cola: Una cola se caracteriza por el número máximo de clientes que puede admitir. Las colas pueden ser finitas o infinitas.

El proceso de servicio: Define cómo son atendidos los clientes.

Para este modelo se considera lo siguiente:

1.- Las llegadas son aleatorias y provienen de una distribución de probabilidad de Poisson o de Markov.

2.- Se supone que el tiempo de servicio es también una variable aleatoria que sigue una distribución exponencial o de Markov. Se supone además que los tiempos de servicios son independientes entre sí e independientes del proceso de llegada.

3.- Sólo hay una unidad de servicio.

4.- La disciplina de cola se basa en el principio FIFO (primero en llegar primero en salir) y no hay un límite para el tamaño de la cola.

5.- Las tasas de llegadas y de servicio no cambian con el tiempo. El proceso ha estado en operación el tiempo suficiente para eliminar los efectos de las condiciones iniciales.













INVENTARIO PROBABILISTICO


Con el pasar del tiempo se ha tratado de adaptar el modelo determinístico de cantidad económica  de pedido EOQ para que refleje la naturaleza probabilista de la demanda, usando una aproximación que sobrepone una existencia constante de reserva sobre el nivel de inventario. El tamaño de la reserva (punto de reorden) se determina de tal modo que la probabilidad de que se agote la existencia durante el tiempo de entrega (el periodo entre la colocación de la orden y la recepción del pedido) no sea mayor que un valor especificado.











La hipótesis principal de este modelo es que la demanda durante el tiempo de entrega, tiene una distribución normal, con media μ y desviación estándar σ. (μ se define como la demanda promedio durante el tiempo de entrega y σ es la desviación estándar de la demanda durante este mismo periodo).

El valor promedio de  la demanda, la cual podemos ver ubicada en el punto medio de la curva de distribución normal, nos da a saber que existe  una probabilidad de que  en el 50% de las veces nuestro inventario no podrá satisfacer los requerimientos del mercado. Por tal razón al implementar este sistema de inventario, se debe establecer en primera instancia un porcentaje tolerable de error (α= probabilidad  máxima admisible de que se agote la reserva durante el tiempo de entrega), en otras palabras un número de veces en el que se es permitido que la demanda supere nuestras reservas y no se pueda satisfacer con las exigencias del mercado.

Dos números críticos dentro de este sistema son, el  punto de reorden (R)  y la cantidad a pedir (Q). La política de inventario se puede resumir en estas dos variables, de la siguiente manera: Siempre que el nivel de inventario de un producto baje a R unidades, se coloca una orden de Q unidades para reabastecer el inventario. Estas dos variables se ven condicionadas por el tiempo de entrega (L), periodo en el cual la fluctuación de la demanda determinará el punto mínimo de  unidades a mantener en inventario. Q se determinará como se venía haciendo en el modelo básico de EOQ

En resumen las variables de este modelo son : 

L= tiempo  den entrega entre la colocación de la orden y la recepción del pedido.
μL = Demanda promedio durante el tiempo de entrega.
σL = Desviación estándar de la demanda durante el tiempo de entrega
R = Punto de reorden (tamaño de la existencia de reserva).
α= Probabilidad máxima admisible de que se agote la existencia durante el tiempo de entrega. 

La demanda durante el tiempo de entrega L se suele describir con una función de densidad de probabilidades por unidad de tiempo (es decir por día o por semana), a partir de la que se puede determinar la distribución de la demanda durante L. Dado que la demanda por unidad de tiempo es normal, con media D y desviación estándar σ, la media μL y la desviación estándar σL de la demanda, durante el tiempo de entrega L, se calculan como sigue: 


El punto de reorden lo definimos como 

 En donde el valor de Z se encuentra en las tablas de distribución normal y toma el valor de Z = 1-α

Existen 3 situaciones por considerar en cada una de las siguientes formas para el PRO, la demanda promedio durante el tiempo de entrega es el primer termino y el inventario de seguridad es el segundo.

DEMANDA VARIABLE - TIEMPO DE ENTREGA CONSTANTE


DEMANDA CONSTANTE - TIEMPO DE ENTREGA VARIABLE


DEMANDA Y TIEMPO DE ENTREGA VARIABLES 






TEORIA DE INVENTARIO CON FALTANTE

Como mencionamos con anterioridad el modelo EOQ, puede tener diversas aplicaciones de esta forma el modelo EOQ Con faltantes, se basa en que la compañía permite que haya tiempos de espera entre un pedido y otro, es decir, que hayan pedidos atrasados, de esta manera se supone que hay un tiempo donde la demanda no se satisface a tiempo y se produce una escasez. De todo esto, también en se incurre en un nuevo costo que es el de las unidades faltantes durante el periodo t. De esta forma este modelo de inventario tiene unos supuestos, que se basan en los mismos del EOQ clásico con la diferencia que se agregan:

  •  Se permiten las faltantes
  •  Se incurre en un costo de Faltante
  •  La demanda es Constante y conocida: Esto se refiere a que por ejemplo, si la demanda ocurre a una tasa de 1000 unidades por año, la demanda durante cualquier periodo de t meses será 1000t/12.
  • Los tiempos de reposición son instantáneos: Esto quiere decir que un pedido llega tan pronto se hace.
  • Existen Costos de hacer un pedido
  • Existen Costos de Mantener guardado en inventario
  • Los costos de mantener inventario y el costo de pedir no varían en el tiempo.
  •  La cantidad a pedir es constante
  •  Existe una relación directa costo-volumen


De esta manera aparece una cantidad “S” que es la cantidad máxima que permite la empresa como faltante. Observemos la gráfica:



De esta grafica se deduce que la empresa tiene en inventario un inventario máximo, que al consumirse totalmente por la demanda (llega a cero) la empresa esta permitiendo que una cantidad S de unidades le falten, para hacer un nuevo pedido que satisfaga la demanda de las unidades faltantes mas las de las unidades que se demandan diariamente; de esto tenemos, que:

Imax= Es mi inventario máximo
D=la demanda del periodo t
S= cantidad de unidades de demanda faltantes
Q= cantidad de unidades que se piden.

  • Costo de un periodo 

  • Costo total anual 

  • Cantidad optima a pedir 
  • Cantidad faltante optima






EJEMPLOS

La demanda de un artículo es de 1.000 unidades al mes, se permite déficit. Si el costo unitario es de $1,50, el costo de hacer una compra es de $600, el costo de tenencia de una unidad es de $2 por año y el costo de déficit es de $10 por unidad al año. Determinar la cantidad optima que debe comprar y el número óptimo de unidades agotadas

Solución:

 

Una empresa española anualmente tiene una demanda aproximada de 8500unidades al año, el costo de mantener el inventario es de $5 y cada vez que quiere realizar un pedido a su proveedor se le genera un cobro de $30 por unidad, la empresa ha decidido implementar el sistema de inventario con faltantes. El costo por faltantes es de $7 por unidad. Se nos pide calcular la cantidad optima que se debe comprar y el número óptimo de unidades agotadas.





TEORÍA DE INVENTARIO

INVENTARIO: se puede definir inventarios de Materias Primas, Partes en Proceso y de Productos Terminados, ya que se encuentran en algún lugar y en un determinado tiempo dentro del Sistema de Producción. 

El objetivo del inventario es permitir y/o facilitar la producción entre dos unidades de producción o dos etapas de producción que están ubicadas secuencialmente.

Por lo tanto, el inventario cumple una función de capacitor entre ambas  unidades, permitiendo por un lado, absorber las distintas capacidades y formas de producción, y por otro, las variaciones que experimenta cada unidad dentro del Proceso de Producción

El principal objetivo de analizar un Sistema de Inventario es encontrar respuestas a preguntas como las que se presentan a continuación:

·         ¿Qué artículos deben mantenerse en inventario?
·         ¿Qué cantidad de artículos debe  ser ordenada o producida?
·         ¿Cuándo deben generarse las órdenes para que el costo total de manejo de inventarios sea el mínimo posible?
·         ¿Qué Sistema de Control de Inventario deberá utilizarse para cada caso?

SUPOSICIÓN DEL MODELO EOQ
  • Se conoce la tasa de demanda (d) por unidad de tiempo
  • La cantidad a ordenar (Q) para restablecer el inventario llega todo junto cuando se desea
  • No permite faltantes
  • En general la longitud del ciclo es:



  • El costo por producir u ordenar por ciclo:

  • El costo de mantener en inventario por ciclo
  • Por lo tanto el costo total por ciclo es :
  • Entonces el costo por unidad de tiempo:

  • Por lo tanto es costo total es :
  • Cantidad optima de pedido 










sábado, 7 de junio de 2014

PERT - CPM

El método PERT (Program Evaluation and Review Technique) es una metodología que a diferencia de CPM permite manejar la incertidumbre en el tiempo de término de las actividades.

En este sentido el tiempo de ejecución de las actividades es obtenido a través de la estimación de 3 escenarios posibles: optimista (a), normal (m) y pesimista (b). El tiempo (aleatorio) que requiere cada actividad está asociado a una función probabilística beta, que ha demostrado ser la que mejor modela la distribución del tiempo de duración de una actividad. A continuación se presenta un gráfico que muestra la función de densidad de probabilidad para la función beta, la cual tiene una asimetría positiva.




Luego, el tiempo esperado (te) y la varianza asociada a cada actividad se obtienen a través de las siguientes fórmulas:



EJEMPLO

Consideremos el proyecto utilizado para ejemplificar la metodología CPM. Sin embargo, asumiremos distintos escenarios de ocurrencia asociados al tiempo necesario para completar cada actividad, los que se resumen en la siguiente tabla:


El primer paso consiste en calcular el tiempo esperado (te) asociado a cada actividad, utilizando la fórmula presentada anteriormente:
Notar que en este caso m = te para cada actividad, lo cual no tiene que ser necesario. Lo importante es tener en cuenta la metodología a utilizar. Luego, una vez obtenido el tiempo esperado (te) para cada actividad se procede a calcular la duración del proyecto utilizando un procedimiento similar a CPM. Los resultados se resumen en el siguiente diagrama:


La ruta crítica (única) esta conformada por las actividades B-C-E-F-H con una duración total de 49 semanas. (Ver detalle en CPM). Posteriormente se calcula la varianza para cada actividad (aun cuando en estricto rigor sólo es necesario para las actividades críticas, es decir, con holgura igual a cero), de modo de obtener finalmente la varianza (y desviación estándar) de la ruta crítica.

Con esta información podemos responder a preguntas como ¿Cuál es la probabilidad de completar el proyecto en 52 semanas o menos? Básicamente esto consiste en determinar el porcentaje del área acumulada para una distribución normal para determinado valor de Z.


P[Tp<=52]=P[Z<=(52-49)/2,81]=P[Z<=1,07]=85,77%
En conclusión, la probabilidad de completar el proyecto en 52 semanas o menos es de un 85,77%.




















viernes, 6 de junio de 2014

ÁRBOL DE EXPANSIÓN MINIMA


En teoría de grafos, un árbol de expansión, árbol generador o árbol recubridor  de un grafo conexo, no dirigido G es un árbolcompuesto por todos los vértices y algunas (quizá todas) de las aristas de G. Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T.
Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.

CICLOS FUNDAMENTALES Y CORTES FUNDAMENTALES

Si se añade una sola arista a un árbol de expansión, se crea un ciclo: los ciclos de ese tipo se denominan ciclos fundamentales. Hay un ciclo fundamental distinto para cada arista; es decir, hay una correspondencia  (uno a uno) entre ciclos fundamentales y aristas ausentes del árbol de expansión. Para un grafo biyectiva conexo con V vértices, cualquier árbol de expansión tiene V-1 aristas, y así, un grafo con E aristas tiene E-V+1 ciclos fundamentales. En cualquier árbol de expansión dado, esos ciclos forman una base del espacio de ciclos.
De manera dual a la noción de ciclo fundamental, existe el concepto de corte fundamental. Al eliminar una arista del árbol de expansión, los vértices se dividen en dos conjuntos disjuntos (desconectados). El corte fundamental se define como el conjunto de aristas que deben ser eliminados de un grafo G para llegar a la misma división. Por tanto, hay exactamente V-1 cortes fundamentales en un grafo, uno por cada arista del árbol de expansión.
La dualidad entre cortes y ciclos fundamentales se manifiesta al observar que las aristas de un ciclo que no pertenece al árbol de expansión sólo pueden aparecer en los cortes de otras aristas del ciclo, y viceversa: las aristas en un corte sólo pueden aparecer en aquellos ciclos no contenidos en la arista correspondiente al corte. 
En teoría de grafos, un árbol de expansión, árbol generador o árbol recubridor  de un grafo conexo, no dirigido G es un árbolcompuesto por todos los vértices y algunas (quizá todas) de las aristas de G. Informalmente, un árbol de expansión de G es una selección de aristas de G que forman un árbol que cubre todos los vértices. Esto es, cada vértice está en el árbol, pero no hay ciclos. Por otro lado, todos los puentes de G deben estar contenidos en T.
Un árbol de expansión o árbol recubridor de un grafo conexo G puede ser también definido como el mayor conjunto de aristas de G que no contiene ciclos, o como el mínimo conjunto de aristas que conecta todos los vértices.






 

jueves, 5 de junio de 2014

FLUJO MÁXIMO - ALGORITMO DE FORD-FULKERSON

  
la teoría de grafos, una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se le asocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales se mantiene la ley de corriente de kirchoff, en donde la suma de flujos entrantes  a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el trafico en un sistema de autopistas, fluidos viajando en tuberías, corrientes electricas en circuitos eléctricos o sistemas similares por lo que viaje algo entre modos.
Tenemos el conocido problema de flujo máximo o maximal: ¿Cual es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad? En otras palabras, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino. El procedimiento para obtener el flujo máximo posible en esa trayectoria.Podemos, mediante el algoritmo de Ford-Fulkerson, encontrar el flujo máximo de una red.



CAMINO MAS CORTO

En la teoría de grafos, el problema de los caminos más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas. 
El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de la siguiente generalización:
·   El problema de los caminos más cortos desde un origen en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.
·   El problema de los caminos más cortos con un destino en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.
·   El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v , v') en el grafo.