首页 > 试题广场 >

以下哪个算法不是整数规划的精确算法()

[单选题]
以下哪个算法不是整数规划的精确算法()
  • 分支定价
  • 单纯型算法
  • Benders’分解
  • 隐枚举
分支定价类似于分支定界,但在求解LP松弛时使用列生成 。分支定界我理解就是一种有规律的枚举,所以它是可以求出精确的解。分支定界几个关键点就是设定界限函数,随着搜索的过程中逐渐更新界限,直至上界和下界重合;构建节点表,在每个分支的过程中需要将信息记录下来,按照某一个标准在节点表里储存,后续取点删点。
Benders分解技术是一种求解混合整数规划问题的算法。Benders分解算法将具有复杂变量的规划问题分解为线性规划和整数规划,用割平面的方法分解出主问题与子问题,通过迭代的方法求解出最优值。Benders分解算法是一个很常用的算法,用来计算像最小整数非线性规划问题和随机规划问题之类的难以计算的难题。理论上来说,Benders 算法是能解决大部分的整数规划问题。在实际运用中,它主要是从求解的运算次数和运算时间上来使求解问题得到优化
单纯形算法从线性方程组找出一个个的单纯形,每一个单纯形可以求得一组解,然后再判断该解使目标函数值是增大还是变小了,决定下一步选择的单纯形。通过优化迭代,直到目标函数实现最大或最小值。
隐枚举法(implicit enumeration method)一种特殊的分支定界法。对0-1规划问题,利用变量只能取0或1的两个值的特性,进行分支定界,以达到隐枚举的目的。0-1规划是一种特殊的纯整数规划
发表于 2019-03-21 16:58:48 回复(0)
顺丰的题也太。。。好吧,菜是原罪🙃
发表于 2020-03-21 20:42:54 回复(1)