《4.第四章整数规划》由会员分享，可在线阅读，更多相关《4.第四章整数规划（16页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 整数规划整数规划 整数规划的难度远大于一般线性规划整数规划的难度远大于一般线性规划管理与人文学院管理与人文学院 忻展红忻展红 1999，44.1 整数规划简介整数规划简介要求所有要求所有 xj 的解为整数，称为纯整数规划的解为整数，称为纯整数规划要求部分要求部分 xj 的解为整数，称为混合整数规划的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解
2、24.2 整数规划的分枝定界法整数规划的分枝定界法 4.2.1 思路与解题步骤思路与解题步骤只解松弛问题只解松弛问题1、在全部可行性域上解松弛问题、在全部可行性域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的若松弛问题最优解为整数解，则其也是整数规划的最优解最优解2、分枝过程分枝过程若松弛问题最优解中某个若松弛问题最优解中某个 xk=bk 不是整数不是整数，令令 bk 为为 bk 的整数部分的整数部分构造两个新的约束条件构造两个新的约束条件 xk bk 和和 xk bk +1，分分别加于原松弛问题，形成两个新的整数规划别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题、求解
3、分枝的松弛问题 定界过程定界过程设两个分枝的松弛问题分别为问题设两个分枝的松弛问题分别为问题 1 和问题和问题 2 ，它，它们的最优解有如下情况们的最优解有如下情况 3表表4.2.1 分枝问题解可能出现的情况分枝问题解可能出现的情况情况情况 2, 4, 5 找到最优解找到最优解情况情况 3 在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6 问题问题 1 的整数解作为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题 2 的后的后续分枝所得到的解进行比较，结论如情况续分枝所得到的解进行比较，结论如情况 4 或或 54 4.2.2 分枝定界法举例分枝定界法举例 例例4.1
4、.1 解解：松弛问题的最优解为：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23 由由 x1=2.5 得到得到两个分枝如下：两个分枝如下：5 表表4.2.3 分枝问题的松弛解分枝问题的松弛解问题问题II的解即原整数问题的最优解的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同时可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解况下相当于组
5、合所有可能的整数解 一般整数规划问题属于一类未解决的难题，一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如只有少数特殊问题有好的算法，如任务分配问题任务分配问题、匹配问题匹配问题64.6 任务分配问题任务分配问题例例4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表完成每项任务的工时耗费如表4.6.1，问如何分配任务使完，问如何分配任务使完成四项任务的总工时耗费最少？成四项
6、任务的总工时耗费最少？7 任务分配问题的数学模型任务分配问题的数学模型模型中：模型中：xij 为第为第 i 个工人分配去做第个工人分配去做第 j 项任务；项任务； aij 为第为第 i 个工人为完成第个工人为完成第 j 项任务时的工时消耗；项任务时的工时消耗； aijm m 称为称为效率矩阵效率矩阵 运输问题是任务分配问题的松弛问题运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划，而且是任务分配问题不但是整数规划，而且是0 1规划规划 任务分配问题有任务分配问题有2m个约束条件，但有且只有个约束条件，但有且只有m个非零解，个非零解，是自然是自然高度退化高度退化的的任务分配是任务分配
7、是两部图两部图的的匹配问题匹配问题，有著名的，有著名的匈牙利算法匈牙利算法下面介绍一种适合手算的算法下面介绍一种适合手算的算法(出自清华教科书出自清华教科书)8 4.6.1 清华算法清华算法定理定理 1 如果从效率矩阵如果从效率矩阵aijm m中每行元素分别减去一个常数中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数从每列元素分别减去一个常数 vj ，所得新的效率矩阵所得新的效率矩阵bijm m的任务分配问题的最优解等价于原问题的最优解。的任务分配问题的最优解等价于原问题的最优解。 证明：略证明：略定理定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方若方阵中一部分元素为零
8、，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。元素的最多个数。 证明：略证明：略 清华算法的清华算法的基本思路基本思路：根据根据定理定理 1 变换效率矩阵，使矩阵中有足够多的零。若变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在矩阵中存在 m 个不同行不同列的零，就找到了最优解个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚条，就尚未找到最优解，设法进一步变换矩阵，增加新的零未找到最优解，设法进一步变换矩阵，增加新的零9
9、清华算法的步骤：例清华算法的步骤：例4.6.1第一步第一步：变换效率矩阵，使每行每列至少有一个零：变换效率矩阵，使每行每列至少有一个零行变换行变换：找出每行最小元素，从该行各元素中减去之：找出每行最小元素，从该行各元素中减去之列变换列变换：找出每列最小元素，从该列各元素中减去之：找出每列最小元素，从该列各元素中减去之第二步第二步：检查覆盖所有零元素的直线是否为：检查覆盖所有零元素的直线是否为m条条划线规则划线规则1、逐行检查、逐行检查，若该行只有一个未标记的零，对其加，若该行只有一个未标记的零，对其加( )标记，将标记，将 ( )标记元素同行同列上其它的零打上标记元素同行同列上其它的零打上*标
10、记。若该行有二个以上标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；未标记的零，暂不标记，转下一行检查，直到所有行检查完；10 清华算法的步骤：例清华算法的步骤：例4.6.12、逐列检查、逐列检查，若该列只有一个未标记的零，对其加，若该列只有一个未标记的零，对其加( )标记，将标记，将( )标标记元素同行同列上其它的零打上记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；零，暂不标记，转下一列检查，直到所有列检查完；3、重复、重复1、2后，可能出现三种情况：后，可能出现三种情况：a
11、. 每行都有一个每行都有一个 (0)，显然已找到最优解，令对应，显然已找到最优解，令对应(0)位置的位置的 xij=1；b. 仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为为僵局状态僵局状态，因为无法采用，因为无法采用 1、 2 中的方法继续标记。中的方法继续标记。4、打破僵局打破僵局。令未标记零对应的同行同列上其它未标记零的个数为。令未标记零对应的同行同列上其它未标记零的个数为该零的该零的指数指数，选，选指数最小指数最小的先标记的先标记 ( )；采用这种方法直至所有零都；采用这种方法直至所有零都被标记，或出现被标记，或出
12、现 情况情况 a，或或 情况情况 c 。11 清华算法的步骤：例清华算法的步骤：例4.6.1c. 所有零都已标记所有零都已标记，但标有，但标有( )的零的个数少于的零的个数少于m； 开始开始划线过程划线过程： 对没有标记对没有标记 ( ) 的行打的行打 对打对打 行上所有其它零元素对应的列打行上所有其它零元素对应的列打 再对打再对打 列上有列上有 ( ) 标记的零元素对应的行打标记的零元素对应的行打 重复重复 ，直至无法继续，直至无法继续 对没有打对没有打 的行划的行划横线横线，对所有，对所有打打 的列划的列划垂线垂线 划线后会出现两种情况：划线后会出现两种情况：(1) 标记标记( )的零少于
13、的零少于m个，但划有个，但划有 m条直线，说明矩阵中已存在条直线，说明矩阵中已存在 m 个个不同行不同列的零，但打破僵局时不同行不同列的零，但打破僵局时选择不合理，没能找到。回到选择不合理，没能找到。回到 b 重重新标记；新标记；(2) 少于少于m条直线，到条直线，到第三步第三步；12 清华算法的步骤：例清华算法的步骤：例4.6.1第三步：第三步：进一步变换进一步变换； 在未划线的元素中找在未划线的元素中找最小者最小者，设为，设为 对未被直线覆盖的各元素减去对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变只有一条直线覆盖的
14、元素保持不变以上步骤实际上仍是利用以上步骤实际上仍是利用 定理定理 1第四步：第四步：抹除所有标记，回到抹除所有标记，回到第二步第二步，重新标记，重新标记；13 清华算法的步骤：例清华算法的步骤：例4.6.1答：最优分配方案为答：最优分配方案为 x13= x21= x34 = x42 =1，其余为其余为0， 即甲即甲C，乙乙A，丙丙D，丁丁B，OBJ=2014 4.6.2 关于清华算法的适用条件关于清华算法的适用条件要求所有要求所有aij 0若某些若某些 aij 0 ，则利用定理则利用定理 1 进行变换，使所有进行变换，使所有 bij 0目标函数为目标函数为min型型对于对于max型目标函数，
15、将效率矩阵中所有型目标函数，将效率矩阵中所有 aij 反号，则等反号，则等效于求效于求min型问题；再利用定理型问题；再利用定理 1 进行变换，使所有进行变换，使所有 bij 0，则可采用清华算法则可采用清华算法 打破僵局时选择不当的结果：打破僵局时选择不当的结果： 结果仅出现结果仅出现 3 个标记个标记( )，但却划出，但却划出 4 条线，条线， 说明什么？！说明什么？！15线性规划有关的英文词汇线性规划有关的英文词汇Operational/operations research 运筹学运筹学Linear programming 线性规划线性规划 Feasible domain 可行域可行域
16、Convex set 凸集凸集 Basic feasible solutions 基础可行解基础可行解Simplex algorithm 单纯型法单纯型法 Pivot 主元主元 Pivoting 主元变换主元变换Revised, dual simplex algorithm 修正、对偶单纯型法修正、对偶单纯型法Relative cost 相对成本相对成本(机会成本机会成本) Shadow price 影子价格影子价格Slack, Surplus, Artificial variable 松弛，剩余，人工变量松弛，剩余，人工变量Unbounded, Infeasible, Degenerate solution 无界解无界解, 无可行解无可行解, 退化退化解解Duality 对偶性对偶性 Primal, dual problem 原问题，对偶问题原问题，对偶问题Complementary slackness 互补松弛互补松弛 Sensitivity analysis 灵敏度分析灵敏度分析Ttransportation problem 运输问题运输问题Assignment problem 任务分配任务分配(指派指派) 问题问题Bipartite matching 两部图匹配两部图匹配 Hungarian method 匈牙利算法匈牙利算法16
