整数规划和混合整数规划.pdf

整数规划与混合整数规划 2015/10/22 应用优化技术 1 整数规划与混合整数规划  混合整数规划问题  分支定界法  0-1规划的隐数法  割平面法  混合整数非线性规划 2015/10/22 应用优化技术 2 混合整数规划问题 f ,h,g线性 LP min f (x, y ) x , y Y空 s.t . h(x , y ) 0 一大类 NLP g (x , y )  0 优化命题 f ,h,g非线性 x X R n f ,h,g线性 MILP y Y整数 Y非空 f ,h,g非线性 MINLP 2015/10/22 应用优化技术 3 混合整数线性规划问题 min cT x d T y LP x , y s.t . Ax By b x  0, x X R n 0-1规划 y  0,1   y y L z 1 2z 2 4z 3  2N 1z N log y U y L     N 1INT    log 2    2015/10/22 应用优化技术 4 实例一  0-1背包问题  容积v  物品j ：价值w ，体积v j j  设 1 j 放入 xj  0 j 不放  n max w x j j j 1