Python设备资源分配优化算法咨询及linprog约束问题排查

问题背景 #

有固定总量的两类资源，需执行50+组实验，每组实验有固定基准耗时及对应两种资源的需求量。目标是优化资源分配方案，确保实验总耗时不超过设定上限。当前使用scipy.optimize.linprog时因约束模型错误导致求解失败，需修正方案及相关技术参考。

现有代码问题分析 #

1. 目标函数定义错误：linprog仅支持线性目标函数，但当前代码将实验基准耗时直接作为目标系数，未对应实际总耗时的计算逻辑（总耗时与资源分配量呈非线性反比关系）。
2. 约束逻辑缺失：未关联同组实验的两类资源分配比例（比如实验i的Brazos分配量与Z2 Rack分配量需匹配其需求比例，否则会造成资源浪费或无法完成实验），且强制资源全量分配（eq约束）而非上限约束（ineq），易导致无解。
3. 非线性问题误用线性规划：实验耗时随资源分配量的变化是非线性关系（投入资源越多，耗时越短），linprog无法处理此类非线性优化场景。

修正方案 #

方案1：改用非线性优化工具（scipy.optimize.minimize） #

假设每组实验需按需求比例投入资源（即投入倍数k_i同时作用于两类资源），总耗时为各实验基准耗时除以投入倍数之和，约束为两类资源总投入不超过总量。示例代码如下：

import pandas as pd
from scipy.optimize import minimize

df = pd.read_excel('Book3.xlsx')

# 总可用资源
total_brazos = 11
total_z2_rack = 3

# 提取实验参数
rb = df["Brazos Req"].values
rz = df["Z2 Rack Req"].values
t = df["Working Days"].values
n_experiments = len(df)

# 目标函数：最小化总耗时（非线性）
def objective(k):
    return sum(t / k)

# 约束条件：资源总投入不超过总量，且每个k_i >=1（至少投入基准资源量完成实验）
constraints = [
    {'type': 'ineq', 'fun': lambda k: total_brazos - sum(k * rb)},
    {'type': 'ineq', 'fun': lambda k: total_z2_rack - sum(k * rz)}
]
bounds = [(1, None) for _ in range(n_experiments)]  # k_i >=1

# 初始值：每个实验投入基准资源量
initial_guess = [1.0] * n_experiments

# 求解
result = minimize(objective, initial_guess, bounds=bounds, constraints=constraints, method='SLSQP')

if result.success:
    df["Resource Multiplier"] = result.x
    df["Actual Days"] = df["Working Days"] / df["Resource Multiplier"]
    df["Brazos Allocated"] = df["Resource Multiplier"] * df["Brazos Req"]
    df["Z2 Rack Allocated"] = df["Resource Multiplier"] * df["Z2 Rack Req"]
    
    print("优化后分配方案：")
    print(df)
    print(f"总耗时：{sum(df['Actual Days']):.2f}")
else:
    print(f"求解失败，原因：{result.message}")

方案2：使用整数规划工具（PuLP） #

若需考虑实验执行的调度顺序（资源在时间上的复用），需将问题建模为整数规划，示例框架如下：

import pandas as pd
from pulp import LpProblem, LpMinimize, LpVariable, lpSum

df = pd.read_excel('Book3.xlsx')
total_brazos = 11
total_z2_rack = 3
max_total_days = 30  # 设定总耗时上限

# 创建问题实例
prob = LpProblem("ExperimentScheduling", LpMinimize)

# 定义变量：x_i_j表示实验i在时间段j是否占用资源（0/1），t_i表示实验i的完成时间
n_experiments = len(df)
max_time = max_total_days
x = LpVariable.dicts("Assign", [(i, j) for i in range(n_experiments) for j in range(max_time)], cat='Binary')
t = LpVariable.dicts("FinishTime", range(n_experiments), lowBound=0)

# 目标：最小化总耗时
prob += lpSum(t)

# 约束1：每个实验需持续执行其基准耗时的时间
for i in range(n_experiments):
    prob += lpSum([x[i][j] for j in range(max_time)]) == df["Working Days"].iloc[i]
    prob += t[i] >= df["Working Days"].iloc[i]

# 约束2：任意时间段内，资源占用总量不超过上限
for j in range(max_time):
    prob += lpSum([x[i][j] * df["Brazos Req"].iloc[i] for i in range(n_experiments)]) <= total_brazos
    prob += lpSum([x[i][j] * df["Z2 Rack Req"].iloc[i] for i in range(n_experiments)]) <= total_z2_rack

# 求解
prob.solve()

# 输出结果
if prob.status == 1:
    print("调度方案：")
    for i in range(n_experiments):
        print(f"实验{df['Experiment'].iloc[i]}完成时间：{t[i].value()}")
else:
    print("无法在设定总耗时上限内完成所有实验")

适用工具与技术参考 #

• 线性/整数规划：PuLP（开源轻量）、Gurobi（商业高性能，支持学术授权）
• 非线性优化：scipy.optimize.minimize（支持多种非线性算法）
• 启发式调度：DEAP（遗传算法框架）、SimPy（离散事件仿真）
• 参考资料：
  • 《运筹学导论》（线性规划与调度问题基础）
  • Scipy官方优化文档
  • PuLP官方教程

内容的提问来源于stack exchange，提问作者Jesh Kundem