整数规划的难度远大于一般线性规划(PPT 16页)

整数规划
   整数规划的难度远大于一般线性规划
4.1 整数规划简介
要求所有 xj 的解为整数，称为纯整数规划
要求部分 xj 的解为整数，称为混合整数规划
对应没有整数解要求的线性规划称之为松弛问题
整数规划的解是可数个的，最优解不一定发生在极点
整数规划的最优解不会优于其松弛问题的最优解
4.2 整数规划的分枝定解法
    4.2.1 思路与解题步骤
只解松弛问题
1、在全部可行性域上解松弛问题
若松弛问题最优解为整数解，则其也是整数规划的最优解
2、分枝过程
若松弛问题最优解中某个 xk=bk 不是整数，令  bk  为 bk 的整数部分
构造两个新的约束条件 xk  bk  和 xk  bk +1，分别加于原松弛问题，形成两个新的整数规划
3、求解分枝的松弛问题 — 定界过程
设两个分枝的松弛问题分别为问题 1 和问题 2 ，它们的最优解有如下情况

..............................