网络优化-3-整数优化

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

网 络 优 化Network Optimization清华大学课号： 清华大学课号：70420133(研) (

整数规划(Integer Programming) 第3章 整数规划清华大学数学科学系 谢金星 办公室：理科楼2206# (电话：010-62787812)Email:jxie@http://www.77cn.com.cn http://www.77cn.com.cn/~jxie/courses/netopt1

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

整数规划问题的例子例(续例1.4) 指派问题 续例 ) 指派问题(Assignment Problem) 一家公司经理准备安排N名员工去完成 项任务 每人一项. 一家公司经理准备安排 名员工去完成N项任务，每人一项 由 名员工去完成 项任务， 于各员工的特点不同，不同的员工去完成同一项任务时所获得 于各员工的特点不同， 的回报是不同的. 如何分配工作方案可以使总回报最大？ 的回报是不同的 如何分配工作方案可以使总回报最大？

max ∑i =1 ∑ j =1 wij xijn n

线性整数规划(LIP) 线性整数规划(LIP)

s.t.

∑ ∑

x = 1, i =1 ijn

n

j = 1,2, L, n, i = 1,2,L , n,

非线性整数规划(NIP) 非线性整数规划(NIP) 纯整数规划(PIP) 纯整数规划(PIP) 混合整数规划(MIP) 混合整数规划(MIP) 特例： 特例：0-1规划2

xij = 1, j =1

xij ∈ {0,1}.

许多网络优化问题也可以用整数规划(IP)来建模 许多网络优化问题也可以用整数规划(IP)来建模 (IP)

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

3.1.1

整数规划问题的几种描述形式min c T x s.t. Ax = b (3.1)

线性规划(LP:Linear Programming)问题的标准形式 线性规划(LP: Programming)

