Modelos de redes PDF

Preview

Summary

Se explica detalladamente la teoria, interpretacion y elaboracion de los modelos de redes...

Description

UNIDAD TRES MODELOS DE REDES OBJETIVO El alumno identificará y aplicará modelos para la solución de problemas específicos en el área de administración.

INTRODUCCION Los proyectos en gran escala han existido desde tiempos antiguos; este hecho lo atestigua la construcción de las pirámides de Egipto y los acueductos de Roma. Pero sólo desde hace poco se han analizado por parte de los investigadores operacionales los problemas gerenciales asociados con dichos proyectos. El problema de la administración de proyectos surgió con el proyecto de armamentos del Polaris, empezando 1958. Con tantas componentes y subcomponentes juntos producidos por diversos fabricantes, se necesitaba una nueva herramienta para programar y controlar el proyecto. El PERT (evaluación de programa y técnica de revisión) Casi al mismo tiempo, la Compañía DuPont, junto con la División UNIVAC de la Remington Rand, desarrolló el método de la ruta crítica (CPM). Los problemas de redes surgen de una gran variedad de situaciones reales tales como redes de transportes, eléctricas y de comunicación. La representación de redes se utiliza ampliamente en campos tan diversos como son: Producción, Distribución, Planeación de proyectos, Localización de instalaciones, Administración de recursos humanos y Planeación financiera. De hecho una representación de redes proporciona un panorama general y ayuda a visualizar las relaciones entre los componentes de los sistemas que se utilizan ya sea científicamente, socialmente y económicamente.

1

Uno de los mayores desarrollos en la investigación de operaciones ha sido el rápido avance tanto en la metodología como en la aplicación de los modelos de redes. En esta parte del curso solo se podrán plantear las bases de la metodología de redes, estos problemas tienen una estructura específica que surge con frecuencia en la vida práctica. La Planeación y control de proyectos es el tipo de problemas que se resuelven por la técnica de redes utilizando el método de PERT/CPM proporciona una herramienta para controlar y monitorear el progreso del proyecto. Estas herramientas han demostrado ser muy simples pero eficaces en la planeación y control de proyectos.

3.1 CONCEPTOS Los modelos de redes son aplicables a una extensa variedad de problemas de decisión, los cuales pueden ser modelados como problemas de optimización de redes que pueden ser eficiente y efectivamente resueltos. Algunos de estos problemas de decisión son realmente problemas físicos, tales como el transporte o flujo de bienes materiales. Sin embargo, muchos problemas de redes son más que una representación abstracta de procesos o actividades, tales como el camino crítico en las actividades entre las redes de un proyecto gerencial. La familia de redes de los problemas de optimización incluye los siguientes la ruta mas corta, el árbol de expansión mínimo, la ruta critica. Los problemas son establecidos fácilmente mediante el uso de arcos de redes y de los nodos. ¿Que es un Nodo? Es usualmente llamado vértice, o punto. Es usualmente representado por un círculo. En las redes de transporte, estos deberían ser las localidades o las ciudades en un mapa.

2

¿Que es un Arco? Es usualmente llamado borde o flecha. Este podría ser directo o indirecto. La cabeza es el destino, y la cola el origen. La cabeza y la cola son nodos que pueden estar tanto al origen como al final. En las redes de transporte, los arcos podrían ser los caminos, los canales de navegación en un río, o los patrones de vuelo de un avión. Los arcos proporcionan la conectividad entre los nodos. Una calle de una sola dirección podría ser representada por un arco, mientras que una calle de dos direcciones podría representada por un arco sin dirección o por dos arcos que apuntan a direcciones opuestas.

En esta unidad utilizaremos el concepto de red que se representa de la siguiente manera con sus respectivos elementos.

Red Dirigida D

B

F

A

C

E

Red No Dirigida B

A

D C 3

Nodos

Arcos o Ramas

A

B

C

D

