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

haohai9309 / 2024-06-10 / 原文

练习1

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

工序	产品及工艺设计	外购配套件	下料、锻件	工装制造1	木模、铸件	机械加工1	工装制造2	机械加工2	机械加工3	装配调试
工序代号	A	B	C	D	E	F	G	H	I	K
所需时间	60	45	10	20	40	18	30	15	25	35
紧后工序	B, C, D, E	K	F	G, H	H	K	I	K	K	-

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

# Define the edges with the new data structure
edges = {
    'A': {'nodes': ('1', '2'), 'weight': 4},
    'B': {'nodes': ('2', '3'), 'weight': 5},
    'C': {'nodes': ('2', '4'), 'weight': 3},
    'D': {'nodes': ('2', '6'), 'weight': 2},
    'E': {'nodes': ('3', '4'), 'weight': 2},
    'F': {'nodes': ('3', '5'), 'weight': 1},
    'G': {'nodes': ('4', '6'), 'weight': 4},
    'H': {'nodes': ('5', '8'), 'weight': 3},
    'I': {'nodes': ('6', '7'), 'weight': 2},
    'J': {'nodes': ('7', '8'), 'weight': 4}
}

# 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: 21
Critical path nodes: ['1', '2', '3', '4', '6', '7', '8']
Critical path edges: A -> B -> E -> G -> I -> J.

练习3

某项目的作业明细表如下，试计算其工序的作业时间参数，最后作甘特图表示关键路线。

工作	A	B	C	D	E	F	G	H	I	J
持续时间	2	3	5	2	3	3	2	3	6	2
紧前工作	-	A	A	B	B	D	F	E,F	C,E,F	G,H

3.1 网络计划图

3.2 Python程序

作业明细表数据输入结构

import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.patches import Patch

# 第一部分：数据结构
# 定义任务字典('partment': 'IT'仅仅为了后面作图采用不同的颜色表示，无实际意义)
dictA = {'工作名称': 'A', '紧前工作': '-', '持续时间': 2, 'partment': 'IT'}
dictB = {'工作名称': 'B', '紧前工作': 'A', '持续时间': 3, 'partment': 'MKT'}
dictC = {'工作名称': 'C', '紧前工作': 'A', '持续时间': 5, 'partment': 'ENG'}
dictD = {'工作名称': 'D', '紧前工作': 'B', '持续时间': 2, 'partment': 'PROD'}
dictE = {'工作名称': 'E', '紧前工作': 'B', '持续时间': 3, 'partment': 'FIN'}
dictF = {'工作名称': 'F', '紧前工作': 'D', '持续时间': 3, 'partment': 'IT'}
dictG = {'工作名称': 'G', '紧前工作': 'F', '持续时间': 2, 'partment': 'MKT'}
dictH = {'工作名称': 'H', '紧前工作': 'E,F', '持续时间': 3, 'partment': 'PROD'}
dictI = {'工作名称': 'I', '紧前工作': 'C,E,F', '持续时间': 6, 'partment': 'FIN'}
dictJ = {'工作名称': 'J', '紧前工作': 'G,H', '持续时间': 2, 'partment': 'MKT'}

lis = [dictA, dictB, dictC, dictD, dictE, dictF, dictG, dictH, dictI,dictJ]

# 创建 DataFrame
df = pd.DataFrame(lis)

工序时间参数的计算

# 初始化 CPM 分析的列
df['Earliest_Start'] = 0
df['Earliest_Finish'] = 0
df['Latest_Start'] = 0
df['Latest_Finish'] = 0
df['Total_Float'] = 0
df['Free_Float'] = 0

# 第二部分：网络参数计算
# 正向传递：计算最早开始和最早结束时间
for i, row in df.iterrows():
    if row['紧前工作'] == '-':
        df.at[i, 'Earliest_Finish'] = row['持续时间']
    else:
        predecessors = row['紧前工作'].split(',')
        max_ef = 0
        for pred in predecessors:
            pred_ef = df.loc[df['工作名称'] == pred, 'Earliest_Finish'].values[0]
            if pred_ef > max_ef:
                max_ef = pred_ef
        df.at[i, 'Earliest_Start'] = max_ef
        df.at[i, 'Earliest_Finish'] = max_ef + row['持续时间']

# 反向传递：计算最迟开始和最迟结束时间
project_duration = df['Earliest_Finish'].max()
for i in range(len(df) - 1, -1, -1):
    row = df.iloc[i]
    if i == len(df) - 1:
        df.at[i, 'Latest_Finish'] = project_duration
        df.at[i, 'Latest_Start'] = project_duration - row['持续时间']
    else:
        successors = df[df['紧前工作'].str.contains(row['工作名称'])]
        min_ls = project_duration
        for j, succ_row in successors.iterrows():
            succ_ls = df.at[j, 'Latest_Start']
            if succ_ls < min_ls:
                min_ls = succ_ls
        df.at[i, 'Latest_Finish'] = min_ls
        df.at[i, 'Latest_Start'] = min_ls - row['持续时间']

