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

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,一、整数规划简介,整数规划是数学规划的一个重要分支，它研究的是一类要求其局部或全部变量取整数的最优化问题要求所有的解xj 为整数，称为纯整数规划,要求局部的xj 为整数，称为混合整数规划,要求xj 的取值只能是0和1 ，称为0-1型整数规划,整数规划数学模型,第四章 整数规划,对应没有整数解要求的线性规划称之为松弛问题,整数规划的解是可数个的，最优解不一定发生在极点,整数规划的最优解不会优于其松弛问题的最优解,整数规划问题,A,其松弛问题,B,二、整数规划的解法,分枝定界法,是一种计算与分析判断相结合的求解整数规划问题的重要方法它既能解决纯整数规划问题，又能解决混合整数规划问题这种方法有很强的适应能力，是目前较为成功的求解整数规划问题的一种方法1.分枝定界法,根本思想：分枝定界法是通过有系统的“分枝和“定界步骤来寻求最优解的它是先求解松弛问题，如果其最优解不符合整数条件，那么求出整数规划的上下界，用增加约束条件的方法把相应的线性规划的可行域分成子区域称为分枝，再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界距离，最后取得整数规划的最优解。

分枝定界法的解题步骤：,Step1 求解松弛问题B，,-假设松弛问题B无解，那么整数规划A也无解,那么停止假设B有最优解，且符合问题A的整数条件，那么B的最优解也是 A的最优解，那么停止假设B有最优解，但不符合A的整数条件，记其目标函数值为f1Step2 确定A的最优目标函数值f*的上下界，其上界为f1，即,再用观察法找到A的一个整数可行解，求其目标函数值作为f*的下界，记为f，这时有,Step3 判断 是否等于 如果 ，那么A的最优解即为其目标函数值等于 的那个整数可行解否那么，进行Step4Step4 分枝，在B的最优解中任选一个不符合整数条件的变量xj=bj，以bj表示小于bj的最大整数构造两个约束条件：,xj bj 和 xj bj+1,将这两个约束条件分别参加问题B，得到B的两个分枝B1和B2Step5 求解分枝B1,B2修改A的最优目标函数值的上下界在各分枝问题的最优解中，找出最优目标函数值最大者作为新的上界从已符合整数条件的各分枝中，找出目标函数值最大者作为新的下界，这就是定界过程Step6 比较与剪枝各分枝的最优目标函数中假设有小于 者，那么剪掉这枝，即以后不再考虑了假设大于 ，且不符合整数条件，那么重复Step4至Step6,直至 ，求出整数最优解为止。

各分枝问题的解可能出现的情况,情况 2,4,5 找到最优解,情况 3 在缩减的域上继续分枝定界法,情况 6 问题 1 的整数解作为界被保存，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4或5,例1,解：松弛问题,B,的最优解为,x,1,=2.5,x,2,=2,f,=23,分枝定界法举例,问题,A,松弛问题,B,由,x,1,=2.5,得到两个分枝如下：,显然,x,1,=1,x,2,=1,是问题,A,的可行解，其目标函数值为10,于是有 10,f,*,23,求解两个分枝问题,问题,B,2,的解即为原整数规划问题,A,的最优解,可能存在两个分枝都是非整数解的情况，那么需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程,当有很多变量有整数约束时，分枝既广又深，在最坏情况下相当于组合所有可能的整数解,松弛问题,B,x,1,=2.5,x,2,=2,f,=23,问题,B,1,x,1,=2,x,2,=2.25,f,1,=21,问题,B,2,x,1,=3,x,2,=1,f,2,=22,x,1,2,x,1,3,10,f,*,23,22,f,*,23,例2,解：松弛问题,B,的最优解为,x,1,=3.142,x,2,=3.285,f,=288.5,分枝定界法举例,问题,A,由,x,2,=3.285,得到两个分枝如下：,x,1,=1,x,2,=1,显然是问题,A,的一个可行解,其目标函数值为90,这时有,松弛问题,B,求解各分枝问题,问题,B,1,问题,B,2,x,1,=3.3,x,2,=3,f,1,=285,x,1,=2.25,x,2,=4,f,2,=272.5,因,f,1,f,2,，,故有,继续对问题,B,1,和,B,2,进行分解，,因,f,1,f,2,，,先分解,B,1,为,B,3,和,B,4,求解各分枝问题,问题,B,3,问题,B,4,x,1,=3,x,2,=3,f,3,=270,x,1,=4,x,2,=2,f,4,=280,因,f,4,f,3,，,故有,因,f,2,=272.5280，,所以再分解,B,2,已无必要，剪去该分枝。

