线性双层规划的性质和算法研究

论文摘要

许多实际问题,如生产计划、资源分配和工程设计问题等,需要考虑系统的层次性,即在整个系统中不只一个决策者,并且它们控制不同的决策变量和目标函数。用传统的数学规划技术已不能较好地解决这类问题,因此多层规划已逐步引起人们的重视。双层规划是多层规划的基本形式,任何多层规划可以看作是双层规划的复合。因而双层规划具有重要的研究价值。论文分六章进行讨论:第1章绪论部分着重介绍了双层规划的主要特点及其数学模型,对双层规划在主要领域的应用和求解算法的研究现状进行了综述。第2章讨论了线性双层规划问题,介绍了线性双层规划数学模型、概念和一些性质,并总结了目前求解线性双层规划的主要思想和方法。论文第3、4、5章是本文研究的主要内容。第3章通过分析线性双层规划转化形式,引入平衡点概念,利用平衡点分析线性双层规划的有关性质和最优性条件。在平衡点基础上,对线性双层规划上层目标函数值进行定界,利用二分法原理,构造一个双线性规划来修正当前的界,直到求得线性双层规划的全局最优解。提出了求解线性双层规划问题的ε-全局最优解算法,并验证了算法的有限终止性和可行性。第4章由于线性双层规划的约束条件全部是线性函数,而单纯形方法是目前解决线性规划最有力的工具,如何将线性双层规划进行变形,进而利用单纯形方法去求解问题是本章考虑的对象。基于这种思路,对可行极点对应的检验数进行讨论,提出两种求解线性双层规划局部最优解的单纯形方法,第一种是先对可行极点进行单纯形迭代,然后判断新得到极点的可行性;第二种是先选取合理的进基变量,然后进行迭代,确保得到新的可行极点。第5章在局部最优解的基础上,利用割平面的思想,提出两个求解线性双层规划的全局最优解算法。最后,总结论文所做的工作,并展望了以后研究的工作方向。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 双层规划产生的背景
• 1.2 双层规划问题及其数学模型
• 1.3 双层规划应用及研究现状
• 1.4 论文的内容与结构
• 2 线性双层规划
• 2.1 模型与定义
• 2.2 基本结论
• 2.3 线性双层规划求解算法介绍
• 3 平衡点理论
• 3.1 模型与性质
• 3.2 算法与算例
• 3.3 小结
• 4 线性双层规划的局部优化算法
• 4.1 求解线性双层规划的单纯形法
• 4.2 求解线性双层规划的修正单纯形法
• 4.3 小结
• 5 线性双层规划的全局优化算法
• 5.1 引言
• 5.2 全局优化算法一
• 5.3 全局优化算法二
• 5.4 小结
• 6 总结
• 致谢
• 参考文献
• 攻读学位期间发表的论文