整数线性规划.ppt

《整数线性规划.ppt》由会员分享，可在线阅读，更多相关《整数线性规划.ppt（45页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、整数规划(Integer Programming)王广民中国地质大学 经济管理学院1、概述、概述整数规划（整数规划（Integer Programming，简记简记IP)主要是主要是指指整数线性规划整数线性规划,是近二、三十年来发展起来的数是近二、三十年来发展起来的数学规划当中的一个重要分支，讨论整数规划对研学规划当中的一个重要分支，讨论整数规划对研究管理问题有重要意义，究管理问题有重要意义，比如项目投资问题、人比如项目投资问题、人员分配问题等都可以化为一个整数规划问题（因员分配问题等都可以化为一个整数规划问题（因为如人员分配等的一些问题显然不可能出现小数为如人员分配等的一些问题显然不可能出现

2、小数或者分数的情况）或者分数的情况）,可分为：可分为：纯整数规划（所有变量都限制为整数）纯整数规划（所有变量都限制为整数）混合整数规划（一部分变量限制为整数）混合整数规划（一部分变量限制为整数）0-1规划（所有变量的取值都限制为规划（所有变量的取值都限制为0或或1）一、一、整数规划问题及其数学模型整数规划问题及其数学模型所谓整数规划是指具有下列模型的线性规划问题所谓整数规划是指具有下列模型的线性规划问题其中其中A矩阵、矩阵、b、c向量中所有的元素数都是整数向量中所有的元素数都是整数或有理数或有理数.(1)、模型阐述、模型阐述2、整数规划问题的模型、整数规划问题的模型其实，如果不考虑（其实，如果

3、不考虑（IP）问题中问题中“X是整数是整数”的条件，则整数规划问题仍可看成一个一般的的条件，则整数规划问题仍可看成一个一般的线性规划（线性规划（LP）问题：问题：称为该整数规划问题的称为该整数规划问题的松弛问题松弛问题(slack Problem).(2)、整数规划的例子、整数规划的例子例例 投资问题投资问题设某公司在设某公司在m个时段里有个时段里有n项投资计划，由于资金项投资计划，由于资金限制不能全部进行。已知限制不能全部进行。已知1、第、第 i 个时段里该公司可动用的资金是个时段里该公司可动用的资金是bi，2、第第 j 项投资计划所需要的资金是项投资计划所需要的资金是aij,能够得到能够得

4、到的利润是的利润是cij。问该公司如何选择投资计划，使问该公司如何选择投资计划，使m个时段内的总个时段内的总利润最大利润最大.解：设解：设xij表示在第表示在第i个时段内对第个时段内对第j个投资计划的决策个投资计划的决策变量变量即当即当xij=1时，表示第时，表示第i 个时段内选中并执行第个时段内选中并执行第j个投资个投资计划，当计划，当xij=0时，表示第时，表示第i 时段内未选中第时段内未选中第j个投资计个投资计划划.因此因此,可以建立该投资问题的可以建立该投资问题的数学模型数学模型为：为：例例 工作分配问题工作分配问题设某单位现有设某单位现有n个人员个人员A1,A2An来完成来完成n项工

5、作项工作B1,B2,Bn。按工作要求，每个人员需干一项工作，按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员每项工作也需一人去完成。已知人员Ai做工作做工作Bj的的效率是效率是cij。问应如何分配，才使总效率最好问应如何分配，才使总效率最好.解：令解：令xij表示对人员表示对人员Ai完成工作完成工作Bj的决策变量的决策变量即即xij=1表示分配表示分配Ai干工作干工作Bj，xij=0表示不分配表示不分配Ai干干工作工作Bj。按问题要求，建立该问题的数学模型为：按问题要求，建立该问题的数学模型为：线性规划（线性规划（LP）的任一整数可行解都是整数规划的任一整数可行解都是整数规划

6、（IP）的一个可行解，显然（的一个可行解，显然（IP）的所有解（包括的所有解（包括可行解）对应于（可行解）对应于（LP）的整数可行解。的整数可行解。当（当（LP）的最优解不是一个整数解时，一般情况下的最优解不是一个整数解时，一般情况下不可以通过对非整数解进行不可以通过对非整数解进行“四舍五入四舍五入”、“凑整凑整法法”得出（得出（IP）问题的最优解。问题的最优解。整数线整数线性规划及其松弛问题，从解的特点上来说，性规划及其松弛问题，从解的特点上来说，二者之间既有密切的联系，又有本质的区别二者之间既有密切的联系，又有本质的区别.进一步地，如果（进一步地，如果（LP）的最优解是一个整数解，的最优解

