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