第3章 整数规划(Integer Programming)

Presentation on theme: "第3章 整数规划(Integer Programming)"— Presentation transcript:

1 第3章 整数规划(Integer Programming)
网 络 优 化 Network Optimization 清华大学课号： （研） 第3章 整数规划(Integer Programming) 清华大学数学科学系 谢金星 办公室：理科楼2206# （电话： ）

2 整数规划问题的例子 例（续例1.4） 指派问题(Assignment Problem)
一家公司经理准备安排N名员工去完成N项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的. 如何分配工作方案可以使总回报最大？ 线性整数规划(LIP) 非线性整数规划(NIP) 纯整数规划(PIP) 混合整数规划(MIP) 特例：0-1规划 许多网络优化问题也可以用整数规划(IP)来建模

3 3.1.1 整数规划问题的几种描述形式 ，A是行满秩的，且 ，A是行满秩的，且
3.1.1 整数规划问题的几种描述形式 线性规划（LP：Linear Programming）问题的标准形式 ，A是行满秩的，且 纯整数线性规划(PILP，以后简称整数规划（IP）)的标准形式 ，A是行满秩的，且

4 3.1.1 整数规划问题的几种描述形式 整数规划的一般形式 整数规划的规范形式
3.1.1 整数规划问题的几种描述形式 整数规划的一般形式 整数规划的规范形式 整数规划的上述三种形式是等价的：一种形式下的实例，可以简单地等价变化为另一种形式下的实例.

5 3.2.2 整数规划问题的求解难度 x2 C A B x1 整数规划问题是NP困难的.
为什么不先求解相应的线性规划问题（一般称为整数规划问题的线性规划松弛问题，或简称LP-Relaxation），然后将得到的解四舍五入到最接近的整数？ 目标函数下降方向 x1 x2 C A B IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点.但LP松弛的最优解为C(3.5,2.5)

6 3.2全么模阵 IP的LP松弛的最优解什么时候一定是整数解呢？
假设在（3.1）式所示的线性规划问题中等式约束个数等于决策变量个数(m=n), 则此时的等式约束构成一个线性方程组Ax=b. 如果方阵A为整数矩阵且b为整数向量, 则det(A)和det(Aj)都是整数. 当然，解x未必是整数向量. 如果det(A) = 1或-1, 则解x一定是整数向量.

7 - Hoffman-Kruskal定理（1956）
3.2全么模阵 定理3.1 设在（3.1）式所示的线性规划问题中A为整数矩阵，且A 满行秩，则下面三个条件等价： （1）对每个基矩阵B，其行列式det（B）=1或-1. （2）对任何整数向量b，其可行域 的每个极点都是整数向量. （3）对每个基矩阵B，其逆矩阵也是整数矩阵. 证明 （1）=>（2）： （2）=>（3）：设B为任一基矩阵，如果其逆矩阵不是整数矩阵，任取整数向量y 使得 ，这里ei表示第i个分量为1其余分量为0的“单位向量”. 令 ，则b为整数向量，且向量 为D（b）的一个极点的基向量，因此是整数向量. 因此 为整数向量，即 是整数矩阵. (3)=>(1)：设B为任一基矩阵，由于 ，又知B 和 都是整数矩阵，所以det（B）=1或-1.

8 – 定义 3.2全么模阵 定义3.1 如果一个矩阵A的任何子方阵的行列式的值都等于0，1或-1，则称A是全么模的（TU：Totally Unimodular，又译为全单位模的），或称A是全么模矩阵. 全么模矩阵的元素只能取0，1和-1. 定理3.2 （全么模矩阵的性质）下列命题等价： A是全么模矩阵. -A是全么模矩阵. AT是全么模矩阵. （A，A）是全么模矩阵. （A，I） ，（A，0）是全么模矩阵. A为全么模矩阵时的整数规划问题实际上等价于对应的LP松弛问题（单纯形算法）.

