P3_OP.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNhpfcfrH9rUlXgf2KXZlj7",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/rociavl/UNI/blob/main/P3_OP.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import networkx as nx\n",
        "\n",
        "def crear_grafo(precedencias, tiempos_proyecto):\n",
        "    # Crear el grafo dirigido\n",
        "    G_proyecto = nx.DiGraph()\n",
        "\n",
        "    # Agregar un nodo ficticio inicial\n",
        "    nodo_inicial_ficticio = 'α'\n",
        "    for tarea, predecesores in precedencias.items():\n",
        "        if not predecesores:  # Si la tarea no tiene predecesores\n",
        "            G_proyecto.add_edge(nodo_inicial_ficticio, tarea, weight=0)  # Conectar al nodo ficticio con peso 0\n",
        "        for predecesor in predecesores:\n",
        "            G_proyecto.add_edge(predecesor, tarea, weight=tiempos_proyecto[tarea])\n",
        "\n",
        "    # Añadir nodo ficticio final\n",
        "    nodo_final_ficticio = 'ω'\n",
        "    for tarea in list(G_proyecto.nodes):\n",
        "        if G_proyecto.out_degree(tarea) == 0 and tarea != nodo_inicial_ficticio:\n",
        "            G_proyecto.add_edge(tarea, nodo_final_ficticio, weight=0)\n",
        "\n",
        "    # Añadir tiempos de procesamiento como atributos de nodos\n",
        "    nx.set_node_attributes(G_proyecto, tiempos_proyecto, 'duration')\n",
        "    camino_critico = nx.dag_longest_path(G_proyecto)\n",
        "\n",
        "    return G_proyecto, camino_critico\n",
        "\n",
        "def recalcular_tiempos(G, tiempos_proyecto):\n",
        "    \"\"\"Función para recalcular los tiempos de inicio y final para el grafo modificado\"\"\"\n",
        "\n",
        "    # Calcular Early Start (ES) y Early Finish (EF)\n",
        "    early_start = {nodo: 0 for nodo in tiempos_proyecto}  # Solo nodos reales\n",
        "\n",
        "    for nodo in nx.topological_sort(G):  # Orden topológico\n",
        "        if nodo in tiempos_proyecto:  # Solo calcular para nodos reales\n",
        "            for predecesor in G.predecessors(nodo):\n",
        "                if predecesor in early_start:  # Verificar que el predecesor esté en early_start\n",
        "                    early_start[nodo] = max(early_start[nodo], early_start[predecesor] + tiempos_proyecto[predecesor])\n",
        "\n",
        "    early_finish = {nodo: early_start[nodo] + tiempos_proyecto[nodo] for nodo in early_start}\n",
        "\n",
        "    # Duración total del proyecto es el máximo tiempo de finalización\n",
        "    duracion_total_proyecto = max(early_finish.values())\n",
        "\n",
        "    # Calcular Late Finish (LF) y Late Start (LS) hacia atrás\n",
        "    late_finish = {nodo: duracion_total_proyecto for nodo in tiempos_proyecto}  # Solo nodos reales\n",
        "\n",
        "    for nodo in reversed(list(nx.topological_sort(G))):  # Invertimos el orden topológico\n",
        "        if nodo in tiempos_proyecto:  # Solo calcular para nodos reales\n",
        "            for sucesor in G.successors(nodo):\n",
        "                if sucesor in late_finish:  # Verificar que el sucesor esté en late_finish\n",
        "                    late_finish[nodo] = min(late_finish[nodo], late_finish[sucesor] - tiempos_proyecto[sucesor])\n",
        "\n",
        "    late_start = {nodo: late_finish[nodo] - tiempos_proyecto[nodo] for nodo in late_finish}\n",
        "\n",
        "\n",
        "    return early_start, early_finish, late_start, late_finish, duracion_total_proyecto\n",
        "\n",
        "def incompatibilidad(node1, node2, early_start, late_start, tiempos_proyecto, duracion_total_proyecto):\n",
        "    \"\"\"Calcula el impacto en la duración total del proyecto si se cambia la precedencia entre node1 y node2\"\"\"\n",
        "    # D_max calcula el nuevo tiempo para ambas opciones\n",
        "    D_max = {\n",
        "        'Right': early_start[node1] + tiempos_proyecto[node1] + (duracion_total_proyecto - late_start[node2]),\n",
        "        'Left': early_start[node2] + tiempos_proyecto[node2] + (duracion_total_proyecto - late_start[node1])\n",
        "    }\n",
        "\n",
        "    mejor_opcion = min(D_max, key=D_max.get)  # Mejor opción\n",
        "    respuesta = f'{node1} -> {node2}' if mejor_opcion == 'Right' else f'{node2} -> {node1}'\n",
        "\n",
        "    # Ahorro calculado\n",
        "    ahorro = max(D_max.values()) - min(D_max.values())\n",
        "    return min(D_max.values()), respuesta, ahorro\n",
        "\n",
        "def comp_incompatibilidad(Casos, G, early_start, late_start, tiempos_proyecto, duracion_total_proyecto):\n",
        "    \"\"\"Función que evalúa todas las incompatibilidades y selecciona la mejor opción\"\"\"\n",
        "    ahorros = {}\n",
        "    for caso in Casos:\n",
        "        node1, node2 = caso\n",
        "        nueva_duracion_total, respuesta, ahorro = incompatibilidad(\n",
        "            node1, node2, early_start, late_start, tiempos_proyecto, duracion_total_proyecto\n",
        "        )\n",
        "        ahorros[respuesta] = (ahorro, nueva_duracion_total)\n",
        "\n",
        "    # Mostrar ahorros calculados para cada caso\n",
        "    print(\"   Ahorros calculados:\", ahorros)  # Debug: Muestra ahorros\n",
        "\n",
        "    # Encontrar la opción con mayor ahorro\n",
        "    mejor_opcion = max(ahorros, key=lambda x: ahorros[x][0])\n",
        "    ahorro_maximo, nueva_duracion = ahorros[mejor_opcion]\n",
        "\n",
        "    return mejor_opcion, nueva_duracion, ahorro_maximo\n",
        "\n",
        "def modificar_grafo_y_recalcular(G, mejor_opcion, tiempos_proyecto):\n",
        "    \"\"\"Modifica el grafo según la mejor opción de precedencia y recalcula los tiempos\"\"\"\n",
        "    # Modificar el grafo\n",
        "    node1, node2 = mejor_opcion.split(' -> ')\n",
        "    if mejor_opcion == f'{node1} -> {node2}':\n",
        "        G.add_edge(node1, node2, weight=tiempos_proyecto[node2])  # Añadir la relación\n",
        "    else:\n",
        "        G.add_edge(node2, node1, weight=tiempos_proyecto[node1])  # Añadir la relación inversa\n",
        "\n",
        "    # Recalcular los tiempos tras la modificación\n",
        "    early_start, early_finish, late_start, late_finish, duracion_total_proyecto = recalcular_tiempos(G, tiempos_proyecto)\n",
        "\n",
        "    return G, early_start, late_start, duracion_total_proyecto\n",
        "\n",
        "# Configuración inicial del proyecto\n",
        "precedencias = {\n",
        "    'A': [], 'B': [], 'C': ['A'], 'D': ['A', 'B'], 'E': ['C'], 'F': ['D'], 'G': ['D'], 'H': ['E']\n",
        "}\n",
        "\n",
        "# Ingresar el valor de X para la actividad D\n",
        "X = input(\"Ingrese el valor de X para la actividad D: \")\n",
        "x = int(X)  # Convertir el valor ingresado a entero\n",
        "tiempos_proyecto = {'A': 5, 'B': 7, 'C': 3, 'D': x, 'E': 2, 'F': 3, 'G': 5, 'H': 6}\n",
        "\n",
        "# Crear el grafo del proyecto\n",
        "G_proyecto = crear_grafo(precedencias, tiempos_proyecto)[0]\n",
        "Camino_critico = crear_grafo(precedencias, tiempos_proyecto)[1]\n",
        "if 'α' in Camino_critico:\n",
        "    Camino_critico.remove('α')\n",
        "\n",
        "# Recalcular los tiempos originales\n",
        "early_start_ori, early_finish_ori, late_start_ori, late_finish_ori, duracion_total_proyecto_ori = recalcular_tiempos(G_proyecto, tiempos_proyecto)\n",
        "print(f\"1. Duración total del proyecto: {duracion_total_proyecto_ori} días, Camino crítico: {' -> '.join(Camino_critico)}\")\n",
        "\n",
        "\n",
        "# Evaluar incompatibilidades y realizar modificaciones\n",
        "contador = 1  # Inicializar contador de opciones\n",
        "Casos = [('C', 'D'), ('D', 'E'), ('F', 'G')]  # Definir los casos a evaluar\n",
        "\n",
        "print(f'3. Evaluación incompatibilidad ...')\n",
        "while Casos:\n",
        "    # Evaluar el mejor caso de incompatibilidad\n",
        "    mejor_opcion, nueva_duracion, ahorro_maximo = comp_incompatibilidad(Casos, G_proyecto, early_start_ori, late_start_ori, tiempos_proyecto, duracion_total_proyecto_ori)\n",
        "\n",
        "    # Imprimir el resultado de la incompatibilidad con mayor ahorro\n",
        "    letra_opcion = chr(96 + contador)  # a = 97 en ASCII\n",
        "    print(f\"   {letra_opcion}) \\033[1mMejor opción de precedencia: {mejor_opcion}\\033[0m\")\n",
        "    print(f\"      \\033[1mDuración nueva del proyecto: {nueva_duracion} días\\033[0m\")\n",
        "    print(f\"      Ahorro en la duración: {ahorro_maximo} días\")\n",
        "\n",
        "    # Modificar el grafo con la mejor opción y recalcular tiempos\n",
        "    G_proyecto, early_start_ori, late_start_ori, duracion_total_proyecto_ori = modificar_grafo_y_recalcular(G_proyecto, mejor_opcion, tiempos_proyecto)\n",
        "\n",
        "    # Eliminar el caso procesado de Casos\n",
        "    node1, node2 = mejor_opcion.split(' -> ')\n",
        "    Casos = [caso for caso in Casos if (node1, node2) != caso and (node2, node1) != caso]\n",
        "\n",
        "    contador += 1\n",
        "\n"
      ],
      "metadata": {
        "id": "-9sRp0q0RKMd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fab3ee5f-6214-4227-df50-56c4d34a9272"
      },
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Ingrese el valor de X para la actividad D: 4\n",
            "1. Duración total del proyecto: 16 días, Camino crítico: A -> C -> E -> H\n",
            "3. Evaluación incompatibilidad ...\n",
            "   Ahorros calculados: {'C -> D': (5, 17), 'D -> E': (0, 19), 'F -> G': (0, 19)}\n",
            "   a) \u001b[1mMejor opción de precedencia: C -> D\u001b[0m\n",
            "      \u001b[1mDuración nueva del proyecto: 17 días\u001b[0m\n",
            "      Ahorro en la duración: 5 días\n",
            "   Ahorros calculados: {'E -> D': (1, 19), 'F -> G': (0, 20)}\n",
            "   b) \u001b[1mMejor opción de precedencia: E -> D\u001b[0m\n",
            "      \u001b[1mDuración nueva del proyecto: 19 días\u001b[0m\n",
            "      Ahorro en la duración: 1 días\n",
            "   Ahorros calculados: {'F -> G': (0, 22)}\n",
            "   c) \u001b[1mMejor opción de precedencia: F -> G\u001b[0m\n",
            "      \u001b[1mDuración nueva del proyecto: 22 días\u001b[0m\n",
            "      Ahorro en la duración: 0 días\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "4. Determine el instante mínimo de finalización según las condiciones de precedencias,\n",
        "sin tener presentes las incompatibilidades, y si sólo se dispone de dos equipos de\n",
        "trabajo. Utilizar ambos esquemas (serie y paralelo), así como una ordenación de\n",
        "actividades por número total de sucesoras (en caso de empate, utilizar el orden\n",
        "alfabético)."
      ],
      "metadata": {
        "id": "n39QNDMltt_a"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import networkx as nx\n",
        "\n",
        "# Ejemplo de grafo con precedencias\n",
        "precedencias_es = {'A': [], 'B': [], 'C': ['A'], 'D': ['A', 'B'], 'E': ['C'], 'F': ['D'], 'G': ['D'], 'H': ['E']}\n",
        "# Ingresar el valor de X para la actividad D\n",
        "x_2 = int(input(\"Ingrese el valor de X para la actividad D: \"))  # Convertir el valor ingresado a entero\n",
        "tiempos_proyecto_es = {'A': 5, 'B': 7, 'C': 3, 'D': x_2, 'E': 2, 'F': 3, 'G': 5, 'H': 6}\n",
        "\n",
        "# Crear el grafo del proyecto\n",
        "G_proyecto_esquema = nx.DiGraph()\n",
        "# Agregar nodos y aristas al grafo según las precedencias\n",
        "for tarea, predecesores in precedencias_es.items():\n",
        "    G_proyecto_esquema.add_edges_from((predecesor, tarea) for predecesor in predecesores)\n",
        "\n",
        "def contar_sucesores_hacia_atras(G, nodo, visitados=None):\n",
        "    \"\"\"Contar todos los sucesores de un nodo dado desde el final hacia atrás.\"\"\"\n",
        "    visitados = visitados or set()\n",
        "    if nodo in visitados:\n",
        "        return 0\n",
        "    visitados.add(nodo)\n",
        "    return sum(1 + contar_sucesores_hacia_atras(G, sucesor, visitados) for sucesor in G.successors(nodo))\n",
        "\n",
        "def debug_sucesores_hacia_atras(G):\n",
        "    \"\"\"Imprimir el conteo total de sucesores desde el final de cada nodo en el grafo.\"\"\"\n",
        "    for nodo in G.nodes:\n",
        "        if nodo not in ['α', 'ω']:  # Ignorar nodos ficticios\n",
        "            print(f\"Nodo {nodo} tiene un total de {contar_sucesores_hacia_atras(G, nodo)} sucesores hasta el final.\")\n",
        "\n",
        "# Ejecutar la función de debug\n",
        "debug_sucesores_hacia_atras(G_proyecto_esquema)\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Y0rEEyARttsc",
        "outputId": "01a1e9cc-1557-4c0e-bc4c-be207e3b0ffb"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Ingrese el valor de X para la actividad D: 2\n",
            "Nodo A tiene un total de 6 sucesores hasta el final.\n",
            "Nodo C tiene un total de 2 sucesores hasta el final.\n",
            "Nodo D tiene un total de 2 sucesores hasta el final.\n",
            "Nodo B tiene un total de 3 sucesores hasta el final.\n",
            "Nodo E tiene un total de 1 sucesores hasta el final.\n",
            "Nodo F tiene un total de 0 sucesores hasta el final.\n",
            "Nodo G tiene un total de 0 sucesores hasta el final.\n",
            "Nodo H tiene un total de 0 sucesores hasta el final.\n"
          ]
        }
      ]
    }
  ]
}