运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2005年
1期
13-20
,共8页
运筹学%非线性整数规划%凹背包问题%分枝定界方法%线性下逼近
運籌學%非線性整數規劃%凹揹包問題%分枝定界方法%線性下逼近
운주학%비선성정수규화%요배포문제%분지정계방법%선성하핍근
Operations research%nonlinear integer programming%concave knapsack problem%branch-and-bound method%linear underestimation
凹整数规划是一类重要的非线性整数规划问题,也是在经济和管理中有着广泛应用的最优化问题.本文主要研究用分枝定界方法求解凹整数规划问题,这一方法的基本思想是对目标函数进行线性下逼近,然后用乘子搜索法求解连续松弛问题.数值结果表明,用这种分枝定界方法求解凹整数规划是有效的.
凹整數規劃是一類重要的非線性整數規劃問題,也是在經濟和管理中有著廣汎應用的最優化問題.本文主要研究用分枝定界方法求解凹整數規劃問題,這一方法的基本思想是對目標函數進行線性下逼近,然後用乘子搜索法求解連續鬆弛問題.數值結果錶明,用這種分枝定界方法求解凹整數規劃是有效的.
요정수규화시일류중요적비선성정수규화문제,야시재경제화관리중유착엄범응용적최우화문제.본문주요연구용분지정계방법구해요정수규화문제,저일방법적기본사상시대목표함수진행선성하핍근,연후용승자수색법구해련속송이문제.수치결과표명,용저충분지정계방법구해요정수규화시유효적.
Concave integer programming is an important class of nonlinear integer programming problems with applications in optimization models involving economies of scale. In this paper, we investigate branch-and-bound method for solving concave integer programming problems. The method is based on the linear underestimation of the objective function and continuous relaxation. The continuous subproblem at each node is solved by a spe-cial Lagrangian multiplier search procedure. Extensive computational experiment showsthat the branch-and-bound method is efficient in solving concave integer programmingproblems.
