整数规划(数学建模资料).ppt

* 网 络 优 化 Network Optimization 清华大学数学科学系 谢金星 办公室：理科楼1308# （电话 Email:jxie@ /faculty/~jxie 清华大学课号本）研） 第3章 整数规划(Integer Programming) 整数规划问题的例子 例（续例1.4） 指派问题(Assignment Problem) 一家公司经理准备安排N名员工去完成N项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的. 如何分配工作方案可以使总回报最大？ 许多网络优化问题也可以用整数规划(IP)来建模 线性整数规划(LIP) 非线性整数规划(NIP) 纯整数规划(PIP) 混合整数规划(MIP) 特例：0-1规划 3.1.1 整数规划问题的几种描述形式 线性规划（LP：Linear Programming）问题的标准形式 纯整数线性规划(PILP，以后简称整数规划（IP）)的标准形式 ，A是行满秩的，且 ，A是行满秩的，且 3.1.1 整数规划问题的几种描述形式 整数规划的一般形式 整数规划的规范形式 整数规划的上述三种形式是等价的：一种形式下的实例，可以简单地等价变化为另一种形式下的实例. 3.2.2 整数规划问题的求解难度 整数规划问题是NP困难的. 为什么不先求解相应的线性规划问题（一般称为整数规划问题的线性规划松弛问题，或简称LP-Relaxation），然后将得到的解四舍五入到最接近的整数？ IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点.但LP松弛的最优解为C(3.5,2.5) 目标函数下降方向 x1 x2 C A B IP的LP松弛的最优解什么时候一定是整数解呢？ 假设在（3.1）式所示的线性规划问题中等式约束个数等于决策变量个数(m=n), 则此时的等式约束构成一个线性方程组Ax=b. 如果方阵A为整数矩阵且b为整数向量, 则det(A)和det(Aj)都是整数. 当然，解x未必是整数向量. 如果det(A) = 1或-1, 则解x一定是整数向量. 3.2全么模阵 3.2全么模阵 证明 （1）=（2）： （2）=（3）：设B为任一基矩阵，如果其逆矩阵不是整数矩阵，任取整数向量y 使得 ，这里ei表示第i个分量为1其余分量为0的“单位向量”. 令 ，则b为整数向量，且向量 为D（b）的一个极点的基向量，因此是整数向量. 定理3.1 设在（3.1）式所示的线性规划问题中A为整数矩阵，且A 满行秩，则下面三个条件等价： （1）对每个基矩阵B，其行列式det（B）=1或-1. （2）对任何整数向量b，其可行域 的每个极点都是整数向量. （3）对每个基矩阵B，其逆矩阵也是整数矩阵. 因此 为整数向量，即 是整数矩阵. (3)=(1)：设B为任一基矩阵，由于 ，又知B 和 都是整数矩阵，所以det（B）=1或-1. - Hoffman-Kruskal定理（1956） 3.2全么模阵 定义3.1 如果一个矩阵A的任何子方阵的行列式的值都等于0，1或-1，则称A是全么模的（TU：Totally Unimodular，又译为全单位模的），或称A是全么模矩阵. 定理3.2 （全么模矩阵的性质）下列命题等价： A是全么模矩阵. -A是全么模矩阵. AT是全么模矩阵. （A，A）是全么模矩阵. （A，I） ，（A，0）是全么模矩阵. – 定义 全么模矩阵的元素只能取0，1和-1. A为全么模矩阵时的整数规划问题实际上等价于对应的LP松弛问题（单纯形算法）. 定理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为方阵且满足条件（