求解整数规划常用的方法有分枝定界法和割平面法这两种

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,求解整数规划常用的方法有分枝定界法和割平面法。,这两种方法的共同特点：通过增加附加约束，使,整数最优解最终成为线性规划的一个顶点，于是整,个问题就可使用单纯形法找到这个整数最优解；它,们的相异之处是附加约束条件的选取原则及方法不,同。,上周内容回顾,基本思想,割平面法的基础仍然是用解线性规划的方法去解整数规划问题。首先不考虑变量为整数这一条件，但增加线性约束条件（几何术语，称为,割平面,），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解。切除的结果使整数解可能成为顶点。,关键：,如何找到割平面约束方程,，使切割后最终得到这样的可行解域，它的一个整数坐标的顶点恰好是问题的最优解。,整数线性规划模型的求解,割平面法,（1）由单纯形最终表得到决策变量非整数解方程，设为,其中,b,i,是基变量的非整数解。,（2）将,a,ik,和,b,i,分解为整数,N,和正真分数,f,两部分之和,将（2）代入(1)中,然后将整数置于方程左边，分数置于方程右变，即,(3)得割平面方程,寻找割平面方程,基本思想,通过分枝枚举来寻找最优解。首先不考虑对变量的整数要求，求解相应的线性规划模型，如求得最优解不符合整数要求，则把原模型分解为两部分，每一部分都增加新的约束条件以减少相应线性规划模型的可行域。通过不断分解，逐步逼近满足要求的整数最优解，在这个过程中包括了“分枝”和“定界”两个关键步骤。,整数线性规划模型的求解,分枝定界法,（,1,）求解相应的线性规划模型，确定初始上、下界。,（,a,）,LP,无解，则,IP,无解，停止计算。,（,b,）,LP,的最优解满足整数要求，即为,IP,的最优解，计算完毕。,（,c,）,LP,的最优解中有非整数分量，其目标函数值是,IP,的初始上界。,（,2,）分枝并求解,在非整数最优解中任选一个不满足整数约束条件的变量,x,j,=b,j,，以,b,j,表示不大于,b,j,的最大整数，构造两个约束条件,x,j,b,j,，和,x,j,b,j,+1,将这两个约束条件分别加到,LP,中，构成两个新的线性规划分支，求解它们。,分枝定界法步骤：,（,3,）定界,上界：以每个后继问题为一分支，标明求解的结果，与其他问题解的结果比较，找出目标函数值最大者作为,IP,新的上界,z,。,下界：从已符合整数条件的分支中，找出目标函数最大者作为新的下界，若无符合条件者，则取,z,=0,。,（,4,）比较和剪枝,（,a,）该枝无可行解；,（,b,）该枝已得到整数最优解；,（,c,）该枝得到非整数最优解，且目标函数值小于,z,。,在求解的各分支的线性规划中，若其值大于,z,，即,z*,z,但不符合整数条件则返回（,2,）继续分,枝直到,z,=z*= z,。,有,n,项任务，恰好,n,个人承担，第,i,人完成第,j,项任务的花费(时间或费用等)为,c,ij,，,如何分派使总花费最省？,第,j,项工作由一个人做,第,i,人做一项工作,分派第,i,人做第,j,项工作,不分派第,i,人做第,j,项工作,8.6,指派问题（,Assignment Problem,）,人员,工作,A,B,C,D,甲,9,17,16,7,乙,12,7,14,16,丙,8,17,14,17,丁,7,9,11,9,引入决策变量,x,ij,【例,8-7】,有,4,个工人，要分别指派他们完成,4,项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少？,MinZ=9,x,11,+17,x,12,+16,x,13,+7,x,14,+12,x,21,+7,x,22,+14,x,23,+16,x,24,+,8,x,31,+17,x,32,+14,x,33,+17,x,34,+7,x,41,+9,x,42,+11,x,43,+9,x,44,s.t.,x,11,+,x,12,+,x,13,+,x,14,= 1 (,甲只能干一项工作,),x,21,+,x,22,+,x,23,+,x,24,= 1 (,乙只能干一项工作,),x,31,+,x,32,+,x,33,+,x,34,= 1 (,丙只能干一项工作,),x,41,+,x,42,+,x,43,+,x,44,= 1 (,丁只能干一项工作,),x,11,+,x,21,+,x,31,+,x,41,= 1 ( A,工作只能一人干,),x,12,+,x,22,+,x,32,+,x,42,= 1 ( B,工作只能一人干,),x,13,+,x,23,+,x,33,+,x,43,= 1 ( C,工作只能一人干,),x,14,+,x,24,+,x,34,+,x,44,= 1 ( D,工作只能一人干,),x,ij,为,0-1,变量,，,i,j,= 1,2,3,4,指派问题是0-1规划问题。,因每个人仅能承担一项任务，每项任务也只能分派给一个人，因此上述问题的线性规划模型也可写为：,满足该约束条件的可行解可写成矩阵形式,分派问题是线性规划，又是运输问题。,定理：从(,c,ij,),矩阵的每行(或每列)减或加一个常数,u,i,(v,j,),构成新矩阵,， ，,则对应,的(,x,ij,),最优解与原问题(,c,ij,),的最优解相同。,-,4,-,2,-,3,-,3,-,1,(c,ij,),例如：,(c,ij,),利用这一性质，可以使原系数矩阵(,c,ij,),变换成含有,很多0元素的新系数矩阵 ，而最优解保持不变。,匈牙利法是针对,目标要求极小化问题,提出的,基本原理：为了实现目标极小，在系数矩阵元素,c,ij,0,条件下，如果能使矩阵具有一组处于不同行不同列的零元素,c,ij,0,，画上圈符号“”，表示对应该元素的决策变量,x,ij,=1,，未画圈元素对应的决策变量,x,ij,0,，那么目标的数值,z,0,为最小，这样的组合解,x,就是最优解。所以匈牙利法又称画圈法。,画圈法的关键是如何实现系数矩阵具有一组处于,不同行又不同列的,0,元素,（,独立零,），并保证所画的圈的个数等于矩阵的阶数。,【例,8-8】,用匈牙利算法求解下面的指派问题，使得,总的费用最小。,匈牙利算法的步骤：,（1）变换系数矩阵，使其每行每列都出现0元素。首先每行减去该行最小数，再每列减去该列最小数。,(2)进行试分派，寻求最优解。,经第（1）步变换后，系数矩阵每行每列都已有了0元素，但需找出,n,个独立的0元素，为此，按下列的步骤进行。,-,4,-,2,-,3,-,3,-,1,从只有一个0元素的行（列）的0元素开始，给这个0元素加圈，即作，这表示对这行所代表的人 ，只有一种任务可分派。然后划去所在列（行）的其它0元素 ，记作,，这表示这列所代表的任务已分派完，不必再考虑别人了。,给只有一个0元素的列(行)的元素加圈，记作；然后划去所在的行的其它0元素，即作,。,若仍有没有圈出或划掉的0元素，且同行（列）的0元素至少有2个，则找出0元素的闭回路，任选一个0元素加圈，破闭回路，直到所有0元素都已圈出和划掉为止。列如：,反复进行、 两步，直到所有0元素都被圈出或划掉为止。转第步。,若元素的数目等于矩阵的阶数，那末，这分派问题的最优解已经得到，否则转第（3）步。,（3）作最少的直线覆盖所有的0元素，以确定该系数矩阵能找到最多的独立0元素。为此按以下步骤进行：,对没有的行打号；,对已打的行中所有0元素所对应的列打号；,再对打有的列中元素所对应的行打号；,重复、 ，直到得不出新的打号的行、列为止。,对没有打号的行画一横线，有打号的列画一纵线，这就得到覆盖所有的0元素的最少直线数。,做最少直线,（4） 在未被直线覆盖的部分中找出最小元素，然后在打行各元素中都减去这最小元素，而在打列的各元素都加上这最小元素。这样得到新的系数矩阵（它的最优解和原问题相同）。,调整后，再试指派,指派结果：,第,1,个人做第,3,个工作；第,2,个人做第,1,个工作,第,3,个人做第,2,个工作；第,4,个人做第,4,个工作,调整后，再试指派,【例,8-9】6,个人完成,4,项任务，由于个人的技术专长不同，他们完成,4,项任务所获得的收益如表所示，且规定每人只能做一项工作，一项工作只能由一个人来完成，试求总收益最大的分配方案。,A,B,C,D,1,3,5,4,5,2,6,7,6,8,3,8,9,8,10,4,10,10,9,11,5,12,11,10,12,6,13,12,11,13,运用匈牙利法求解分派问题有以下三个条件：,（1）目标函数为求极小值型；,（2）目标系数矩阵为方阵；,（3）目标系数矩阵,对于不属于上述三个条件的分派问题，可以先将条件进行转化，再求解。,A,B,C,D,E,F,1,3,5,4,5,0,0,2,6,7,6,8,0,0,3,8,9,8,10,0,0,4,10,10,9,11,0,0,5,12,11,10,12,0,0,6,13,12,11,13,0,0,非平衡的指派问题，设两项虚任务，其收益为,0,，化为平衡指派问题。,用匈牙利法求解,求最大值问题转化为求最小值问题，利用下式,即,-,(-5),-,(-8),-,(-10),-,(-11),-,(-12),-,(-13),最优解：第,3,个人做,D,工作,第,4,个人做,C,工作,第,5,个人做,B,工作,第,6,个人做,A,工作,最大收益为：,10+9+11+13=43,第,9,章 目标规划,9.1,目标规划问题的提出及其数学模型,9.2,线性目标规划的基本概念及其数学模型,9.3,目标规划的图解法,9.4,目标规划的单纯形法,9.5,目标规划应用举例,目标规划问题的提出,（,1,）线性规划只研究在满足一定条件下,单一目标函数取得最优解,而在企业管理中,经常遇到多目标决策问题,如拟订生产计划时,不仅考虑总产值,同时要考虑利润,产品质量和设备利用率等。这些指标之间的重要程度,(,即优先顺序,),也不相同,有些目标之间往往相互发生矛盾；,（,2,）线性规划最优解存在的前提条件是可行域为非空集,否则,线性规划无解。然而实际问题中,有时可能出现资源条件满足不了管理目标的要求的情况,此时,仅做无解的结论是没有意义的；,9.1,目标规划问题的提出及其数学模型,（,3,）线性规划问题中的约束条件是不分主次,同等对待的,是一律要满足的,“,硬约束,”,而在实际问题中,多个目标和多个约束条件并不一定是同等重要的,而是有轻重缓急和主次之分的；,（,4,）线性规划的最优解可以说是绝对意义下的最优,但很多实际只需,(,或只能,),找出满意解就可以。,目标规划是解决多目标决策问题的方法之一。,是针对线性规划单目标、单一最优解的局限性以及,刚性约束而发展起来的。,【,例题,】,某公司分厂用一条生产线生产两种产品,A,和,B，,每周生产线运行时间为60小时，生产一台,A,产品需要4小时，生产一台,B,产品需要6小时。根据市场预测,A、B,产品平均销售量分别为每周9、8台,它们销售利润分别为12、18万元。在制定生产计划时经理考虑下述4项目标：,首先，产量不能超过市场预测的销售量；,其次，工人加班时间最少；,第三，希望总利润最大；,最后，要尽可能满足市场需求,当不能满足时,市场认为,B,产品的重要性是,A,产品的2倍。,建立这个问题的数学模型,若把总利润最大看作目标，而把产量不能超过市场预测的销售量、工人加班时间最少和要尽可能满足市场需求的目标看作约束，则可建立一个单目标线性规划模型。,设决策变量,x,1,，x,2,分别为产品,A，B,的产量,容易求得上述线性规划的最优解为(9,4),T,到 (3,8),T,所在线段上的点，最优目标值为,Z,*,= 180,即可选方案有多种。,在实际上，这个结果并非完全符合决策者的要求，它只实现了经理的第一、二、三条目标，而没有达到最后的一个目标。,第四个目标为:,x,1,9，,x,2,8,；,要尽可能满足市场需求, 当不能满足时, 市场认为,B,产品的重要性是,A,产品的2倍。,第三个目标为: 希望总利润最大，要表示成不等式需要找到一个目标下界，这里可以估计为252（=12,9+18,8），于是有：,12,x,1,+ 18,x,2,252,；,第二个目标为:,4,x,1,+ 6,x,2,60,（工人加班时间最少）；,如果把第4个目标表示为不等式，仍设决策变量,x,1,，x,2,分别为产品,A，B,的产量，则,第一个目标为:,x,1,9,，x,2,8,（产量不能超过市场预测的销售量）；,要实现全体目标是不可能的。,线性目标规划和线性规划比较，具有下面的特点,（,1,）线性规划只讨论单目标线性函数在一组线性约束条件下的最优值问题，而目标规划能统筹兼顾处理实际问题中出现的多目标关系，求得切合实际的最优解。,（,2,）线性规划是求最优解，而目标规划是求满意解。,（,3,）线性规划将约束条件看出同等重要，而目标规划将依实际情况将约束条件主次有别地进行求解。,【,例,9-3,】,某工厂生产,甲,、,乙,两种产品，已知有关数据如下表：试求获利最大的生产方案,.,甲,乙,拥有量,原材料,(kg),2,1,11,设备,(k,1,),1,2,10,利润,/,千元,8,10,用图解法求得最优决策为,:,x,1,*,=4,x,2,*,=3,Z=62,解：设,x,1,，x,2,分别表示,生产,A,、,B,两种产品的生产量，,则,数学模型为：,9.2,线性目标规划的基本概念及其数学模型,实际上工厂正在作决策时要考虑市场等一系列,其他条件，如：,1.,根据市场信息产品,A,的销售量有下降的趋势，故,考虑产品,A,的产量不大于产品,B,；,2.,超过计划供应的原材料时，需要高价采购，使,成本增加；,3.,应尽可能充分利用设备，但不希望加班；,4.,应尽可能达到并超过计划利润指标,56,千,元。,产品决策时，为多目标决策。,仍设决策变量,x,1,， x,2,分别为产品,A，B,的产量，则该厂决策者考虑,4,个目标，用数学表达式表示为：,下面引入与建立目标规划数学模型有关的概念,产品,A,的产量不大于产品,B,不超过计划供应的原材料,充分利用设备,达到并超过计划利润指标,56,元,（,1,）目标值（理想值）,预先给定的某个目标函数的期望值，如：,右端值是对目标所赋予的期望值,（,2,）,正、负偏差量,实际值与目标值之间的差异。,设,x,1,x,2,为决策变量，,d,+,、,d,-,为正、负偏差变量。,d,+,：实际值超过目标值部分；,d,-,：实际值未达到目标值部分；,恒有,d,+,d,-,=0,目标约束：,目标规划特有的，当,把约束右端项看作要努力追求的目标值，但允许发生正式负偏差，用在约束中加入正负偏差变量来表示，于是称它们是软约束,（,3,）目标约束,和绝对约束,绝对约束：必须严格满足的等式约束和不等式约束如在线性规划问题中考虑的约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束如生产甲，乙产品所需原材料数量有限制，如果无法从其它渠道予以补充，则构成绝对约束。,（,4,）优先因子（优先等级）与权系数。,目标的主次。要求第一位达到的目标赋予优先因子,p,1,，次位的目标赋予优先因子,p,2,规定,p,R,p,R+1,，,R=1,2, ,K.,首先保证,p,1,级目标的实现，这时可不考虑次级目标。,p,2,级目标的实现是在实现,p,1,级目标的基础上,若要区别具有相同优先因子的两个目标的差别，,决策者可根据具体情况分别赋予它们不同的权系数,w,j,。,权系数由决策者按具体情况而定。,比如,【,例,9-3】,决策者考虑的首先是甲产品的产量不能超过乙产品的产量；赋予优先级为,p,1,其次是充分利用设备有效机时，不加班；,赋予优先级为,p,2,。,（,5,）目标规划的目标函数。,目标规划的目标函数（准则函数）是按各自目标,约束的正、负偏差变量和赋予相应的优先因子而构造,的。每当一目标值确定后，决策者的要求是,尽可能缩,小偏离目标值,，因此目标规划的目标函数只能是,minZ=f(d,+,d,-,),其基本形式有三种：,要求恰好达到目标值，即正、负偏差变量都要,尽可能地小，这时，,minZ=d,+,+d,-,要求不超过目标值，即允许达不到目标值，就是,正偏差变量要尽可能地小，这时，,minZ=d,+,要求超过目标值，即超过量不限，就是负偏差,变量要尽可能地小，这时，,minZ=d,-,对每一个具体目标规划问题，可根据决策者的要求和赋予各目标的优先因子来构造目标函数。,对于,【,例,9-3】,决策者在原材料供应受到严格限制的基础上。考虑：,首先是甲产品的产量不能超过乙产品的产量；,赋予优先级为,p,1,其目标函数可表示为,minp,1,(d,1,+,),其次是充分利用设备有效机时，不加班，希望设备台时用完；,赋予优先级为,p,2,其目标函数可表示为,minp,2,(d,2,-,+ d,2,+,),再次是利润额不小于,56,千元，,赋予优先级为,p,3,其目标函数可表示为,minp,3,(d,3,-,),（,6,）目标规划的数学模型,按决策者所要求的分别赋予这三个目标,p,1,、,p,2,、,p,3,优先因子，模型为,硬约束,可添上正负偏差变量变为软约束。,其偏差变量为第一优先级。,在目标规划中，无论是约束条件中的硬约束和,目标约束的软约束，均可通过添加正负偏差变量后,把所有约束均作为目标约束（软约束）来处理。,设有,L,个目标，,K,个优先级别，同一优先级中不同目标的正、负偏差变量的重要程度不同，并赋予不同的权系数,W,kl,+,、,W,kl,-,，,则目标规划的一般数学模型为：,软约束,建立目标规划的数学模型时，需确定目,标值,g,l,、,优先等级、权系数,w,i,等，具有一定的主观性和模糊性，,会随决策者的不同而不同。可用专家评定法给以量化。,目标规划的一般数学模型为,:,目标函数,目标约束,系统,(,绝对,),约束,非负约束,