线性规划的松弛 在数学中整数规划的线性规划的松弛是这样的问题把每个变量必须为或的约束替换为较弱的每个变量属于区间的约束 也就是说对于原整数规划的每个下列形式的约束 x i       displaystyle xiin  我们转而使用一对线性约束来代替   x i   displaystyle leq xileq  这样产生的松弛是线性规划因此得名线性规划的松弛这种松弛技术把NP难的最优化问题整数规划转化为一个相关的多项式时间可解的问题线性规划我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息