论文部分内容阅读
电力系统中存在大量优化问题,较高比例是混合整数规划问题,即变量中存在整数变量。整数变量的存在,很大程度上增加了计算难度。高效、准确的求解这些问题可以为实际生产带来明显的效益。对于非线性问题,可以通过线性化的方法转换为线性问题求解。提高线性混合整数规划算法的计算效率和精度,对于求解电力系统中的各种实际问题都有着重要的研究意义。线性混合整数规划问题在计算求解时,有着大量计算信息被浪费、计算出现零步长及迭代循环,计算效率存在提升空间等问题。为此,本文对线性混合整数规划问题的算法进行了优化改进,本文具体工作如下:(1)提出了线性整数规划新息分支定界算法,用于实现父节点问题与子节点问题之间的信息继承,以提高子问题的计算效率。该方法在求解子节点问题时,选取父节点问题单纯形表中分支变量第一次入基的前一步时的单纯形表,在此基础上更改单纯形表构成子节点问题求解的初始单纯形表,从该表开始求解子节点问题。对若干大规模案例进行测试与对比,结果表明,与分支定界法相比线性整数规划新息分支定界算法可以有效减少子节点问题求解计算所需的迭代步数。(2)针对退化的线性规划问题,提出了线性规划防稀疏改选主元算法。该算法当b向量稀疏度大于一定门槛值时,如果主元所在的行所对应的b向量中元素为零,那么插入一步改选主元,选择能让目标函数下降的主元,并使b向量变得稠密,保证后续大部分的计算步骤都能使目标函数的值得到改善。同时还确定了该算法中需要插入的改选主元次数,一般情况下只需1次。对若干不同稀疏度的线性规划问题进行测试与对比,结果表明该方法能有效地提高高稀疏情形下线性规划问题的计算效率,b向量的稀疏度越高,改进效果越明显。(3)以新息分支定界算法与防稀疏改选主元算法为基础,提出了新息分支定界与防稀疏改选主元相结合的线性混合整数规划优化算法。该算法在线性混合整数规划整体求解时采用新息分支定界算法,同时将防稀疏改选主元算法运用于每一个子问题的松弛线性规划问题的计算中。并确定了分支策略为每次分支时选择父问题的所有元素中最晚第一次进基的非整数元素为分支变量,搜索策略为每次比较不满足整数约束的松弛问题的最优值的大小,按最优值从优到劣的顺序依次进行分支搜索。对若干大规模案例采用该方法进行计算与对比,结果表明,该算法可以更进一步的改善线性混合整数规划问题的计算效率。(4)提出了新息分支定界与防稀疏改选主元相结合的线性混合整数规划优化算法在电力系统实际问题中的应用。分别以机组组合问题以及售电公司购电策略优化问题为例,采用分支定界法与本文的优化算法对两者进行求解,结果验证了本文所提出的优化算法的可以有效的求解电力系统中的相关问题,提高了电力系统相关问题的优化效率,说明了该算法在电力系统实际问题应用中的适用性和有效性。本文提出了线性混合整数规划问题的优化改进算法,主要提出了线性整数规划新息分支定界算法与线性规划防稀疏改选主元算法两个方面的改进。不同情形下的实例计算表明,本文提出的方法可以有效改善线性混合整数规划问题的计算效率,能够有效的求解电力系统相关的优化问题。