-
整数规划是从1958年由R.E戈莫里提出割平面法之后 ，经过三十多年的发展，已经不断出现了很多解决整数规划问题的方法。当然，解整数规划（最优化）最典型的解决方案是逐步转化原整数规划问题，从而让原问题逐步生成一个相关的数学模型，称其为原文题的衍生问题。然后对每一个衍生问题进一步转化，再形成一个比衍生问题更简单、更易于求解的松弛问题（称衍生问题为松弛问题的原问题）。最后对松弛问题进行求解，然后回归到原问题进行实际的检验，一方面这决定原问题应该被舍弃，还是再生成一个或多个其本身的衍生问题来替换它；另一方面，再选择一个尚未被舍弃或替代的衍生问题，重复以上步骤，知道所有的衍生问题都被解决掉。28849
- 上一篇：频扫天线技术国内外研究现状
- 下一篇：网络爬虫技术国内外研究现状
0-1整数最优化问题作为整数规划中特殊的一部分，在整数规划中占有重要的地位。其首要原因是因为在实际生活中的很多问题，比如送货问题、选址问题以及指派问题等都可以化为0-1整数规划的一部分，另外，任何有界变量的整数最优化都与0-1整数规划等价，除此之外，0-1规划还可以把多种规划问题转化成整数最优化问题，所以现阶段有不少的知名学者致力于这方面的研究。一般对于初学者，求解0-1整数规划问题最基本的方法就是分支定界法。对于特殊问题（比如指派问题）可以用匈牙利方法进行求解。除了这些基本、常见的方法外，为了更方面用0-1整数规划解决各个领域中的实际问题，国内外学者还提出了一些求解0-1规划的新算法。如：在Kenney和Eberhart的二进制粒子群算法（BPSO）的基础上提出了一种改进的二进制粒子群算法（BPSO），将这种方法应用在背包问题上的计算结果表明，和遗传算法相比，二进制粒子群算法拥有更快的收敛速度 ；对于求靶场效能优化这类复杂的0-1整数规划问题，提出的混沌搜索算法能找到最优的全局最优解，并使得它优于传统的优化算法 ；基于三螺旋结构的DNA链的独特结构，殷志祥首次将DNA计算应用到0-1规划问题的求解中，提出了生物算法 ；通过将简单的遗传算法和启发式贪婪算法相结合形成的混合遗传算法 可以求解大规模的背包问题，相比较原始的遗传算法和启发式贪婪算法，这种发放对背包问题解得计算和精确性都有了较大的提高。论文网
除了上面介绍的对0-1整数规划的一些算法外，1982年，Kirkpatrick等人巧妙的将退火思想应用到组合优化领域，探索出了一种求解大规模整数规划全局优化问题的随机性方法 ——模拟退火的整数规划算法。它不仅具有使用范围广的优点，而且其算法简单，可靠性较高；除此之外，还有有约束非线性解整数规划模型的模拟植物生长算法 等。