双层规划的若干算法研究

论文摘要

本文主要对双层规划进行了探讨,包括双层线性规划、双层非线性规划和混合整数双层线性规划。讨论了它们的基本模型、定义以及一些基本性质,并在此基础上给出了几个求解算法。论文首先介绍了双层规划产生的背景、定义、主要特点、数学模型、双层规划的应用以及求解算法的研究现状。对连续变量双层线性规划,给出了它的基本模型、定义以及一些基本理论。它的重要几何性质是:可行集由约束域的若干面组成,最优解具有顶点可达性。重点讨论了双层线性规划解的最优性条件以及基于最优性条件构造了一个全局优化算法。关于上层目标函数为非线性可微函数,下层目标函数为凸二次函数,约束条件为线性不等式的一类双层非线性规划问题,通过对下层问题K-T条件的讨论,利用罚函数原理,把下层问题的互补松弛条件作为惩罚项附加到上层目标函数中,将双层非线性规划问题转化为求解一系列非线性规划问题,借助于非线性规划中的Frank-Wolfe方法,给出了一个求解双层非线性规划K-T点的算法。对含整数型双层线性规划问题,由于变量的离散性,使问题变得复杂。本文仅对上层决策变量为整数变量,而下层决策变量为连续变量的混合整数双层线性规划问题进行了探讨,研究了它的解结构,利用可行解都在约束域边界上取得的特点,提出了一个求解全局最优解的枚举算法。对上层变量是0-1的混合整数双层线性规划,给出了界的设计和分枝准则的选择,在此基础上,提出了一个分枝定界算法。最后,对论文所做的工作进行了总结,并对以后的工作进行了展望。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 双层规划产生的背景
• 1.2 双层规划的定义与特点
• 1.3 双层规划的数学模型
• 1.4 双层规划的应用
• 1.5 求解双层规划的研究现状
• 1.6 论文的内容与结构
• 2 双层线性规划
• 2.1 模型与基本结论
• 2.2 算法与算例
• 2.3 小结
• 3 双层非线性规划
• 3.1 模型与定义
• 3.2 基本理论
• 3.3 算法与算例
• 3.4 小结
• 4 混合整数双层线性规划
• 4.1 模型与基本结论
• 4.2 枚举法
• 4.3 分枝定界法
• 4.4 小结
• 5 总结
• 致谢
• 攻读学位期间发表的论文
• 参考文献