Investigacion de operaciones

Universidad de Sonora Departamento de Matemáticas

Tesis

dIBLIOTECA 1 DE CIENCIAS EXACTA Y NATURALES

Algoritmos de Gráficas para el Método de Ruta Crítica
ue para obtener el titulo de

Licenciado en Matemáticas

Presenta

Reynaldo Figueroa Galindo

Hermosillo, Sonora, 15 de Agosto de 1997

Contenido
Introducción 1 EL PROBLEMA DE LA SECUENCIA DE PROYECTOS 1.1 Problema de laRuta Crítica (CPM) 1.2 Diagramas o modelos 1.3 Planteamiento de Problemas 1.3.1 Problema de construcción 1.3.2 Establecimiento de una fabrica 1.3.3 Fabricación de un nuevo Producto 2 LA TECNICA CPM EN LA SECUENCIA DE PROYECTOS 2.1 Determinación de la Ruta Crítica 2.1.1 Definición de Ruta Crítica 2.2 Determinación de las Holguras 2.3 Relación entre Duración y el Costo de unaActividad 2.4 Acortamiento de una actividad 2.5 Representación Lineal del CPM 2.6 Modelo Matemático del CPM 2.7 Como Determinar P(A) 3 Ejemplo con Aplicaciones del Algoritmo de Fulkerson 3.1 Ejemplo 1 3

5
6 6 9 9 11 13 17 18 21 22 23 25 44 47 58 63 63

CONTENIDO Conclusiones A ALGORITMOS DE GRAFICAS PARA EL PROBLEMA CPM A.1 Algoritmo de Dijkstra A.2 Algoritmo de Ford FulkersonBibliografía 119 121 121 123 125

CONTENI DO 3 INTRODUCCION

En la actualidad existe un gran problema para poder planificar y programar proyectos de la industria y de la construcción. Hoy en dia existe una gran cantidad de libros de Investigación de operaciones en los cuales hablan mucho de estos problemas pero ninguno nos dicen como llevarlos a la practica, el proposito de nuestrotrabajo es dar a conocer al lector un procedimiento para resolver este tipo de problemas. Uno de los métodos usados para resolver este tipo de problemas es el Método de la ruta crítica (CPM) en el que representa un proyecto mediante una red, la cual consiste en una serie de actividades que tienen una determinada secuencia para realizarlas, es decir, existe una relación de tal manera que una no se puederealizar hasta que otra halla terminado. Aqui presentamos un procedimiento para desarrollar un proyecto de tal manera que resulta muy sencillo utilizando gráficas denominadas redes, cómo las actividades se pueden realizar más rapido a costo de un precio más alto. Nuestro objetivo es encontrar una solución al problema donde el costo sea mínimo bajo un tiempo razonable. El trabajo se divide en 4capítulos, en los 3 primeros se desarrolla todo el material teótico y en el cuarto capítulo desarrollamos un ejemplo completo. En el primer capítulo se presentan el método del CPM y algunos ejemplos de problemas los cuales se representan mediante una red que los modela y se quiere encontrar el costo mínimo bajo un tiempo razonable para lo cual el CPM es un método muy práctico para resolver nuestrotrabajo. Aqui se resuelve un ejemplo intuitivamente. En el capítulo 2 determinaremos como podemos encontrar y definir la ruta crítica, las holguras las cuales nos indican el tiempo que debemos esperar para empezar una actividad, ademas veremos la relación que existe entre la duración y el costo de una actividad, y resolveremos un ejemplo para observar como se acortan dichas actividades. En estecapítulo se incluye tambien los fundamentos teoricos de nuestro trabajo En el capítulo 3 desarrollaremos un ejemplo completo utilizando el algoritmo de Ford Fulkerson para encontrar el mayor flujo posible para poder observar todos las posibles soluciones que existen y poder ver cual es la mejor, es decir, la que nos da el mejor costo bajo un tiempo rasonable. Por último, tenemos un anexo en dondemencionamos los algoritmos que utilizamos para la solución de nuestros problemas entre ellos se encuentran el de Dijkstra y Ford Fulkerson.

CONTENIDO

Capítulo 1
EL PROBLEMA DE LA SECUENCIA DE PROYECTOS
Un proyecto es una serie de actividades las cuales tienen una determinada secuencia para poder realizarlas, es decir, existe una relación tal que una actividad no se realiza hasta que otras...