modelosdeinventario

MODELOS DE REDES

INTRODUCCION:

Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redes detransporte, 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.

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 ARBOL DE LA EXPANSION MINIMA

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

EJEMPLOS:

La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual contará con la urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la ciudad. Dado que el terreno en el que se construirá no se encontraba hasta ahora dentro de las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura necesaria para satisfacer las necesidades de servicios públicos en materia de suministro de agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto madre, el cual cuenta con las conexiones de las unidades de vivienda propias de cada proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre del acueducto municipal para contar con su suministro). El acueducto municipal al ver la situación del plan parcial debe de realizar las obras correspondientes a la instalación de ductos madres que enlacen todos los nodos del plan con el nodo Meléndez (nodo que se encuentra con suministro de agua y que no pertenece al plan parcial de vivienda, además es el más cercano al mismo), la instalación de los ductos implica obras de excavación, mano de obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es fundamental. Las distancias existentes (dadas en kilometros) correspondientes a las rutas factibles capaces de enlazar los nodos del plan parcial se presentan a continuación. Además la capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer las necesidades de presión que necesita la red madre.

UTILIZANDO EL PROGRAMA WINQSB

Luego debemos seleccionar la opción Minimal Spanning Tree (Árbol de Expansión Mínima). Además en este submenú debemos de especificar el nombre del problema y el número de nodos. En nuestro caso el número de nodos es igual a 8, luego click en OK.

Una vez se realiza el paso anterior se abrirá una ventana en la cual aparecerá la siguiente matriz

WinQSB - Bryan Antonio Salazar López

En esta matriz se deben de consignar los valores de los ramales que unen las conexiones entre los nodos correspondientes, según el contexto de nuestro problema se deben de consignar las distancias entre los nodos si es que dichas conexiones existen de lo contrario en caso que la conexión no exista se debe dejar la celda en blanco. Hay que tener en cuenta que las distancias entre los nodos en este caso son exactamente conmutativas, es decir que si el nodo fuente es 2 y el destino es 4 la distancia existente entre estos es exactamente igual a la distancia existente entre un nodo fuente 4 y un nodo destino 2, sin embargo esta propiedad debe de especificarse en la matriz consignando los valores correspondientes a una conexión dos veces, es decir en la celda [From 1 - To 4] se debe de consignar la distancia 6, además debe de consignarse la misma distancia en la celda [From 4 - To 1].

Luego damos click en Solve and Analize y tendremos la siguiente ventana solución inmediatamente.

Podemos cotejar los resultados con los obtenidos de manera manual, 21 kilometros de ductos es la distancia total una vez ejecutado el algoritmo del Árbol de Expansión Mínima.

PROBLEMA DEL FLUJO MAXIMO

Este modelo se utiliza para reducir los embotellamientos entre ciertos puntos de partida y destino en una red.

Existe un flujo que viaja desde un único lugar de origen hacia un único lugar destino a través de arcos que conectan nodos intermedios

.Pasos a seguir :

Primer paso: Elegir una ruta arbitraria.

Segundo paso: En dicha ruta escoger aquel ramal de menor flujo en ese sentido y transportar por esa ruta la cantidad escogida.Hacer esto repetitivamente hasta que no sea posible encontrar una ruta con capacidad de flujo.

El origen puede despachar 28 unidades y el destino puede recibir 22 unidades, pero por las restricciones, el destino solo puede recibir 19 unidades en la ruta AB- BC – CD – DF – FG.

Algoritmo de Ford-Fulkerson

En 1962, L. R. Ford y D. R. Fulkerson desarrollaron una técnica efectiva para resolver problemas de flujo máximo. Es un método genérico para aumentar la capacidad de los flujos incrementalmente a lo largo de los caminos que van del origen al destino, que sirve como la base para un familia de algoritmos. Esta técnica es conocida como el método Ford-Fulkerson en la literatura clásica, aunque también puede encontrarse como el aumenting-path method.

El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, L. R. Ford, Jr. y D. R. Fulkerson.

