运筹学练习Python精解——网络计划技术

练习1

某新产品研制项目的各项工序、所需时间及相互关系如下表所示，试画出该项目的网络图，试求出关键路线。

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] = es
    
    for 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] = lf
    
    return 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 += 1

plt.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.