学位论文 > 优秀研究生学位论文题录展示

非线性双层规划的算法研究

作　者: 杨龙飞
导　师: 赵茂先
学　校: 山东科技大学
专　业: 运筹学与控制论
关键词: 双层规划非线性双层规划信赖域算法下降方向法两阶段算法
分类号: O221.2
类　型: 硕士论文
年　份: 2010年
下　载: 133次
引　用: 0次
阅　读: 论文下载

内容摘要

本文的主要内容是探讨双层规划中的非线性双层规划的算法。通过分析非线性双层规划的数学模型、性质,以线性—二次双层规划为研究的起点,延伸到上层为非线性、下层为二次的情形,给出算法并证明其收敛性。论文首先通过一个交通网络中路段收费问题介绍双层规划的实际背景、定义、主要特点和复杂性。这种最优化问题的特殊性在于：约束条件中包含一个最优化问题。双层规划的解有两种基本形式,乐观形式和悲观形式。由于其内在的困难,算法研究举步维艰,一方面,有人证明了双层规划是NP-hard问题,另一方面,局限在某些特殊类型上,人们已提出了较为有效的算法。目前,非线性双层规划的算法大致上分为三类,分枝定界法(枚举法)、下降法和罚函数法。本文选择线性—二次双层规划为突破口,给出了它的数学模型、基本理论和最优性条件,并将其化为混合整数单层规划求解,为后面的算法研究打下基础。对于上层非线性、下层为二次规划的双层规划,充分利用二次规划的研究成果,以K-T条件代替下层问题,将下层问题线性化,借助旋转步骤找到诱导域极点,沿诱导域极点下降方向不断改进上层目标函数值,但由于上层目标函数非线性,极小值不一定在诱导域极点取到,所以,这种方法未必能找到局部极小点。信赖域算法在单层规划中是很有效的近似算法,把它迁移到双层规划中来也是一个不错的想法,用线性—二次双层规划作为模型可以构造信赖域算法,但其收敛性难以证明。在以上工作的基础上,综合下降算法和信赖域算法各自的优势，提出了两阶段算法,并在较强的假设下给出收敛性的证明,在本文末尾给出一个算例。最后,对论文所做的工作进行了总结,并提出以后研究的方向。

全文目录

摘要  5-6
Abstract  6-9
1 绪论  9-19
  1.1 引言  9-11
  1.2 双层规划的一般形式和基本概念  11-14
  1.3 应用举例  14-15
  1.4 双层规划的研究现状  15-17
  1.5 论文的内容和结构  17-19
2 非线性双层规划暨线性—二次双层规划  19-28
  2.1 非线性双层规划的研究现状  19-22
  2.2 线性—二次双层规划  22-25
  2.3 算例  25-27
  2.4 小结  27-28
3 下层为二次规划的双层规划  28-42
  3.1 下层为二次规划的双层规划模型  28-30
  3.2 基本理论  30-33
  3.3 两阶段算法  33-37
  3.4 收敛性分析  37-39
  3.5 算例  39-41
  3.6 小结  41-42
4 总结与展望  42-43
致谢  43-44
攻读硕士期间主要成果  44-45
参考文献  45-49

非线性双层规划的算法研究

内容摘要

全文目录

相似论文