Considérese cualquier camino dirigido del origen al destino en la red de flujos. Sea x la mínima de las capacidades de las aristas no usadas en el camino. Es posible incrementar el flujo de la red al menos en x, incrementando el flujo de las aristas del camino en dicho monto. De esta forma se obtiene el primer intento de flujo en la red. Luego debemos encontrar otro camino, incrementar el flujo en el camino, y continuar hasta que todos los caminos del origen al destino tengan al menos una arista llena (el flujo usa toda la capacidad de la arista).
Las siguientes figuras ilustran el funcionamiento de esta estrategia sobre el grafo de ejemplo. La secuencia de ilustraciones va de izquierda a derecha

FlujoMax1.png

Aunque esta estrategia calcula el flujo máximo en varios casos, también falla en muchos otros. Para mejorar el algoritmo de tal manera de que siempre encuentre el flujo máximo, se debe considerar una manera más general de incrementar el flujo de origen a destino a través del grafo no dirigido subyacente. Las aristas de cualquier camino del origen al destino avanzan o retroceden.
Las aristas que avanzan van con el flujo y las que retroceden van en sentido contrario al flujo. Ahora bien, para cada camino que no tenga aristas llenas que avancen ni aristas vacías (flujo cero) que retrocedan, podemos incrementar la cantidad de flujo en la red incrementando el flujo en las aristas que avanzan y decrementándo lo en las aristas que retroceden. La cantidad en la que el flujo puede ser incrementado está limitada por la mínima capacidad que no haya sido usada en las aristas que avanzan y los flujos de las aristas que retroceden.
Las siguientes figuras ilustran el funcionamiento de esta última estrategia en un nuevo grafo de ejemplo. La secuencia de ilustraciones va de izquierda a derecha y de arriba hacia abajo.

FlujoMax2.png

Hasta este punto no se han tomado en cuenta las aristas en retroceso y se tiene un flujo cuyo valor es 6. Ahora tratemos el camino 0 -1-2-3, pero usando la arista 2-1 que va en dirección contraria al flujo.

FlujoMax3.png

Obsérvese que se le resto valor al flujo que retrocede para agregárselo a los que avanzan. Aquí se obtiene un flujo de 7, que es el flujo máximo de esta red. En este momento ya no hay más caminos que no tengan aristas llenas que avancen o aristas vacías que retrocedan y el algoritmo culmina su ejecución.
Este proceso describe la base para el algoritmo clásico de Ford-Fulkerson (aumenting-path method) para problemas de flujo máximo en redes. En resumen:
Se comienza con flujo nulo en todas partes. Luego se incrementa el flujo a lo largo de cualquier camino de origen a destino que no tenga aristas llenas que avancen o aristas vacías que retrocedan. Se continúa hasta que no haya más caminos como estos en la red.
Este método siempre encuentra el flujo máximo, sin importar como se escojan los caminos.
Cuando las capacidades son valores enteros, el flujo se incrementa en al menos una unidad en cada iteración, así que la terminación es finita. Más aún, para un grafo con V nodos y A aristas con capacidades enteras positivas, el algoritmo ejecuta un máximo de V*A iteraciones para encontrar el flujo máximo. Chvátal describe el caso en el que las capacidades son irracionales.

Ejemplo: Determinar el flujo máximo en la red siguiente:

Iteración 1:

Determinan:
Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Paso 2: S1={2,3,4}.

Paso 3: k=2 y a2=c12=max{20,10,10}=20. Clasificamos el nodo 2 con [20,1]. Tomamos i=2 y repetimos el paso 2.

Paso 2: S2={3,5}

Paso 3: k=3 y a3=c23=max{30,40}=40. Clasificamos el nodo 3 con [40,2]. Tomamos i=3 y repetimos el paso 2.

Paso 2: S3={4} (c35=0, el nodo 1 ya ha sido clasificado y el nodo 2 cumple ambas condiciones, por tanto los nodos 1, 2 y 5 no pueden ser incluidos en S3).

Paso 3: k=4 y a4=c34=10. Clasificamos el nodo 4 con [10,3]. Tomamos i=4 y repetimos el paso 2.

Paso 2: S4={5}

Paso 3: k=5 y a5=c45=20. Clasificamos el nodo 5 con [20,4]. Logramos la penetracION

ITERRACION 2

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Paso 2: S1={2,3,4}.

