广义Benders分解法求解机组组合问题

该文介绍了一种用于求解机组组合问题的广义Benders分解方法（Generalized Benders Decomposition Method, GBDM），这是一种解决混合整数二次规划问题（Mixed Integer Quadratic Programming, MIQP）的算法。文章指出，GBDM能够将混合整数非线性规划问题分解为混合整数线性规划主问题（MILP Master Problem）和非线性规划子问题（NLP Subproblem）。通过交替求解这两个问题，可以找到原问题的最优解。在Matlab 7.5环境中使用CPLEX软件包进行求解，并在不同规模的机组组合问题上进行了仿真，展示了方法的快速收敛性和有效性。 算法步骤如下： 1. 初始化：设置Uz为无穷大，ky为初始离散变量值。 2. 解决NLP子问题(13)，得到最优解kx和对应的KKT乘子kλ。如果U(kz f)Τ > c(yx)，更新Uz和ky。 3. 解决MILP主问题(14)，得到最优解1k+y和最优值Lz。如果Lz >= Uz，停止计算并输出最优解(x*, y*)；否则，更新k值并返回步骤1。 在算法中，如果NLP子问题无解，可以在MILP主问题中添加整数割平面来排除不可行解。具体操作是，基于定义的Sj集合，加入整数割平面约束。 通过10到100台机组、24时段的系统数据进行仿真，GBDM在所有案例中仅需两次迭代即达到收敛，显示出快速的收敛速度。计算时间随着机组数量增加而增长，但仍然保持在可接受范围内。 表1给出了不同规模系统下的计算结果，显示了GBDM的高效性。表2则对比了GBDM与其他7种方法，证明在多数情况下，GBDM的计算结果优于其他方法，尤其适用于大规模的机组组合问题求解。 该研究为电力系统的机组组合问题提供了一个有效的解决方案，结合了Benders分解和广义形式，提高了问题的求解效率，适用于处理复杂的电力系统优化问题。