9 定理3.3 设A是由0，1和-1组成的矩阵，如果下面两个条件同时成立，则A为全么模矩阵. （1）A的每一列至多含有两个非零元素.
3.2全么模阵 - 充分条件 定理3.3 设A是由0，1和-1组成的矩阵，如果下面两个条件同时成立，则A为全么模矩阵. （1）A的每一列至多含有两个非零元素. （2）A的行可以分为A1，A2两个集合，使得：如果A的一列中有两个符号不同的元素，则相应的两行在同一集合A1或A2中；如果A的一列中有两个符号相同的元素，则相应的两行分别位于两个集和A1和A2中. 证明 如果矩阵A满足条件（1）和（2），则A的任意子矩阵仍然满足条件（1）和（2）. 所以，只需证明当A为方阵且满足条件（1）和（2）时，det（A）= 0，1或-1即可. 下面用数学归纳法证明 当A为1阶方阵时，显然=0，1或-1. 假设结论对任意（n-1）阶方阵均成立，下面考虑A为n阶方阵的情形. 有且只有以下三种可能： A的某一列元素全为0，则det（A） =0. A的某一列元素只有一个不为0 ，则det（A） =0 ，1或-1. A的每一列均含有两个非零元 ， 则det（A） =0.

10 3.2全么模阵 - 与网络优化的关系 推论 （1）一个有向图的关联矩阵为全么模矩阵.
（2）一个无向图的关联矩阵为全么模矩阵，当且仅当该图为二部图. 当采用整数规划来描述网络优化问题时，其约束矩阵一般是有向图的关联矩阵或它的简单变形，一般都是全么模矩阵. 因此可以认为，许多网络优化问题都是一类特殊的整数规划，其LP松弛与原问题有相同的最优解. 网络优化处于线性规划和整数规划的结合点上，或者说处于连续优化和离散优化（组合优化）的结合点上.

11 3.3分数割平面法 Gomory（1958） 如果给线性规划增加一个约束，则原线性规划问题的可行域集合可能缩小, 即可行域相当于被“割掉”了一块. 基本思想：如果给整数线性规划增加一个线性约束，而没有“割掉”其任何可行整数解，则新问题与原问题有相同的整数解. 增加的相应约束通常被称为割平面（Cutting Plane）. 首先用原始单纯形法求解整数线性规划（3.2）的LP松弛（3.1），得到一个最优基本解. 设它对应的基为B，且设对应的单纯形表中第i个方程(第i行)为： （i=0,1,2,…,m) 记 对约束方程两边取“地板函数”（用 表示），即取小于或等于对应的实数值的最大整数值. 由于x为非负整数，所以

12 分数割平面法 两式相减： 令 则 第i行的Gomory割 为了将它加入已经得到的单纯形表并仍然保持一个基本解,将它进一步变为
令 则 第i行的Gomory割 为了将它加入已经得到的单纯形表并仍然保持一个基本解,将它进一步变为 其中s为引进的新变量（非负）. 引理3.1 约束(3.10)加入到LP松弛问题的最优表之后，没有割掉任何整数可行点；并且当 不是整数时，新表里是一个对偶基本可行解，但不是原始可行解. s与B一起构成新的基变量；基本解中 单纯形表第0行不变，所以基本解是对偶基本可行解.

13 分数对偶算法算法(Fractional Dual Algorithm,Gomory,1958)
STEP0. 解ILP的LP松弛问题. 如果松弛问题无解,则令 feasible=“no”；否则得松弛问题的最优解,令feasible=“yes”, 继续STEP1. STEP1. 如果feasible=“no”, 则原问题无解, 结束; 如果feasible=“yes”且是整数解, 则得到原问题的最优解, 结束; 否则继续STEP2. STEP2. 选取某行生成割平面；在单纯形表中加上生成的Gomory割（3.10）和对应的基变量s. STEP3. 应用对偶单纯形法求解新问题. 如果对偶问题无解, 令 feasible=“no”；否则设为新的当前最优解. 转STEP1.

14 分数对偶算法算法(Fractional Dual Algorithm,Gomory,1958)
例3.1 用分数割平面法求解： 将其LP松弛问题化为标准形： b -z = -1 = 6 3 2 1 -3

15 分数对偶算法算法(Fractional Dual Algorithm,Gomory,1958)
b -z = -1 = 6 3 2 1 -3 b -z = -3/2 1/2 = 6 1 -1 b -z = 3/2 1/4 = 1 1/6 -1/6