E

F

AB, AC, BD, CE, DF, EF

Si a un arco se le permite su flujo en una sola dirección se dice que es un arco dirigido, si una red se compone solamente de arcos dirigidos se le da el nombre de red dirigida. Si aun arco se le permite su flujo en ambas direcciones a este se le da el nombre de arco no dirigidos, si una red Contiene al menos un arco no dirigido esta red se le llamara red no dirigida.

3.2 LA RUTA MÁS CORTA El problema de la ruta más corta se refiere a la red en la que cada árbol o rama tiene asociado un número que se interpreta como la distancia, el costo o el tiempo que hay entre los nodos. El objetivo principal consiste en determinar la ruta más corta de un nodo y otro. SUPOSICIONES DEL PROBLEMA LA RUTA MAS CORTA. Se precisa escoger una ruta a través de la red que comienza en cierto nodo, llamado origen y termina en otro nodo, llamado destino. Las líneas o flechas que conectan ciertos pares de nodos, en general son ligaduras (que permiten viajar en cualquier dirección) 4

Cada flecha o arco tiene asociado un número que se interpreta como la distancia, el costo o el tiempo que hay entre los nodos. El objetivo es hallar la ruta mas corta (la ruta con la distancia mínima total) desde el origen hasta el destino. Las tres principales categorías de aplicación son las siguientes: Minimizar la distancia total recorrida. Minimizar el costo total de una secuencia de actividades. Minimizar el tiempo total de una secuencia de actividades El algoritmo que se usa, emplea el procedimiento de etiquetas es decir, conforme avanza el algoritmo se determina una etiqueta para cada nodo. Esta etiqueta asocia 2 números en un rectángulo para cada nodo, el primer número de la etiqueta representa la distancia entre un nodo y el otro y el segundo representa al nodo predecesor.

Et i que t as

Distancia entre 2 nodos

Nodo predecesor

Tempor al es Ti posde Et i que t as Per manent es

DESCRIPCION DE ALGORITMOS PARA ENCONTRAR LA RUTA MÁS CORTA. 5

1.- Se etiqueta el primer nodo de la red con etiqueta permanente. 2.- A partir de este nodo se ramifica hacia fuera y en cada nodo se le asigna una etiqueta temporal con su respectiva distancia y nodo predecesor. 3.- Se escoge de todas las etiquetas temporales la etiqueta con menor distancia y se hace permanente, si hubiera algún empate se escoge una arbitrariamente. 4.- Se repiten los pasos anteriores hasta que todos los nodos de la red tengan su etiqueta permanente. 5.- La información de cada nodo se encuentra en las etiquetas permanentes.

EJEMPLO: Cierta empresa realiza frecuentes repartos a 9 municipios del Edo. De Morelos desde su planta ubicada en Civac. La siguiente figura muestra los 9 municipios como sus posibles rutas. La figura también muestra los kilómetros de distancia que existe entre un municipio y el otro. Determine la ruta mas corta del nodo P al nodo I, nodo P al nodo G, del P al F. SOLUCION Se inicia en el nodo P con etiqueta permanente 0,0(en la figura no aparece el 0,0 pero debe de aparecer) Se ramifica Asia afuera. Es decir, el nodo A tendrá una etiqueta temporal P,4. El nodo B tendrá su etiqueta temporal P,3. El nodo C tendrá su etiqueta temporal P,5. Tal como se muestra en la figura. De estas tres etiquetas temporales la que tenga la menor distancia se vuelve etiqueta permanente.(es la P,3 del nodo B) Del nodo B se ramifica Asia afuera y tendremos las siguientes etiquetas temporales, para el nodo D su etiqueta temporal será B,7( se suman los valores 3+4). Para el nodo F su etiqueta temporal será B,9(se suman los valores 3+6).para el nodo E su etiqueta temporal será B,6(se suman los valores 3+3). De todas la etiquetas temporales hasta este momento que son Nodo A, nodo C, nodo D, nodo E y nodo F, se escoge la etiqueta con menor valor que es la etiqueta del nodo A y se hace permanente. A partir de esta etiqueta permanente (nodo A) se ramifica asía afuera. SE REPITEN LOS PASOS ANTERIORES HASTA QUE TODOS LOS NODOS DE LA RED TENGAN SU ETIQUETA PERMANENTE. 6

