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

改进的求解线性多层规划的主元标单纯形法

作　者: 张美芳
导　师: 成央金
学　校: 湘潭大学
专　业: 运筹学与控制论
关键词: 线性二层规划线性三层规划主元标单纯形法 Frank-Wolf方法主元标罚函数
分类号: O221.1
类　型: 硕士论文
年　份: 2009年
下　载: 45次
引　用: 0次
阅　读: 论文下载

内容摘要

本文第1章简单地介绍了线性多层规划的起源及其发展历史.并着重介绍了线性多层规划问题模型的结构,以及现有的针对线性多层规划问题算法已有的成果。第2章给出了研究本文课题所需的预备知识.首先,简单介绍了本文所研究的线性二层规划的基本模型,以及针对该模型的基本概念和重要结论。其次,我们介绍了针对于一层规划问题而产生的原始的主元标单纯形法和Frank-Wolf算法的基本原理和算法步骤.最后,我们总结了现有的针对二层线性规划问题的算法思路,并对各种思路所产生的部分算法做了比较。另外针对线性三层规划求解算法相对较少的现状,根据前人的算法思路进一步引申出本文算法。在第3章中,我们主要列举了本课题所产生的主要结果。针对线性二层规划的两种模型,我们通过改变基变量的选择规则得到改进的主元标单纯形法,当求解上层目标函数带约束条件的模型时,再次对算法作了相应的调整,并通过算例得到了很好的结果。对于线性三层规划模型,我们在利用主元标单纯形法进行计算的基础上,结合Frank-Wolf线性逼近的思想和罚函数的思想得到改进的Frank-Wolf算法,其优点是可以通过求解有限个线性规划而得到线性三层规划的解,同样通过算例验证了该算法的可行性。本文的第4章,我们给出了结论和展望.由于线性规划问题已形成了相对完备的知识体系,而线性规划又是多层线性规划的基础,我们期待可以类似得到更加完善的多层线性规划的知识体系。另外由于线性多层规划问题本身的复杂性,决定了对其增加许多很强的限制才能实现其求解过程,而对这些强的限制条件的能否解除也将是我们必须继续研究的问题。

全文目录

摘要  4-5
ABSTRACT  5-8
第1章绪论  8-11
第2章预备知识  11-17
  2.1 二层线性规划的基本概念及性质  11-12
  2.2 主元标单纯形法和Frank-Wolf算法简介  12-15
  2.3 多层线性规划已有主要算法介绍  15-17
第3章主要结果  17-36
  3.1 二层线性规划的改进的主元标单纯形法  17-20
  3.2 二层线性规划的算例  20-25
  3.3 三层线性规划的改进的算法  25-30
  3.4 三层线性规划的算例  30-36
第4章结论和展望  36-37
参考文献  37-42
致谢  42-43
附录  43

改进的求解线性多层规划的主元标单纯形法

内容摘要

全文目录

相似论文