整数线性规划

整数规划(IntegerProgramming)王广民中国地质大学经济管理学院[e-mail]1、概述整数规划（IntegerProgramming，简记IP)主要是指整数线性规划,是近二、三十年来发展起来的数学规划当中的一个重要分支，讨论整数规划对研究管理问题有重要意义，比如项目投资问题、人员分配问题等都可以化为一个整数规划问题（因为如人员分配等的一些问题显然不可能出现小数或者分数的情况）,可分为：纯整数规划（所有变量都限制为整数）混合整数规划（一部分变量限制为整数）0-1规划（所有变量的取值都限制为0或1）一、整数规划问题及其数学模型所谓整数规划是指具有下列模型的线性规划问题是整数XXbAXtsCXzIP0..max)(其中A矩阵、b、c向量中所有的元素数都是整数或有理数.(1)、模型阐述2、整数规划问题的模型其实，如果不考虑（IP）问题中“X是整数”的条件，则整数规划问题仍可看成一个一般的线性规划（LP）问题：0maxXbAXCXz称为该整数规划问题的松弛问题(slackProblem).(2)、整数规划的例子例投资问题设某公司在m个时段里有n项投资计划，由于资金限制不能全部进行。已知1、第i个时段里该公司可动用的资金是bi，2、第j项投资计划所需要的资金是aij,能够得到的利润是cij。问该公司如何选择投资计划，使m个时段内的总利润最大.解：设xij表示在第i个时段内对第j个投资计划的决策变量1execute0notexecuteijx即当xij=1时，表示第i个时段内选中并执行第j个投资计划，当xij=0时，表示第i时段内未选中第j个投资计划.因此,可以建立该投资问题的数学模型为：11max1,2,,..0,1mnijijijnijijijiijzcxaxbimstx例工作分配问题设某单位现有n个人员A1,A2……An来完成n项工作B1,B2,…Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好.解：令xij表示对人员Ai完成工作Bj的决策变量即xij=1表示分配Ai干工作Bj，xij=0表示不分配Ai干工作Bj。按问题要求，建立该问题的数学模型为：10ijx11maxmnijijijzcx11110,1nijjmijiijxxx线性规划（LP）的任一整数可行解都是整数规划（IP）的一个可行解，显然（IP）的所有解（包括可行解）对应于（LP）的整数可行解。当（LP）的最优解不是一个整数解时，一般情况下不可以通过对非整数解进行“四舍五入”、“凑整法”得出（IP）问题的最优解。整数线性规划及其松弛问题，从解的特点上来说，二者之间既有密切的联系，又有本质的区别.进一步地，如果（LP）的最优解是一个整数解，那么，这个解也一定是（IP）问题的最优解。一般情况下，（LP）的最优解不会恰好是一个整数解，自然就不是（IP）的最优解，（IP）的最优值不会优于（LP）的最优值.3、关于整数规划的解例如：求下列整数规划的最优解是整数2121212121,0,5.45.0143223xmaxzxxxxxxxxx解：在先不考虑“x1,x2是整数”的条件下，对相应的线性规划问题易由图解法得出最优解是：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)、如果要求目标的最大值ijzmaxijijxc令ijijcMb其中}max{ijcM效率矩阵可变为B，将分配问题转换为一个极小化问题'ijminzijijbx4、几点说明(2)、如果分配问题中，人员数m不等于工作数n时，可以类似于不平衡运输问题建立模型的方法，增加虚拟人员或虚拟工作。当mn时，由于虚拟工作无须人员去做，对于极小化问题，可设其的效率为0；对于极大化问题，可设其效率是一个充分大的正数M。当mn时，也可类似处理。1、分枝定界法概述直接通过枚举法求整数最优解毫无实用应用价值.分枝定界法是一种隐枚举法或部分枚举法，它不是一种有效算法，是枚举法基础上的改进。它是一种“巧妙”地枚举整数规划问题的可行解的思想来设计算法的，其关键步骤是分枝和定界。分枝定界法可用于解纯整数或混合的整数规划问题.本世纪六十年代初由LandDoig和Dakin等人提出.由于这种方法灵活且便于用计算机求解，所以现在它是解整数规划的主要方法。三、分枝定界法其基本思想是：设有最大化的整数规划问题IP，与它相关的线性规划问题为LP。从解问题LP开始，若其最优解不符合IP的整数条件，则LP的最优目标函数必定是IP的最优目标函数z*的上界，记作可行解必定是z*的下界，记作z，而IP的任意z下面将LP的可行域分成子区域（称为分枝），逐步减小，增大，最终达到解决z*。zz分枝定界法的理论基础：2112,(1)maxmax(max,max,,max)(2)maxmax(3)max,maxkjiikijxxxxijxxxxicxcxcxcxcxcxxcxcxcx若，则如果存在使得那么一定不在中对于求最大的整数规划，上界是通过松弛方法得到，作用是判断最优，下界找可行解得到，作用是剪枝。上界定不好难以得到最优解，下界定不好难以剪枝，仅仅是多计算几步。对于不满足整数约束的变量就行分枝；如何分枝和定界上下界的作用分枝给定整数规划问题IP为整数向量XXbAXXCzT0max去掉“X为整数向量”的约束,得到相应的线性规划问题P00maxXbAXXCzT的一个上界。是则的最优解，是设IPXCzPxT000分解为两个子问题则将不是整数，的某个分量若IPxxi00][00maxiixxXXbAXXTCz为整数向量1][00maxiixxXXbAXXTCz为整数向量][00maxiixxXXbAXXTCz为整数向量1][00maxiixxXXbAXXTCz为整数向量。，为相应的线性规划问题记21PP，与的最优解与分别求出2121XXPP枝；域就查清了，不要再分的一个下界，这个子将是是整数，则如果IPXCzXT1111][][22kkkkxxxx或如此继续下去。；和又分解为问题将432PPP（1）相应子问题Pi的最优解是整数解；（2）相应子问题Pi无可行解.此时称点Pi为分枝数的树叶.若不满足整数要求，设分量不是整数，则按照2X2kx直到问题Pi的解是下面两种情况之一而结束.分枝定界：以继续分枝。点称为活点，从活点可为死点，其余的剪枝，并称分枝，将无须再由的目标函数值均成立的子域上所有可行解则说明，数要求的最大目标值而此时所得到的满足整，，其最优值为个点假设分枝过程进行到某kkkmkTkkmkkPPPzzXCXPzzzP注：一般是选择不符合整数要求的最小的变量进行分枝.1212121212max4090975672070,0,integerzxxxxxxxxxx2、算例解：首先不考虑整数条件，解相应的线性规划问题B0，得到最优解为：1204.81,1.82,356xxz显然这个解不满足整数条件，这时的最优解356就成为IP问题的上界。B0：12121212max4090975672070,0zxxxxxxxx记0zz而120,0xx显然是IP问题的一个整数可行解,此时0zz即*0356z因x1=4.81,对问题B0增加两个约束条件114,5xx将问题B0分解为两个子问题B1和B2(分枝),分别解B1,B2得B1:x1=4,x2=2.10,z1=349B2:x1=5,x2=1.57,z2=341121212112max40909756720704,0zxxxxxxxxxB1121212112max40909756720705,0zxxxxxxxxxB2定界：由于z1z2，故令,所以.349z*0349zB1:x1=4,x2=2.10,z1=349B2:x1=5,x2=1.57,z2=341*0356z由于z1z2，故先对B1进行分解。对B1增加条件222,3xx得：B3:增加条件x22;B4:增加条件x23.解B3,B4得:B3:x1=4,x2=2,z3=340B4:x1=1.41,x2=3,z4=327定界:340z*341注:B4不用分解，因z4=327，B4被剪枝.121212112max40909756720704,0zxxxxxxxxx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=341340z*341定界:340z*340问题B0x1=4.81x2=1.82Z0=356问题B1x1=4x2=2.1Z1=349问题B2x1=5x2=1.57Z2=341问题B3x1=4x2=2Z3=340问题B4x1=1.42x2=3Z4=327问题B5x1=5.44x2=1Z5=308问题B6无可行解x14x15x22x23x21x22*0356z*0349z340z*341340z*340分支树：问题B0x1=4.81x2=1.82Z0=356问题B1x1=4x2=2.1Z1=349问题B2x1=5x2=1.57Z2=341问题B3x1=4x2=2Z3=340问题B4x1=1.42x2=3Z4=327问题B5x1=5.44x2=1Z5=308问题B6无可行解x14x15x22x23x21x22012345678910x1x21234567（4，2）B0B1B2B3B4B6B5图解示意：1、概述匈牙利法是用来解决人员分配问题的一个解法。1955年，库恩（W.W.Kuhn)利用匈牙利数学家康尼格（D.Kǒnig)的一个定理构造了这个解法，故称为匈牙利法。人员分配问题：设某单位现有n个人员A1,A2…An来完成n项工作B1,B2,……Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好。四、指派问题及