-
题名解ILP的割平面法中导出方程的选取准则
被引量：1
- 1
-
-
作者
熊义杰
李天歌
-
机构
西安理工大学经济与管理学院
-
出处
《数学的实践与认识》
北大核心
2016年第7期282-287,共6页
-
文摘
解整数规划问题的割平面法在应用时,必须要选出合适的割平面方程,才能使收敛的速度快,迭代的次数少.通过对割平面法的一般性推导,指出最优值减少的越多,则割平面的约束能力就越强,从而在尽量少的迭代次数下得到最优整数解,并给出了割平面方程选取准则的具体计算方法.
-
关键词
整数规划
割平面方程
导出方程
最优值
-
Keywords
integer Linear Programming （ILP）
cutting plane equation
export equation
optimal value
-
分类号
O221.4
[理学—运筹学与控制论]
-
-
题名整数规划中割平面法的研究
被引量：4
- 2
-
-
作者
李裕梅
连晓峰
徐美萍
曹显兵
-
机构
北京工商大学理学院
北京工商大学计算机与信息工程学院
-
出处
《数学的实践与认识》
CSCD
北大核心
2011年第11期82-90,共9页
-
基金
北京市优秀人才培养项目(2009D005003000001)
北京市属高校科技创新平台项目(201098)
-
文摘
割平面法是求解整数规划问题常用方法之一.用割平面法求解整数规划的基本思路是:先用单纯形表格方法去求解不考虑整数约束条件的松弛问题的最优解,如果获得的最优解的值都是整数,即为所求,运算停止.如果所得最优解不完全是整数,即松弛问题最优解中存在某个基变量为非整数值时,就从最优表中提取出关于这个基变量的约束等式,再从这个约束式出发构造一个割平面方程加入最优表中,再求出新的最优解,这样不断重复的构造割平面方程,直到找到整数解为止.主要研究以下四个关键点:一是研究从最优表中提取出的、关于基变量的约束等式出发,通过将式中的系数进行整数和非负真分数的分解,从而得到一个小于等于0的另外一个不等式的推导过程;二是总结出从小于等于0的那个约束不等式出发构造割平面方程的四种方法;三是分析构造割平面方程的这四种方法相互之间的区别和联系;四是探讨割平面法的几何意义.通过对这四个方面的分析和研究,对割平面法进行透彻的剖析,使读者能够全面把握割平面法.
-
关键词
整数规划
割平面法
割平面方程的构造
四个关键点
-
Keywords
integer programming
cutting plane method
construction of cutting plane equation
four critical aspects
-
分类号
O221.4
[理学—运筹学与控制论]
-
