• 整数规划

1. 建立逻辑变量来整合多个方案。如0-1变量（要说明0和1分别表示什么）见P79
2. 求解纯整数规划的分支定界法：
   1. 求解整数规划的松弛问题的最优解
   2. 若松弛问题的最优解满足整数要求，则得到整数规划的最优解，否则转下一步
   3. 任意选一个非整数解的变量xi（选择分数部分最小的，如同时存在6.1，6.2，则选择6.1），在松弛问题中分别加上约束Xi≤[Xi]以及Xi≥[Xi]+1，组成两个新的松弛问题
   4. 检查所有分支的解以及目标函数值，若某分支的解是整数并且目标函数值大于等于其他分支的目标值，则将其他分支剪去（删了），不再计算，若还存在非整数解并且目标值大于整数解的目标值，则继续分支，直到得到最优解.
3. 求解IP的割平面法
   1. 求对应松弛问题的最优解
   2. 当某个解xi不满足整数要求时,寻早一个约束方程并添加到松弛问题中

新约束要割掉松弛问题的非整数最优解

新约束要保留所有整数可行解

Ep：

此时将进的约束带入计算（要构造新的松弛变量X5）

1. 0-1型整数规划的求解
   1. 整数规划中变量只能取0或1，称这样的整数规划为0-1整数规划
   2. 隐枚举法：
      • 找出任意可行解，目标函数值为Z0
      • 对于最大化问题，按目标函数系数从小到大排列。

对于最小化问题，按目标函数系数从大到小排列。 目的是使得最优解尽早出现。

• • • 原问题求最大值时增加一个约束；求最小值时，符号改为≤
    • 列出所有可能解，对每个可能解先检验式（*），若满足，再检验其他约束，若不满足，则认为不可行；若某个解满足所有约束，则该解为可行解
    • 目标函数值最大（最小）的解就是最优解

Ep: