矩阵搜索优化：柴油机组功率组合最小油耗求解提速

术语翻译 #

• n：功率（kW）
• i：机组编号
• Av：油耗（克/千瓦时）

问题概述 #

现有6台柴油机组的功率-油耗数据矩阵（6列375行），需为每台机组选择一个功率值，满足总功率等于用户指定值的约束，同时实现总油耗最低。原Python实现计算效率过低，需优化至1小时内完成，当前已尝试基于Pulp的线性规划方案，需完善油耗函数部分。

核心实现思路 #

这是一个**混合整数线性规划（MILP）**问题，通过Pulp框架实现：

• 定义二进制变量标记每台机组是否选择某个功率选项
• 约束条件：每台机组仅选一个功率值；所有选中功率的总和等于指定值
• 目标函数：最小化总油耗，总油耗计算公式为：总油耗 = Σ（选中的功率值 × 对应油耗）（单位：克）

完整优化代码 #

import pulp
import numpy as np

# ---------------------- 数据加载（替换为你的实际数据） ----------------------
# 模拟数据：power_matrix[375行×6列] 对应6台机组的375个功率选项
# fuel_matrix[375行×6列] 对应各功率选项的油耗（克/千瓦时）
np.random.seed(42)
power_matrix = np.random.randint(10, 100, size=(375, 6))
fuel_matrix = np.random.uniform(200, 250, size=(375, 6))

target_power = 300  # 用户指定的目标总功率（kW）
max_solve_time = 3600  # 最大求解时间（1小时）

# ---------------------- 线性规划问题初始化 ----------------------
prob = pulp.LpProblem("Minimize_Total_Fuel", pulp.LpMinimize)

# 定义二进制变量：x[(i,k)] = 1 表示第i台机组选择第k个功率选项
x = pulp.LpVariable.dicts(
    "Unit_Selection",
    [(i, k) for i in range(6) for k in range(375)],
    cat=pulp.LpBinary
)

# ---------------------- 目标函数（核心油耗计算部分） ----------------------
# 总油耗 = 每台机组选中功率 × 对应油耗 的总和
prob += pulp.lpSum([
    power_matrix[k][i] * fuel_matrix[k][i] * x[(i, k)]
    for i in range(6)
    for k in range(375)
]), "Total_Fuel_Consumption"

# ---------------------- 约束条件 ----------------------
# 1. 每台机组只能选择一个功率选项
for unit_idx in range(6):
    prob += pulp.lpSum([x[(unit_idx, k)] for k in range(375)]) == 1, f"Single_Selection_Unit_{unit_idx}"

# 2. 总功率等于目标值
prob += pulp.lpSum([
    power_matrix[k][i] * x[(i, k)]
    for i in range(6)
    for k in range(375)
]) == target_power, f"Total_Power_Target_{target_power}"

# ---------------------- 求解与结果输出 ----------------------
# 使用CBC求解器，设置最大时间限制
solver = pulp.PULP_CBC_CMD(maxSeconds=max_solve_time, msg=True)
prob.solve(solver)

# 输出结果
print(f"求解状态: {pulp.LpStatus[prob.status]}")
if pulp.LpStatus[prob.status] == "Optimal":
    total_fuel = pulp.value(prob.objective)
    total_selected_power = 0
    print("\n各机组选型结果：")
    for unit_idx in range(6):
        for k in range(375):
            if pulp.value(x[(unit_idx, k)]) == 1:
                selected_power = power_matrix[k][unit_idx]
                selected_fuel_rate = fuel_matrix[k][unit_idx]
                total_selected_power += selected_power
                print(f"机组{unit_idx+1}: 功率={selected_power}kW，油耗={selected_fuel_rate:.2f}克/千瓦时")
    print(f"\n总功率: {total_selected_power}kW，总油耗: {total_fuel:.2f}克")
else:
    print("未找到可行解，请检查目标功率是否合理，或调整求解参数")

效率优化建议 #

• 求解器选择：如果CBC求解速度不足，可尝试商业求解器（如Gurobi、CPLEX），它们在大规模整数规划问题上的计算效率更高
• 数据预处理：过滤每台机组中冗余的功率选项（如重复值、或明显无法满足总功率约束的极端值），减少变量数量
• 求解器参数调优：开启并行计算（部分求解器支持）、调整分支定界启发式策略，进一步压缩求解时间

内容的提问来源于stack exchange，提问作者Sigel Alex