x≥0 c, x ∈ R n , b ∈ R m , A ∈ R m×n ,A是行满秩的，且 m ≤ n, b ≥ 0 是行满秩的，纯整数线性规划(PILP,以后简称整数规划(IP))的标准形式 纯整数线性规划(PILP,以后简称整数规划(IP) (PILPmin c T x s.t. Ax = b x≥0 xi ∈ Zn 是行满秩的， c, x ∈ Z n , b ∈ Z m , A ∈ Z m×,A是行满秩的，且 m ≤ n, b ≥30

(3.2)

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

3.1.1

整数规划问题的几种描述形式min c T x s.t. aiT x = bi , i ∈ M aiT x ≥ bi , i ∈ M xj ∈Z +, j ∈ N xj ∈ Z, j ∈ N (3.3)

整数规划的一般形式

整数规划的规范形式

s.t.

min cT x Ax ≥ b x≥0 xi ∈ Z

(3.4)

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

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

3.2.2 整数规划问题的求解难度整数规划问题是NP困难的 整数规划问题是 困难的. 困难的 为什么不先求解相应的线性规划问题(一般称为整数规划问题 为什么不先求解相应的线性规划问题( 的线性规划松弛问题， 或简称LP-Relaxation) 的线性规划松弛问题 ， 或简称 -Relaxation ) , 然后将 得到的解四舍五入到最接近的整数？ 得到的解四舍五入到最接近的整数？

x2 C A目标函数下降方

向

B x1IP可行解对应于整点A(2,2)和B(1,1),而最优解为A IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点.但LP松弛的最 可行解对应于整点A(2,2) 而最优解为 LP松弛的最 优解为C(3.5,2.5) 优解为C(3.5,2.5)5

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

3.2全么模阵 3.2全么模阵IP的LP松弛的最优解什么时候一定是整数解呢？ 的 松弛的最优解什么时候一定是整数解呢 松弛的最优解什么时候一定是整数解呢？ 假设在( ) 假设在(3.1)式所示的线性规划问题中等式约束个数等于决策 变量个数(m=n), 则此时的等式约束构成一个线性方程组 则此时的等式约束构成一个线性方程组Ax=b. 变量个数

xj =

det( A j ) det( A)

,

j = 1,2,..., n.

如果方阵A为整数矩阵且 为整数向量 如果方阵 为整数矩阵且b为整数向量 则det(A)和det(Aj)都是整 为整数矩阵且 为整数向量, 和 都是整 当然， 未必是整数向量. 数. 当然，解x未必是整数向量 未必是整数向量 如果det(A) = 1或-1, 则解 一定是整数向量 一定是整数向量. 如果 或 则解x一定是整数向量

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

Hoffman-Kruskal定理 1956) 定理( 3.2全么模阵 - Hoffman-Kruskal定理(1956) 3.2全么模阵定理3.1 设在(3.1) 为整数矩阵， 满行秩， 定理3.1 设在(3.1)式所示的线性规划问题中A为整数矩阵，且A 满行秩， 则下面三个条件等价： 则下面三个条件等价： 其行列式det det( =1或 (1)对每个基矩阵B,其行列式det(B)=1或-1. ) (2)对任何整数向量b,其可行域 D(b) = {x | Ax = b, x ≥ 0} 的每个 ) 极点都是整数向量. 极点都是整数向量. 其逆矩阵也是整数矩阵. (3)对每个基矩阵B,其逆矩阵也是整数矩阵.( B 0 ) adj b =>( 证明 (1)=>(2): x B = ( B ) b = 0 det( B )0 1

(2)=>(3):设B为任一基矩阵，如果其逆矩阵不是整数矩阵，任 =>( ):设 为任一基矩阵，如果其逆矩阵不是整数矩阵， 这里e 个分量为1 取整数向量y 使得 z = y + B 1ei ≥ 0 ,这里 i表示第i个分量为1其余分量为 单位向量” 0的“单位向量”. 为整数向量， 令 b = Bz = B ( y + B 1ei ) = By + ei ,则b为整数向量，且向量 的一个极点的基向量，因此是整数向量 整数向量. z = B 1b ≥ 0 为D(b)的一个极点的基向量，因此是整数向量. 1 1 为整数向量， 是整数矩阵. 因此 B ei = z y 为整数向量，即 B 是整数矩阵.

(3)=>(1): 为任一基矩阵， (3)=>(1):设B为任一基矩阵，由于 B 1 B = I ,又知B 和 B 都是整数 7 矩阵，所以det det( =1或 矩阵，所以det(B)=1或-1.

1

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

3.2全么模阵 – 定义 3.2全么模阵定义3.1 如果一个矩阵A的任何子方阵的行列式的值都等于0, 定义3.1 的任何子方阵的行列式的值都等于0 是全么模的(TU: Unimodular, 1或-1,则称A是全么模的(TU:Totall

y Unimodular,又译为 全单位模的), ),或称 是全么模矩阵. 全单位模的),或称A是全么模矩阵. 全么模矩阵的元素只能取0,1和-1. 全么模矩阵的元素只能取0 定理3 全么模矩阵的性质)下列命题等价： 定理3.2 (全么模矩阵的性质)下列命题等价： 1) A是全么模矩阵. 是全么模矩阵.

2) -A是全么模矩阵. 是全么模矩阵.3) AT是全么模矩阵. 是全么模矩阵. 4) (A,A)是全么模矩阵. 是全么模矩阵. 是全么模矩阵. 5) (A,I) ,(A,0)是全么模矩阵. A为全么模矩阵时的整数规划问题实际上等价于对应的LP 松弛问题(单纯形算法).

清华大学的网络优化课件,衷心感谢老师的辛勤劳动。

3.2全么模阵 3.2全么模阵

- 充分条件

定理3.3 设A是由 ，1和-1组成的矩阵，如果下面两个条件同时成立， 是由0, 和 组成的矩阵 如果下面两个条件同时成立， 组成的矩阵， 定理 是由 为全么模矩阵. 则A为全么模矩阵 为全么模矩阵 的每一列至多含有两个非零元素. (1)A的每一列至多含有两个非零元素 ) 的每一列至多含有两个非零元素 的行可以分为A1, 两个集合 使得：如果A的一列中有 …… 此处隐藏：6723字，全部文档内容请下载后查看。喜欢就下载吧 ……