练习1
某新产品研制项目的各项工序、所需时间及相互关系如下表所示，试画出该项目的网络图，分别用和双代号、单代号方法以及表上计算法计算事项时间参数，并求出关键路线。
| 工序 | 工序代号 | 所需时间 | 紧后工序 |
|---|---|---|---|
| 产品及工艺设计 | A | 60 | B, C, D, E |
| 外购配套件 | B | 45 | K |
| 下料、锻件 | C | 10 | F |
| 工装制造1 | D | 20 | G, H |
| 木模、铸件 | E | 40 | H |
| 机械加工1 | F | 18 | K |
| 工装制造2 | G | 30 | I |
| 机械加工2 | H | 15 | K |
| 机械加工3 | I | 25 | K |
| 装配调试 | K | 35 | - |
1.1 绘制网络计划图
1.2 Python求解
#网络计划的最长路算法
import networkx as nx# Define the edges with the new data structure
edges = {'A': {'nodes': ('1', '2'), 'weight': 60},'B': {'nodes': ('2', '7'), 'weight': 45},'C': {'nodes': ('2', '3'), 'weight': 10},'D': {'nodes': ('2', '4'), 'weight': 20},'E': {'nodes': ('2', '5'), 'weight': 40},'F': {'nodes': ('3', '7'), 'weight': 18},'G': {'nodes': ('4', '6'), 'weight': 30},'L': {'nodes': ('4', '5'), 'weight': 0},'H': {'nodes': ('5', '7'), 'weight': 15},'I': {'nodes': ('6', '7'), 'weight': 25},'K': {'nodes': ('7', '8'), 'weight': 35}
}# Initialize a directed graph
G = nx.DiGraph()# Add edges to the graph using the new data structure
for edge_name, edge_data in edges.items():start, end = edge_data['nodes']weight = edge_data['weight']G.add_edge(start, end, weight=weight, name=edge_name)# Compute the longest path using the networkx library
length, path = nx.algorithms.dag.dag_longest_path_length(G, weight='weight'), nx.algorithms.dag.dag_longest_path(G, weight='weight')# Extract the names of the edges in the critical path
critical_path_edges = []
for i in range(len(path) - 1):critical_path_edges.append(G[path[i]][path[i + 1]]['name'])# Format the critical path output
formatted_critical_path = " -> ".join(critical_path_edges) + "."print(f"Length of the critical path: {length}")
print(f"Critical path nodes: {path}")
print(f"Critical path edges: {formatted_critical_path}")
Length of the critical path: 170
Critical path nodes: ['1', '2', '4', '6', '7', '8']
Critical path edges: A -> D -> G -> I -> K.
练习2
import networkx as nx
import matplotlib.pyplot as plt
from matplotlib import rcParams# 设置字体
rcParams['font.sans-serif'] = ['Arial'] # 使用Arial字体
rcParams['axes.unicode_minus'] = False # 解决坐标轴负号显示问题# 定义任务、紧前任务和任务时间
tasks = {'A': {'pre': ['G', 'M'], 'time': 3},'B': {'pre': ['H'], 'time': 4},'C': {'pre': [], 'time': 7},'D': {'pre': ['L'], 'time': 3},'E': {'pre': ['C'], 'time': 5},'F': {'pre': ['A', 'E'], 'time': 5},'G': {'pre': ['B', 'C'], 'time': 2},'H': {'pre': [], 'time': 5},'I': {'pre': ['A', 'L'], 'time': 2},'K': {'pre': ['F', 'L'], 'time': 1},'L': {'pre': ['B', 'C'], 'time': 7},'M': {'pre': ['C'], 'time': 9}
}# 构建有向图
G = nx.DiGraph()# 添加任务节点和时间
for task, details in tasks.items():G.add_node(task, time=details['time'])# 添加任务依赖关系
for task, details in tasks.items():for pre in details['pre']:G.add_edge(pre, task)# 计算最早开始时间和最晚完成时间
def calculate_earliest_latest_times(G):earliest_start = {}latest_finish = {}for node in nx.topological_sort(G):es = max([earliest_start.get(pred, 0) + G.nodes[pred]['time'] for pred in G.predecessors(node)], default=0)earliest_start[node] = esfor node in reversed(list(nx.topological_sort(G))):lf = min([latest_finish.get(succ, float('inf')) - G.nodes[node]['time'] for succ in G.successors(node)], default=earliest_start[node] + G.nodes[node]['time'])latest_finish[node] = lfreturn earliest_start, latest_finish# 计算关键路径
def calculate_critical_path(G, earliest_start, latest_finish):critical_path = []for node in nx.topological_sort(G):if earliest_start[node] == latest_finish[node] - G.nodes[node]['time']:critical_path.append(node)return critical_path# 计算并显示结果
earliest_start, latest_finish = calculate_earliest_latest_times(G)
critical_path = calculate_critical_path(G, earliest_start, latest_finish)print("Earliest Start Times:", earliest_start)
print("Latest Finish Times:", latest_finish)
print("Critical Path:", critical_path)# 按时间线组织节点布局
pos = {}
layer = 0
for node in nx.topological_sort(G):pos[node] = (earliest_start[node], layer)layer += 1plt.figure(figsize=(12, 8))# 绘制所有节点和边
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_size=10, font_weight='bold', arrowsize=20, font_family='sans-serif')# 添加节点标签
node_labels = {node: f"{node}\n{G.nodes[node]['time']} days" for node in G.nodes}
nx.draw_networkx_labels(G, pos, labels=node_labels, font_size=10, font_family='sans-serif')# 添加边标签
edge_labels = {(pre, succ): f"ES: {earliest_start[succ]}" for pre, succ in G.edges}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color='red', font_size=8, font_family='sans-serif')# 高亮关键路径
critical_edges = [(critical_path[i], critical_path[i + 1]) for i in range(len(critical_path) - 1)]
nx.draw_networkx_edges(G, pos, edgelist=critical_edges, edge_color='r', width=2)plt.title("Network Diagram")
plt.show()
Length of the critical path: 170
Critical path nodes: ['1', '2', '4', '6', '7', '8']
Critical path edges: A -> D -> G -> I -> K.
