整数线性规划ppt课件.ppt

整数规划(Integer Programming),王广民中国地质大学 经济管理学院,1、概述整数规划（Integer Programming，简记IP)主要是指整数线性规划,是近二、三十年来发展起来的数学规划当中的一个重要分支，讨论整数规划对研究管理问题有重要意义， 比如项目投资问题、人员分配问题等都可以化为一个整数规划问题（因为如人员分配等的一些问题显然不可能出现小数或者分数的情况）,可分为：纯整数规划（所有变量都限制为整数）混合整数规划（一部分变量限制为整数）0-1规划（所有变量的取值都限制为0或1）,一、整数规划问题及其数学模型,所谓整数规划是指具有下列模型的线性规划问题,其中A矩阵、b、c向量中所有的元素数都是整数或有理数.,(1)、模型阐述,2、整数规划问题的模型,其实，如果不考虑（IP）问题中“X是整数”的条件，则整数规划问题仍可看成一个一般的线性规划（LP）问题：,称为该整数规划问题的松弛问题(slack Problem).,(2)、整数规划的例子,例 投资问题设某公司在m个时段里有n项投资计划，由于资金限制不能全部进行。已知1、第 i 个时段里该公司可动用的资金是bi，2、第 j 项投资计划所需要的资金是aij ,能够得到的利润是cij。问该公司如何选择投资计划，使m个时段内的总利润最大.,解：设xij表示在第i个时段内对第j个投资计划的决策变量,即当xij =1时，表示第i 个时段内选中并执行第j个投资计划，当xij =0时，表示第i 时段内未选中第j个投资计划.因此,可以建立该投资问题的数学模型为：,例 工作分配问题设某单位现有n个人员A1,A2An来完成n项工作B1, B2, Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好.,解：令xij表示对人员Ai完成工作Bj的决策变量,即xij =1表示分配Ai干工作Bj， xij= 0表示不分配Ai干工作Bj。按问题要求，建立该问题的数学模型为：,线性规划（LP）的任一整数可行解都是整数规划（IP）的一个可行解，显然（IP）的所有解（包括可行解）对应于（LP）的整数可行解。,当（LP）的最优解不是一个整数解时，一般情况下不可以通过对非整数解进行“四舍五入”、 “凑整法”得出（IP）问题的最优解。,整数线性规划及其松弛问题，从解的特点上来说，二者之间既有密切的联系，又有本质的区别.,进一步地，如果（LP）的最优解是一个整数解，那么，这个解也一定是（IP）问题的最优解。,一般情况下，（LP）的最优解不会恰好是一个整数解，自然就不是（IP）的最优解， （ IP）的最优值不会优于（LP）的最优值.,3、关于整数规划的解,例如 ：求下列整数规划的最优解,通过凑整法，可以得出4种组合(4,3),(4,2),(3,3),(3,2)。,(4,3),(4,2),(3,3)都不是可行解，(3,2)虽是可行解，但不是最优解,满足问题的整数最优解是(4,1) ，最优值是14。而最优解(4,1)并不是相应线性规划的可行域的顶点。,结论：直接利用图解法（或者甚至利用单纯形法）无法直接找出整数规划的最优解。,1、求解思路割平面法是求解整数规划的最早提出的一个方法。基本思想是：首先利用单纯形法（或者其它方法）求解整数规划的松弛线性规划；经过判断，如果达不到变量的整数条件，则针对某一个非整变量增加特定割平面，把LP问题中对该变量的非整数部分给去除掉，保留了全部有整数解的部分，同时经过切割后的可行域其凸性质不改变。逐次反复上面的过程，只要整数规划问题有最优整数解，则必定可以在经过若干次的切割后的凸可行域的顶点中找到最优解。,二、Gomory割平面法,割平面法在1958年由高莫瑞(R.E.Gomory)首先提出，故又称Gomory割平面法。在割平面法中每次增加的用于“切割”的线性约束称为割平面约束或Gomory约束。构造割平面约束的方法很多，介绍最常用的一种，它可以从相应线性规划的最终单纯形表中直接产生。实际解题时，经验表明若从最优单纯形表中选择具有最大小(分)数部分的非整分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数。,(1)、如果要求目标的最大值,令,其中,效率矩阵可变为B，将分配问题转换为一个极小化问题,4、几点说明,(2)、如果分配问题中，人员数 m 不等于工作数 n 时，可以类似于不平衡运输问题建立模型的方法，增加虚拟人员或虚拟工作。当mn时，由于虚拟工作无须人员去做，对于极小化问题，可设其的效率为 0；对于极大化问题，可设其效率是一个充分大的正数M。 当mn 时，也可类似处理。,1、分枝定界法概述,直接通过枚举法求整数最优解毫无实用应用价值.分枝定界法是一种隐枚举法或部分枚举法，它不是一种有效算法，是枚举法基础上的改进。它是一种“巧妙”地枚举整数规划问题的可行解的思想来设计算法的，其关键步骤是分枝和定界。,分枝定界法可用于解纯整数或混合的整数规划问题.本世纪六十年代初由Land Doig 和Dakin等人提出.由于这种方法灵活且便于用计算机求解，所以现在它是解整数规划的主要方法。,三、分枝定界法,下面将LP的可行域分成子区域（称为分枝），逐步减小 ，增大 ，最终达到解决z*。,分枝定界法的理论基础：,对于求最大的整数规划，上界是通过松弛方法得到，作用是判断最优，下界找可行解得到，作用是剪枝。上界定不好难以得到最优解，下界定不好难以剪枝，仅仅是多计算几步。对于不满足整数约束的变量就行分枝；如何分枝和定界上下界的作用,分枝,给定整数规划问题IP,去掉“X为整数向量”的约束,得到相应的线性规划问题P0,（1）相应子问题Pi的最优解是整数解；,（2）相应子问题Pi无可行解.,此时称点Pi为分枝数的树叶.,若 不满足整数要求，设分量 不是整数，则按照,直到问题Pi的解是下面两种情况之一而结束.,分枝,定界：,注：一般是选择不符合整数要求的最小的变量进行分枝.,2、算例,解：首先不考虑整数条件，解相应的线性规划问题B0，得到最优解为：,显然这个解不满足整数条件，这时的最优解356就成为IP问题的上界。,B0：,记,而,显然是IP问题的一个整数可行解,此时,即,因 x1=4.81,对问题B0增加两个约束条件,将问题B0分解为两个子问题B1和B2(分枝),分别解B1,B2得B1: x1=4, x2=2.10, z1=349B2: x1=5, x2=1.57, z2=341,B1,B2,定界：由于z1 z2，故令 ,所以 .,B1: x1=4, x2=2.10, z1=349B2: x1=5, x2=1.57, z2=341,由于z1 z2，故先对B1进行分解。对B1增加条件,得：B3:增加条件 x2 2; B4:增加条件 x2 3.,解B3,B4得: B3: x1=4, x2=2, z3=340 B4: x1=1.41, x2=3, z4=327,定界: 340 z* 341,注: B4不用分解，因 z4=327，B4被剪枝.,B1,分解B2得: B5: 增加条件 x2 1; B6: 增加条件 x2 2.解得： B5：z5=308 . B6：无可行解.,于是B3的解 x1=4, x2=2 是原问题的最优整数解 ，z*=340.,B2: x1=5, x2=1.57, z2=341,340 z* 341,定界: 340 z* 340,340 z* 341,340 z* 340,分支树：,0 1 2 3 4 5 6 7 8 9 10 x1,x2,1,2,3,4,5,6,7,（4，2）,B0,B1,B2,B3,B4,B6,B5,图解示意：,1、概述,匈牙利法是用来解决人员分配问题的一个解法。1955年，库恩（W.W.Kuhn)利用匈牙利数学家康尼格（D.Knig)的一个定理构造了这个解法，故称为匈牙利法。,人员分配问题：设某单位现有n个人员A1,A2An来完成n项工作B1,B2,Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好。,四、指派问题及匈牙利法,令xij表示对人员Ai完成工作Bj的决策变量,表示分配Ai干工作Bj,表示不分配Ai干工作Bj,按问题要求，建立该问题的数学模型为：,这就是一般分配问题的数学模型.,此模型也可以看成一个特殊的运输问题，如果用表上作业法得出的一个最优解又满足“xij =0,1”的条件，这个解也是分配问题的最优解。用表上作业法求解的过程往往出现退化情况。,注：人员分配问题有各种提法。如果完成任务的效率表现为资源的消耗，则所谓的效率最好是指消耗的资源最少，分配问题就是一个最小化问题；如果完成任务的效率表现为生产效率的高底，则分配问题就是一个最大化问题。所有分配问题可以建立相同的数学模型.,2、相关概念,a、0-1变量及其应用,如前所述,若变量只能取值0或l，则称其为0-1变量.,0-1变量作为逻辑变量，常被用来表示系统是否处于某个待定状态或者决策时是否取某个待定方案.例如,当决策取方案 P 时当决策不取方案 P 时,五、0-1型整数规划,当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述。一般地，设问题有有限项要素 El,E2,En。其中每项 Ej 有两种选择 ， ,( j1,2,n )，则可令,那么,向量 (x1 , x2 , , xn)T 就描述了问题的特定状态或方案，即,若 Ej 选择若 Ej 选择,例1 含有相互排斥的约束条件的问题,在例中，设备台时的约束条件为,现在假设还有一种新的加工方式，相应的设备台时约束变成,如果只能从两种加工方式中选择一种，那么，上两式就成为两个相互排斥的约束条件。,为了统一在一个问题中，引入0-1变量,若采用原加工方式若不采用原加工方式,和,若采用新加工方式若不采用新加工方式,于是，相互排斥的约束条件(1)和(2)可用下列三个约束条件统一起来:,例2 固定费用问题,有三种资源被用于生产三种产品。资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。,解 总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。建模碰到的因难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生。下面借助0-1变量解决这个困难。,设 xj 是第 j 种产品的产量，j1,2,3；再设,若生产第 j 种产品（即xj 0）若不生产第 j 种产品（即xj = 0）,j1,2,3.,则问题的整数规划模型是,其中 Mj 为 xj 的某个上界。例如，根据第3个约束条件，可取M1100，M250，M334。,如果生产第 j 种产品，则其产量 xj 0。此时，由约束条件 知 yj =1。因此，相应的固定费用在目标函数中将被考虑。如果不生产第 j 种产品，则其产量 xj =0 。此时,由约束条件 可知 yj 可以是0，也可以是1。但 yj =1 不利于目标函数的最大化，因而在问题的最优解中必然是 yj =0，从而相应的固定费用在目标函数中将不被考虑。,b、0-1型整数规划的解法,0-1型整数规划是一种特殊的整数规划。若含有 n 个变量，则可以产生 2n 个可能的变量组合。当 n 较大时，采用完全枚举法解题几乎是不可能的。已有的求解0-1型整数规划的方法一般都属于隐枚举法。,在2n个可能的变量组合中，往往只有一部分是可行解。只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其它约束条件是否可行。对于可行解，其目标函数值也有优劣之分。若已发现一个可行解，则根据它的目标函数值可以产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性。在以后的求解过程中，每当发现比原来更好的可行解则以此替换原来的过滤条件。上述这些做法，都可以减少运算次数，使最优解能较快地被发现.,例3 求解0-1型整数规划,求解过程可以列表表示,1,0,z8,z0,5,z5,-2,3,3,8,6,谢 谢,