学位论文 > 优秀研究生学位论文题录展示
0-1二次规划的全局最优性条件及算法
作 者: 陈伟
导 师: 张连生
学 校: 上海大学
专 业: 运筹学与控制论
关键词: 0-1二次规划 全局优化 全局最优性条件 填充函数 整数规划
分类号: O224
类 型: 博士论文
年 份: 2005年
下 载: 472次
引 用: 1次
阅 读: 论文下载
内容摘要
全局优化问题广泛见于工程、国防、经济等诸多重要领域,是数学规划理论的一个重要研究领域。本文首先讨论一类特殊结构的全局优化问题:二次规划的全局优化问题。我们给出了0-1二次规划的全局最优性条件,并讨论了其相应的算法。然后,对于一般结构的全局优化问题,我们给出了一个新的无参数的填充函数方法。 本论文的第一章介绍全局优化理论的一些研究成果。第二章讨论无约束0-1二次规划的全局最优性条件。在第二节得到一个充分条件和一个必要条件的基础上,我们希望能够得到一些充要条件。为此,我们首先在第三节中给出在线性约束条件下,(?)成为一个凸的二次函数的全局极大点的充分必要条件。从这个结论出发,在第四节,我们得到了无约束0-1二次问题全局最优的充分必要条件及其等价形式。在第五节,我们将注意力放在全局最优的必要条件上。我们得到的必要条件都不含对偶变量,仅用到原问题的数据。这样,这些条件在实际中都是可以被检验的。进一步,为了使必要条件在实际中易被检验、易操作,我们降低了必要条件中的维数,在比原问题维数更低的空间中,给出一些简洁的必要条件,以达到方便检验的目的。 在第三章,我们进一步研究有约束的0-1二次规划的全局最优条件。对于带有线性不等式约束的0-1二次问题,我们在第一节中得到了它全局最优的充分条件和必要条件。必要条件也不含对偶变量。当系数矩阵正定时,我们建立了原0-1问题的解与松弛问题的解之间的联系。对于带有线性等式约束的0-1二次问题,我们在第二节证明了一个带有线性等式约束的0-1二次规划问题,它的全局最优解集和其相应的罚问题的全局最优解集是相等的。这样,带有线性等式约束的0-1二次问题的解,可以通过无约束0-1二次规划问题的解得到。第三章的另一个内容是讨论0-1二次规划问题的实际应用。将我们得到的一些结论运用于极大团问题和二次分派问题,我们得出了一些相关的结论。 将全局最优条件发展成为可实现的算法,是全局优化研究中的重要的工作。本文的第四章讨论无约束0-1二次规划问题的算法。首先我们将原0-1问题化为一个等价的半正定的0-1二次问题。在得到这个半正定二次问题的松弛解x之后,取与x“最接近的”0-1解y,在一定的条件之下,y就是原0-1问题的全局最优解。由于松弛后的问题是凸的二次规划问题,可以在多项式时间内求解,所以,我们的算法是可实现的。为了确定y是否是原问题的最优解,我们设计了三种算法。在研究了第二章所给
|
全文目录
摘要 8-10 Abstract 10-14 第一章 全局优化研究的一些新进展 14-21 §1.1 引言 14-15 §1.2 全局最优性条件简介 15-18 §1.2.1 D.C.规划、反凸规划 16-17 §1.2.2 二次规划 17-18 §1.3 全局优化的确定性算法概述 18-20 §1.4 相关定义和假设 20-21 第二章 无约束0-1二次规划问题的全局最优性条件 21-38 §2.1 引言 21-22 §2.2 充分条件和必要条件 22-24 §2.3 带有线性约束的二次规划的全局最优条件 24-29 §2.4 0-1问题全局最优的充分必要条件 29-33 §2.5 0-1问题全局最优的一些必要条件 33-38 第三章 有约束的0-1二次规划的全局最优性条件 38-54 §3.1 带有不等式约束的0-1二次规划的的全局最优条件 38-45 §3.2 带有等式约束的0-1二次规划问题 45-47 §3.3 0-1二次规划问题的应用 47-54 §3.3.1 极大团问题 47-50 §3.3.2 二次分派问题 50-54 第四章 无约束0-1二次规划的算法 54-72 §4.1 引言 54-55 §4.2 无约束0-1二次规划问题的一个算法 55-62 §4.3 充分条件之间的关系 62-67 §4.4 对算法的进一步讨论 67-72 第五章 无参数填充函数方法 72-90 §5.1 引言 72-73 §5.2 整变量问题的填充函数方法 73-76 §5.3 连续变量问题的填充函数 76-78 §5.4 算法 78-81 §5.5 算例 81-90 §5.5.1 测试问题 81-83 §5.5.2 整变量问题的计算结果 83-84 §5.5.3 连续变量问题的计算结果 84-85 §5.5.4 结论 85-90 参考文献 90-98 作者攻读博士学位期间完成的论文 98-99 致谢 99
|
相似论文
- 比式和问题的全局优化算法,O224
- 时变网络乡村邮路问题割平面及蚁群算法研究,O221.4
- 相控阵雷达资源优化管理,TN958.92
- 优化算法在调度与控制问题中的应用研究,TP273
- 二次规划的若干算法研究,O221.2
- 企业生产与供应链网络同步优化模型及其在露天矿中的应用,F274;F426.1
- 约束优化QP子问题与线性方程组相结合的一个新的超线性收敛算法,O241.6
- 综合运输通道系统协调发展优化研究,U11
- 基于供应链的图书分销企业配送中心选址问题研究,F274
- 全局优化理论几种算法的改进与研究,O224
- 基于遗传算法的组卷系统的研究与应用,O224
- 非线性全局优化问题的填充函数算法研究,O224
- 非线性全局优化的辅助函数方法研究,O224
- 求解0-1非线性整数规划问题的非单调光滑牛顿算法,O221.4
- 非线性规划问题的若干算法研究,O221.2
- 基于模糊规划方法的连锁店选址与配送中心选择联合决策研究,F721
- 求解非线性规划问题全局最优解的全局凸填充函数法,O221.2
- 蒸馏塔防腐注剂量建模与优化的研究,TE6264
- 基于食物链生态进化算法的输电网扩展规划,TM715
- 城市高压电网无功优化,TM714.3
- 基于Lanchester平方律方程的一类海战实例的决策分析,E911
中图分类: > 数理科学和化学 > 数学 > 运筹学 > 最优化的数学理论
© 2012 www.xueweilunwen.com
|