整数线性规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,整数规划,(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,个时段里该公司可动用的资金是,b,i,，,2,、,第,j,项投资计划所需要的资金是,a,ij,能够得到的利润是,c,ij,。,问该公司如何选择投资计划，使,m,个时段内的总利润最大,.,解：设,x,ij,表示在第,i,个时段内对第,j,个投资计划的决策变量,即当,x,ij,=1,时，表示第,i,个时段内选中并执行第,j,个投资计划，当,x,ij,=0,时，表示第,i,时段内未选中第,j,个投资计划,.,因此,可以建立该投资问题的,数学模型,为：,例 工作分配问题,设某单位现有,n,个人员,A,1,A,2,A,n,来完成,n,项工作,B,1,B,2,B,n,。,按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员,A,i,做工作,B,j,的效率是,c,ij,。,问应如何分配，才使总效率最好,.,解：令,x,ij,表示对人员,A,i,完成工作,B,j,的决策变量,即,x,ij,=1,表示分配,A,i,干工作,B,j,，,x,ij,=0,表示不分配,A,i,干工作,B,j,。,按问题要求，建立该问题的数学模型为：,线性规划（,LP,）,的任一整数可行解都是整数规划（,IP,）,的一个可行解，显然（,IP,）,的所有解（包括可行解）对应于（,LP,）,的整数可行解。,当（,LP,）,的最优解不是一个整数解时，一般情况下不可以通过对非整数解进行“四舍五入”、“凑整法”得出（,IP,）,问题的最优解。,整数线,性规划及其松弛问题，从解的特点上来说，二者之间既有密切的联系，又有本质的区别,.,进一步地，如果（,LP,）,的最优解是一个整数解，那么，这个解也一定是（,IP,）,问题的最优解。,一般情况下，（,LP,）,的最优解不会恰好是一个整数解，自然就不是（,IP,）,的最优解，（,IP,）,的最优值不会优于（,LP,）,的最优值,.,3,、关于整数规划的解,例如：求下列整数规划的最优解,解：在先不考虑“,x,1,x,2,是整数”的条件下，对相应的线性规划问题易由图解法得出最优解是：,X,=（3.25,2.5）,通过凑整法，可以得出,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,时，可以类似于不平衡运输问题建立模型的方法，增加虚拟人员或虚拟工作。,当,m,n,时，由于虚拟工作无须人员去做，对于极小化问题，可设其的效率为,0,；对于极大化问题，可设其效率是一个充分大的正数,M,。,当,m,z,2,，,故令,所以,.,B,1,:,x,1,=4,x,2,=2.10,z,1,=349,B,2,:,x,1,=5,x,2,=1.57,z,2,=341,由于,z,1,z,2,，,故先对,B,1,进行,分解,。对,B,1,增加条件,得：,B,3,:,增加条件,x,2,2;B,4,:,增加条件,x,2,3.,解,B,3,B,4,得,:B,3,:,x,1,=4,x,2,=2,z,3,=,340,B,4,:,x,1,=1.41,x,2,=3,z,4,=327,定界,:340,z*341,注,:B,4,不用分解，因,z,4,=327,，,B,4,被,剪枝,.,B,1,分解,B,2,得,:B,5,:,增加条件,x,2,1;B,6,:,增加条件,x,2,2.,解得：,B,5,：,z,5,=308.,B,6,：,无可行解,.,于是,B,3,的解,x,1,=4,x,2,=2,是原问题的最优整数解，,z*=340.,B,2,:,x,1,=5,x,2,=1.57,z,2,=341,340,z*341,定界,:340,z*340,问题,B,0,x,1,=4.81,x,2,=1.82,Z,0,=356,问题,B,1,x,1,=4,x,2,=2.1,Z,1,=349,问题,B,2,x,1,=5,x,2,=1.57,Z,2,=341,问题,B,3,x,1,=4,x,2,=2,Z,3,=340,问题,B,4,x,1,=1.42,x,2,=3,Z,4,=327,问题,B,5,x,1,=5.44,x,2,=1,Z,5,=308,问题,B,6,无可行解,x,1,4,x,1,5,x,2,2,x,2,3,x,2,1,x,2,2,340,z*341,340,z*340,分支树：,问题,B,0,x,1,=4.81,x,2,=1.82,Z,0,=356,问题,B,1,x,1,=4,x,2,=2.1,Z,1,=349,问题,B,2,x,1,=5,x,2,=1.57,Z,2,=341,问题,B,3,x,1,=4,x,2,=2,Z,3,=340,问题,B,4,x,1,=1.42,x,2,=3,Z,4,=327,问题,B,5,x,1,=5.44,x,2,=1,Z,5,=308,问题,B,6,无可行解,x,1,4,x,1,5,x,2,2,x,2,3,x,2,1,x,2,2,0 1 2 3 4 5 6 7 8 9 10,x,1,x,2,1,2,3,4,5,6,7,（,4,，,2,）,B,0,B,1,B,2,B,3,B,4,B,6,B,5,图解示意：,1,、概述,匈牙利法是用来解决人员分配问题的一个解法。,1955,年，库恩（,W.W.Kuhn),利用匈牙利数学家康尼格（,D.Knig),的一个定理构造了这个解法，故称为,匈牙利法,。,人员分配问题,：设某单位现有,n,个人员,A,1,A,2,A,n,来完成,n,项工作,B,1,B,2,B,n,。,按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员,A,i,做工作,B,j,的效率是,c,ij,。,问应如何分配，才使总效率最好。,四、,指派问题及匈牙利法,令,x,ij,表示对人员,A,i,完成工作,B,j,的决策变量,表示分配,A,i,干工作,B,j,表示不分配,A,i,干工作,B,j,按问题要求，建立该问题的数学模型为：,这就是一般分配问题的数学模型,.,此模型也可以看成一个特殊的,运输问题,，如果用表上作业法得出的一个最优解又满足“,x,ij,=0,1”,的条件，这个解也是分配问题的最优解。用表上作业法求解的过程往往出现退化情况。,注：人员分配问题有各种提法。,如果完成任务的效率表现为,资源的消耗,，则所谓的效率最好是指消耗的资源最少，分配问题就是一个最小化问题；,如果完成任务的效率表现为,生产效率,的高底，则分配问题就是一个最大化问题。,所有分配问题可以建立相同的数学模型,.,2,、相关概念,a,、,0,-1,变量及其应用,如前所述,若变量只能取值,0,或,l,，,则称其为,0-1,变量,.,0-1,变量作为逻辑变量，常被用来表示系统是否处于某个待定状态或者决策时是否取某个待定方案,.,例如,当决策取方案,P,时,当决策不取方案,P,时,五、,0-1,型整数规划,当问题含有多项要素，而每项要素皆有两种选择时，可用一组,0-1,变量来描述。,一般地，设问题有有限项要素,E,l,E,2,E,n,。,其中每项,E,j,有两种选择 ，,(,j,1,2,n,),，,则可令,那么,向量,(,x,1,x,2,x,n,),T,就描述了问题的特定状态或方案，即,若,E,j,选择,若,E,j,选择,例,1,含有相互排斥的约束条件的问题,在例中，设备台时的约束条件为,现在假设还有一种新的加工方式，相应的设备台时约束变成,如果只能从两种加工方式中选择一种，那么，上两式就成为两个相互排斥的约束条件。,为了统一在一个问题中，引入,0-1,变量,若采用原加工方式,若不采用原加工方式,和,若采用新加工方式,若不采用新加工方式,于是，相互排斥的约束条件,(1),和,(2),可用下列三个约束条件统一起来,:,例,2,固定费用问题,有三种资源被用于生产三种产品。资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。,单耗量 产品,资源,资源量,A,2,4,8,500,B,2,3,4,300,C,1,2,3,100,单件可变费用,4,5,6,固定费用,100,150,200,单件售价,8,10,12,解 总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。建模碰到的因难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生。下面借助,0-1,变量解决这个困难。,设,x,j,是第,j,种产品的产量，,j,1,2,3,；,再设,若生产第,j,种产品（即,x,j,0,）,若不生产第,j,种产品（即,x,j,=0,）,j,1,2,3.,则问题的整数规划模型是,其中,M,j,为,x,j,的某个上界。例如，根据第,3,个约束条件，可取,M,1,100,，,M,2,50,，,M,3,34,。,如果生产第,j,种产品，则其产量,x,j,0,。,此时，由约束条件 知,y,j,=1,。,因此，相应的固定费用在目标函数中将被考虑。,如果不生产第,j,种产品，则其产量,x,j,=0,。,此时,由约束条件 可知,y,j,可以是,0,，也可以是,1,。但,y,j,=1,不利于目标函数的最大化，因而在问题的最优解中必然是,y,