Paso 3: k=2 y a2=c12=max{20,10,10}=20. Clasificamos el nodo 2 con [20,1]. Tomamos i=2 y repetimos el paso 2.

Paso 2: S2={3,5}

Paso 3: k=3 y a3=c23=max{30,40}=40. Clasificamos el nodo 3 con [40,2]. Tomamos i=3 y repetimos el paso 2.

Paso 2: S3={4} (c35=0, el nodo 1 ya ha sido clasificado y el nodo 2 cumple ambas condiciones, por tanto los nodos 1, 2 y 5 no pueden ser incluidos en S3).

Paso 3: k=4 y a4=c34=10. Clasificamos el nodo 4 con [10,3]. Tomamos i=4 y repetimos el paso 2.

Paso 2: S4={5}

Paso 3: k=5 y a5=c45=20. Clasificamos el nodo 5 con [20,4]. Logramos la penetración, vamos al paso 5.

Paso 5: La ruta de la penetración es: 5→[20,4]→4→[10,3]→3→[40,2]→2→[20,1]→1.Entonces la ruta es N2={1,2,3,4,5} y f2=min{∞,20,40,10,20}=10. Las capacidades residuales a lo largo de esta ruta son:

(c12,c21)=(20-10, 0+10)=(10,10)

(c23,c32)=(40-10, 0+10)=(30,10)

(c34,c43)=(10-10, 5+10)=(0,15)

(c45,c54)=(20-10, 0+10)=(10,10)

Iteración 3:

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
Paso 2: S1={2,3,4}.
Paso 3: k=2 y a2=c12=max{10,10,10}=10, rompemos el empate arbitrariamente. Clasificamos el nodo 2 con [10,1]. Tomamos i=2 y repetimos el paso 2.
Paso 2: S2={3,5}
Paso 3: k=3 y a3=c23=max{30,30}=30. Clasificamos el nodo 3 con [30,2]. Tomamos i=3 y repetimos el paso 2.
Paso 2: S3 vacío ya que c34=c35=0. Vamos al paso 4 para retroceder.
Paso 4: La clasificación [30,2] nos dice que el nodo inmediatamente precedente es el 2. Eliminamos el nodo 3 de una consideración posterior en esta iteración. Tomamos i=2 y repetimos el paso 2.
Paso 2: S2={5}
Paso 3: k=5 y a5=c25=30. Clasificamos el nodo 5 con [30,2]. Logramos la penetración, vamos al paso 5.
Paso 5: La ruta de la penetración es: 5→[30,2]→2→[10,1]→1.Entonces la ruta es N2={1,2,5} y f3=min{∞,10,30}=10. Las capacidades residuales a lo largo de esta ruta son:

(c12,c21)=(10-10, 10+10)=(0,20)

(c25,c52)=(30-10, 0+10)=(20,10)

Iteración 4

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
Paso 2: S1={3,4}.
Paso 3: k=3 y a3=c13=max{10,10}=10. Clasificamos el nodo 3 con [10,1]. Tomamos i=3 y repetimos el paso 2.
Paso 2: S3={2}
Paso 3: k=2 y a2=c32=10. Clasificamos el nodo 2 con [10,3]. Tomamos i=2 y repetimos el paso 2.
Paso 2: S2={5}
Paso 3: k=5 y a5=c25=20. Clasificamos el nodo 5 con [20,2]. Logramos la penetración, vamos al paso 5.
Paso 5: La ruta de la penetración es: 5→[20,2]→2→[10,3]→3→[10,1]→1.Entonces la ruta es N4={1,3,2,5} y f4=min{∞,10,10,20}=10. Las capacidades residuales a lo largo de esta ruta son:

(c13,c31)=(10-10, 20+10)=(0,30)

(c32,c23)=(10-10, 30+10)=(0,40)

(c25,c52)=(20-10, 10+10)=(10,20)

