双层线性规划全局优化算法研究

"双层线性规划的全局优化方法基于割平面约束的单纯形法" 双层线性规划是一种特殊的优化问题，它包含两个相互关联的线性规划问题，上层和下层。上层问题的目标函数依赖于下层问题的解，而下层问题的解又受到上层决策的影响。在2009年的研究中，作者危学茂、赵茂先和张志江提出了一个利用割平面约束和单纯形法寻找双层线性规划全局最优解的算法。 该算法基于双层线性规划的一个关键性质，即全局最优解可能出现在其约束域的极点处。结合线性规划的对偶理论，他们引入了与上层目标函数相关的割平面约束。割平面约束是一种用来削减不必要区域的工具，它可以将原始问题的可行域逐步分割，从而逼近全局最优解。通过不断迭代和更新这些割平面，算法能够逐步剔除那些无法达到全局最优解的区域。 具体实现过程中，算法使用了单纯形法，这是一种经典的线性规划求解策略。单纯形法通过在当前解的基础上移动到相邻的顶点来逐步优化解的质量。在双层线性规划的上下层问题中，这种移动不仅考虑了上层的目标函数，还考虑了下层问题的优化结果。每一步迭代，算法都会检查新的割平面是否能够进一步减小对偶间隙，对偶间隙是衡量双层问题近似解与全局最优解差距的一个重要指标。 通过算例分析，该算法展示了其求解过程，并证实了其在找到双层线性规划全局最优解方面的有效性。文章指出，对于给定的双层线性规划问题，该算法能够逐步收敛至全局最优解，而且效率较高，因为它能有效地排除非最优解所在的区域。 关键词：双层线性规划的这一全局优化算法与对偶间隙、ε-全局最优解紧密相关，表明它特别关注找到满足一定精度的全局最优解。这种方法在解决实际问题时具有重要意义，尤其是在那些需要确保找到最佳决策路径的领域，如资源配置、投资决策或供应链管理等。 中图分类号和文献标志码显示这是一项科学研究，发表在《山东科技大学自然科学》期刊上，表明它代表了学术界对双层线性规划全局优化方法的最新进展。文章编号为1672-3767（2009）01-0099-04，提供了该研究的具体引用信息。