应用数学与计算数学学报
應用數學與計算數學學報
응용수학여계산수학학보
Communication on applied mathematics and computation
2015年
3期
278-287
,共10页
占优%占优组%分支定界%二次背包问题%整数规划%全局最优
佔優%佔優組%分支定界%二次揹包問題%整數規劃%全跼最優
점우%점우조%분지정계%이차배포문제%정수규화%전국최우
给出了一种求解一般二次整数背包问题(quadratic integer knapsack problem,QIKP)的新算法.该方法把占优的概念与分支定界思想结合,旨在寻求全局最优解.对QIKP给出了占优的定义,通过变量系数之间的关系,很容易找到占优组和极小占优组,从而删除可行域中那些非最优点.新的占优定义对凹的二次函数尤其有效.在理论证明的基础上,设计相应的算法,并进行了数值计算.结果显示,在随机产生的例子中,该算法是有效的,并且与传统的分支定界算法相比,得到了更好的最优解,最优值有了较大的提升.
給齣瞭一種求解一般二次整數揹包問題(quadratic integer knapsack problem,QIKP)的新算法.該方法把佔優的概唸與分支定界思想結閤,旨在尋求全跼最優解.對QIKP給齣瞭佔優的定義,通過變量繫數之間的關繫,很容易找到佔優組和極小佔優組,從而刪除可行域中那些非最優點.新的佔優定義對凹的二次函數尤其有效.在理論證明的基礎上,設計相應的算法,併進行瞭數值計算.結果顯示,在隨機產生的例子中,該算法是有效的,併且與傳統的分支定界算法相比,得到瞭更好的最優解,最優值有瞭較大的提升.
급출료일충구해일반이차정수배포문제(quadratic integer knapsack problem,QIKP)적신산법.해방법파점우적개념여분지정계사상결합,지재심구전국최우해.대QIKP급출료점우적정의,통과변량계수지간적관계,흔용역조도점우조화겁소점우조,종이산제가행역중나사비최우점.신적점우정의대요적이차함수우기유효.재이론증명적기출상,설계상응적산법,병진행료수치계산.결과현시,재수궤산생적례자중,해산법시유효적,병차여전통적분지정계산법상비,득도료경호적최우해,최우치유료교대적제승.
