系统工程---第四章 整数规划.ppt

一、 整数规划简介 整数规划是数学规划的一个重要分支，它研究的是一类要求其部分或全部变量取整数的最优化问题。 要求所有的解xj 为整数，称为纯整数规划 要求部分的xj 为整数，称为混合整数规划 要求xj 的取值只能是0和1 ，称为0-1型整数规划,第四章 整数规划,对应没有整数解要求的线性规划称之为松弛问题 整数规划的解是可数个的，最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解,整数规划问题A,其松弛问题B,二、整数规划的解法,分枝定界法是一种计算与分析判断相结合的求解整数规划问题的重要方法。它既能解决纯整数规划问题，又能解决混合整数规划问题。这种方法有很强的适应能力，是目前较为成功的求解整数规划问题的一种方法。,1.分枝定界法,基本思想：分枝定界法是通过有系统的“分枝”和“定界”步骤来寻求最优解的。它是先求解松弛问题，如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的方法把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界距离，最后取得整数规划的最优解。,分枝定界法的解题步骤：,Step1 求解松弛问题B， -若松弛问题B无解，则整数规划A也无解,则停止。 -若B有最优解，且符合问题A的整数条件，则B的最优解也是 A的最优解，则停止。 -若B有最优解，但不符合A的整数条件，记其目标函数值为f1。 Step2 确定A的最优目标函数值f*的上下界，其上界为f1，即 再用观察法找到A的一个整数可行解，求其目标函数值作为f*的下界，记为f，这时有 Step3 判断 是否等于 。如果 ，则A的最优解即为其目标函数值等于 的那个整数可行解。否则，进行Step4。,Step4 分枝，在B的最优解中任选一个不符合整数条件的变量xj=bj，以bj表示小于bj的最大整数。构造两个约束条件： xj bj 和 xj bj+1 将这两个约束条件分别加入问题B，得到B的两个分枝B1和B2。 Step5 求解分枝B1, B2。修改A的最优目标函数值的上下界。 在各分枝问题的最优解中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分枝中，找出目标函数值最大者作为新的下界，这就是定界过程。 Step6 比较与剪枝。各分枝的最优目标函数中若有小于 者，则剪掉这枝，即以后不再考虑了。若大于 ，且不符合整数条件，则重复Step4至Step6,直至 ，求出整数最优解为止。,各分枝问题的解可能出现的情况,情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4或5,例1,解：松弛问题B的最优解为 x1=2.5 , x2=2 , f =23,分枝定界法举例,问题A,松弛问题B,由 x1=2.5 得到两个分枝如下：,显然x1=1 , x2=1是问题A的可行解，其目标函数值为10,于是有 10f *23,求解两个分枝问题,问题B2的解即为原整数规划问题A的最优解,可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程 当有很多变量有整数约束时，分枝既广又深，在最坏情况下相当于组合所有可能的整数解,x12,x13,10f *23,22f *23,例2,解：松弛问题B的最优解为 x1=3.142 , x2=3.285 , f =288.5,分枝定界法举例,问题A,由 x2=3.285 得到两个分枝如下：,x1=1 , x2=1 显然是问题A的一个可行解, 其目标函数值为90 , 这时有,松弛问题B,求解各分枝问题,因f1 f2，故有,继续对问题B1和 B2进行分解，,因f1 f2，先分解B1为B3和 B4,求解各分枝问题,因f4 f3，故有,因f2=272.5280，所以再分解 B2已无必要，剪去该分枝。,故x1=4 ，x2=2 为原问题A的最优解，最优目标函数值为280。,x23,x14,x13,x24,2. 0-1规划的解法,枚举法,即检查变量取值为0或1的每一个组合，比较目标函数值的大小以求得最优解。,例3 求解0-1规划,解 （x1，x2，x3）共有23=8种不同的组合，各种组合下目标函数及各约束条件左端的值列于下表：, ,枚举法表,（x1，x2，x3）,约束条件,最优解为X*= （1，0，1）,隐枚举法,所谓隐枚举法就是只检查变量取值组合的一部分就能求得问题最优解的方法。其基本思路是：先找到一组可行解，增加一个过滤条件，然后改进过滤值，直至不能改进为止。, ,例3 求解0-1规划,解 用观察法找一个可行解（x1，x2，x3）= （1，0，0）， 其目标函数值为3。,于是增加过滤条件： 3x1-2x2+5x33 ,隐枚举法表,（x1，x2，x3）,约束条件,最优解为X*= （1，0，1）,3.指派问题,（1）指派问题的数学模型: 引入0-1变量xij (i,j=1,2,n),模型中：cij 为第 i 个工人完成第 j 项任务的时间(成本、费用)； cijnn 称为效率矩阵,指派问题不但是整数规划，而且是01规划 指派问题也是运输问题的特例，即m=n , ai=bj=1。 指派问题有2n个约束条件，但有且只有n个非零解，是自然高度退化的 指派问题的可行解矩阵中，各行各列的元素之和都是1。如： 指派问题，有著名的匈牙利算法,指派问题的特点：,指派问题实例,例1 有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表，问如何分配任务使完成四项任务的总工时耗费最少？,（2）指派问题的算法-匈牙利算法,定理 2 若效率矩阵中一部分元素为零，一部分元素非零，则覆盖矩阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。 匈牙利算法的基本思路： 根据定理 1变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 n个不同行不同列的零，就找到了最优解。 若覆盖变换后的效率矩阵零元素的直线少于n条，就尚未找到最优解，设法进一步变换矩阵，增加新的零。,匈牙利算法的理论基础 定理1如果从效率矩阵(cij)的某一行(列)各元素中分别减去一个常数k，得到一个新的矩阵(bij)，那么，以(bij)为效率矩阵的指派问题的最优解和原问题的最优解相同。,匈牙利算法的步骤：例1,第一步：变换效率矩阵，使每行每列至少有一个零 行变换：找出每行最小元素，从该行各元素中减去之 列变换：找出每列最小元素，从该列各元素中减去之,第二步：进行试指派，以寻求最优解,*,*,*,*,*,从只有一个0元素的行开始，给这个0元素加圈，记作，然后划去所在列的其它0元素，记作0 。,从只有一个0元素的列开始，给这个0元素加圈，记作，然后划去所在行的其它0元素，记作0 。,反复进行、直到所有的0元素都被圈出和划掉为止。,若元素的数目m等于矩阵的阶数n，则指派问题的最优解已经得到。否则，进入第三步。,第三步：做能覆盖所有0元素的最少直线集合。 对没有的行打号。 对已打号的行上的所有0元素的列打号。 再对打号的列上有的行打。 重复、 直到得不出新的打号的行、列为止。 对没有打号的行画横线，所有打号的列画竖线，所得直线就是能覆盖所 有0元素的最少直线集合。,令直线数为l。若l n,说明必须再变换当前的效率矩阵，才能找到n个独立的0元素。为此转入第四步。,第四步：从没有被直线覆盖的各元素中分别减去它们中的最小元素，同时对位于横竖线交叉处的元素加上这个最小元素，其它被横竖线画到的元素不变。,再回到第二步。,最优解矩阵：,min f =20,匈牙利算法求解指派问题 例2,机床,零件,解：,-1,最优解矩阵：,min f =20,（3）目标函数求最大值的指派问题,匈牙利算法适用于：,所有cij0,对于目标函数为max型的指派问题，将效率矩阵中所有cij反号，则等效于求min型问题；在利用定理1进行变换，使所有bij 0，则可采用匈牙利算法求解。,例3有A、B、C、D四项工作，需要甲、已、丙、丁四人完成，每人只能完成其中的一项。各人完成不同工作的产值如下表所示，问如何分配任务才能使总产值最大？,人员,任务,解：先把最大化问题化为最小化问题，再按匈牙利法求解。,最优指派方案为：甲B ， 乙A ， 丙C，丁D,1. 现有A、B、C、D、E 5个人，挑选其中4人去完成4项工作。已知每人完成各项工作的时间如表所示。规定每项工作只能由一人去完成，每人最多承担一项工作，又假定A必须分配到一项工作，D因某种原因决定不承担第4项工作。问应如何分配，才能使完成4项工作总的花费时间最少？,练习,2. 用4台机器加工4种不同的零件，由于各机床性能不同，加工每一零件时，单位时间获得利润也不同，其效率如下表，求利润最大的分派方案。,（4）最短工期指派问题,有n项工作需要分派给n个人去完成，每个人做一项工作，且每项工作只派一个人去完成，设第i个人完成第j项工作的工时数为cij，若这n个人同时开始工作，问如何进行指派，才能在最短的时间内将这n项工作完成？我们称该问题为最短工期的指派问题。,则该问题的数学模型为：,（P）,定理1 若对效率矩阵C中的每个元素分别减去一个正数 ，设得到的新矩阵为 ，则以B为效率矩阵的（P）的最优解和以C为效率矩阵的（P）的最优解相同。 定理2 若矩阵B中的所有零元素构不成n个位于不同行不同列的零元素，此时令 ，其中 则以D为效率矩阵的问题（P）有最优解的充分必要条件是以B为效率矩阵的问题（P）有最优解，且最优解相同。,最短工期指派问题的算法,Step1：令 ； Step2：若B的每一行每一列都有零元素，转Step4，否则转Step3； Step3:令 这里 转Step2。,Step4：进行试指派，以寻求最优解，具体按以下步骤进行,从只有一个0元素的行（或列）开始，给这个0元素加圈，记作，然后划去所在列和行上的其它0元素，记作0； 重复进行1.中的过程，直到所有零元素都被圈出或划掉为止； 若仍有没有划掉的0元素，且同行（列）的0元素至少有两个，则从剩有0元素最少的行（或列）开始，比较这行（或列）各0元素所在列（行）中0元素的数目，选择0元素少的那列（行）的这个0元素加圈，然后划掉同行同列的其它0元素，如此反复进行，直到所有0元素都已圈出或划掉为止； 若元素的数目m等于矩阵的阶数n，则指派问题（P）的最优解已得到，若mn，则转Step3；,最短工期指派问题举例,例某公司准备将5项工作分派给其下属的5家企业，已知各企业完成每项任务所需时间如下表，若要求每家企业