Iteración 5:

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
Paso 2: S1={4}.
Paso 3: k=4 y a4=c14=10. Clasificamos el nodo 4 con [10,1]. Tomamos i=4 y repetimos el paso 2.
Paso 2: S4={3,5}
Paso 3: k=3 y a3=c23=max{15,10}=15. Clasificamos el nodo 3 con [15,4]. Tomamos i=3 y repetimos el paso 2.
Paso 2: S3 vacío ya que c32=c34=c35=0. Vamos al paso 4 para retroceder.
Paso 4: La clasificación [15,4] nos dice que el nodo inmediatamente precedente es el 4. Eliminamos el nodo 3 de una consideración posterior en esta iteración. Tomamos i=4 y repetimos el paso 2.
Paso 2: S4={5}
Paso 3: k=5 y a5=c45=10. Clasificamos el nodo 5 con [10,4]. Logramos la penetración, vamos al paso 5.
Paso 5: La ruta de la penetración es: 5→[10,4]→4→[10,1]→1.Entonces la ruta es N2={1,4,5} y f3=min{∞,10,10}=10. Las capacidades residuales a lo largo de esta ruta son:

(c14,c41)=(10-10, 0+10)=(0,10)

(c45,c54)=(10-10, 10+10)=(0,20)

Iteración 6:

No son posibles más penetraciones, debido a que todos los arcos fuera del nodo 1 tienen residuales cero. Vayamos al paso 6 para determinar la solución.

Paso 6: El flujo máximo en la red es F=f1+f2+...+f5=60 unidades. El flujo en los diferentes arcos se calcula restando las últimas residuales obtenidas en la última iteración de las capacidades iniciales:

Arco	(Cij, Cji) - (cij, cji)en it. 6	Cantidad de flujo	Dirección
(1,2)	(20, 0) - (0, 20) = (20, -20)	20	1→2
(1,3)	(30, 0) - (0, 30) = (30, -30)	30	1→3
(1,4)	(10, 0) - (0, 10) = (10, -10)	10	1→4
(2,3)	(40, 0) - (40, 0) = (0, 0)	0	-
(2,5)	(30, 0) - (10, 20) = (20, -20)	20	2→5
(3,4)	(10, 5) - (0, 15) = (10, -10)	10	3→4
(3,5)	(20, 0) - (0, 20) = (20, -20)	20	3→5
(4,5)	(20, 0) - (0, 20) = (20, -20)	20	4→5

PERT (Program Evaluation and

Review Technique)

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 obtenenido 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 esta asociado a una función probabilistica 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 PERT:

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:

		Tiempo (Semanas)
Actividad	Predecesor	a	m	b
A	-	4	6	8
B	-	2	8	12
C	A,B	8	12	16
D	C	1	4	7
E	C	4	6	8
F	D,E	10	15	20
G	E	6	12	18
H	F,G	7	8	9

El primer paso consiste en calcular el tiempo esperado (te) asociado a cada actividad, utilizando la fórmula presentada anteriormente:

Actividad	te
A	6
B	8
C	12
D	4
E	6
F	15
G	12
H	8

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:

EJEMPLO 2:

RED EN TIEMPO OPTIMISTA

1. Probabilidad de que Z > 40

Calcule la varianza del proyecto:

Aplique la formula:

= 1- P (2.24)

Busque en la tabla de la distribución normal Z = 2.24; este es igual a =0.9875, entonces:

= 1- 0.9875 = 0.0125

La probabilidad de ocurrencia de este evento es de 1.25%

2. Probabilidad de que Z < 35

= P (-1.69) = 0.0455 = 4.55%

3. Probabilidad de que Z>37.15

= 1 - P (0) = 1 - 0.5 = 0.5 = 50%

CMP (RUTA CRTICA)

El método CPM o Ruta Crítica (equivalente a la sigla en inglés Critical Path Method) es frecuentemente utilizado en el desarrollo y control de proyectos. El objetivo principal es determinar la duración de un proyecto, entendiendo éste como una secuencia de actividades relacionadas entre sí, donde cada una de las actividades tiene una duración estimada.

En este sentido el principal supuesto de CPM es que las actividades y sus tiempos de duración son conocidos, es decir, no existe incertidumbre. Este supuesto simplificador hace que esta metodología sea fácil de utilizar y en la medida que se quiera ver el impacto de la incertidumbre en la duración de un proyecto, se puede utilizar un método complementario como lo es PERT.

Una ruta es una trayectoria desde el inicio hasta el final de un proyecto. En este sentido, la longitud de la ruta crítica es igual a la la trayectoria más grande del proyecto. Cabe destacar que la duración de un proyecto es igual a la ruta crítica.

