洛阳师范学院学报
洛暘師範學院學報
락양사범학원학보
JOURNAL OF LUOYANG TEACHERS' COLLEGE
2014年
5期
1-4,12
,共5页
整数规划%割平面法%Gomory约束%对偶单纯形法
整數規劃%割平麵法%Gomory約束%對偶單純形法
정수규화%할평면법%Gomory약속%대우단순형법
integer programming%cutting plane method%Gomory constraint%dual simplex method
在使用割平面法求解整数规划时，寻找Gomory约束是其中最为关键的一步。一般地，选取非整数解变量中分数部分最大的一个基变量，写下相应行的约束，由此推导出Gomory约束。本文主要讨论当非整数解变量中分数部分最大的基变量有两个以上时，如何通过比较选取切割条件较强的 Gomory约束，以减少切割次数和运算量，较快地找到最优解。
在使用割平麵法求解整數規劃時，尋找Gomory約束是其中最為關鍵的一步。一般地，選取非整數解變量中分數部分最大的一箇基變量，寫下相應行的約束，由此推導齣Gomory約束。本文主要討論噹非整數解變量中分數部分最大的基變量有兩箇以上時，如何通過比較選取切割條件較彊的 Gomory約束，以減少切割次數和運算量，較快地找到最優解。
재사용할평면법구해정수규화시，심조Gomory약속시기중최위관건적일보。일반지，선취비정수해변량중분수부분최대적일개기변량，사하상응행적약속，유차추도출Gomory약속。본문주요토론당비정수해변량중분수부분최대적기변량유량개이상시，여하통과비교선취절할조건교강적 Gomory약속，이감소절할차수화운산량，교쾌지조도최우해。
When using cutting plane method for solving integer programming , finding Gomory constraint is one of the key steps .In general , we choose the basis variable whose fraction is largest among all variables of the non-integer solution .Then write the equality constraint in the corresponding row , and derive Gomory constraint .In this paper , we mainly discuss the case that there are more than two basis variables whose fractions are largest among all variables of the non-integer solution .By comparison we choose stronger Gomory constraint .Thus the number of cut-ting and the amount of computation can be lessened .We can find the optimal solution more quickly .