7、是一个整数解，那么，这个解也一定是（那么，这个解也一定是（IP）问题的最优解。问题的最优解。一般情况下，（一般情况下，（LP）的最优解不会恰好是一个整的最优解不会恰好是一个整数解，自然就不是（数解，自然就不是（IP）的最优解，的最优解，（IP）的最的最优值不会优于（优值不会优于（LP）的最优值的最优值.3、关于整数规划的解、关于整数规划的解例如例如：求下列整数规划的最优解：求下列整数规划的最优解解：在先不考虑解：在先不考虑“x1,x2是是整数整数”的条件下，对相应的条件下，对相应的线性规划问题易由图解的线性规划问题易由图解法得出最优解是：法得出最优解是：X=（3.25,2.5）通过凑整法，可以

8、得出通过凑整法，可以得出4种种组合组合(4,3),(4,2),(3,3),(3,2)。(4,3),(4,2),(3,3)都不是可行解，都不是可行解，(3,2)虽是可行解，虽是可行解，但不是最优解但不是最优解满足问题的整数满足问题的整数最优解最优解是是(4,1)，最优值是，最优值是14。而最优。而最优解解(4,1)并不是相应线性规划的可行域的顶点。并不是相应线性规划的可行域的顶点。结论：直接利用图解法（或者甚至利用单纯形法）无结论：直接利用图解法（或者甚至利用单纯形法）无法直接找出整数规划的最优解。法直接找出整数规划的最优解。1、求解思路、求解思路割平面法是求解整数规划的最早提出的一个方法。割平

9、面法是求解整数规划的最早提出的一个方法。基本思想基本思想是：首先利用单纯形法（或者其它方法）求解整数是：首先利用单纯形法（或者其它方法）求解整数规划的松弛线性规划；经过判断，如果达不到变量的整数条规划的松弛线性规划；经过判断，如果达不到变量的整数条件，则针对某一个非整变量增加特定割平面，把件，则针对某一个非整变量增加特定割平面，把LP问题中对问题中对该变量的非整数部分给去除掉，保留了全部有整数解的部分，该变量的非整数部分给去除掉，保留了全部有整数解的部分，同时经过切割后的可行域其凸性质不改变。同时经过切割后的可行域其凸性质不改变。逐次反复上面的过程，只要整数规划问题有最优整数解，则逐次反复上面

10、的过程，只要整数规划问题有最优整数解，则必定可以在经过若干次的切割后的凸可行域的顶点中找到最必定可以在经过若干次的切割后的凸可行域的顶点中找到最优解。优解。二、二、Gomory割平面法割平面法割平面法在割平面法在1958年由高莫瑞年由高莫瑞(R.E.Gomory)首先首先提出，故又称提出，故又称Gomory割平面法。割平面法。在割平面法中每次增加的用于在割平面法中每次增加的用于“切割切割”的线的线性约束称为割平面约束或性约束称为割平面约束或Gomory约束。约束。构造割平面约束的方法很多，介绍最常用的一构造割平面约束的方法很多，介绍最常用的一种，它可以从相应线性规划的最终单纯形表中种，它可以从

11、相应线性规划的最终单纯形表中直接产生。直接产生。实际解题时，经验表明若从最优单纯形表中选实际解题时，经验表明若从最优单纯形表中选择具有最大小择具有最大小(分分)数部分的非整分量所在行构数部分的非整分量所在行构造割平面约束，往往可以提高造割平面约束，往往可以提高“切割切割”效果，效果，减少减少“切割切割”次数。次数。(1)、如果要求目标的最大值、如果要求目标的最大值令令其中其中效率矩阵可变为效率矩阵可变为B，将分配问题转换为一个极将分配问题转换为一个极小化问题小化问题4、几点说明、几点说明(2)、如果分配问题中，人员数、如果分配问题中，人员数 m 不等于工作不等于工作数数 n 时，可以类似于不平

12、衡运输问题建立模型时，可以类似于不平衡运输问题建立模型的方法，增加虚拟人员或虚拟工作。的方法，增加虚拟人员或虚拟工作。当当mn时，由于虚拟工作无须人员去做，对于时，由于虚拟工作无须人员去做，对于极小化问题，可设其的效率为极小化问题，可设其的效率为 0；对于极大化问；对于极大化问题，可设其效率是一个充分大的正数题，可设其效率是一个充分大的正数M。当当mz2，故令故令 ,所以所以 .B1:x1=4,x2=2.10,z1=349B2:x1=5,x2=1.57,z2=341由于由于z1 z2，故先对故先对B1进行进行分解分解。对。对B1增加条件增加条件得：得：B3:增加条件增加条件 x2 2;B4:增

