有向图配方边最优权重求解：最大化目标产物产量及能耗约束处理

问题求解思路 #

这个问题属于典型的*线性规划（Linear Programming, LP）*问题，所有约束和目标函数都是线性结构，直接套用线性规划框架即可求解，具体建模和求解步骤如下：

变量定义 #

假设你总共有m个配方，每个配方对应一个非负连续变量 x_i，代表第i个配方的执行次数（即边权重），基础约束为 x_i ≥ 0。

无能耗约束的基础场景建模 #

物品存量约束

假设你总共有n种物品，初始存量为 s_j（j为物品编号，s_j ≥ 0）：

• 先为每个物品j统计所有配方的净消耗系数：第i个配方每执行1次，如果消耗a单位的物品j，净系数记为 +a；如果产出b单位的物品j，净系数记为 -b
• 每个物品j的总消耗量不能超过初始存量，对应约束为：Σ(i=1到m) (c_ij * x_i) ≤ s_j，其中c_ij为第i个配方对物品j的净消耗系数

目标函数

如果你的目标是最大化指定物品k的产出量，先统计所有配方对物品k的净产出系数 p_ik：第i个配方每执行1次产出d单位物品k就记 +d，消耗e单位就记 -e，目标函数即为最大化 Σ(i=1到m) (p_ik * x_i)

加入能耗约束的扩展场景 #

你只需要新增1条线性约束即可适配能耗要求：

• 为每个配方i定义净能耗系数 e_i：配方i执行1次净产出能量则e_i为正，净消耗能量则e_i为负
• 新增约束：Σ(i=1到m) (e_i * x_i) ≥ 0，刚好对应「总能量产出减去总能量消耗≥0」的要求

求解工具选择 #

不需要手动实现算法，直接用现成线性规划求解器输入上述模型即可得到最优权重：

• 小规模问题可以用Excel自带的规划求解功能，或者Python的scipy.optimize.linprog库
• 中大规模问题可以用Python的PuLP、CVXPY库，或者Gurobi、CPLEX的免费个人版

内容的提问来源于stack exchange，提问作者Rebecca Stevens