# 计算总浮动和自由浮动
for i, row in df.iterrows():
    df.at[i, 'Total_Float'] = row['Latest_Start'] - row['Earliest_Start']
    successors = df[df['紧前工作'].str.contains(row['工作名称'])]
    if len(successors) == 0:
        df.at[i, 'Free_Float'] = df.at[i, 'Total_Float']
    else:
        min_es = min(successors['Earliest_Start']) if not successors.empty else row['Earliest_Finish']
        df.at[i, 'Free_Float'] = min_es - row['Earliest_Finish']

# 将DataFrame转置并完整显示
pd.set_option('display.max_columns', None)
print(df.T)

工作名称         A    B    C     D    E   F    G     H      I    J
紧前工作         -    A    A     B    B   D    F   E,F  C,E,F  G,H
持续时间         2    3    5     2    3   3    2     3      6    2
partment         IT  MKT  ENG  PROD  FIN  IT  MKT  PROD    FIN  MKT
Earliest_Start    0    2    2     5    5   7   10    10     10   13
Earliest_Finish   2    5    7     7    8  10   12    13     16   15
Latest_Start      0    2    5     5    7   7   12    11     10   14
Latest_Finish     2    5   10     7   10  10   14    14     16   16
Total_Float       0    0    3     0    2   0    2     1      0    1
Free_Float        0    0    3     0    2   0    1     0      0    1

可视化甘特图

# 反转 DataFrame 的顺序用于绘图
df = df.iloc[::-1]

# 绘制甘特图
fig, ax = plt.subplots(1, figsize=(16, 6))

# 绘制任务条
ax.barh(df['工作名称'], df['current_num'], left=df['Earliest_Start'], color=df['color'])
ax.barh(df['工作名称'], df['days_start_to_end'], left=df['Earliest_Start'], color=df['color'], alpha=0.5)

# 添加百分比文本
for idx, row in df.iterrows():
    ax.text(row['Latest_Finish'] + 0.1, len(df) - idx - 1, f"{int(row['Flexible'] * 100)}%", va='center', alpha=0.8)

# 部门图例
c_dict = {'MKT': '#E64646', 'FIN': '#E69646', 'ENG': '#34D05C', 'PROD': '#34D0C3', 'IT': '#3475D0'}
legend_elements = [Patch(facecolor=c_dict[i], label=i) for i in c_dict]
plt.legend(handles=legend_elements)

plt.xlabel('Days')
plt.ylabel('Tasks')
plt.title('Gantt Chart')
plt.show()

关键工序的百分比为0%

练习4

某公司的产前分析网络工程图的工序明细表和网络图如下图所示，求出网络中每个节点的最早开始时间、最迟开始时间、关键路线及所需最短时间。

工作	A	B	C	D	E	F	G	H	I	J	K
持续时间	5	10	11	4	4	15	21	35	25	15	20
紧前工作	-	-	-	B	A	C,D	B,E	B,E	B,E	F,G,I	F,G

4.1 网络计划图

4.2 Python程序

import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.patches import Patch

# 第一部分：数据结构
# 定义任务字典('partment': 'IT'仅仅为了后面作图采用不同的颜色表示，无实际意义)
dictA = {'工作名称': 'A', '紧前工作': '-', '持续时间': 5, 'partment': 'IT'}
dictB = {'工作名称': 'B', '紧前工作': '-', '持续时间': 10, 'partment': 'MKT'}
dictC = {'工作名称': 'C', '紧前工作': '-', '持续时间': 11, 'partment': 'ENG'}
dictD = {'工作名称': 'D', '紧前工作': 'B', '持续时间': 4, 'partment': 'PROD'}
dictE = {'工作名称': 'E', '紧前工作': 'A', '持续时间': 4, 'partment': 'FIN'}
dictF = {'工作名称': 'F', '紧前工作': 'C,D', '持续时间': 15, 'partment': 'IT'}
dictG = {'工作名称': 'G', '紧前工作': 'B,E', '持续时间': 21, 'partment': 'MKT'}
dictH = {'工作名称': 'H', '紧前工作': 'B,E', '持续时间': 35, 'partment': 'PROD'}
dictI = {'工作名称': 'I', '紧前工作': 'B,E', '持续时间': 25, 'partment': 'FIN'}
dictJ = {'工作名称': 'J', '紧前工作': 'F,G,I', '持续时间': 15, 'partment': 'MKT'}
dictK = {'工作名称': 'K', '紧前工作': 'F,G', '持续时间': 20, 'partment': 'FIN'}

lis = [dictA, dictB, dictC, dictD, dictE, dictF, dictG, dictH, dictI,dictJ,dictK]

# 创建 DataFrame
df = pd.DataFrame(lis)

#后面语句与练习3完全相同