上海大学学报（自然科学版）
上海大學學報（自然科學版）
상해대학학보（자연과학판）
JOURNAL OF SHANGHAI UNIVERSITY (NATURAL SCIENCE EDITION)
2006年
4期
389-393
,共5页
0-1多项式背包问题%拉格朗日松弛%分枝定界法%最大流法
0-1多項式揹包問題%拉格朗日鬆弛%分枝定界法%最大流法
0-1다항식배포문제%랍격랑일송이%분지정계법%최대류법
提出了0-1多项式背包问题的一种新的精确算法.该算法是一个基于拉格朗日松弛和对偶搜索的分枝定界方法.用外逼近法求拉格朗日对偶问题得到上界,其中拉格朗日松弛问题通过转化为一个网络最大流问题来求解.为了提高算法的效率,利用两种启发式方法求初始可行解,并用填充和交换的方法改进后得到初始下界;并且在分枝定界前,利用所得到的拉格朗日界,先固定最优解中某些变量的值.数值结果表明该算法是有效的.
提齣瞭0-1多項式揹包問題的一種新的精確算法.該算法是一箇基于拉格朗日鬆弛和對偶搜索的分枝定界方法.用外逼近法求拉格朗日對偶問題得到上界,其中拉格朗日鬆弛問題通過轉化為一箇網絡最大流問題來求解.為瞭提高算法的效率,利用兩種啟髮式方法求初始可行解,併用填充和交換的方法改進後得到初始下界;併且在分枝定界前,利用所得到的拉格朗日界,先固定最優解中某些變量的值.數值結果錶明該算法是有效的.
제출료0-1다항식배포문제적일충신적정학산법.해산법시일개기우랍격랑일송이화대우수색적분지정계방법.용외핍근법구랍격랑일대우문제득도상계,기중랍격랑일송이문제통과전화위일개망락최대류문제래구해.위료제고산법적효솔,이용량충계발식방법구초시가행해,병용전충화교환적방법개진후득도초시하계;병차재분지정계전,이용소득도적랍격랑일계,선고정최우해중모사변량적치.수치결과표명해산법시유효적.
