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

非线性整数规划问题的若干新算法

作　者: 王粉兰
导　师: 孙小玲
学　校: 上海大学
专　业: 运筹学与控制论
关键词: 非线性整数规划 区域分割 凹背包间题 分枝定界 二次非线性整数规划 可分离非线性整数规划 不可分离整数规划 拉格朗日松弛 拉格明日分解 等值面切割
分类号: O221.4
类　型: 博士论文
年　份: 2006年
下　载: 980次
引　用: 3次
阅　读: 论文下载
 

内容摘要


整数规划问题是指在一些等式约束、不等式约束和整数变量的限制下，最小化或最大化一个目标函数的优化问题。如果问题中的所有函数都是线性的，那就是线性整数规划问题。否则，就称之为非线性整数规划问题。研究整数规划的主要任务就是要设计一些有效算法来解决各种涉及整数变量的实际问题。随着解决线性整数规划问题的一系列高效算法和软件的发展，再加上高速计算机的发明，线性整数规划已经成为解决各个领域实际问题的一个重要工具。然而，由于目标函数的非线性性或者约束函数的非线性性，使得应用领域中的许多实际问题，不能用一个线性整数规划问题来表示，甚至也不能用一个线性整数规划问题来充分逼近。近30年来，人们在求解非线性整数规划问题方面作出了很大努力，并且取得了很大进展。与线性整数规划和非线性连续优化不同的是，非线性整数规划几乎没有一种能应用广泛的有效算法，针对不同结构和特性的问题所设计的算法有时差异会很大。在这一点非线性整数规划与组合优化很类似。本文就三类不同的非线性整数规划问题给出了几种有效的精确算法。 全文共分五章，每章都有详细的数值例子和图形说明，而且还包含大量的计算实验，并且以表格的形式给出数值计算结果。 第一章介绍了非线性整数规划问题的发展背景，并且给出几个非线性整数规划问题在不同应用领域的实际模型，问题涉及分层抽样的最优样本配置问题和制造业中的容量计划问题等。 第二章研究了一类带有单个线性约束的凹背包问题。我们对这类问题提出了一种有效的精确算法。该算法利用线性函数来下逼近目标函数，通过求解松弛后的线性规划问题得到问题的下界和上界。然后运用区域分割来消除对偶间隙。对

全文目录


摘要  6-8
Abstract  8-13
第一章 绪论  13-35
  1.1 非线性整数规划的发展背景  13-15
  1.2 非线性整数规划模型  15-18
    1.2.1 分层抽样中的最优样本配置  15-16
    1.2.2 制造业容量计划问题  16-17
    1.2.3 投资组合问题  17-18
  1.3 非线性整数规划问题的一般形式及常用解法  18-20
  1.4 可分离的非线性整数规划问题  20-25
    1.4.1 混合算法  21-25
  1.5 非线性背包问题  25-29
    1.5.1 一般形式及应用  25-26
    1.5.2 非线性背包问题的现有解法  26-27
    1.5.3 非凸背包问题的现状及本文所做的相关工作  27-29
  1.6 目标函数是二次函数的可分离整数规划问题  29-32
    1.6.1 二次可分离整数规划问题的应用及现有的解法  29-30
    1.6.2 拉格朗日对偶方法和本文所做的相关工作  30-32
  1.7 不可分离凸背包问题  32-35
    1.7.1 不可分离凸背包问题的现有解法  32-33
    1.7.2 拉格朗日分解方法和本文所做的相关工作  33-35
第二章 凹背包问题的一种精确算法  35-49
  2.1 用线性下逼近求原问题的界  35-38
  2.2 区域分割  38-41
  2.3 求精确解的算法  41-46
  2.4 数值结果  46-47
  2.5 结论  47-49
第三章 具有二次目标函数的可分离整数规划问题的一种收敛的拉格朗日等值面切割算法  49-87
  3.1 拉格朗日对偶及对偶搜索  49-56
    3.1.1 对偶搜索  54-56
  3.2 二次目标函数的等值面切割法  56-61
    3.2.1 椭球体等值面  57-58
    3.2.2 等值面切割  58-61
  3.3 单约束问题的收敛拉格朗日等值面切割法  61-68
    3.3.1 算法提出的动机  61-66
    3.3.2 主要算法  66-68
  3.4 多个约束的情况  68-73
  3.5 目标函数为不定二次函数的情况  73-78
  3.6 数值结果  78-85
    3.6.1 测试问题  78-79
    3.6.2 数值实验  79-80
    3.6.3 与其它方法的比较  80-85
  3.7 结论  85-87
第四章 不可分离凸背包问题的拉格朗日分解和域分割法  87-97
  4.1 拉格朗日分解法  87-90
  4.2 求解最优解的算法  90-94
  4.3 数值结果  94
  4.4 结论  94-97
第五章 总结  97-99
参考文献  99-109
本人在博士期间所发表的论文  109-111
致谢  111

相似论文

  1. MTO供应链中3PL运输协调调度问题研究,F224
  2. 供应链金融下的库存模型优化,F224;F832
  3. 监控图像中ROI提取及目标检测技术研究,TP391.41
  4. 地区电网无功优化的研究,TM714
  5. 求解0-1非线性整数规划问题的非单调光滑牛顿算法,O221.4
  6. 求解非线性规划问题全局最优解的全局凸填充函数法,O221.2
  7. 基于Lanchester平方律方程的一类海战实例的决策分析,E911
  8. 炼钢—精炼—连铸生产调度与过程监控系统,TP277
  9. 视频图像中维语文字的提取和识别,TP391.41
  10. 基于区域的图像检索相关技术研究,TP391.41
  11. 红外与可见光图像融合技术研究,TP391.41
  12. 手指静脉识别关键技术研究,TP391.41
  13. 基于边缘检测的半脆弱水印技术研究,TP309.7
  14. 卫星数传调度优化算法及可视化仿真技术研究,V556
  15. 基于改进Canny边缘检测算子的电子稳像算法研究,TP391.41
  16. 整数规划算法效率的研究,O221.4
  17. 考虑动态安全约束的电力系统机组组合研究,TM73
  18. 基于噪声统计模型的区域分割,TP391.41
  19. 基于ICA的运动目标检索方法研究,TP391.41
  20. 基于约束传播技术的资源受限项目调度问题求解算法,F270
  21. 彩色图像分割,TP391.41

中图分类: > 数理科学和化学 > 数学 > 运筹学 > 规划论（数学规划） > 整数规划
© 2012 www.xueweilunwen.com