16 分数对偶算法算法(Fractional Dual Algorithm,Gomory,1958)
b -z= 3/2 1/4 = 1 1/6 -1/6 -1/2 -1/4 b -z= 1 = 2/3 -1/3 2 -4 b -z= 1 = 2/3 -1/3 2 -4 -2/3

17 分数对偶算法算法(Fractional Dual Algorithm,Gomory,1958)
b -z= 1 = 2/3 -1/3 2 -4 -2/3 b -z= 1 = -1/2 -5 3/2 -3/2 得到最优解为（1，1），是整数解. 结束，原问题最优解为（1，1），最大值为1.

18 对分数割平面算法,我们作以下几点说明 (1)该算法能否保证其有限性,即是否一定在有限步内停止?我们知道,线性规划的单纯形法可能出现循环,因此不一定在有限步内停止.所以, 分数割平面算法也不一定在有限步内停止.但是,当在(对偶)单纯形法中采用字典序反循环法则时,可以证明分数割平面算法一定在有限步内停止. (2)可以看出,该算法在计算过程中不断增加割平面的个数,因此约束越来越多.为了防止割平面个数任意增加,一般可以作如下处理:如果一个松弛变量应进入基,则将相应的行和列从单纯形表中去掉,即去掉了对应的割平面.因此,单纯形表中的约束行数不会多于变量个数. (3) 该算法在计算机上实现过程中会有一点麻烦:由于存在误差,判定一个实数是否为整数是比较困难的.为了克服这一困难,人们提出了全整数算法. (4) 分数对偶算法采用对偶单纯形法,在达到最优解之前得不到原问题的可行解,因此如果计算时间过长而不得不中间停机时,结果往往无法使用.为了解决这一问题,人们提出了原始整数割平面算法.

19 3.4 分枝定界法（Branch and Bound）
基本思想：隐式地枚举一切可行解（组合优化） 所谓分枝，就是逐次对解空间进行划分；而所谓定界，是指对于每个划分后的解空间（即每个分枝），要计算原问题的最优解的下界（对极小化问题）. 这些下界用来在求解过程中判定是否需要对目前的解空间（即分枝）进一步划分，也就是尽可能去掉一些明显的非最优点，从而避免完全枚举. 定界方法中经常采用的有Lagrange松弛方法和线性规划松弛方法等 若在某一时刻，得到一个全整数解的费用为zm，则zm为原问题的一个上界; 否则得该分枝的一个下界，继续分枝．

20 分枝定界算法 STEP0. 令activeset={0}(原问题);U = ∞；currentbest=0. STEP1. 如果activeset=, 则已经得到原问题的最优解, 结束; 否则从活跃分枝点集合activeset中选择一个分枝点k；将k从activeset中去掉, 继续STEP2. STEP2. 生成k的各分枝 及其对应的下界zi. STEP3.对分枝 : 如果分枝i得到的是全整数解且zi<U, 则令U=zi且 currentbest=i；如果分枝i得到的不是全整数解且<U, 则把i加入activeset中. STEP4. 转STEP1.

21 分枝定界算法 – 例 例3.2 用分枝定界法求解： （P0） 该问题的LP松弛解为 ,不是整数解,最优值为z0=-4.
(P1): (P0)加上 ; (P2): (P0)加上 问题(P1)的LP松弛解为 ,不是整数解,最优值为z1=-3.5 (P3): (P1)加上 ; (P4): (P1)加上 问题(P3)的LP松弛无可行解.

22 分枝定界算法 – 例 问题(P4)的LP松弛解为 ,不是整数解,最优值为z4=-3.25 (P5): (P4)加上 ;
再看问题(P2).问题(P2)的LP松弛解为 ,不是整数解,最优值为z2=-2.5 > z6 ,因此没有必要继续从问题(P2)进行分枝. ,

23 布 置 作 业 目的 掌握整数规划的基本概念； 掌握全么模阵的基本概念和性质； 掌握割平面法和分枝定界算法 内容 《网络优化》第95-96页
3; 7; 10（2）； 9*(1)（min改为max, 此题选做）