求关键路径，AOE网中所有关键路径

求出如图所示的AOE网中所有关键路径，请写出事件的最早发生时间和最晚发生时间

img

要求 AOE 网中所有的关键路径，需要先进行关键路径分析，找到所有的关键路径。

构建 AOE 网，标记出各个事件节点的最早开始时间和最晚开始时间，同时标记出各个活动的最早开始时间和最晚开始时间。

计算各个活动的总时差（即最晚开始时间减去最早开始时间）。

如果一个活动的总时差为 0，则该活动所在的路径就是一个关键路径。

按照上述方式找出所有的关键路径。

下面是 Python 示例代码：

import numpy as np

# 构建邻接矩阵
adjMatrix = np.array([
    [0, 3, 5, 0, 0, 0],
    [0, 0, 0, 2, 6, 0],
    [0, 0, 0, 7, 4, 2],
    [0, 0, 0, 0, 0, 5],
    [0, 0, 0, 0, 0, 4],
    [0, 0, 0, 0, 0, 0]
])

# 计算每个事件节点的最早开始时间
earliest = np.zeros(len(adjMatrix), dtype=int)
for i in range(len(adjMatrix)):
    earliest[i] = adjMatrix[:, i][adjMatrix[:, i] != 0].max() if adjMatrix[:, i].any() else 0

# 计算每个事件节点的最晚开始时间
latest = np.zeros(len(adjMatrix), dtype=int)
for i in reversed(range(len(adjMatrix))):
    latest[i] = min(latest[ j ] - adjMatrix[i, j] if adjMatrix[i, j] != 0 else float('inf') for j in range(len(adjMatrix)))

# 计算所有活动的总时差
slack = latest - earliest

# 找到所有关键路径
criticalPaths = []
for i in range(len(adjMatrix)):
    for j in range(len(adjMatrix)):
        if adjMatrix[i, j] != 0 and slack[i] == 0 and slack[j] == 0 and latest[i] - earliest[i] == adjMatrix[i, j]:
            # 记录一条新的关键路径
            criticalPath = [i, j]
            node = j
            while node != i:
                # 找到关键路径上的前一个节点
                nodeList = []
                for k in range(len(adjMatrix)):
                    if adjMatrix[k, node] != 0:
                        nodeList.append((k, earliest[k]))
                node, _ = min(nodeList, key=lambda x: x[1])
                criticalPath.insert(0, node)
            criticalPaths.append(criticalPath)

# 输出所有关键路径
print("所有关键路径：")
for p in criticalPaths:
    print(" -> ".join(str(x) for x in p))

上述代码中的邻接矩阵是一个 6x6 的矩阵，每个数字表示一个活动的持续时间，数字为 0 表示对应的活动不存在。在计算时，首先计算出每个事件节点的最早开始时间和最晚开始时间。然后计算各个活动的总时差，如果一个活动的总时差为 0，则该活动所在的路径就是一个关键路径。最后按照上述方式找出所有的关键路径，并输出到控制台中。

不知道你这个问题是否已经解决, 如果还没有解决的话:

  • 以下回答来自chatgpt:

    在需要对项目进行时间管理时，就需要求解AOE(活动图)网中的关键路径。关键路径反映的是从开始结点到结束结点的最长路径，关键路径上的活动相当于是至关重要的，必须按时完成，否则整个工程的完成时间就会被影响。可以使用AOE网中的关键路径来确定项目的整体时间、安排资源和分配工作等。

    具体地说，需要根据AOE网中各个结点的最早开始时间(ve)和最迟开始时间(vl)来计算出每个任务的最早和最迟开始时间，并确定那些任务是关键路径上的任务。最早开始时间(ve)表示在没有耽误前提下，某个任务能够开始执行的最早时间；最迟开始时间(vl)表示任务最迟必须开始时间，否则将导致总工作时间延误。在AOE网中，一条关键路径上所有的活动都必须严格按照最早完成时间进行，且这个时间不能被缩短。因此，关键路径可以反映出对整个项目来说哪些任务是非常重要的。

    输出方面，可以输出AOE网中的关键路径邻接矩阵，其中被标记为关键路径上的活动权值为该活动的权值，其余为-1。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^