线性双层规划中的若干全局收敛算法研究

摘要

本文介绍了双层规划问题的主要特点及其数学模型，对双层规划在主要领域的应用和目前求解算法的研究进行了综述，阐明了研究双层规划求解算法的重要性和复杂性。 通过对连续线性双层规划最优性条件的研究，给出了一些新的理论结果，在此基础上提出了几种求解连续线性双层规划的全局收敛算法，并用算例说明了算法的求解过程。 采用线性规划对偶理论，讨论了连续线性双层规划的最优解与下层问题的对偶问题可行域上极点之间的关系。利用这一关系，可以将连续线性双层规划转化为有限个线性规划去求解，设计了基于这一思想的极点枚举算法。通过对下层问题对偶间隙的探讨，利用罚函数原理可以将问题转化成一个易于求解的单层优化问题，为此设计了求解连续线性双层规划的罚函数算法。 通过分析连续线性双层规划可行解集合的结构特征，提出了一种求解问题局部最优解方法。在此基础上，构造了二种不同形式的割平面约束，利用线性规划单纯形方法和双线性规划求解技术来修正局部解，分别设计了二个求解全局最优解的割平面算法。由于连续线性双层规划的全局最优解可在其约束域的极点上达到，所以通过引进一种极点对应的割平面约束，提出了第三个全局收敛的割平面算法。 本文研究的另一个主要内容，是对混合整数线性双层规划的探讨，通过对其三种基本问题及性质的讨论，分析了求解此类问题的复杂性和困难性。对上层所有变量为连续型变量、下层所有变量为离散型变量和上、下层都含离散型变量的两种基本问题，目前还没有可行的方法加以求解。对上层所有变量为离散变量、下层所有变量为连续变量的问题，给出了一种定界规则，设计了分支定界求解算法；对上层所有变量为0-1型变量、下层所有变量为连续变量的问题，利用整数线性规划技术和连续线性双层规划的结果，提出了一种求解算法，并用算例说明了这两种算法的求解过程。 最后，对论文进行了总结，并指出了进一步研究的工作。

目录

文摘

英文文摘

独创性声明及关于论文使用授权的声明

第1章绪论

第2章连续线性双层规划

第3章求解连续线性双层规划的极点枚举法

第4章求解连续线性双层规划的罚函数法

第5章求解连续线性双层规划的割平面法

第6章混合整数线性双层规划

第7章 混合整数线性双层规划的求解算法

第8章总结与展望

参考文献

附录一线性规划

附录二整数线性规划

致谢

博士期间发表论文情况