第3章 整数线性规划 3.1 整数规划问题举例 3.2 割平面法.

Presentation on theme: "第3章 整数线性规划 3.1 整数规划问题举例 3.2 割平面法."— Presentation transcript:

1 第3章 整数线性规划 3.1 整数规划问题举例 3.2 割平面法

2 整数（线性）规划 整数规划问题与模型 整数规划算法 2018/12/8 山东大学 软件学院

3 背包问题 1 实例：一个背包，容量为W。 n 件物品，物品 i 容量（重量）为 wi，价值 vi。
2 3 4 5 6 7 8 9 10 体积 200 350 500 430 320 120 700 420 250 100 价格 15 45 70 50 75 90 20 30 2018/12/8 山东大学 软件学院

4 问题分析（建模） 变量xi – 是否选择物品 i。 整数规划（0-1规划）： max i vixi s.t. i wixi  W
2018/12/8 山东大学 软件学院

5 集合覆盖（Set Cover）问题 实例：基础集合U = {e1, e2, …, en}，集合族C = {S1, S2, …, Sm}，每一个集合Si是U的一个子集。 询问：最小数目的子集的集合族C’ C，使得C’中子集的“并”包含（覆盖）U中的所有元素。 整数规划（0-1规划）： 定义判定变量xi，xi = 1表示集合Si被选取，xi = 0表示集合Si未被选取。 min i xi s.t. Si: e  Si xi  1, e  U xi  {0, 1} 2018/12/8 山东大学 软件学院

6 旅行售货员（TSP）问题 实例：给定 n+1 个城市，任两个城市 vi 和 vj 之间有一个距离cij  0（cij = cji, cii = 0）。一个旅行售货员，从城市 v0 出发，走遍所有的城市，再回到 v0。 询问：售货员应该怎样走，才能使走过的总距离最短？ 2018/12/8 山东大学 软件学院

7 TSP实例 2018/12/8 山东大学 软件学院

8 TSP实例 2018/12/8 山东大学 软件学院

9 建模 变量 xij：是否使用从城市 vi 到城市 vj 的路径。 约束 每个城市只能到达一次、离开一次。
所走过的路径构成一个圈（不能多于一个圈）。 2018/12/8 山东大学 软件学院

10 TSP的整数规划 2018/12/8 山东大学 软件学院

11 强制路径构成仅一个圈 2018/12/8 山东大学 软件学院

12 整数线性规划的特征、模型 特征—变量整数性要求 性质—可行域是离散点的集合 整数线性规划的常见模型： 问题本身的要求 引入的逻辑变量的需要
一般整数规划模型——变量取值为整数。 0-1整数规划模型——变量取值为0或1。 混合整数规划模型——部分变量取值为整数，部分变量取值为实数。 2018/12/8 山东大学 软件学院

13 整数规划与线性规划的关系 整数规划 线性规划 线性规划是整数规划的放松。 整数规划的可行解是对应的放松问题的可行解。
放松的线性规划的最优值  整数规划的最优值。 2018/12/8 山东大学 软件学院

14 解整数规划 对整数规划的几点说明： 对放松问题的最优解进行简单的舍入（如，四舍五入）不能得到整数规划的最优解。这样的整数解对于原整数规划甚至是不可行的。 整数可行解的数目可呈爆炸性增长，简单的枚举法不可取。 2018/12/8 山东大学 软件学院

15 算法 求精确解： 割平面算法 分枝定界算法 求近似解： 舍入法 原始-对偶方法 2018/12/8 山东大学 软件学院

16 割平面算法[Gomory, 1958] 基本思想 用单纯形法解松驰问题(P0)，求到最优解x0。
若x0是整数向量，则x0是ILP问题(P)的最优解，计算结束。 否则，根据x0设法对(P0)增加一个约束条件，称为割平面条件。这个割平面条件将(P0)的可行域割掉一块，且x0在被割掉的区域中，而原ILP的任何一个整数可行解都没有被割掉。 记增加了约束条件的问题为(P1)。对(P1)继续上述过程，直到求到一个整数最优解为止。 2018/12/8 山东大学 软件学院

17 说明 如果在增加约束的过程中，得到的LP没有可行解，则原ILP没有可行解。 如果得到的LP问题无界，则原ILP问题或者无界，或者没有可行解。
2018/12/8 山东大学 软件学院

18 割平面生成方法 2018/12/8 山东大学 软件学院

19 割平面生成方法 2018/12/8 山东大学 软件学院

20 割平面生成方法 2018/12/8 山东大学 软件学院

21 注意 2018/12/8 山东大学 软件学院

22 Gomory割平面算法 求放松问题的 最优基可行解 是否为 整数解？ 是 得到最优解， 停止。 否
将割平面方程加入到单纯形表，得到新的松弛问题。用对偶单纯形算法求最优解。 2018/12/8 山东大学 软件学院

23 算例 (1,1.5) x1 x2 3x1 + 2x2 = 6 3x1 + 2x2 = 0 2018/12/8 山东大学 软件学院

24 得到松弛问题LP0 2018/12/8 山东大学 软件学院

25 解松弛问题LP0 2018/12/8 山东大学 软件学院

26 得到松弛问题LP1 2018/12/8 山东大学 软件学院

27 解松弛问题LP1 2018/12/8 山东大学 软件学院

28 得到松弛问题LP2 2018/12/8 山东大学 软件学院

29 解松弛问题LP2 2018/12/8 山东大学 软件学院

30 对割平面的解释 2018/12/8 山东大学 软件学院

31 对割平面的解释 x1 x2 3x1 + 2x2 = 6 3x1 + 2x2 = 0 x2 = 1 x1  x2 = 0
2018/12/8 山东大学 软件学院

32 2018/12/8 山东大学 软件学院