Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 106 vistas

    Mmdi U3 A3 Rudr

    Cargado por

    RUBEN DELGADO REYES
    Este documento presenta una actividad sobre el algoritmo de Dijkstra para encontrar la ruta crítica o camino más largo en un proyecto. Se proporciona una tabla de actividades para comprar un auto y se pide construir un grafo representando el proyecto, aplicar el algoritmo de Dijkstra usando un software de grafos para encontrar la ruta crítica, y copiar la imagen del grafo y los resultados.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Mmdi U3 A3 Rudr

    Cargado por

    RUBEN DELGADO REYES
    106 vistas7 páginas
    Este documento presenta una actividad sobre el algoritmo de Dijkstra para encontrar la ruta crítica o camino más largo en un proyecto. Se proporciona una tabla de actividades para comprar un auto y se pide construir un grafo representando el proyecto, aplicar el algoritmo de Dijkstra usando un software de grafos para encontrar la ruta crítica, y copiar la imagen del grafo y los resultados.

    Descripción original:

    Título original

    MMDI_U3_A3_RUDR.docx

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta una actividad sobre el algoritmo de Dijkstra para encontrar la ruta crítica o camino más largo en un proyecto. Se proporciona una tabla de actividades para comprar un auto y se pide construir un grafo representando el proyecto, aplicar el algoritmo de Dijkstra usando un software de grafos para encontrar la ruta crítica, y copiar la imagen del grafo y los resultados.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    106 vistas7 páginas

    Mmdi U3 A3 Rudr

    Cargado por

    RUBEN DELGADO REYES
    Este documento presenta una actividad sobre el algoritmo de Dijkstra para encontrar la ruta crítica o camino más largo en un proyecto. Se proporciona una tabla de actividades para comprar un auto y se pide construir un grafo representando el proyecto, aplicar el algoritmo de Dijkstra usando un software de grafos para encontrar la ruta crítica, y copiar la imagen del grafo y los resultados.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    de 7

    Unidad 3 Matemáticas Discretas

    Universidad Abierta y a Distancia de México.

    Licenciatura en Matemáticas

    Discretización y Modelación de problemas


    mediante la teoría grafica (aplicación)

    Nombre del alumno: Rubén Delgado Reyes

    Matricula: AL508930
    Unidad 3 Matemáticas Discretas

    Actividad 3: Algoritmo de Dijkstra para la modelación y solución de


    un problema de ruta crítica o camino más largo.
    Antecedentes.

    El algoritmo de Dijkstra, aunque fue diseñado para encontrar la ruta más corta, se puede
    transformar fácilmente para encontrar la ruta más larga (camino crítico), cambiando simplemente
    su función objetivo. El camino crítico estará formado por tareas críticas (que se representarán por
    nodos) cuya duración, representada por los arcos, determina la duración total de un proyecto. Si
    una tarea crítica se retrasa o su duración cambia durante la realización del proyecto, afectaría
    directamente a la duración total del proyecto y a su fecha de finalización. Encontrar el camino
    crítico de la planificación de un proyecto es lo mismo que encontrar el camino más largo desde el
    nodo inicial (tarea inicial) al nodo final (última tarea); esto es, la mínima cantidad de tiempo
    necesaria para finalizar un proyecto.
    Instrucciones: A partir de la siguiente tabla de actividades para comprar un auto nuevo, realiza lo
    que se pide en cada inciso. Para la solución de este problema es indispensable que uses el
    programa Grafos (u otro software que maneje Teoría de Gráficas como el Geogebra), pues el
    objetivo es que aprendas a manejar un software que te ayude a darle solución a una amplia
    variedad de problemas que puedan resolverse mediante algoritmos de la Teoría de Gráficas.
    Consulta el algoritmo de Dijkstra, así como ejemplos de su solución, en los documentos y videos
    recomendados en el foro de Planeación didáctica de la unidad.

    1. Usando el algoritmo de Dijkstra:


    Unidad 3 Matemáticas Discretas
    i. Construye una gráfica que describa el proyecto.
    ii. Encuentra el camino crítico o ruta crítica (el camino más largo).

    (TIP: Los vértices o nodos serán las actividades y los pesos de las aristas serán los tiempos de
    duración. En este caso considera el tiempo de la actividad como el peso de la arista precedente.
    Puede ayudarte adicionar dos nodos ficticios como inicio y final, en donde el peso de la arista que
    una al nodo inicio con el nodo A será la duración de A. El peso de la arista que una al nodo O con
    el nodo final será de cero. También considera que no estás buscando el camino mínimo sino el
    camino máximo, la función objetivo cambia por lo que los vértices que seleccionarás serán los
    máximos).

    I.-
    Unidad 3 Matemáticas Discretas
    II.-

    La ruta crítica es:

    1-A-B-E-2-F-G-H-3-J-K-L-4-0-5

    Real:

    A-B-E-F-G-H-J-K-O

    Coste: 26
    Unidad 3 Matemáticas Discretas

    2. Usa el programa GRAFOS para encontrar la ruta crítica del proyecto mediante el
    algoritmo de Dijkstra. En este caso tendrás que construir con el programa la
    representación gráfica del problema y aplicarle el algoritmo de Dijkstra para el
    camino crítico, seleccionando el nodo inicial y el nodo final. Copia como imagen la
    gráfica y el resultado del cálculo del algoritmo.

    Arco calculados del nodo origen 1 hasta 5

    - 1----(5)--A
    - A---(3)-- B
    - B----(2)- E
    - E----(0)-2
    - 2----(1)- F
    - F----(1)--G
    - G----(3)--H
    - H----(0)--3
    - 3----(2)--J
    - J----(2)--J
    - K----(4)--L
    - L----(0)--4
    - 4----(3)--0
    Unidad 3 Matemáticas Discretas
    - 0----(0)--5

    - Coste total 26

    Matriz de Arcos con coste máximo


    Unidad 3 Matemáticas Discretas

    También podría gustarte