13、加条件增加条件 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=341340 z*341定界定界:340 z*340问题问题B0 x1=4.81x2=1.8

14、2Z0=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 2340 z*341340 z*340分支树：分支树：问题问题B0 x1=4.81x2=1.82Z0=356问题问题 B1x1=4x2=2.1Z1=349问题问题 B2x1=5x2=1.57Z2=341问题问题 B3x1=4x2=2Z3=340问题问题 B4x1=1.42x2=

15、3Z4=327问题问题 B5x1=5.44x2=1Z5=308问题问题B6无可行无可行解解x1 4x1 5x2 2x2 3 x2 1x2 20 1 2 3 4 5 6 7 8 9 10 x1x21234567（4，2）B0B1B2B3B4B6B5图解示意：图解示意：1、概述、概述匈牙利法是用来解决人员分配问题的一个解法。匈牙利法是用来解决人员分配问题的一个解法。1955年，库恩（年，库恩（W.W.Kuhn)利用匈牙利数学家康利用匈牙利数学家康尼格（尼格（D.Knig)的一个定理构造了这个解法，故称的一个定理构造了这个解法，故称为为匈牙利法匈牙利法。人员分配问题人员分配问题：设某单位现有：设某单

16、位现有n个人员个人员A1,A2An来来完成完成n项工作项工作B1,B2,Bn。按工作要求，每个人员按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人需干一项工作，每项工作也需一人去完成。已知人员员Ai做工作做工作Bj的效率是的效率是cij。问应如何分配，才使总效问应如何分配，才使总效率最好。率最好。四、四、指派问题及匈牙利法指派问题及匈牙利法令令xij表示对人员表示对人员Ai完成工作完成工作Bj的决策变量的决策变量表示分配表示分配Ai干工作干工作Bj表示不分配表示不分配Ai干工作干工作Bj按问题要求，建立该按问题要求，建立该问题的数学模型为：问题的数学模型为：这就是一般分配这就是

17、一般分配问题的数学模型问题的数学模型.此模型也可以看成一个特殊的此模型也可以看成一个特殊的运输问题运输问题，如果用表，如果用表上作业法得出的一个最优解又满足上作业法得出的一个最优解又满足“xij=0,1”的条件，的条件，这个解也是分配问题的最优解。用表上作业法求解这个解也是分配问题的最优解。用表上作业法求解的过程往往出现退化情况。的过程往往出现退化情况。注：人员分配问题有各种提法。注：人员分配问题有各种提法。n如果完成任务的效率表现为如果完成任务的效率表现为资源的消耗资源的消耗，则所谓，则所谓的效率最好是指消耗的资源最少，分配问题就是一的效率最好是指消耗的资源最少，分配问题就是一个最小化问题；

18、个最小化问题；n如果完成任务的效率表现为如果完成任务的效率表现为生产效率生产效率的高底，则的高底，则分配问题就是一个最大化问题。分配问题就是一个最大化问题。所有分配问题可以建立相同的数学模型所有分配问题可以建立相同的数学模型.2、相关概念、相关概念a、0-1变量及其应用变量及其应用如前所述如前所述,若变量只能取值若变量只能取值0或或l，则称其为则称其为0-1变量变量.0-1变量作为逻辑变量，常被用来表示系统是否处变量作为逻辑变量，常被用来表示系统是否处于某个待定状态或者决策时是否取某个待定方案于某个待定状态或者决策时是否取某个待定方案.例如例如当决策取方案当决策取方案 P 时时当决策不取方案当

19、决策不取方案 P 时时五、五、0-1型整数规划型整数规划当问题含有多项要素，而每项要素皆有两种选择当问题含有多项要素，而每项要素皆有两种选择时，可用一组时，可用一组0-1变量来描述。变量来描述。一般地，设问题有有限项要素一般地，设问题有有限项要素 El,E2,En。其中其中每项每项 Ej 有两种选择有两种选择 ，,(j1,2,n)，则可则可令令那么那么,向量向量(x1 ,x2,xn)T 就描述了问题的特定就描述了问题的特定状态或方案，即状态或方案，即若若 Ej 选择选择若若 Ej 选择选择 例例1 含有相互排斥的约束条件的问题含有相互排斥的约束条件的问题在例中，设备台时的约束条件为在例中，设备

