求解线性0-1规划的一种连续化方法

• 作 者: 李艳艳 李兴斯
• 机 构: 大连理工大学应用数学系,大连理工大学工业装备结构分析国家重点实验室
• 出 处: 大连理工大学学报
• 发表日期: 2009年2期
• 关键词: 0-1规划 拉格朗日松弛 对偶规划 连续化 凝聚函数
• 基金项目: 国家自然科学基金资助项目(10572031)

线性0-1规划作为一种特殊形式的整数规划，在科学和工程问题中有许多应用．基于拉格朗日松弛方法，提出求解线性0-1规划的一种连续化方法．该方法不仅给出了原问题显式形式的对偶函数，而且对偶变量的数目仅等于原问题部分约束的个数，原来的线性0-1规划问题被转化为只有简单约束的普通优化问题．极大地方便了工程应用．以背包问题为例进行的数值实验表明，该方法是求解线性0-1规划的行之有效的实用方法．