Tal como se muestra en la figura

a). Nodo P al Nodo I = 15 Km.

Nodos = PB, BF, FI

b). Nodo P al Nodo G = 14 Km.

Nodos = PB, BF, FG

c). Nodo P al Nodo F = 9 Km.

Nodos = PB, BF

nota: el nodo D tiene dos etiquetas, la etiqueta temporal 4,A tiene un error en ves de 4 debe ser 8.

7

EJEMPLO 2 Determine la ruta mas corta del nodo Z a los siguientes H, I , J

3

Z

9

A

6

A

1

3

2 2

Z 0

0

6

C

5

8

6

9

J 3

C

4

F

E

4

Z

15 I

18 12H F

4

H

3

5

4

8

K

19 I

RECORRI DO

J

19 I 20 A

16 H

12 E

Distancia mínima de Z – L 19 Km.

L

7

12 F

B

20

7

I

6

B 5

11 D

6

5

4

17 G

G

3

Z

14 F

2

D

nodos de la red. L,

4

ZC, CF, FI, IL Z – H 12 Km. Z – I 12 Km.

ZC,CF,FH ZC, CF, FI

Z – J 15 Km. ZC, CF, FI, IJ

El Árbol De Expansión Mínimo. Es un problema clásico de optimización combinatoria, formulado en 1926 por Boruvka quien lo planteó para resolver el problema de hallar la forma más económica de distribuir energía eléctrica en el sur de Moravia. La formulación de este problema ha sido útil para la realización de muchas investigaciones en varios campos como el transporte, electrónica, telecomunicaciones e investigación de operaciones. El modelo contempla un conjunto de arcos que conectan todos los nodos de la red sin crear un solo ciclo o vuelta. El problema consiste en determinar el árbol que minimiza la distancia de conexión total; se resuelve por el Algoritmo de Etiquetado. En cuanto a la introducción de datos y el proceso de solución es similar al modelo anterior. El problema del Árbol de expansión mínimo problema de la ruta mas corta, sin embargo encontrar la ruta mas corta a través de toda expansión mínimo es una red que contiene distancia.

tiene algunas similitudes con el la diferencia principal radica en la red. En resumen el Árbol de todos los nodos con la mínima

Procedimiento Para Encontrar El Árbol De Expansión Mínimo: 1.- Se ubican las distancias de la red en una tabla. 2.- Se inicia con el primer renglón de la tabla o el renglón que tenga el mínimo valor. Este se designa como nodo conectado y se le asigna una marca a este renglón, se tacha la columna que corresponda a este renglón marcado. 3.- Considerando todos los renglones que están marcados se busca el valor mínimo en todas las columnas que no han sido tachadas y se encierra ese valor en un circulo, si hubiere algún empate se escoge (alguno) uno arbitrariamente. La columna que contenga este valor mínimo se tacha y se coloca una marca al renglón correspondiente a esta columna. 4.- Se repite el punto anterior hasta que todos los renglones de la tabla estén marcados. 5.- Se constituye el Árbol de expansión mínimo mediante los valores encerrados en circulo pare formar un red y se determina su mínima longitud. Ejercicio 1. 9

Cierto banco va a instalar una red de comunicación entre las 12 sucursales que se encuentran en las principales ciudades del Estado de Morelos, con la finalidad de optimizar sus transacciones entre ellas. Los costos de los posibles enlaces directos entre las sucursales aparecen en el siguiente diagrama. Determine la red mínima o el Árbol de expansión mínimo para enlazar las 12 sucursales bancarias a un costo mínimo.