故,x,1,=4,，,x,2,=2,为原问题,A,的最优解，最优目标函数值为,280松弛问题,B,x,1,=3.142,x,2,=3.285,f,=288.5,问题,B,3,x,1,=3,x,2,=3,f,3,=270,问题,B,1,x,1,=3.3,x,2,=3,f,1,=285,问题,B,2,x,1,=2.25,x,2,=4,f,2,=272.5,问题,B,4,x,1,=4,x,2,=2,f,4,=280,x,2,3,x,1,4,x,1,3,x,2,4,2.,0-1规划的解法,枚举法,即检查变量取值为0或1的每一个组合，比较目标函数值的大小以求得最优解例3 求解0-1规划,解 x1，x2，x3共有23=8种不同的组合，各种组合下目标函数及各约束条件左端的值列于下表：,枚举法表,满足约,束条件,？,f,值,（0，0，0）,（0，0，1）,（0，1，0）,（0，1，1）,（1，0，0）,（1，0，1）,（1，1，0）,（1，1，1）,0 0 0 0,-1 1 0 1,2 4 1 4,1 5 1 5,1 1 1 0,0 2 1 1,3 5 2 4,2 6 2 5,0,5,-2,3,8,x1，x2，x3,约束条件,最优解为X*=1，0，1,隐枚举法,所谓隐枚举法就是只检查变量取值组合的一局部就能求得问题最优解的方法。

其根本思路是：先找到一组可行解，增加一个过滤条件，然后改进过滤值，直至不能改进为止例3 求解0-1规划,解 用观察法找一个可行解x1，x2，x3=1，0，0，,其目标函数值为3于是增加过滤条件,：3,x,1,-2,x,2,+5,x,3,3 ,隐枚举法表,满足约,束条件,？,f,值,（0，0，0）,（0，0，1）,（0，1，0）,（0，1，1）,（1，0，0）,（1，0，1）,（1，1，0）,（1，1，1）,0,5 -1 1 0 1,-2,3,3,8 0 2 1 1,1,6,5,8,x1，x2，x3,约束条件,最优解为X*=1，0，1,3,.,指派问题,1指派问题的数学模型:引入0-1变量xij (i,j=1,2,n),模型中：cij 为第 i 个工人完成第 j 项任务的时间(本钱、费用)；,cijnn 称为效率矩阵,指派问题不但是整数规划，而且是,0,1规划,指派问题,也,是运输问题的特例，即,m,=,n,a,i,=,b,j,=1指派问题有2,n,个约束条件，但有且只有,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,A,B,C,D,甲,乙,丙,丁,5,7,8,7,7,4,10,7,8,3,14,9,8,4,12,2,机床,零件,解：,-1,最优解矩阵：,min,f,=20,3目标函数求最大值的指派问题,匈牙利算法适用于：,所有,c,ij,0,对于目标函数为max型的指派问题，将效率矩阵中所有cij反号，那么等效于求min型问题；在利用定理1进行变换，使所有bij 0，那么可采用匈牙利算法求解。

例3,有,A,、,B,、,C,、D,四项工作，需要甲、已、丙、丁四人完成，每人只能完成其中的一项各人完成不同工作的产值如下表所示，问如何分配任务才能使总产值最大？,A,B,C,D,甲,乙,丙,丁,1,5,4,3,8,7,5,1,4,6,6,4,1,3,3,2,人员,任务,解：先把最大化问题化为最小化问题，再按匈牙利法求解最优指派方案为：,甲,B,，,乙,A,，,丙,C，,丁,D,1.现有A、B、C、D、E 5个人，挑选其中4人去完成4项工作每人完成各项工作的时间如表所示规定每项工作只能由一人去完成，每人最多承担一项工作，又假定A必须分配到一项工作，D因某种原因决定不承担第4项工作问应如何分配，才能使完成4项工作总的花费时间最少？,人,工作,A,B,C,D,E,1,2,3,4,10,5,15,20,2,10,5,15,3,15,14,13,15,2,7,6,9,4,15,8,练习,2.用4台机器加工4种不同的零件，由于各机床性能不同，加工每一零件时，单位时间获得利润也不同，其效率如下表，求利润最大的分派方案零件,工作,B,1,B,2,B,3,B,4,A,1,A,2,A,3,A,4,35,28,35,24,27,34,24,32,28,29,32,25,37,40,33,28,4最短工期指派问题,有n项工作需要分派给n个人去完成，每个人做一项工作，且每项工作只派一个人去完成，设第i个人完成第j项工作的工时数为cij，假设这n个人同时开始工作，问如何进行指派，才能在最短的时间内将这n项工作完成？我们称该问题为最短工期的指派问题。

那么该问题的数学模型为：,P,定理1 假设对效率矩阵C中的每个元素分别减。