基于含连通图约束的背包问题的图分割方法

图分割技术(网络分割技术)在互联网研究、交通运输、电网故障诊断和电力系统解列等方面有着重要的意义。首次建立一个新的图分割问题——含连通图约束的背包问题(connected graph constrained knapsack problem,CGKP),并提出其有效近似算法。引入与图连通性相关的4个新节点集合,证明这些新节点集合的性质,并提出这些节点集合的搜索方法;结合新节点集合的性质及搜索算法,通过对含图约束的背包问题近似算法进行扩展,提出求解CGKP的近似算法,并讨论此算法的计算复杂性。算例结果证明了该算法的有效性。因电力系统主动最优解列问题在一定条件下可归结为一个CGKP,该研究成果为电力系统最优主动解列断面搜索问题的求解奠定了理论基础。

基于主从问题的电力系统最优主动解列

系统主动解列的完整模型为大规模非线性混合整数规划问题,大多采取完全分解方法,因而只能求得近似解,针对此问题提出了基于主从问题交替求解电力系统最优主动解列断面的新策略,从而求得更优解。该策略基于图背包理论(connected graph constrained knapsack problem,CGKP)将完整主动解列模型转化为主从问题;主问题为图的最优平衡分割问题,采用CGKP技术进行求解;从问题为基于直流最优潮流(optimal power flow,OPF)的调度问题,采用OPF技术进行求解;主从问题之间通过节点负荷的调节量实现耦合。通过主从问题之间的交替迭代获得更优的解列方案,同时也使得解列方案更接近于完整模型的最优解。算例分析表明,该算法相对于其他近似求解策略,所获得的解列方案可使系统总切机切负荷量更少,从而证明了该方法的有效性和可行性。

电力系统主动解列断面搜索的研究

进行了IEEE 39节点系统失稳分析;运用基于含连通图约束的背包问题(connected graph constrained knapsack problem,CGKP)的模型和算法,进行IEEE 39节点主动解列断面搜索,对CGKP不足提出了改进意见;给出了针对福建系统类似问题的分析方向。