Llenado de tabla.

ļ ļ ļ ļ ļ ļ ļ ļ ļ ļ ļ ļ

X X X X X X X X X X 1 2 3 4 5 6 7 8 9 10 1 4 1 2 4 6 3 3 6 7 7 4 7 2 5 1 4 9 6 3 4 5 7 7 7 5 2 8 2 2 9 9 5 10 7 5 11 5 3 12 4

Se suman los números encerrados o de color. La red que conecta a los 12 nodos tiene un costo de 37.

10

X X 11 12

5 4 3 2 2

Después de sumar, se marca la red en el diagrama, correspondiendo cada número marcado. Ejercicio 2. El contador de un despacho tiene el compromiso de instalar 12 terminales de cómputo en red para sus empleados. Con el objetivo de aumentar la productividad en su trabajo. Determine el árbol de expansión mínimo que enlaza las 12 terminales a un costo mínimo, los posibles enlaces y sus costos entre ellos se muestran en la figura siguiente:

Llenado de tabla.

ļ ļ ļ ļ ļ ļ ļ ļ ļ ļ ļ ļ

X X X X X X X X X X 1 2 3 4 5 6 7 8 9 10 1 3 6 2 2 3 5 3 5 3 5 7 5 4 7 4 4 5 6 4 4 6 2 3 4 6 4 2 7 5 5 4 6 5 4 8 4 5 9 4 4 3 10 2 4 3 11 4 3 12 7 7

La red que conecta a los 12 nodos tiene un costo de 38.

11

X X 11 12

4

7 7

3 5 5

3.3 ADMINISTRACION DE PROYECTOS CON PERT / CPM Los proyectos modernos abarcan desde la construcción de un centro comercial hasta servir un banquete a domicilio incluyendo desarrollar un nuevo software o la instalación de un centro de cómputo. Complementar o terminar dichos proyectos a tiempo y dentro del presupuesto fijado no es tarea fácil. En particular tenemos que los problemas se complican cuando se reprograman dichos proyectos normalmente ciertas actividades no pueden realizase antes de terminarse otras. También es posible que los productos involucren muchas relaciones de dependencia entre las actividades, por lo que el personal encargado de llevar a cabo dicho proyecto busque nuevos métodos efectivos de análisis como son: P. E .R. T. / C. P. M. METODO PERT (program evaluatión Review technique ) el método PERT (Program Evaluation and Review Technique) desarrollado por la Armada de los Estados Unidos de América, en 1957, para controlar los tiempos de ejecución de las diversas actividades integrantes de los proyectos espaciales, por la necesidad de terminar cada una de ellas dentro de los intervalos de tiempo disponibles. Fue utilizado originalmente por el control de tiempos del proyecto Polaris y actualmente se utiliza en todo el programa espacial, también ha sido ampliamente aceptada en la industria privada y en el gobierno. Este método se aplica a problemas tan diversos; como la perforación de un pozo. Llevar una auditoria, instalación de un sistema de computadora. Hay muchas empresas y dependencias gubernamentales que exigen que todos sus contratistas o proveedores usen el método P.E.R.T METODO C.P.M. (Critical Paw Method). método actual, fue desarrollado también en 1957 en los Estados Unidos de América, por un centro de investigación de operaciones para la firma Dupont y Remington Rand, buscando el control y la optimización de los costos de operación mediante la planeación adecuada de las actividades componentes del proyecto. Ambos métodos aportaron los elementos administrativos necesarios para formar el método del camino crítico actual, utilizando el control 12

