李艳艳,李兴斯.求解线性0-1规划的一种连续化方法[J].,2009,(2):299-302 |
求解线性0-1规划的一种连续化方法 |
A continuous solution to linear 0-1 programming |
|
DOI:10.7511/dllgxb200902025 |
中文关键词: 0-1规划 拉格朗日松弛 对偶规划 连续化 凝聚函数 |
英文关键词: 0-1 programming Lagrangian relaxation dual programming continuation aggregate function |
基金项目:国家自然科学基金资助项目(10572031). |
|
摘要点击次数: 1195 |
全文下载次数: 838 |
中文摘要: |
线性0-1规划作为一种特殊形式的整数规划,在科学和工程问题中有许多应用.基于拉格朗日松弛方法,提出求解线性0-1规划的一种连续化方法.该方法不仅给出了原问题显式形式的对偶函数,而且对偶变量的数目仅等于原问题部分约束的个数,原来的线性0-1规划问题被转化为只有简单约束的普通优化问题,极大地方便了工程应用.以背包问题为例进行的数值实验表明,该方法是求解线性0-1规划的行之有效的实用方法. |
英文摘要: |
Linear 0-1 programming, as a special form of integer programming, has numerous applications to theory as well as to engineering. A Lagrangian relaxation-based continuous solution is presented for solving linear 0-1 programming. It transforms the primal problem into an ordinary optimization problem with an explicit dual function and simple constraints, with smaller size than primal constraints. It is convenient for engineering application. Numerical experiments have been made on certain knapsack problems and computational results show that the proposed algorithm is very promising. |
查看全文
查看/发表评论 下载PDF阅读器 |
关闭 |