整数规划的产生和发展报告课件

单击此处编辑母版文本样式,第二级,第三级,单击此处编辑母版标题样式,PPT,模板下载：,行业,PPT,模板：,节日,PPT,模板：,PPT,素材下载：,PPT,背景图片：,PPT,图表下载：,优秀,PPT,下载：,PPT,教程：,Word,教程：,Excel,教程：,资料下载：,PPT,课件下载：,范文下载：,试卷下载：,教案下载：,整数规划报告,PPT模板下载： 行业PPT模板： 整数规划报告,1,第五章 整数规划,第五章 整数规划,引言,什么是整数规划,在第,4,章中的线性规划问题，其设计变量都是连续变量，其最优解可以出现分数或小数。但当设计变量表示零件数、劳动力人数、设备的台数时，其取值则必须为非负整数，此时一般的线性规划求解方法就可能失效。我们称要求,设计变量的部分分量或者全部分量取整数值,的最优化问题为整数规划问题,整数规划的产生和发展,整数规划（,Integer Programming,，简写为,IP,）和线性规划一样属于运筹学中数学规划的一个分支，其研究的问题包括整数线性规划和整数非线性规划,整数规划是从,1958,年由,R. E. Gomory,提出割平面法之后形成独立分支的。之后在该领域虽然也发展出诸如分枝定界法和割平面法等主流方法，但它仍是数学规划中稍弱的一个分支，目前的方法仅适合解中等规模的整数线性规划问题，而对于大规模整数线性规划和整数非线性规划问题，还没有成熟的办法,整数规划的分类,纯整数规划：全部设计变量都取整数,混合整数规划：部分设计变量取整数,0-1,规划：设计变量仅取,0,或,l,两个值,引言什么是整数规划,典型的整数规划问题,装载问题,有一列用于运货的火车，其最大承载能力为,b,。现有,n,种不同的货物,p,1,p,2,p,n,可供装载，设每件,p,i,的重量为,a,i,，装载收费为,c,i,(,i,=1,2,n,),，则应采用何种装载方案能够使得该列火车载货的收入最大？,设,x,j,为列车上装载,p,j,的数量，则,x,j,必为非负整数，根据该货船最大可承载,b,吨货,物可知所有集装箱的重量之和必须,b,，故有约束条件：,由对每个,j,种货物收费为,c,j,，可知载货的总收入为：,该例的目标即使得目标函数,f,最大化。综合上述分析可得如下整数规划问题：,典型的整数规划问题 装载问题,典型的整数规划问题,工厂选址问题,某地区有,m,座铁矿,A,1,A,2,A,m,，,A,i,每年的产量为,a,i,(,i,=1,2,m,),，该地区已有一个钢铁厂,B,0,，每年铁的用量为,p,0,，每年固定运营费用为,r,0,。由于当地经济的发展，政府拟建立一个新的钢铁厂，于是今后该地区的,m,座铁矿将全部用于支持这两个钢铁厂的生产运营。现在有,n,个备选的厂址，分别为,B,1,B,2,B,n,，若在,B,j,(,j,=1,2,n,),处建厂，则每年固定的运营费用为,r,j,。由,A,i,向,B,j,每运送,1t,钢铁的运输费用为,c,ij,(,i,=1,2,m,;,j,=0,1,n,),。那么应当如何选择新厂厂址，铁矿所开采出来的铁矿石又当如何分配给两个钢铁厂，才能使每年的总费用（固定运营费用和煤的运费）最低？,钢铁厂,B,0,每年需要用铁,p,0,，而且今后该地区,m,座铁矿将全部用于支持这两个钢铁厂的生产，故新的钢铁厂每年用铁量,p,为该,m,座铁矿的总产量减去,B,0,的用铁量：,令设计变量为,v,i,，若,v,i,=1,则表示选择,B,i,作为新厂厂址，否则,v,i,=0,：,典型的整数规划问题工厂选址问题,典型的整数规划问题,工厂选址问题,设,x,ij,为每年从,Ai,运往,Bj,的钢铁数量，于是每年的总费用为：,由铁矿,Ai,运出的所有钢铁将等于铁矿,A,i,的产量,a,i,原钢铁厂,B,0,钢铁的用量,p,0,为,m,座铁矿为其供应，故其收量应当等于,m,座铁矿对分别对其供应量的总和，即：,同样的，对于备选厂,B,j,，可知其钢铁的用量为,p,，且由,m,座铁矿供应，由于备选厂址只有一座，故在,p,前面需要乘以系数,v,j,，即代表如果选择,B,j,为备选厂址，则用铁矿，否则，则该厂不存在，不需要使用铁矿，此时，对应的,x,ij,将全部取零值，故：,由,A,i,向,B,j,钢铁的运输量均为非负实数,备选的钢铁厂只有一处,典型的整数规划问题工厂选址问题,典型的整数规划问题,工厂选址问题,根据如上分析，根据设计变量的取值规则，要么建厂取,0,，要么不建厂取,1,，同时该问题还要确定如果选择了厂址，应当如何分配,m,座铁矿对两个钢铁厂的钢铁供应量,x,ij,，而该变量的取值为非负实数即可，故该问题为一混合整数规划问题，且为混合,0-1,规划，可以归纳为如下形式：,典型的整数规划问题工厂选址问题,典型的整数规划问题,背包问题,夫妇两人要赴,A,地进行长途旅行，需要整理行李，现有,3,个旅行包，其容积大小分别为,10,升、,15,升和,20,升，两人在列出物品清单后根据需要已经整理出了,10,个包装袋，其中一些包装袋中装的是必带物品，共有,7,件，其体积大小分别为,4,升、,3,升、,1.5,升、,2.5,升、,4.5,升、,7.6,升和,1.9,升。尚有,8,个包装袋可带可不带，不带则可在,A,地购买，这些可选包装袋的容积和其对应物品在,A,地的价格如表所示。,试根据上述信息给出一个合理的打包方案。,在这个问题中，我们需要确定的是，选带哪几个可选的包装袋，且将必带物品和选带物品放到哪个旅行包中。为此我们设第,i,个包装袋是否放在第,j,个旅行包中，并以此作为设计变量。同时，设第,i,个包装袋的容积可以用,w,i,(,i,=1,2,3,15),来表示，可选包装袋对应的价格用,p,i,(,i,=8,9,10,15),来表示。由于第,i,个包装袋要么在第,j,个旅行包中，要么在要么不在，故设只取,0,和,1,，且表述如下,：,物品,1,2,3,4,5,6,7,8,容积,2.5,4,5.5,4.8,3.7,1.6,7.5,4.5,价格,20,50,105,75,55,80,200,100,典型的整数规划问题背包问题 物品12345678容积2.54,典型的整数规划问题,背包问题,由于每个旅行包的容积确定，故装入第,j,个旅行包中的所有包装袋的容积的总和必须小于第,j,个旅行包的容积，即需要满足约束条件：,由于旅行袋中有,7,件为必带，故这,7,个包装袋必然在,3,个旅行包中的其一，设包装袋的编号为,i,，则在设计变量,x,i,1,、,x,i,2,和,x,i,3,中必有一个取值为,1,，另外两个取值为,0,，其和为,1,。根据上述分析，对于,7,件必带的包装袋必须满足如下约束：,对于可选的包装袋，则其要么在某个旅行包中，要么不在旅行包中，设包装袋的编号为,i,，如果它在某个旅行包中，则设计变量,x,i,1,、,x,i,2,和,x,i,3,取值之和为,1,，如果它不在旅行包之中，则设计变量,x,i,1,、,x,i,2,和,x,i,3,取值之和为,0,，故对于可选的包装袋必须满足如下约束：,典型的整数规划问题背包问题,典型的整数规划问题,背包问题,我们的目标就是使得在到达,A,地之后，所买物品的价格最低，即不在旅行包中的包装袋的总价格最低，如果某包装袋,i,不在旅行包中，则有： 故其价格可以用 来表示，故所有不在旅行包中的包装袋的价值,f,可表达如下,我们确定打包方案的原则就是使得,f,取得最小值，故综合以上分析，该背包问题的数学模型为：,典型的整数规划问题背包问题,整数规划问题的数学模型,一般形式,在整数规划中还有许多其他典型的问题，例如在第,3,章中提到的分派问题，还有旅行商问题、下料问题等，其问题均可以归结为如下的一般形式,上述形式是仿照线性规划中的标准型给出的，其中设计变量,x,为,n,维的列向量，,c,为,n,维的行向量，,A,为,m,n,的矩阵，且,A,行满秩，,b,为,m,维列向量。,在模型中，,(1),可以是最大化也可以是最小化，对于约束,(2),，可以是等式的形式也可以是不等式的形式。对于对设计变量的约束,(3),，如果要求,x,全部分量为整数，则为纯整数规划；如果要求,x,的部分分量为整数，则为混合整数规划，如果要求,x,分量的取值只能为,0,和,1,，则为,0-1,规划。,整数规划问题的数学模型 一般形式,整数规划的求解,直观想法,既然整数规划问题的可行方案数目有限，则我们经过,枚举比较,之后，总能求出最好方案，这种想法对于维数很低的整数规划问题行得通，但是随着设计变量维数的增加，该方法的计算量是不可想象的，因而此种想法不可行。,另一种想法更为直接，因为整数规划问题实际上是在线性规划问题的基础上增加了整数约束，因而是否可以考虑先忽略整数约束，解一个线性规划问题，然后用,四舍五入法取得其整数解,？但事实证明，这样经过四舍五入的结果甚至不是问题的可行解,可行否,枚举法随着变量维数增加呈指数增长，不可行！,四舍五入可能都不是可行解，不可行！,四舍五入后的解不是可行解！,整数规划的求解 直观想法四舍五入后的解不是可行解！,整数规划的求解,求解思路,由上述分析可知，舍入法一般是不可取的，当然如果对应线性规划的最优解恰好满足整数要求，则该解也是整数规划的最优解，那么何时才能满足此要求呢？我们直接给出一个结论：,假设由整数规划问题除去整数要求之后得到的线性规划标准型中，等式约束个数等于决策变量个数,(,m,=,n,),，则此时的等式约束构成一个线性方程组,Ax=b,，如果,det(A) = 1,或,-1,，则解,x,一定是整数向量，当然这种情况在解决实际问题的过程中一般还是比较少见的。,对于整数规划问题的解法，一般有利用分解技术的算法和不利用分解技术的算法,利用分解技术的算法有分枝定界法和针对,0-1,规划的隐枚举法,不利用分解技术的算法为割平面法和群论方法,针对特定的问题还有特定的简化方法，例如求解分派问题的匈牙利方法，等等。,整数规划的求解求解思路,求解整数规划的理论基础,利用分解技术求解整数规划中的几个概念,分解,对于整数规划问题,P,，令,F,(,P,),表示,P,的可行域。对问题,P,的子问题,P,1, ,P,m,，若满足下述条件：,则称,P,问题被分解成为子问题,P,1, ,P,m,之和，最常用的方法就是两分法，例如若,x,j,是,P,的,0-1,变量，则问题,P,可以按照条件,x,j,=0,和,x,j,=1,分解成两个问题之和。,松弛,凡是放弃问题,P,的某些约束后所得到的问题,Q,都称为,P,的松弛问题。通常的松弛方式是放弃设计变量的整数约束，若,P,是整数规划，则,Q,就是线性规划。,由于对于,P,的任何松弛问题,Q,，都有 ，故问题,P,与其松弛问题,Q,之间的关系为：,若,Q,没有可行解，则,P,也没有可行解；,对于最大化的目标函数而言，,P,的最大值小于或者等于,Q,的最大值，对于最小化的目标函数而言，,P,的最小值大于或者等于,Q,的最小值；,如果,Q,的一个最优解,x,是,P,的可行解，则,x,也是,P,的一个最优解。,求解整数规划的理论基础利用分解技术求解整数规划中的几个概念,求解整数规划的理论基础,利用分解技术求解整数规划中的几个概念,探测,假设按照某种规则，已经将问题,P,分解称为子问题,P,1, ,P,m,之和，,P,i,对应的松弛问题为,Q,i,。且问题需要最大化目标函数，则有如下结论：,如果,Qi,没有可行解，则,P,i,也无可行解，因此可将,P,i,从,P,的分解表上删去；,假设已知,P,的一个可行解,x,*,，其对应的目标函数值为,f,*,。若,Q,i,的目标函数的最大值小于或者等于,f,*,，则说明,P,i,中没有比,x,*,更好的可行解，因此可将,P,i,从,P,的分解表上删去；,如果,Q,i,的最优解是,P,i,的可行解，则已求得,P,i,的最优解，故无须进一步考虑,P,i,，可从表上删去，若,P,i,的最优解比,x,*,好，则以,P,i,的最优解代替,x,*,如果分解表上各个,Q,i,的目标函数值均不大于,x,*,，则,x,*,便是,P,的一个最优解,求解整数规划的步骤,首先按照某种方式确定,P,的松弛问题,Q,，若,Q,无可行解则,P,也无可行解，若,Q,的最优解为,P,的可行解，则也是,P,的最优解。若,Q,的最优解不是,P,的可行解，则要么以一种更好的方式确定松弛问题,Q,，继续探测,P,，要么将,P,分解成为几个子问题之和，然后逐个探测，当某个子问题已被探明时，就从表中删除，否则继续对子问题进行分解,求解整数规划的理论基础利用分解技术求解整数规划中的几个概念,求解整数规划的分枝定界法,分枝定界法的思想,根据理论基础，若整数规划问题,P,除去整数约束的松弛问题,Q,为线性规划，则有如下几个推论,若,Q,无可行解，则,P,也一定无可行解,若,Q,的一个最优解是整数解，则这个解也是整数规划,P,的最优解,若,Q,的最优解不是整数解，则,P,的最优目标函数值不会好于,Q,的最优值。因此，,Q,的最优目标函数值是,P,的最优目标函数值的一个界，在最大化目标函数值时为上界，在最小化目标函数值是下界,如果在求解过程中已经找到一个整数解，则最优整数解一定不会劣于该整数解，因此，它也是最优目标函数值的一个界，在最大化目标函数值时为下界，在最小化目标函数值是上界,如果用,f,表示,Q,的最优值，用,f,i,表示已经找到的最佳整数解的最优值，,f*,为,P,的最优值，,lb,表示下界，,ub,表示上界，则对于最大化目标函数的问题，一定存在关系 ，而对于最小化目标函数的问题，则为,，分枝定界法的思想就是,不断降低上界，提高下界,，最后使得下界接近或者等于上界，通过这个方法来缩小搜索的范围，进而找到问题的最优整数解。,求解整数规划的分枝定界法 分枝定界法的思想,求解整数规划的分枝定界法,分枝定界法的求解步骤,求解其松弛线性规划，如果得到整数解，该解即为整数规划的最优解。否则，所得线性规划的解可作为该问题最优整数解的初始上界，初始下界一般设为,-,。,建立分枝树：在任何一个（子）问题中，从不满足整数要求的变量中选出一个进行处理，通过加入一对互斥的约束将一个（子）问题分枝成为两个受到进一步约束的子问题，并强迫不为整数的变量进一步逼近整数值，一次去掉两个整数之间的非整数域，缩小搜索的区域，由此，子问题若不满足整数要求则继续向下进行分枝，可以形成一个分枝树。,定界与剪枝：通过不断的分枝和求解各个子问题，分枝定界法将不断修正上下界。上界通常由子问题的最大目标函数值确定，而下界则由已经得到的最优的整数解来确定。,求解任何一个（子）问题都有可能出现以下结果：,无可行解，此时无需继续向下分枝；,得到一个整数解，则不必继续向下分枝，如果该整数解是目前得到的最好的整数解，则被记录下来，并用它的值作为新的下界；,得到一个非整数解，如果目标函数值大于剪枝界，则继续向下分枝，否则该子问题被剪枝,按照上述步骤搜索迭代，在每次搜索的过程中，每当下界被修改以后，都应检查所有的还没有求解过的子问题并剪去那些目标函数值小于新的下界的子问题，此时如果没有找到任何整数解，则该问题没有整数解；否则。搜索过程中已经得到的最优的整数解就是该问题的最优解。,求解整数规划的分枝定界法分枝定界法的求解步骤,求解整数规划的分枝定界法,说明,对于上述求解步骤中的第,(4),步，特别说明如下：如果在计算过程中已得到某一个分枝的整数最优解，其最优值为,f,0,。而此时在其他分枝过程中，如果求得某一线性规划所得的目标函数值小于,f,0,，即可停止该枝的计算。因为进一步求解的结果的最优值也只可能比,f,0,更差，这也就是,如何检查下界对分枝树进行剪枝的原则,。,求解整数规划的分枝定界法说明,求解整数规划的分枝定界法,如何选择分枝的节点,深度优先搜索,先选择最后的还没有求解过的子问题并剪去那些目标函数值小于新下界的子问题。在搜索的过程中，如果某子节点的上界小于当前原问题的某一可行解的值，则将该子节点删去不再进行分枝。该方法可以较早的实现剪枝的过程，,很快的搜索到分枝树的较底层找到一个整数解，且存储空间小，缺点就是未顾及其他分枝，找到的整数解的质量未必高。,广度优先搜索,始终选择由最大目标函数值的子问题继续向下分枝，在搜索的过程中，如果某子节点的上界小于当前原问题的某一可行解的值，则将该子节点删去不再进行分枝。因为它每次都以最大上界的子问题进行处理，,故用该搜索方法找到整数解的质量较高，缺点是该方法要在整个分枝树上搜索，故存储空间比深度优先搜索大，求解时间也较长。,预估法,利用一些先验知识和相关技巧预先估计还未求解过的子问题的最好可能整数解，并选择最好预估值的子问题向下分枝，该方法是上述两种方法的,折中选择。,求解整数规划的分枝定界法如何选择分枝的节点,求解整数规划的分枝定界法,如何选择分枝变量,按照目标函数系数选择,选择目标函数中对应系数绝对值最大的设计变量进行分枝,按非整数变量选择,选择与整数值相差最大的非整数变量首先进行分枝,按人为给定的顺序选择,例如选择者按整数变量在问题中的相对重要性排序,求解整数规划的分枝定界法如何选择分枝变量,求解整数规划的分枝定界法,算法描述,Step1,求,P,的松弛线性规划问题,Q,，若,Q,无可行解，则,P,也无可行解，算法结束；若其最优解,符合整数条件，则找到最优解，算法结束，若不满足转,(2),Step2,按照分枝节点和分枝变量的原则选择不符合整数约束条件的设计变量,x,i,=,b,i,，令,b,i,为,b,i,的整数部分（向下取整），构造两个互斥的约束条件,x,i,b,i,和,x,i,b,i,+1,，形成两个整,数规划子问题,P,1,和,P,2,，转,Step3,Step3,求解,P,1,和,P,2,的松弛线性规划问题,Q,1,和,Q,2,，则根据如下情况进一步求解：,Q,1,无可行解，,Q,2,无可行解，则整数规划,P,无可行解，算法结束；,Q,1,无可行解，,Q,2,有整数解，则该解为,P,的最优解，算法按结束；,Q,1,无可行解，,Q,2,有非整数解，则对,Q,2,进行分枝转,Step2,Q,1,有整数解，,Q,2,有整数解，则较优的一个为,P,的最优解，算法结束；,Q,1,有整数解且目标函数值优于,Q,2,，,Q,2,有非整数解，则,Q,1,的整数解为,P,的最优解,Q,1,有整数解，,Q,2,有非整数解且目标函数值优于,Q,1,，则,Q,1,停止分枝，其整数解为新的界，对,Q,2,转,Step2,Q,1,无整数解，,Q,2,也无整数解，可以按照设定的规则选取一枝先进行分枝计算，其中一枝若计算得到的最优解为整数解，且最优值优于另一枝，则所得的整数解就是,P,的最优解，无须对另一枝进行分枝；若得到的最优值劣于另一枝，则对另一枝进行分枝转,Step2,求解整数规划的分枝定界法算法描述Step1求P的松弛线性规划,求解整数规划的分枝定界法,求解整数规划问题,P,首先求解,P,的松弛线性规划问题,Q,，可知其最优解为： ，在最优解处取得的函数最大值为：,f,Q,=4,，此时,上界为,4,，由于,x,Q,的两个分量均不为整数，故需要对问题,P,进行分枝，在此，人为取,x,1,进行分枝，对,x,P,1,=1.5,向下取整得,1,，故加上互斥的约束条件,x,1,1,和,x,1,2,，那么加入该组互斥条件的作用在于：排除了区间,(1,2),之内的非整数解，缩小了搜索的范围；形成了整数规划,P,的两个子问题,P,1,和,P,2,求解整数规划的分枝定界法,求解整数规划的分枝定界法,由于现在已经存在两个子节点,P,1,和,P,2,，下一步选取哪个节点进行分枝需要采用合适的策略，在此我们采用广度优先搜索的方法，由于,Q,2,的目标函数值较大，故对问题,P,2,进行分枝，加入互斥的约束,x,2,1,和,x,2,2,，形成,P,2,的两个子问题,P,3,和,P,4,。当加入新的约束之后，有可能出现三种情况：,(1),新加入的条件和原问题的条件独立，即互不影响，此时直接将约束加入到问题中；,(2),新加入的条件和原问题的条件相矛盾，此时新的问题无可行解；,(3),新加入的约束和原约束存在交集，则此时选择其交集作为作为新问题的约束条件。,求解整数规划的分枝定界法 由于现在已经存,求解整数规划的分枝定界法,由于,Q,3,的目标函数值,f,Q,3,大于,Q,1,的目标函数值,f,Q,1,，故下一步对,P,3,进行分枝，加入互斥的约束,x,1,2,和,x,1,3,，形成,P,3,的两个子问题,P,5,和,P,6,。,现在我们已经在,P,2,的分枝上找到了一组整数解，现在比较,f,Q,5,和,f,Q,1,，由于现在已有整数解的目标函数值,f,Q,5,大于,f,Q,1,，而,P,1,的最优目标函数值不会大于,f,Q,1,，故该分枝的解不会对目标函数值有任何的改善，所以对,P,1,进行剪枝，即停止对,P,1,的,向下分枝，我们已经搜索到了的最优解。,这里需要,注意,的，如果我们发现已经求得整数解的最优值,f,Q,5,要小于,f,Q,1,，则,P,的上界还并未确定，于是问题还需要继续分解下去。,求解整数规划的分枝定界法 由于Q3的目标函,求解整数规划的分枝定界法,上述求解过程示意图,求解整数规划的分枝定界法上述求解过程示意图,求解,0-1,规划的隐枚举法,隐枚举法的提出,由,E Balas,在,1965,年提出的，该方法只检查一部分变量组合，在这过程中根据已有信息自动舍弃许多不可能成为最优解的组合以求得最优解，从而大大减少了工作量，隐枚举法只需比较目标函数在一小部分组合点上的取值大小就能求得最优解和最优值。,隐枚举法的思想,隐枚举法可以看作是分枝定界法的特殊情况，在求解的过程中，它不需要求解其松弛线性规划问题，利用变量只能取,0,或,1,对问题进行分枝。其思路是先将,0-1,规划问题转化为既定的,标准型,，该标准型一般是要最小化目标函数的值，在此前提下，首先令,全部变量取,0,值,（当求最大值时，令全部变量取,1,值），检验解是否满足约束条件，若均满足，已得最优解；若不全满足，则令一个变量分枝取值为,0,或,1,，该分枝变量称为固定变量，将模型分成两个子模型，其余未被指定取值的变量称为自由变量，通过这种方法，依次指定一些变量为,1,，直至得到一个可行解，并将它作为目前最好的可行解并记录下来。此后，经过几次检验后，或者停止分枝，或者将另一个自由变量转为固定变量，令其值为,0,或,l,，如此继续进行，依次试探变量等于,0,或,l,的某些组合，使目前最好的,可行解不断逼近最优值,，直至没有自由变量或全部子问题停止分枝为止，就求出了,0-1,规划的最优解，,求解0-1规划的隐枚举法 隐枚举法的提出,求解,0-1,规划的隐枚举法,取试探解的理由,为什么从全,0,作出初始的试探解，这是因为,0-1,规划的标准型要求对目标函数求最小值，而对于最小化目标函数的问题，由于在后面我们会提到,0-1,规划标准型中,c,j,0,，故因此自由变量为,0,与固定变量组成的子模型能够使得目标函数值最小。同理，如果不用标准型求解，例如对目标函数求最大值的问题，则是将全,1,作为初始的试探解进行分枝计算,隐枚举法和穷举法的不同,隐枚举法和穷举法不同，穷举法需要将所有可行的变量组合逐个列举，而隐枚举法通过试探、分析和判断，排除了许多变量组合作为最优解的可能性。也就是说，它们被隐含枚举了，这也是称其为隐枚举法的原因,隐枚举法的实质,从算法描述可以看出，隐枚举法的实质也是分枝定界法，隐枚举法在求解过程中与一般的分枝定界法不同之处只在于在分枝产生子问题时变量被固定为,0,或,1,，而不是两个范围之值的形式。,求解0-1规划的隐枚举法取试探解的理由,求解,0-1,规划的隐枚举法,隐枚举法的,0-1,规划标准型,非标准型的标准化,若原问题为求,max,f,，则可令,f,=-,f,将问题转化为,min,f,。或者不改变求最值的属性，将全,1,作为,0-1,规划的初始试探解,当某个系数,c,j,f,P,1,，故停止向下分枝。,按照上述方法不断试探，最后可得所有可行解中，,P,9,所对应的,x,P,9,=0 1 0 1,T,所取得的目标函数值最小为,f,P,9,=15,，故,x,P,9,为,P,的最优解。,求解过程示意图如下一页所示。,求解0-1规划的隐枚举法 首先以x1作为,求解,0-1,规划的隐枚举法,求解过程示意图,求解0-1规划的隐枚举法求解过程示意图,求解分派问题的匈牙利算法,匈牙利算法的应用对象,用以解决分派问题,分派问题是一种特殊形式的整数规划。该问题可以总结为，有,n,项任务需要,n,个人分别去完成，每个人只能完成其中的一项，而每项工作也只能由一个人完成，在问题中会以各种形式给出各个人的专长和工作效率，需要求解的问题是考虑分配哪个人去完成哪项任务才能使得总效率最高或者花费的总时间最短。,匈牙利算法的提出,由于分派问题属于,0-1,规划，故我们可以用隐枚举法进行求解，但是鉴于上述问题的特殊性，可以有更简便的方法求解此类问题，由于这种方法是基于匈牙利数学家狄,柯尼格（,D Knig,）证明的两个定理而发展的，故称之为匈牙利法。,求解分派问题的匈牙利算法 匈牙利算法的应用对象,求解分派问题的匈牙利算法,匈牙利算法的,0-1,规划标准型,匈牙利算法是解决最优模型可归结为与分派问题结构一致的最优化问题的有效算法，那么首先回顾一下分派问题的数学模型，假设由第,i,个人完成第,j,项工作的时间为,E,ij,，又设问题中的设计变量为,x,ij,，其意义如下：,则分派问题的标准型为：,需要注意的是，标准型中要求的是,最小化,目标函数的值，且对应于各设计变量的,系数均不小于零,。这是应用匈牙利算法的前提条件。,求解分派问题的匈牙利算法匈牙利算法的0-1规划标准型,求解分派问题的匈牙利算法,非标准型的标准化,目标函数中设计变量,x,mn,对应的系数为负数,E,mn,0,可令 ，此时有 ，取 可,知,于是原目标函数变为：,经过上述转换实现了将目标函数中所有设计变量的系数变成正数,目标函数求最大,令,其中,M,是足够大的常数，一般方法是令,M,为效率矩阵元素,E,ij,中的最大值，即 ， 由于对于任意的,i,j,(,i,=1,2,n,;,j,=1,2,n,),均可满足,max(,E,ij,)-,E,ij,0,，故可以保证,F,ij,0,，,这时，系数矩阵变为：,F,=(,F,ij,),，且满足,F,ij,0,，对应效率矩阵,F,的分派问题的目标函数满足：,显然可以表达成为,，,因为,nM,为一常数，故当,f,取得最小值时，可以取到最大值，即通过这种变换将原分派问题目标函数由最小化变成最大化，以符合匈牙利法的实施条件。,求解分派问题的匈牙利算法非标准型的标准化,求解分派问题的匈牙利算法,匈牙利算法的基本思想,在分派问题的数学模型中，目标函数的系数可以写成,n,n,维的矩阵形式，我们可以用效率矩阵,E,来表示这组参量：,而匈牙利法就是通过对效率矩阵,E,的处理来获得分派问题的最优解。在匈牙利法中，要求矩阵,E,的所有元素均为非负，即,E,ij,0,。其基本的思想就是如果在矩阵,E,中存在一组（,n,个）位于不同行且不同列的零元素，则最优方案就是令对应于这些零元素位置的,x,ij,=1,，其他位置的,x,ij,=0,。但是很显然的，我们建立的分派模型的效率矩阵,E,中几乎没有零元素，要实现上述设想就必须找到合适的方法对矩阵,E,进行变换，来获得这一组位于不同行且不同列的零元素。,求解分派问题的匈牙利算法匈牙利算法的基本思想,求解分派问题的匈牙利算法,匈牙利算法的理论基础,引理,1,：如果将效率矩阵,E,的第,i,行每个元素减去一个常数,u,i,，将第,j,列中每个元,素减去一个常数,v,j,，得到新的效率矩阵,F,，其第,i,行第,j,列的元素为,F,ij,=,a,ij,-,u,i,-,v,j,，,则分别对应于,E,和,F,的两个分派问题的最优解等价，其最优值相差,推论,1,：如果将效率矩阵,E,的每一行（或每一列）各元素分别减去该行（或该列）的最小元素，由此得到的新的效率矩阵,F,，则分别对应于,E,和,F,的两个分派问题的最优解等价,引理,2,：若矩阵,E,的元素可以分成“,0”,元素和“非,0”,元素两部分，则覆盖所有“,0”,元素的最少直线（将直线上的元素全部划去之后矩阵就不再有“,0”,元素，这样所需直线数的最小值）等于位于不同行且不同列的“,0”,元素的最大个数。,根据上面的结论，用匈牙利法求解分派问题的原理即通过对原效率矩阵,E,各行各列元素的同加或者同减运算，构造出等价最优解的效率矩阵,F,，且,F,的所有元素非负且具有,n,个不同行且不同列的“,0”,元素。这样，,n,个“,0”,元素所对应的人做对应的工作就是分派问题的最优解,求解分派问题的匈牙利算法匈牙利算法的理论基础,求解分派问题的匈牙利算法,用匈牙利算法求解,第一步，使得每一行和每一列都出现,0,元素,将,E,的每行元素减去该行中的最小元素，使得每一行至少出现一个,0,元素；,将所得矩阵的每列元素减去该列中的最小元素，使得每一列都至少出现一个,0,元素,如果某行或者某列已经有零元素，则不必再减,对例题中的,E,，操作如下：,求解分派问题的匈牙利算法,求解分派问题的匈牙利算法,第二步，最优性检验，进行试指派，即找出不同行不同列的,0,元素,(I),给只有一个,0,元素的行中的,0,打上括号，记作,(0),，并划去与其同列的其余,0,元素，记作 ；,(II),给只有一个,0,元素的列中的,0,打上括号，记作,(0),，并划去与其同行的其余,0,元素，记作 ；,(III),反复进行,(I),和,(II),，直至所有的,0,都被标记为止；,(IV),若仍有没有被标记的,0,元素，则可从剩余的,0,元素最少的行（列）开始，选择,0,元素少的那列（行）的,0,元素加括号（表示选择性多的要礼让选择性少的）。然后，划去同行同列的其它,0,元素，反复进行，直到所有,0,元素都已被标记为止。,(V),若,(0),元素的数目,m,等于矩阵的阶数,n,，那么这指派问题的最优解已经找到，若,m,n,，转下一步,求解分派问题的匈牙利算法第二步，最优性检验，进行试指派，即找,求解分派问题的匈牙利算法,第三步，矩阵变换,作能覆盖所有,0,元素的最少直线,(a),对没有,(0),的行标记“*”；,(b),对标记“*”行上含有,0,元素的列标记“*”；,(c),对标记“*”列上有,(0),的行标记“*”,(d),重复,(b)(c),直到无法标记“*”为止,(e),对标记“*”的列画纵线，未标记“*”的行画横线，这就是能覆盖所有,0,元素的最少直线,移动,0,元素,在未被划去的元素中找出最小元素,s,，将其作为矩阵变换的调整量；,将标记“*”行的所有元素都减去,s,将标记“*”列的所有元素都加上,s,结果将得到一个新的效率矩阵，转第二步。,求解分派问题的匈牙利算法第三步，矩阵变换,求解分派问题的匈牙利算法,对于本例的示例矩阵，未被划去的元素中最小者为,2,，故首先将第,1,行和第,3,行减去,2,，然后将第,2,列加上,2,，获得新的效率矩阵：,返回第二步，即尝试在上述矩阵中找到不同行且不同列的,n,个,0,元素,求解分派问题的匈牙利算法 对于本例的示例矩,求解分派问题的匈牙利算法,由以上求解结果，可以知道有两种最优的指派方式，相应的分派方案,1,号成员完成,2,号任务，,2,号完成,3,号任务，,3,号完成,1,号任务，,4,号完成,4,号任务；,1,号完成,1,号任务，,2,号完成,3,号任务，,3,号完成,2,号任务，,4,号完成,4,号任务,最优方案耗时,M,1,：,f,=21+12+29+23=85,M,2,：,f,=20+13+29+23=85,求解分派问题的匈牙利算法由以上求解结果，可以知道有两种最优的,一般整数规划问题的,MATLAB,求解,求解方法,由于,MATLAB,优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题，例如比较著名的,YALMIP,，读者可以自行到网上下载相关的工具包并进行学习。这里我们给出开罗大学的,Sherif,和,Tawfik,在,MATLAB Central,上发布的一个用于求解一般混合整数规划的程序，在此命名为,intprog,，笔者在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝,调用格式,x,fval,exitflag=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger),一般整数规划问题的MATLAB求解 求解方法,一般整数规划问题的,MATLAB,求解,标准形式,假设,x,为,n,维设计变量，且问题具有不等式约束,m,1,个，等式约束,m,2,个，那么：,c,、,x,均为,n,维列向量，,b,为,m,1,维列向量，,b,eq,为,m,2,维列向量，,A,为,m,1,n,维矩阵，,A,eq,为,m,2,n,维矩阵。,输入参数有,c,A,b,A,eq,b,eq,lb,ub,M,和,TolXInteger,。其中,c,为目标函数所对应设计变量的系数，,A,为不等式约束条件方程组构成的系数矩阵，,b,为不等式约束条件方程组右边的值构成的向量。,Aeq,为等式约束方程组构成的系数矩阵，,b,eq,为等式约束条件方程组右边的值构成的向量。,lb,和,ub,为设计变量对应的上界和下界。,M,为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为,x,1,x,2,x,6,，要求,x,2,x,3,和,x,6,为整数，则,M=2;3;6,；若要求全为整数，则,M=1:6,，或者,M=1;2;3;4;5;6,。,TolXInteger,为判定整数的误差限，即若某数,x,和最邻近整数相差小于该误差限，则认为,x,即为该整数。,输出参数有,x, fval,和,exitflag,。其中,x,为整数规划问题的最优解向量，,fval,为整数规划问题的目标函数在最优解向量,x,处的函数值，,exitflag,为函数计算终止时的状态指示变量。,一般整数规划问题的MATLAB求解标准形式,一般整数规划问题的,MATLAB,求解,算法实现,intprog.m,%,整数规划的,MATLAB,实现,%Originally Designed By Sherif A. Tawfik,Revised By LiMing, 2009-12-29,%,函数调用形式,x,fval,exitflag=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger),%,函数求解如下形式的整数规划问题,%min f*x,%subject to,% A*x=b,% Aeq*x=beq,% lb=xTolXInteger); %,该条件表示,x0(M),不是整数,%,如果都是整数,if isempty(ind) exitflag=1;,%,如果当前的解优于已知的最优解，则将当前解作为最优解,if fval0flag,br_var=tempbr_var;,br_value=tempbr_value;,flag=temp_flag;,end,end,if isempty(A) r c=size(Aeq);,else r c=size(A);,end,一般整数规划问题的MATLAB求解%程序运行至此，说明松弛线,一般整数规划问题的,MATLAB,求解,%,第,1,个子问题的设置,添加约束条件,Xi=ceil(Xi),，,i,即为上面找到的最接近整数的非整数设计变量的序号,A2=A;zeros(1,c);,A2(end,br_var)=-1;,b2=b;-ceil(br_value);,%,分枝后的第一个子问题的递归求解,x1,fval1,exitflag1,bound1=rec_BranchBound(f,A1,b1,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);,exitflag=exitflag1;,if exitflag10 & bound10 & bound2bound,exitflag=exitflag2;,xx=x2;,fval=fval2;,bb=bound2;,end,一般整数规划问题的MATLAB