CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第四章整数规划 整数规划的难度远大于一般线性规划
第四章 整数规划 整数规划的难度远大于一般线性规划 ©管理与人文学院 忻展红 1999，4
41整数规划简介 要求所有x的解为整数,称为纯整数规划 要求部分x的解为整数,称为混合整数规划 对应没有整数解要求的线性规划称之为松弛问题 ·整数规划的解是可数个的,最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解 max(mm)f(x)=∑cx ∑a1x1≤(=,2)b st J= x1≥0且为整数,j=1,2,…,n
2 4.1 整数规划简介 • 要求所有 xj 的解为整数，称为纯整数规划 • 要求部分 xj 的解为整数，称为混合整数规划 • 对应没有整数解要求的线性规划称之为松弛问题 • 整数规划的解是可数个的，最优解不一定发生在极点 • 整数规划的最优解不会优于其松弛问题的最优解 = = = = = = x j n a x b i m s t f x c x j n j i j j i n j j j 0 , 1,2, , ( , ) , 1,2, , . . max(min) ( ) 1 1 且为整数
42整数规划的分枝定界法 42.1思路与解题步骤 只解松弛问题 1、在全部可行性城上解松弛问题 若松弛问题最优解为整数解,则其也是整数规划的 最优解 分枝过程 若松弛问题最优解中某个x=b不是整数,令Lb」 为b的整数部分 构造两个新的约束条件xsLb」和xk≥LbkH+1,分 别加于原松弛问题,形成两个新的整数规划 3、求解分枝的松弛问题一定界过程 设两个分枝的松弛问题分别为问题1和问题2,它 们的最优解有如下情况
3 4.2 整数规划的分枝定界法 4.2.1 思路与解题步骤 • 只解松弛问题 1、在全部可行性域上解松弛问题 – 若松弛问题最优解为整数解，则其也是整数规划的 最优解 2、分枝过程 – 若松弛问题最优解中某个 xk=bk 不是整数，令 bk 为 bk 的整数部分 – 构造两个新的约束条件 xk bk 和 xk bk +1，分 别加于原松弛问题，形成两个新的整数规划 3、求解分枝的松弛问题 — 定界过程 – 设两个分枝的松弛问题分别为问题 1 和问题 2 ，它 们的最优解有如下情况
表421分枝问题解可能出现的情况 序号 问题1 问题2 说明 无可行解 无可行解 整数规划无可行解 234 无可行解 整数解 此整数解即最优解 无可行解非整数解对问题2继续分枝 整数解 整数解 较优的一个为最优解 5整数解,目标函非整数解问题1的解即最优解 教优于问题2 整数解非整数解,目标问题1停止分枝(剪 函数优于问题1枝),其整数解为界, 对问题2继续分枝 情况2,4,5找到最优解 情况3在缩减的域上继续分枝定界法 情况6问题1的整数解作为界被保留,用于以后与问题2的后 续分枝所得到的解进行比较,结论如情况4或5
4 表4.2.1 分枝问题解可能出现的情况 序 号 问 题 1 问 题 2 说 明 1 无可行解 无可行解 整数规划无可行解 2 无可行解 整数解 此整数解即最优解 3 无可行解 非整数解 对问题 2 继续分枝 4 整数解 整数解 较优的一个为最优解 5 整数解，目标函 数优于问题 2 非整数解 问 题 1 的解即最优解 6 整数解 非整数解，目标 函数优于问题 1 问 题 1 停 止 分 枝 (剪 枝)，其整数解为界， 对问题 2 继续分枝 情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后 续分枝所得到的解进行比较，结论如情况 4 或 5
422分枝定界法举例 例411maxf(x)=6x1+4x2 2x1+4x2≤13 2x1+x2≤7 x1,x2≥0且为整数 解:松弛问题的最优解为x1=2.5,x2=2,OBJ=23 由x1=25得到两个分枝如下: max f(x)=6x+4x2 maxf(x)=6x+4x 2x1+4x,≤13 2x1+4x2≤13 2x1+x2≤7 2x1+x,≤7 问题I 问题I ≥3 x,x2≥0且为整数 x,x2≥0且为整数
5 4.2.2 分枝定界法举例 例4.1.1 + + = + , 0 且为整数 2 7 2 4 13 max ( ) 6 4 1 2 1 2 1 2 1 2 x x x x x x f x x x 解：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23 由 x1=2.5 得到两个分枝如下： + + = + 且为整数 问题 , 0 2 2 7 2 4 13 I max ( ) 6 4 1 2 1 1 2 1 2 1 2 x x x x x x x f x x x + + = + 且为整数 问题 , 0 3 2 7 2 4 13 II max ( ) 6 4 1 2 1 1 2 1 2 1 2 x x x x x x x f x x x
表423分枝问题的松弛解 问题I 问题I 2 3 9/4 21 问题Ⅲ的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况,则需要两边同时 继续分枝,直到有整数解出现,就可以进行定界过程 当存在很多变量有整数约束时,分枝即广又深,在最坏情 况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题,NP- complete 只有少数特殊问题有好的算法,如任务分配问题、匹配问题
6 表4.2.3 分枝问题的松弛解 问 题 I 问 题 I I x1 2 3 x2 9/4 1 f(x) 2 1 2 2 问题II的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同时 继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情 况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，NP-complete， 只有少数特殊问题有好的算法，如任务分配问题、匹配问题
46任务分配问题 例46.1有四个熟练工人,他们都是多面手,有四项任务要他 们完成。若规定每人必须完成且只完成一项任务,而每人 完成每项任务的工时耗费如表46.1,问如何分配任务使完 成四项任务的总工时耗费最少? 任务 工时、ABCD人员 mif(x)=∑∑anxn 人员 1i=1,2 甲乙丙丁 552 9843—1 77641 87551 ∑x=1j=1,2,…,m 0.1 任务
7 4.6 任务分配问题 例4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他 们完成。若规定每人必须完成且只完成一项任务，而每人 完成每项任务的工时耗费如表4.6.1，问如何分配任务使完 成四项任务的总工时耗费最少？ = = = = = = = = = = 0,1 1 1,2, , 1 1,2, , min ( ) 1 1 1 1 i j m i i j m j i j m i m j i j i j x x j m x i m f x a x 任 务 工 时 A B C D 人 员 人 员 甲 1 0 9 7 8 1 乙 5 8 7 7 1 丙 5 4 6 5 1 丁 2 3 4 5 1 任 务 1 1 1 1
任务分配问题的数学模型 模型中:x为第i个工人分配去做第j项任务 a;为第i个工人为完成第j项任务时的工时消耗 {at}mxm称为效率矩阵 当第许个工人分配去做第项任务 xn=0当第个工人未分配去做第项任务 运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划,而且是0-1规划 任务分配问题有2m个约束条件,但有且只有m个非零解 是自然高度退化的 任务分配是两部图的匹配问题,有著名的匈牙利算法 下面介绍一种适合手算的算法出自清华教科书)
8 任务分配问题的数学模型 模型中：xij 为第 i 个工人分配去做第 j 项任务； aij 为第 i 个工人为完成第 j 项任务时的工时消耗； {aij}mm称为效率矩阵 = = i j m i j i j xi j , 1,2, , 0 1 当第 个工人未分配去做第 项任务 当第 个工人分配去做第 项任务 • 运输问题是任务分配问题的松弛问题 • 任务分配问题不但是整数规划，而且是0−1规划 • 任务分配问题有2m个约束条件，但有且只有m个非零解， 是自然高度退化的 • 任务分配是两部图的匹配问题，有著名的匈牙利算法 下面介绍一种适合手算的算法(出自清华教科书)
46.1清华算法 定理1如果从效率矩阵{umm中每行元素分别减去一个常数n;, 从每列元素分别减去一个常数v,所得新的效率矩阵bmm 的任务分配问题的最优解等价于原问题的最优解。 证明:略 定理2若方阵中一部分元素为零,一部分元素非零,则覆盖方 阵内所有零元素的最少直线数等于位于不同行、不同列的零 元素的最多个数 证明:略 清华算法的基本思路: ·根据定理1变换效率矩阵,使矩阵中有足够多的零。若 矩阵中存在m个不同行不同列的零,就找到了最优解 若覆盖变换后的效率矩阵零元素的直线少于m条,就尚 未找到最优解,设法进一步变换矩阵,增加新的零
9 4.6.1 清华算法 定理 1 如果从效率矩阵{aij}mm中每行元素分别减去一个常数 ui， 从每列元素分别减去一个常数 vj ，所得新的效率矩阵{bij}mm 的任务分配问题的最优解等价于原问题的最优解。 证明：略 定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方 阵内所有零元素的最少直线数等于位于不同行、不同列的零 元素的最多个数。 证明：略 清华算法的基本思路： • 根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若 矩阵中存在 m 个不同行不同列的零，就找到了最优解 • 若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚 未找到最优解，设法进一步变换矩阵，增加新的零
清华算法的步骤:例46.1 第一步:变换效率矩阵,使每行每列至少有一个零 行变换:找出毎行最小元素,从该行各元素中减去之 列变换:找出每列最小元素,从该列各元素中减去之 109(7)8行(320(1)列(3200 (5)877换0322换0321 5(4)65 021 1020 2)345)(0123 0122 第二步:检查覆盖所有零元素的直线是否为m条 划线规则 逐行检查,若该行只有一个未标记的零,对其加标记,将 标记元素同行同列上其它的零打上标记。若该行有二个以上 未标记的零,暂不标记,转下一行检查,直到所有行检查完;
10 清华算法的步骤：例4.6.1 第一步：变换效率矩阵，使每行每列至少有一个零 – 行变换：找出每行最小元素，从该行各元素中减去之 – 列变换：找出每列最小元素，从该列各元素中减去之 0 1 2 2 1 0 2 0 0 3 2 1 3 2 0 0 0 1 2 3 1 0 2 1 0 3 2 2 3 2 0 (1) (2) 3 4 5 5 (4) 6 5 (5) 8 7 7 10 9 (7) 8 换 变 列 换 变 行 第二步：检查覆盖所有零元素的直线是否为m条 划线规则 1、逐行检查，若该行只有一个未标记的零，对其加( )标记，将 ( )标记元素同行同列上其它的零打上*标记。若该行有二个以上 未标记的零，暂不标记，转下一行检查，直到所有行检查完；