Etapas de CPM

Para utilizar el método CPM o de Ruta Crítica se necesita seguir los siguientes pasos:

1. Definir el proyecto con todas sus actividades o partes principales.

2. Establecer relaciones entre las actividades. Decidir cuál debe comenzar antes y cuál debe seguir después.

3. Dibujar un diagrama conectando las diferentes actividades en base a sus relaciones de precedencia.

4. Definir costos y tiempo estimado para cada actividad.

5. Identificar la trayectoria más larga del proyecto, siendo ésta la que determinará la duración del proyecto (Ruta Crítica).

6. Utilizar el diagrama como ayuda para planear, supervisar y controlar el proyecto.

Por simplicidad y para facilitar la representación de cada actividad, frecuentemente se utiliza la siguiente notación:

Donde:

IC : Inicio más cercano, es decir, lo más pronto que puede comenzar la actividad.

TC : Término más cercano, es decir, lo más pronto que puede terminar la actividad.

IL : Inicio más lejano, es decir, lo más tarde que puede comenzar la actividad sin retrasar el término del proyecto.

TL : Término más lejano, es decir, lo más tarde que puede terminar la actividad sin retrasar el término del proyecto.

Adicionalmente se define el término Holgura para cada actividad que consiste en el tiempo máximo que se puede retrasar el comienzo de una actividad sin que esto retrase la finalización del proyecto. La holgura de una actividad se puede obtener con la siguiente fórmula:

Holgura = IL - IC = TL - TC

EJEMPLO:

A continuación se presenta un resumen de las actividades que requiere un proyecto para completarse. El tiempo de duración de cada actividad en semanas es fijo. Se solicita que estime la duración total del proyecto a través del método CPM.

*Actividad*	*Duración (sem)*	*Actividad Predecesora*
A	6	-
B	8	-
C	12	A,B
D	4	C
E	6	C
F	15	D,E
G	12	E
H	8	F,G

En consideración a las etapas del método CPM definidas anteriormente, en este caso se debe desarrollar el paso 3 y 5. En este sentido es necesario construir el diagrama identificando las relaciones entre las actividades y con el objetivo de resumir la metodología se incorporará inmediatamente el cálculo de la Holgura, IC, TC, IL, TL para cada actividad, junto con la identificación de la ruta crítica.

Primero se construye el diagrama identificando cada actividad en un nodo (círculo) con su nombre respectivo y entre paréntesis el tiempo estimado. Las flechas entre actividades señalan las relaciones de predecencia, por ejemplo, la actividad F sólo puede comenzar una vez terminadas las actividades D y E.

Luego, se identifica para cada actividad los indicadores IC y TC. Por ejemplo, para la actividad C el inicio más cercano es 8 (esto porque C sólo puede comenzar una vez terminada A y B, siendo B la que más se demora y termina en 8) y el término más cercano es 20 (dado que la actividad C demora 12 semanas).

Posteriormente se obtiene el IL y TL para cada actividad. Con esta información el cálculo de la holgura de cada actividad es simple. Para obtener el IL y TL de cada actividad nos "movemos" desde el final hasta el inicio. En este caso la actividad que termina más tarde es H (49 sem) y por tanto nos preguntamos cuándo es lo más tarde que podría termina H sin retrasar el proyecto (TL), esto claramente es 49. Por tanto si lo más tarde que puede terminar H es 49, lo más tarde que puede comenzar H para cumplir este tiempo es 41 (dado que H dura 8 sem). Luego, la holgura de H es cero. Notar que las actividades con holgura igual a cero corresponden a las actividades de la ruta crítica. Adicionalmente, un proyecto puede tener más de una ruta crítica.

En nuestro ejemplo la ruta crítica (única) esta conformada por las actividades B-C-E-F-H con una duración total de 49 semanas.

modelosdeinventario

Social Icons

Pages

Featured Posts

miércoles, 3 de julio de 2013

TEORIA DE COLAS

modelos de redes

Algoritmo de Ford-Fulkerson

PERT (Program Evaluation and

Review Technique)

EJEMPLO PERT:

Etapas de CPM

Popular Posts

Sample Text

Followers

About Me

Social Icons

Blog Archive

Sample text

Sample Text

Sample Text