de los tiempos de ejecución y los costos de operación, para buscar que el proyecto total sea ejecutado en el menor tiempo y al menor costo posible. El PERT/CPM fue diseñado para proporcionar diversos elementos útiles de información para los administradores del proyecto. Primero, el PERT/CPM expone la "ruta crítica" de un proyecto. Estas son las actividades que limitan la duración del proyecto. En otras palabras, para lograr que el proyecto se realice pronto, las actividades de la ruta crítica deben realizarse pronto. Por otra parte, si una actividad de la ruta crítica se retarda, el proyecto como un todo se retarda en la misma cantidad. Las actividades que no están en la ruta crítica tienen una cierta cantidad de holgura; esto es, pueden empezarse más tarde, y permitir que el proyecto como un todo se mantenga en programa. El PERT/CPM identifica estas actividades y la cantidad de tiempo disponible para retardos.

La programación de proyectos con PERT / CPM consiste en tres etapas. 





PLANEACION. Se inicia descomponiendo el proyecto en actividades distintas, las estimaciones de tiempo para estas actividades se determinan de acuerdo con la experiencia del administrador o el encargado de dicha actividad. Se construye una red donde cada una de sus líneas representan una actividad. La red completa muestra una representación grafica de las interdependencias entre las actividades del proyecto. La construcción de la red como una fase de planeación, tiene la ventaja de estudiar las diferentes actividades en detalle, sugiriendo mejoras antes de que el proyecto se ejecute. PROGRAMACION. En esta etapa se construye el diagrama de tiempo que muestra los tiempos de inicio y de terminación para cada actividad así como su relación con otras actividades del proyecto. Además el programa debe señalar las actividades criticas que requieren atención especial, si el proyecto se quiere terminar en una fecha preestablecida. CONTROL. Es la fase final en la admón. Del proyecto esto incluye el uso de la red y las graficas de tiempo para hacer reportes periódicos del progreso del proyecto. La red puede por consiguiente actualizarse y analizarse las veces que sea necesario para administrar el proyecto con eficiencia.

REPRESENTACION DE LA RED.

13

El diagrama de flechas (RED) representa las interdependencias y las relaciones de procedencia entre las actividades del proyecto, se utiliza comúnmente una flecha para representar una actividad y la punta indicada el sentido de avance del proyecto, la relación de procedencia entre las actividades se especifica utilizando eventos. Un evento significa la terminación de una actividad y el comienzo de una nueva es decir, el punto de inicio y punto final de una actividad esta descrita por 2 eventos conocidos como Evento de Comienzo y Evento Final, tal como se muestra en el siguiente ejemplo.

EJEMPLO:

Actividad A Actividad A

Evento. Inicial

Evento. Final

REGLAS PARA CONSTRUIR REDES. 1.- Cada actividad esta representada por solamente una flecha de red, ninguna actividad puede representarse dos veces en la red. 2.- Dos actividades diferentes no pueden identificarse por los mismos eventos finales y de inicio, una situación como esta puede surgir cuando 2 o más actividades se realizan simultáneamente. El procedimiento a utilizar es introducir una actividad ficticia ya sea entre la actividad A y uno de los eventos finales o entre la actividad B y uno de los eventos finales.

EJEMPLO:

Forma Incorrecta

A

A 14

B

F

F B

FORMA CORRECTA DE REPRESENTAR DOS ACTIVIDADES QUE INICIAN SIMULTANEAMENTE

3.- A fin de asegurar la relación correcta de precedencia en la red las siguientes preguntas deben contestarse cuando se agrega cada actividad a la red: a) Que actividad debe terminarse inmediatamente antes de que la actividad actual vuelva a iniciar. b) Que actividades deben seguir a la actividad actual. c) Que actividades deben efectuarse simultáneamente con esta actividad.

EJEMPLOS Construya una red a partir de las siguientes actividades que se muestran en la tabla

ACTIVIDAD A B C D E

ACTIVIDAD ANTERIOR NINGUNA NINGUNA A B C, D

15

Construya una red a partir de las siguientes actividades que se muestran en la tabla

Ejercicio 2. ACTIVIDAD A B C D E F G N

...