运筹学：第四章 整数规划

第四章第四章 整数规划整数规划 整数规划的难度远大于一般线性规划整数规划的难度远大于一般线性规划管理与人文学院管理与人文学院 1999，424.1 整数规划简介整数规划简介 要求所有要求所有 xj 的解为整数，称为纯整数规划的解为整数，称为纯整数规划 要求部分要求部分 xj 的解为整数，称为混合整数规划的解为整数，称为混合整数规划 对应没有整数解要求的线性规划称之为松弛问题对应没有整数解要求的线性规划称之为松弛问题 整数规划的解是可数个的，最优解不一定发生在极点整数规划的解是可数个的，最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解njxmibxatsxcxfjnjijijnjjj,2,1,0,2,1,),(.)(max(min)11且为整数34.2 整数规划的分枝定界法整数规划的分枝定界法 4.2.1 思路与解题步骤思路与解题步骤 只解松弛问题只解松弛问题1、在全部可行性域上解松弛问题、在全部可行性域上解松弛问题 若松弛问题最优解为整数解，则其也是整数规划的若松弛问题最优解为整数解，则其也是整数规划的最优解最优解2、分枝过程分枝过程 若松弛问题最优解中某个若松弛问题最优解中某个 xk=bk 不是整数，令不是整数，令 bk 为为 bk 的整数部分的整数部分 构造两个新的约束条件构造两个新的约束条件 xk bk 和和 xk bk +1，分，分别加于原松弛问题，形成两个新的整数规划别加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题、求解分枝的松弛问题 定界过程定界过程 设两个分枝的松弛问题分别为问题设两个分枝的松弛问题分别为问题 1 和问题和问题 2，它，它们的最优解有如下情况们的最优解有如下情况 4表表4.2.1 分枝问题解可能出现的情况分枝问题解可能出现的情况序号序号问题问题 1 1问题问题 2 2说说 明明1无可行解无可行解无可行解无可行解整数规划无可行解整数规划无可行解2无可行解无可行解整数解整数解此整数解即最优解此整数解即最优解3无可行解无可行解非整数解非整数解对问题对问题 2 继续分枝继续分枝4整数解整数解整数解整数解较优的一个为最优解较优的一个为最优解5整数解，目标函整数解，目标函数优于问题数优于问题 2非整数解非整数解问题问题 1 的解即最优解的解即最优解6整数解整数解非整数解，目标非整数解，目标函数优于问题函数优于问题 1问题问题 1 1 停止分枝停止分枝(剪剪枝枝)，其整数解为界，其整数解为界，对问题对问题 2 继续分枝继续分枝情况情况 2,4,5 找到最优解找到最优解情况情况 3 在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6 问题问题 1 的整数解作为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题 2 的后的后续分枝所得到的解进行比较，结论如情况续分枝所得到的解进行比较，结论如情况 4 或或 55 4.2.2 分枝定界法举例分枝定界法举例 例例4.1.1 且为整数且为整数 0,7 2134246)(max21212121xxxxxxxxxf解解：松弛问题的最优解为：松弛问题的最优解为 x1=2.5,x2=2,OBJ=23 由由 x1=2.5 得到两个分枝如下：得到两个分枝如下：且为整数且为整数问题问题 0,2 7 21342I46)(max211212121xxxxxxxxxxf且为整数且为整数问题问题 0,3 7 21342II46)(max211212121xxxxxxxxxxf6 表表4.2.3 分枝问题的松弛解分枝问题的松弛解问题问题 I问题问题 IIx123x29/41f(x)2122问题问题II的解即原整数问题的最优解的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同时可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如只有少数特殊问题有好的算法，如任务分配问题任务分配问题、匹配问题匹配问题74.6 任务分配问题任务分配问题例例4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表完成每项任务的工时耗费如表4.6.1，问如何分配任务使完，问如何分配任务使完成四项任务的总工时耗费最少？成四项任务的总工时耗费最少？1,0,2,1 1,2,1 1)(min1111ijmiijmjijmimjijijxmjxmixxaxf任务任务 工时工时ABCD人员人员人员人员甲甲109781乙乙58771丙丙54651丁丁23451任务任务11118 任务分配问题的数学模型任务分配问题的数学模型模型中：模型中：xij 为第为第 i 个工人分配去做第个工人分配去做第 j 项任务；项任务；aij 为第为第 i 个工人为完成第个工人为完成第 j 项任务时的工时消耗；项任务时的工时消耗；aijm m 称为称为效率矩阵效率矩阵mjijijixij,2,1,01项任务项任务个工人未分配去做第个工人未分配去做第当第当第项任务项任务个工人分配去做第个工人分配去做第当第当第 运输问题是任务分配问题的松弛问题运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划，而且是任务分配问题不但是整数规划，而且是0 1规划规划 任务分配问题有任务分配问题有2m个约束条件，但有且只有个约束条件，但有且只有m个非零解个非零解，是自然，是自然高度退化高度退化的的 任务分配是任务分配是两部图两部图的的匹配问题匹配问题，有著名的，有著名的匈牙利算法匈牙利算法下面介绍一种适合手算的算法下面介绍一种适合手算的算法(出自清华教科书出自清华教科书)9 4.6.1 清华算法清华算法定理定理 1 如果从效率矩阵如果从效率矩阵aijm m中每行元素分别减去一个常数中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数从每列元素分别减去一个常数 vj，所得新的效率矩阵所得新的效率矩阵bijm m的任务分配问题的最优解等价于原问题的最优解。的任务分配问题的最优解等价于原问题的最优解。证明：略证明：略定理定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。元素的最多个数。证明：略证明：略 清华算法的清华算法的基本思路基本思路：根据根据定理定理 1 变换效率矩阵，使矩阵中有足够多的零。若变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在矩阵中存在 m 个不同行不同列的零，就找到了最优解个不同行不同列的零，就找到了最优解 若覆盖变换后的效率矩阵零元素的直线少于若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚条，就尚未找到最优解，设法进一步变换矩阵，增加新的零未找到最优解，设法进一步变换矩阵，增加新的零10 清华算法的步骤：例清华算法的步骤：例4.6.1第一步第一步：变换效率矩阵，使每行每列至少有一个零：变换效率矩阵，使每行每列至少有一个零 行变换行变换：找出每行最小元素，从该行各元素中减去之：找出每行最小元素，从该行各元素中减去之 列变换列变换：找出每列最小元素，从该列各元素中减去之：找出每列最小元素，从该列各元素中减去之2210020112300023321012012230)1(023543)2(56)4(5778)5(8)7(910换变列换变行第二步第二步：检查覆盖所有零元素的直线是否为：检查覆盖所有零元素的直线是否为m条条划线规则划线规则1、逐行检查、逐行检查，若该行只有一个未标记的零，对其加，若该行只有一个未标记的零，对其加()标记，将标记，将()标记元素同行同列上其它的零打上标记元素同行同列上其它的零打上*标记。若该行有二个以上标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；未标记的零，暂不标记，转下一行检查，直到所有行检查完；11 清华算法的步骤：例清华算法的步骤：例4.6.12、逐列检查、逐列检查，若该列只有一个未标记的零，对其加，若该列只有一个未标记的零，对其加()标记，将标记，将()标标记元素同行同列上其它的零打上记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；零，暂不标记，转下一列检查，直到所有列检查完；221*0*02)0(1123)0(*0)0(23221*00201123)0(0023查检列逐查检行逐3、重复、重复1、2后，可能出现三种情况：后，可能出现三种情况：a.每行都有一个每行都有一个(0)，显然已找到最优解，令对应，显然已找到最优解，令对应(0)位置的位置的 xij=1；b.仍有零元素未标记，此时，一定存在某些行和列同时有多个零，仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为称为僵局状态僵局状态，因为无法采用，因为无法采用 1、2 中的方法继续标记。中的方法继续标记。4、打破僵局打破僵局。令未标记零对应的同行同列上其它未标记零的个数为。令未标记零对应的同行同列上其它未标记零的个数为该零的该零的指数指数，选，选指数最小指数最小的先标记的先标记()；采用这种方法直至所有零都；采用这种方法直至所有零都被标记，或出现被标记，或出现 情况情况 a，或，或 情况情况 c。12 清华算法的步骤：例清华算法的步骤：例4.6.1c.所有零都已标记所有零都已标记，但标有，但标有()的零的个数少于的零的个数少于m；开始开始划线过程划线过程：对没有标记对没有标记()的行打的行打 对打对打 行上所有其它零元素对应的列打行上所有其它零元素对应的列打 再对打再对打 列上有列上有()标记的零元素对应的行打标记的零元素对应的行打 重复重复 ，直至无法继续，直至无法继续 对没有打对没有打 的行划的行划横线横线，对所有，对所有打打 的列划的列划垂线垂线 221*0*02)0(1123)0(*0)0(23 划线后会出现两种情况：划线后会出现两种情况：(1)标记标记()的零少于的零少于m个，但划有个，但划有 m条直线，说明矩阵中已存在条直线，说明矩阵中已存在 m 个不个不同行不同列的零，但打破僵局时选同行不同列的零，但打破僵局时选择不合理，没能找到。回到择不合理，没能找到。回到 b 重新重新标记；标记；(2)少于少于m条直线，到条直线，到第三步第三步；13 清华算法的步骤：例清华算法的步骤：例4.6.1第三步：第三步：进一步变换进一步变换；在未划线的元素中找在未划线的元素中找最小者最小者，设为，设为 对未被直线覆盖的各元素减去对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用以上步骤实际上仍是利用 定理定理 1221*0*02)0(1123)0(*0)0(2311000202012000241 第四步：第四步：抹除所有标记，回到抹除所有标记，回到第二步第二步，重新标记，重新标记；14解优最列逐行逐记标11)0(*0)0(2*02*012)0(*0)0(24 清华算法的步骤：例清华算法的步骤：例4.6.111000202012000241 答：最优分配方案为答：最优分配方案为 x13=x21=x34=x42=1，其余为，其余为0，即甲即甲C，乙，乙A，丙，丙D，丁，丁B，OBJ=20110002020120*0)0(24记记标标列列110*00202*012)0(*0)0(24局局僵僵破破打打221*0*02)0(1123)0(*0)0(23156 0 2 0 5 0 4 0 0 3 0 1 0 2 0 0 局局僵僵破破打打 4.6.2 关于清华算法的适用条件关于清华算法的适用条件 要求所有要求所有aij 0 若某些若某些 aij 0，则利用定理，则利用定理 1 进行变换，使所有进行变换，使所有 bij 0 目标函数为目标函数为min型型 对于对于max型目标函数，将效率矩阵中所有型目标函数，将效率矩阵中所有 aij 反号，则等反号，则等效于求效于求min型问题；再利用定理型问题；再利用定理 1 进行变换，使所有进行变换，使所有 bij 0，则可采用清华算法，则可采用清华算法 打破僵局时选择不当的结果：打破僵局时选择不当的结果：结果仅出现结果仅出现 3 个标记个标记()，但却划出，但却划出 4 条线，条线，说明什么？！说明什么？！6 0 2 *0 5 0 4 *0 0 3 0 1 *0 2 *0 )0(局局僵僵破破打打6 *0 2 *0 5 )0(4 *0 0 3 0 1 *0 2 *0 )0(局局僵僵破破打打6 *0 2 *0 5 )0(4 *0 *0 3 )0(1 *0 2 *0 )0(局局僵僵破破打打16线性规划有关的英文词汇线性规划有关的英文词汇Operational/operations research 运筹学运筹学Linear programming 线性规划线性规划 Feasible domain 可行域可行域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 匈牙利算法匈牙利算法