20、台时的约束条件为现在假设还有一种新的加工方式，相应的设备台现在假设还有一种新的加工方式，相应的设备台时约束变成时约束变成如果只能从两种加工方式中选择一种，那么，上如果只能从两种加工方式中选择一种，那么，上两式就成为两个相互排斥的约束条件。两式就成为两个相互排斥的约束条件。为了统一在一个问题中，引入为了统一在一个问题中，引入0-1变量变量若采用原加工方式若采用原加工方式若不采用原加工方式若不采用原加工方式和和若采用新加工方式若采用新加工方式若不采用新加工方式若不采用新加工方式于是，相互排斥的约束条件于是，相互排斥的约束条件(1)和和(2)可用下列三可用下列三个约束条件统一起来个约束条件统一起来:

21、例例2 固定费用问题固定费用问题有三种资源被用于生产三种产品。资源量、产品有三种资源被用于生产三种产品。资源量、产品单件可变费用及售价、资源单耗量及组织三种产单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。划，使总收益最大。单耗量单耗量 产品产品资源资源资源量资源量A248500B234300C123100单件可变费用单件可变费用456固定费用固定费用100150200单件售价单件售价81012解解 总收益等于销售收入减去生产上述产品的固定总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。

22、建模碰到的因难主要是事费用和可变费用之和。建模碰到的因难主要是事先不能确切知道某种产品是否生产，因而不能确先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生。下面借助定相应的固定费用是否发生。下面借助0-1变量解变量解决这个困难。决这个困难。设设 xj 是第是第 j 种产品的产量，种产品的产量，j1,2,3；再设再设若生产第若生产第 j 种产品（即种产品（即xj 0）若不生产第若不生产第 j 种产品（即种产品（即xj=0）j1,2,3.则问题的整数规划模型是则问题的整数规划模型是其中其中 Mj 为为 xj 的的某个上界。例如，某个上界。例如，根据第根据第3个约束个约束条件，可取

23、条件，可取M1100，M250，M334。如果生产第如果生产第 j 种产品，则其产量种产品，则其产量 xj 0。此时，由此时，由约束条件约束条件 知知 yj=1。因此，相应的固因此，相应的固定费用在目标函数中将被考虑。定费用在目标函数中将被考虑。如果不生产第如果不生产第 j 种产品，则其产量种产品，则其产量 xj=0。此时此时,由约束条件由约束条件 可知可知 yj 可以是可以是0，也可，也可以是以是1。但。但 yj=1 不利于目标函数的最大化，因而不利于目标函数的最大化，因而在问题的最优解中必然是在问题的最优解中必然是 yj=0，从而相应的固定从而相应的固定费用在目标函数中将不被考虑。费用在目

24、标函数中将不被考虑。b、0-1型整数规划的解法型整数规划的解法0-1型整数规划是一种特殊的整数规划。若含有型整数规划是一种特殊的整数规划。若含有 n 个变个变量，则可以产生量，则可以产生 2n 个可能的变量组合。当个可能的变量组合。当 n 较大时，较大时，采用完全枚举法解题几乎是不可能的。已有的求解采用完全枚举法解题几乎是不可能的。已有的求解0-1型整数规划的方法一般都属于隐枚举法。型整数规划的方法一般都属于隐枚举法。在在2n个可能的变量组合中，往往只有一部分是可行解。个可能的变量组合中，往往只有一部分是可行解。只要发现某个变量组合不满足其中一个约束条件时，就只要发现某个变量组合不满足其中一个

25、约束条件时，就不必再去检验其它约束条件是否可行。对于可行解，其不必再去检验其它约束条件是否可行。对于可行解，其目标函数值也有优劣之分。若已发现一个可行解，则根目标函数值也有优劣之分。若已发现一个可行解，则根据它的目标函数值可以产生一个过滤条件，对于目标函据它的目标函数值可以产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性。在数值比它差的变量组合就不必再去检验它的可行性。在以后的求解过程中，每当发现比原来更好的可行解则以后的求解过程中，每当发现比原来更好的可行解则以此替换原来的过滤条件。上述这些做法，都可以减少以此替换原来的过滤条件。上述这些做法，都可以减少运算次数，使最优解能较快地被发现运算次数，使最优解能较快地被发现.例例3 求解求解0-1型整数规划型整数规划求解过程可以列表表示求解过程可以列表表示(x1,x2,x3)z 值值约束条件约束条件 过滤条件过滤条件（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）10 z8z05 z5-2338 6