《整数线性规划》PPT课件.ppt

第1页,整数规划是数学规划的一个重要分支, 可分为: 纯整数规划(所有变量都限制为整数)、混合整数规划(一部分变量限制为整数)、0-1规划(所有变量都限制取0或1). 本章讨论纯整数线性规划(ILP)及解此规划的割平面法和分枝定界法；分配问题与匈牙利算法.,4.1 整数规划的特点及作用 4.2 分配问题与匈牙利算法 4.3 分枝定界法 4.4 割平面法,第4章 整数规划与分配问题,第2页,4.1 整数规划的特点及作用,4.1.1 整数规划的模型分类 纯整数规划模型 0-1整数规划模型 混合整数规划模型 4.1.2 实例 投资决策问题 背包问题 4.1.3 解整数线性规划的困难性 4.1.4 逻辑变量在建模中的作用,第3页,纯整数规划模型,0-1整数规划模型,混合整数规划模型,4.1.1 整数规划的模型分类,第4页,(1)投资组合问题,1.问题,某财团有B万元的资金, 经出其考察选中n个投资项目, 每个项目只能投资一个. 其中第j 个项目需投资金额为bj万元, 预计5年后获利cj万元, 问应如何选择项目使得5年后总收益最大？,变量 约束 目标,2.分析,3. 数学模型,4.1.2 实例,略,总金额不超过限制,总收益最大,第5页,1.背景,邮递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品,(2)背包问题,某人出国留学打点行李, 现有三个旅行包, 容积大小分别为1000毫升、1500毫升和2000毫升, 根据需要列出需带物品清单, 其中一些物品是必带物品共有7件, 其体积大小分别为400、300、150、250、450、760、190、(单位毫升). 尚有10件可带可不带物品, 如果不带将在目的地购买, 通过网络查询可以得知其在目的地的价格(单位美元). 这些物品的容量及价格分别见下表, 试给出一个合理的安排方案把物品放在三个旅行包里.,2.问题,第6页,3.问题分析,变量对每个物品要确定是否带同时要确定放在哪个包裹里，设变量xij为第i个物品是否放在第j个包裹中,约束,包裹容量限制,必带物品限制,选带物品限制,目标函数,未带物品购买费用最小,第7页,模 型,第8页,特征变量整数性要求 来源问题本身的要求; 引入的逻辑变量的需要 性质可行域是离散集合,4.1.3 解整数线性规划的困难性,与线性规划的关系：,整数规划,可行解是松弛问题的可行解,最优值大于等于松弛问题的最优值,松弛的线性规划问题,第9页,最优解不一定在顶点上达到. 最优解不一定是松弛问题最优解的邻近整数解. 整数可行解远多于松弛问题的顶点,枚举法不可取. 解ILP问题要远难于解松弛的LP问题. 若松弛的LP问题无解,则原ILP问题无解.反之,不一定成立. 如果松弛的LP问题无界呢? 可以证明原ILP问题也无界.,结论,第10页,4.1.4 逻辑变量在建模中的作用,1. m个约束条件中只有k个起作用,m个约束条件可表为,定义,又M为任意大的正数，则,第11页,2. 约束条件的右端项可能是r个值(b1,b2,br)中的某一个,定义,上述约束条件(*)可表示为,即,第12页,3. 两组条件中满足其中一组,定义,又M为任意大的正数，则问题可表述为,第13页,4. 用以表示含有固定费用的函数,第14页,4.2 分配问题与匈牙利算法,4.2.1 分配问题的数学模型 4.2.2 匈牙利算法,第15页,4.2.1 分配问题的数学模型,分配问题(指派问题),假定有m项任务分配给m个人去完成, 并指定每人完成其中一项, 每项只交给其中一个人去完成, 应如何分配使总的效率最高.,效率矩阵：,利用不同资源完成不同计划活动的效率通常用表格形式表示，表格中的数字组成效率矩阵.,分配问题的数学模型:,第i人完成一项任务,第j项任务由一人完成,第16页,4.2.2 匈牙利算法,运输问题,分配问题,表上作业法,匈牙利算法,求解,求解,求解,事实：,若效率矩阵的所有元素, 而其中存在一组位于不同行,其余的xij=0, 得到的就是问题的最优解,例,效率矩阵为,令,问题：,如何产生并寻找这组位于不同行不同列的零元素？,不同列的零元素，,则只要另对应于这些零元素位置的xij=1,其余的xij=0,第17页,匈牙利数学家克尼格(Konig),基础：,两个基本定理,定理1,如果从分配问题效率矩阵aij的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势), 从每一列分别减去(或加上)一个常数vj(被称为该列的位势), 得到一个新的效率矩阵bij, 若其中bij=aij-ui-vj , 则bij的最优解等价于aij的最优解,作用：,构造含有零元素的等价效率矩阵,定理2,若矩阵A的元素分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数.,作用：,判别效率矩阵中有多少个不同行不同列的零元素,第18页,匈牙利算法的步骤：,第一步：,找出效率矩阵每行的最小元素,并分别从每行中减去.,第二步：,再找出矩阵每列的最小元素,再分别从各列中减去.,第三步：,判定由前两步得到的效率矩阵中有多少个不同行不同列的零元素.,按照以下准则进行：,(1) 从第一行开始, 若该行只有一个零元素, 就对这个零元素打上( )号, 对打( )号零元素所在列画一条直线.,(2) 从第一列开始, 若该列只有一个零元素就对这个零元素打上( )号(同样不考虑以划去的零元素), 对打( )号零元素所在行画一条直线.,若该行没有零元素或有两个以上零元素(以划去的不计在内), 则转下一行, 依次进行到最后一行.,若该列没有零元素或有两个以上零元素, 则转下一列, 依次进行到最后一行.,(3) 重复(1)、(2)两个步骤, 可能出现三种情况:,第19页,2,3,1,效率矩阵每行(或每列)都有一个打( )号的零元素, 只要令对应,打( )号零元素的xij=1, 就找到了问题的最优解.,打( )号的零元素个数小于m, 但未被划去的零元素之间存在闭回路, 这时可顺着闭回路的走向, 对每个间隔的零元素打一( )号, 然后对所有打( )号的零元素, 或所在行, 或所在列画一条直线.,矩阵中所有零元素被划去或打上( )号, 但打( )号的零元素个数小于m.,第四步：,为设法使每一行都有一个打( )号的零元素，需要继续按定理1对矩阵进行变换：,(1) 从矩阵未被直线覆盖的数字中找出一个最小的数字k;,(2) 对矩阵的每行, 当该行有直线覆盖时令ui=0, 无直线覆盖的令ui=k,(3) 对矩阵的每列, 当该列有直线覆盖时令vj=-k, 无直线覆盖的令vj=0.,(4) 从原矩阵的每个元素aij中分别减去ui和vj ,得到一个新的矩阵.,第五步：,返回到第三步,反复进行,一直到矩阵的每一行都有一个打号的零元素为止,即找到了最优分配方案.,第20页,举例,有一份说明书，要分别译成英、日、德、俄四种文字，交甲乙丙丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间如表所示。应如何分配，使这四人分别完成 这四项任务总的时间最小。,效率矩阵,工作,人,第一步：,每行减去该行的最小元素,第二步：,min,在第一步的基础上,每列再减去该列的最小元素.,min,第21页,第三步：,判定不同行不同列的零元素的个数,(1) 从第一行开始, 若该行只有一个零元素, 就对这个零元素打上( )号, 对打( )号零元素所在列画一条直线.若该行没有零元素或有两个以上零元素(以划去的不计在内), 则转下一行, 依次进行到最后一行.,(2) 从第一列开始, 若该列只有一个零元素就对这个零元素打上( )号(同样不考虑以划去的零元素), 对打( )号零元素所在行画一条直线.若该列没有零元素或有两个以上零元素, 则转下一列, 依次进行到最后一列.,(3) 重复(1)、(2)两个步骤。可能有三种结果,( ),( ),( ),3,矩阵中所有零元素被划去或打上( )号, 但打( )号的零元素个数小于m.,第22页,第四步：,(1) 从矩阵未被直线覆盖的数字中找出一个最小的数字k;,(2) 对矩阵的每行, 当该行有直线覆盖时令ui=0, 无直线覆盖的令ui=k,(3) 对矩阵的每列, 当该列有直线覆盖时令vj=-k, 无直线覆盖的令vj=0.,(4) 从原矩阵的每个元素aij中分别减去ui和vj ,得到一个新的矩阵.,继续按定理1对矩阵进行变换：,( ),( ),( ),( ),( ),( ),( ),令对应于打( )号的零元素位置的xij=1，即得到了最优解。,第23页,说明：,1)第三步中的第二种结果,2,打( )号的零元素个数小于m, 但未被划去的零元素之间存在闭回路, 这时可顺着闭回路的走向, 对每个间隔的零元素打一( )号, 然后对所有打( )号的零元素, 或所在行, 或所在列画一条直线.,( ),( ),( ),( ),( ),( ),或,( ),( ),( ),( ),( ),( ),( ),( ),或,( ),第24页,例,( ),( ),( ),( ),( ),(1),(2),( ),( ),( ),( ),( ),( ),( ),( ),( ),( ),( ),( ),( ),( ),得到答案,( ),( ),( ),( ),第25页,说明：,1.分配问题中如果人数和任务数不相等时的处理方法.,(2) 人数任务数,(1) 人数任务数,仍规定每人完成一项工作, 每项工作只交给一个人去完成,增添两项假想的工作任务, 每个人完成这两项任务时间为零.,第26页,2.目标函数为 的处理方法.,min,min,第27页,4.3 分枝定界法,分枝定界法是一种隐枚举法，是一种“巧妙”地枚举整数规划问题的可行解的思想来设计算法的，其关键步骤是分枝和定界。,分枝定界法可用于解纯整数或混合的整数规划问题。本世纪六十年代初由Land Doig 和Dakin等人提出。由于这种方法灵活且便于用计算机求解，所以现在它是解整数规划的主要方法。,第28页,分枝定界法的思路和解题步骤：,第一步：,寻找替代问题并求解.,放宽或取消原问题的某些约束,若替代问题的最优解是原问题的可行解,则此解就是原问题的最优解.,寻找替代问题的方法：,替代问题的要求：,易求解; 包含原问题的解.,否则,此解的目标函数值就是最优解的上界(求极大)或下界值(求极小).,例,求下述整数规划的最优解,替代问题,L0的最优解(3.25, 2.5),不是原问题的可行解, 转第二步.,原问题,第29页,第二步：,分枝与定界,若子问题的最优解满足原问题的约束，则该解是原问题的可行解.,将替代问题分成若干子问题(分枝),子问题的要求：,易求解;各子问题解的集合包含原问题的解,否则,该解为所属分枝的边界解(求极大为上界)或(求极小为下界).,若所有子问题的最优解均非原问题的可行解，则取边界值最大(求极大)或最小(求极小)的子问题进一步细分求解,直到找到一个原问题的可行解为止.,若计算中同时出现两个以上的可行解，则取其中最大(求极大)或最小(求极小)的一个保留.,第30页,(3.25, 2.5), z=14.75,(3.5, 2), z=14.5,(2.5, 3), z=13.5,(3, 2), z=13,(4, 1), z=14,第31页,第三步：,剪枝,如果除保留下来的可行解外，其余分枝均被剪去，则该可行解就是原问题的最优解.,将各子问题边界值与保留的可行解的值进行比较，把边界值劣于可行解的分枝剪去.,否则,返回第二步，选取边界值最优的一个继续分枝.如果计算中又出现新的可行解时，则与原可行解比较，保留最优的，并重复上述步骤。,第32页,(3.25, 2.5), z=14.75,(3.5, 2), z=14.5,(2.5, 3), z=13.5,(3, 2), z=13,(4, 1), z=14,第33页,例,用分枝定界法求下述混合整数规划的最优解,解：,(3.25, 2.5), z=14.75,(3.5, 2), z=14.5,(2.5, 3), z=13.5,替代问题,第34页,4.4 Gomory割平面法,割平面法是求解整数规划的一个最早提出的方法, 1958年由高莫雷(Gomory )提出. 基本思想是在与整数规划相对应的线性规划中逐步增加线性约束条件(称为割平面), 使线性规划的可行域缩小, 同时保持整数规划的可行解集合不变; 然后来求解增加约束后的线性规划, 如果得到整数规划的最优解则停止; 如果没有找到整数最优解, 就再增加割平面, 一直到得到或证明无整数最优解为止.,第35页,割平面法的解题步骤：,第一步：,把问题中所有约束条件的系数均化为整数, 解该问题的松弛问题G0 .若得到的是整数解, 得到了原问题的最优解，否则转第二步.,构造Gomory约束.,第二步：,将Gomory约束加到中G0得到新的线性规划问题