0-1整数规划算法分析—配送中心选址应用【毕业设计】.doc

1、本科毕业设计（20届）01整数规划算法分析配送中心选址应用所在学院专业班级数学与应用数学学生姓名学号指导教师职称完成日期年月I【摘要】本文分析了几种求解01整数规划最优解的算法，包括常用的穷举法以及分支定界法，还分析了隐枚举法，同时，还有分层优选法，和一种当决策变量（N10）的改进方法。对这些算法用同一个例子进行了比较，分析。同时，还求得一种01整数规划的算法改进，使计算量大大减少。最后，将隐枚举法运用到配送中心选址应用上。【关键词】01整数规划；算法；配送中心选址；【ABSTRACT】THISPAPERANALYZESSEVERALSOLVE01INTEGERPROGRAMMINGOPTIM

2、ALSOLUTIONALGORITHM,INCLUDINGCOMMONEXHAUSTIVELYMETHODANDBRANCHANDBOUNDMETHODFOR,ANALYZETHEIMPLICITEMUMERATIONMETHOD，,ATTHESAMETIME,ANDTHAT,ANDALAYEREDWORTHYASDECISIONVARIABLEN10IMPROVINGMETHODSWITHTHESAMEEXAMPLEOFTHESEALGORITHMSARECOMPAREDANDANALYZEDATTHESAMETIME,ALSOGETA01INTEGERPROGRAMMINGALGORITH

3、MIMPROVEDGREATLYREDUCECOMPUTATIONFINALLY,IMPLICITEMUMERATIONLAWTOAPPLYTOTHEDISTRIBUTIONCENTERSSITESELECTIONAPPLICATION【KEYWORDS】01INTEGERPROGRAMMINGALGORITHMSDISTRIBUTIONCENTERLOCATIONII目录摘要IABSTRACT错误未定义书签。目录II101整数规划的概念32解01整数规划的方法321穷举法322分支定界法423隐枚举法6231隐枚举法I6232隐枚举法8233隐枚举法III目标排序法1024分层优选法1125

4、对于变量数目很大的新的解法1326算法的改进153模型建立配送中心选址应用1631假设1632宁波市配送中心选址模型及求解164总结20参考文献21致谢20附录错误未定义书签。3101整数规划的概念整数规划是数学规划的重要方面之一，许多重要的组合数学问题实质上都是从属于它，然而目前求解还存在许多困难，基本上是采用穷举法。01整数规划是整数规划中最简单的一种，取0和1两种的整数规划问题01型整数规划是整数规划的特例，其数学模型的目标函数、约束条件与线性规划相同，不同的是其变量只能取0和1，分别表示两种截然相反的结果。01型整数规划应用很广，如土木工程系统的最优工程配置问题，城建规划中的居民点、给

5、水点、加油站和商业网点的最优布局问题，均可应用01型整数规划求得最优解。01型整数规划的数学模型如下2解01整数规划的方法21穷举法解01整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2N个组合。由于01型整数规划的变量个数有限且取值非0即1，所以不难将解的集合找出来，再检验每个解的可行性，凡符合全部约束条件者均为可行解，通过比较目标函数的值便可找到最优解，这个解法称为穷举法。当变量和约束条件很多时，其工作量是非常大的。现有如下的01整数规划模型例1求解123MIN432ZXXX1MAXMI

6、N,1,2,01,1,2,NJJJJIJZIMJNCXXBXNIJJ1目标函数或或约束条件或A4123123232534433101JSTXXXXXXXXX或（J1,2,3）利用穷举法求解列表如下点（123,XXX）条件满足条件（0,0,0）（0,0,1）（0,1,0）（0,1,1）1,0,01,0,11,1,01,1,102354679对于此例中的3个决策变量，有8种可能值，运用穷举法共需要验算24个约束条件，共进行32次运算，并将各个符合满足条件的值比较得到最优解,MIN20,0,1TZX。22分支定界法先将01规划化为规定的标准型，然后令全部变量为0，若其可行，则此解即为最优解，计算终止

7、否则，按所谓“距离”，选定其中某个变量为“固定变量”，令其分别为0和1，将问题分枝成两个问题，而后分别对它们进行检验，即令非固定变量称为自由变量全部为0，检查它们与固定变量所组成的解是否可行若其可行，则此解就是目前最好的可行解，不再分枝，其相应的目标函数值就是原问题的一个下界；否则，在余下的自由变量中，再选定某个为固定变量，把子问题再分枝，继续上面的过程，直至全部子问题不需再分枝，或没有自由变量为止此中最大的下界值所对应的可行解即为最优解。图1是深度为3的满二叉树。5如果一个深度为N1的满二叉树按上述方法顺序排列，并对任一节点I存在。1当I1时，I是根；2当I1时，如果I是偶数，该节点存贮的数

8、据是0，否则存贮的数据是1。那么，从根节点到叶子的一条路径以下简称路径是N个01整数的组合，因而01整数规划的完全枚举可等价于满二叉树的遍历。设路径的节点依次为0，1,N，节点I对应于二叉树的节点LAI，并将路径节点I存贮的数据赋给IX，令从路径节点1I到2I1I0Z；对剩余未经查验的含K个1的N位二进制数，只须就目标函数值大于11Z的解，查验其是否可行，一旦可行，则记其对应的目标函数值为12Z,依此类推，直至所有台K个1的N位二进制数全部查验完为止，并把最后所得的可行解的目标函数值改记为1Z；若此层无可行解，则记1Z0Z，转44若K11Z，则转第二层筛选；否则，若K11，11KJJC1Z，转

9、第三层筛选,若1111MAX,KKJJJJCC1Z，则计算终止,1Z即为最优值，对应的解即为最优解。第二层筛选取所有含有K1个1的N位二进制数为待检验的解2X，仿照第一层筛选的第3步仅就目标函数值大于1Z的解查验其是否可行找出其中可行解所对应的最大目标函数值后，记为2Z；若此层无目标函数值大于1Z的可行解，则记2Z1Z；若K11，11KJJC2Z，则转第三层筛选；否则，若K2，21KJJC2Z，则记3Z2Z，转第四层筛选；若MAX11KJJC,21KJJC2Z，则计算终止，2Z即为最优值，对应的解即为最优解第三层筛选取所有含有K1个1的N位二进制数为待检验的解3X，仿照第一层筛选的第3步，仅就

10、日标函数值大于2Z的解查验其是否可行，找出其中可行解所对应的最大目标函13数值后，记为3Z；若此层无目标函数值大于2Z的可行解，则记3Z2Z；若K2N，21KJJC3Z，则转第四层筛选；否则，若K21，21KJJC3Z，则记4Z3Z，转第五层筛选21KJJC,21KJJC3Z，则计算终止，3Z即为最优值，对应的解即为最优解。依此类推，第四层筛选取所有含K2个1的N位二进制数为待检验的解4X；第五层筛选取所有舍K2个1的N位二进制数为待检验的解5X；直至选出最优值及最优解；或把所有N位二进制数全部分层筛选完毕，仍无可行解，则原问题无最优解分层优选法一开始就从使目标函数取最大值的解出发来查验，求解

11、顺序也基本上都是按目标函数从大到小的顺序排列的，一旦发现可行解，该层其余未经检验过的解绝大部分都可被过滤掉。利用分层优选法解例1，可以得到100,0,0XX，得到的最优解为_10,0,1X，Z2。25对于变量数目很大的新的解法设有如下01整数规划问题1122MAXNNZCXCXCX其中01,2,01,2,1,2,01,2,KIJIKNIMJNIMCAB。目前解决01整数规划问题的常用方法主要有类似于解一般整数规划的分枝定界法和隐枚举法，前者本质上也是一种隐枚举法。对于变量数目较小的01整数规划问题，这两种方法都有较好的适用性，但若变量数目很大，则其计算量相当大，即使借助于计算机，也需耗费大量的

12、求解时间，往往影响许多实际工作的具体实施。1111221112122222112212,01NNNNMMMNNMNAXAXAXBAXAXAXBAXAXAXBXXX或14考虑到上述规划问题的特殊性，我们设计了一种一定情况下比分枝定界法和隐枚举法更有效的方法，其基本思路与分枝定界法有相似之处。利用变量只能取0或1两个值的特性，构造如图1所示的一棵树，图中每个顶点表示一个子集，圆点后面的数字表示已选人的取值为1的变量的下标，圆点前面的数字表示可能进入而又尚未进人计算的取值为0的变量的下标。例如，顶点23N1表示只含变量子集；又如顶点N123N1表示含变量1X至1NX的子集，圆点前面的N表示沿这个顶点

13、往下去，进入计算的变量只可能是N。为了求得最优解，我们先在该树中找出一个可行解和非可行解,以此为参照可剔除一些可行解和非可行解，仅验算一部分较好的可行解，就能定出最优解，从而减少了不少工作量。其具体步骤如下图21检验顶点23N1,3N2,N是否为可行解，若均不可行，则该规划问题无可行域即无最优解；否则，不失一般性可设23N1为可行解。2按该树顶点水平位置以从上至下从左至右的次序“垂直”地一支一支地验算该树各顶点是否为可行解,即深度优先搜索。从图1可看到最左边一支诸顶点的圆点后面数字依次为1，12，123，123N，紧挨的第二支对应的数字为124,，124N，再过来一支诸顶点对应的数字为125,

14、，125N。以此类推，把该树视为家族的家谱，从“树根”即“祖父”开始，沿“父亲”到“长子”方向，访问验算下去。3若一直访问到某一支的端点为可行解，或该端点为非可行解但其“父亲”为可行解，则将此可行解及其对应的目标函数值记录下来，然后再转到该点的“父亲”的“大弟弟”继续进行验算；若访问到某个非端点的分支结点为非可行解，且该结点的“父亲”为可行解，则将此可行解及其目标函数值记录下来T然后再转到该结点的“太弟弟”继续进行验算。由15于该结点的“后代”也为非可行解，故不必再验算了。依次下来，若端点的“父亲”的“大弟弟”或结点的“大弟弟”都已访问完，则转到端点或结点的“祖父”的“大弟弟。4若有待验算的顶

15、点中圆点后面的所有数字是已验算为可行解的某个顶点中圆点后面的数字的一部分，则这样的顶点也为可行解，但其目标函数值较已验算并记录的可行解的目标函数值小，不会是最优解，故不必验算和记录，只需往下继续验算其“后代即可。5按照以上次序，当所有的支都访问完时，比较所有已记录的可行解及其目标函数值，则可得最优解，计算结束。运用此法再次求解例1得到根据之前对于变量数目很大的新的解法，构造如图所示的树求解；由图可知，最优解为3121,0,0XXX；最优值Z2其实，在231这里时可行下面的就不需要再算，所以实际之进行了12次运算。26算法的改进对于之前的7种01整数规划算法，都有优势的地方也有劣势，现就对01整

16、数规划的算法稍作改进，以使计算更简便。继续应用隐枚举法中的将决策变量系数从小到大或者从大到小排列计算最大或者最小值的思路。然后只要任何一个解遇到一个不满足条件即停止运算，这样就会避免不必要的计算。利用递推的方法当遇到满足所有条件的可行解时即为最优解。利用例1举例因为要求得最小值，而且决策变量系数是从大到小排列的，所以从1X，2X，3X都取最小的0开始，很显然如果（1X，2X，3X）（0，0，0）代入满足所有约束条件时必定16为最小值。现将其代入并且当遇到一个不满足约束条件是停止运算点123,XXX条件满足条件Z值（0,0,0）0用递推的方法将其中一个决策变量换成1，则3X1，而1X2X0，如果

17、此解可行则必定得到最小值，必为最优值，代入得到点123,XXX条件满足条件Z值（0,0,1）22可以得到（1X，2X，3X）（0，0，1）为可行解，即可推断为得到的解即为最优解。,MIN20,0,1TZX。运用此改进的方法只需7次运算，计算5个约束条件。比之前的几种方法在求解此类问题时更简便，运算量更小。3模型建立配送中心选址应用31假设在给定某一地区所有备选点的地址集合中选出一定数目的地址作为配送中心,为城市内用户服务,故可不考虑运费问题,使在选出点建立的配送中心与各需求点和供货点形成的配送体系利润最大即可。为便于模型求解,同时使模型具有使用价值,作如下假设仅在一定的备选范围内考虑设置新的配

18、送中心。一个配送中心可由多个供货点供货,一个用户的需求也可由多个配送中心提供。配送中心的固定投资费用已知。运输费用不计。能够实现预计的利润回报的选址地点为最优解。32宁波市配送中心选址模型及求解根据宁波市配送中心现状调查,了解物流需求量、起讫地点、运输费用等有关数据,给出一种合理的算法,满足宁波市特有的社会环境与地理交通环境。在宁波市东、南、北三个地区建设城市综合配送中心。拟建中有6个点IA（I1,2,6）17供选择。规定在东区,由1A，2A两个点中至多选一个在南区,由3A,4A两个点中至多选一个；在北区，由5A,6A两个点中至多选一个。1A点在江东第二实验小学附近,投资估计为1B100万元,

19、每年可获利润估计为1C300万元。2A点在江东中心小学附近,投资估计为2B80万元,每年可获利润估计为2C240万元,3A在天一广场附近,投资估计为3B120万元,每年可获利润估计为3C350万元。4A点在南站附近,投资估计4B110万元,每年可获利润估计为4C320万元。5A点在宁波大学附近,投资估计为5B130万元,每年可获利润估计为5C370万元。6A点在红梅新村附近,投资估计为6B90万元,每年可获利润估计为6C270万元。投资总额不能超过B400万元。选择的地点应使年利润最大。01型整数规划数学模型的建立设变量1,0IIIAXA当点被选用（I1,2,6），当点没被选用,年利润Z表示目

20、标,并使目标函数利润最大化。宁波市配送中心选址的数学模型为61MAXIIIZCX61123456400111101,2,6IIIISTIBXXXXXXXX或，点条件满足条件Z值261435,XXXXXX（0,0,0,0,0,0）0（0,0,0,0,0,1）37013000118。（0,0,0,1,1,1）104002。（0,0,1,0,1,1）10203501111020（0,0,1,1,0,1）990340111990（0,0,1,1,1,0）970330021。（0,1,0,1,1,0）94002（0,1,1,0,1,0）920310111920（0,1,1,1,0,0）890300111

21、890（1,0,0,0,1,1）960330111960。（1,0,0,1,0,1）930320111930（1,1,0,0,1,0）860290111860（1,1,0,1,0,0）830280111830用隐枚举法求解数学模型根据运筹学的理论和方法,求解上述01型整数规划数学模型比较有效的方法是隐枚举法,求解如下261435MAX240270300320350370ZXXXXXX26143578090100110120130140400XXXXXXX121XX341XX561XX101,2,6IIX或，根据条件有点条件满足条Z值19261435,XXXXXX件（0,0,0,0,0,0）0（

22、0,0,0,0,0,1）370130001。（0,0,0,1,1,1）104002。（0,0,1,0,1,1）10203501111020改进过滤条件2614352402703003203503701020XXXXXX代替，继续进行。点条件满足条件Z值261435,XXXXXX（0,0,1,1,0,1）990（0,0,1,1,1,0）970。（0,1,0,1,1,0）940（0,1,1,0,1,0）920（0,1,1,1,0,0）890（1,0,0,0,1,1）960。（1,0,0,1,0,1）930（1,1,0,0,1,0）860用隐枚举法求解上述的数学模型，得到最优解261435,XXXX

23、XX（0,0,1,0,1,1），最优值MAXZ1020万元。所以宁波市东、南、北三处建立配送中心，可获得最高利润1020万元。从而确定了宁20波市配送中心合适的选址地点。4总结如今对于01整数规划问题的算法已经总结了很多，有最基本的穷举法，分支定界法，到延伸的隐枚举法，以及分层优选法和对于变量数目很多时的方法，通过之前的各种算法用同一个例子进行比较得到一般穷举法的计算量是最大的，计算过程也较复杂。用穷举法来求解需要检验2N个变量的组合，当N值很大时,是不可行的。而分支定界法则相对有条理，运算相对简化。比较常用的是隐枚举法，这类方法是解01整数规划最常用的方法，而且对于隐枚举法有三种不断递进的方

24、法隐枚举法I比分支定界和穷举法所用的运算次数少，数学模型无须转化成标准型，减少了人工处理的工作量，但是含有两个不确定性因素，直接影响到本解法对减少工作量的有效性；对隐枚举法II来说,所需检验的方案较少，这是其优点但在检验之前必须通过人工处理将数学模型标准化,当问题复杂时,人工处理的工作量很大，且易出差错,这是其缺点之一。在具体操作过程中还存在如下问题,即此解法有效性的关键在于检验前必须排出一个能体现各解点Z值大小顺序的对各变量取值0或1的各种组合的检验顺序，当变量个数较多的时候，这是相当困难的。隐枚举法III求解例1时运算次数减少，隐枚举法III是非常简便而效的，它无须将数学模型转化为标准型，

25、它保留了隐枚举法I的优点而克服了隐枚举法II的缺陷，它不需要过滤条件，也略去了用过滤条件检验每个目标函数的工作，自然也就排除了两个不确定性因素的干扰。这种直接以Z值大小编排检验顺序的解法，保持了隐枚举法II按序检验的优点，同时又排除了迂回排序和重复检验带来的困扰。这种新的解法省略了所有需要人工处理的环节，对实施电算极为有利。分层优选法不必将线性规划化为标准型，在每一层中选择了高起点的过滤条件，找到最优解较快，但是分层优选法一般用于变量数较少，约束条件较多时；运用变量个数较大的方法则运算次数减少，而且此方法不仅能运用于决策变量较小的数学模型，更解决了决策变量个数较多时的模型。最后通过对于之前几种

26、的算法的总结得出了一种改进方法，这种方法明显简化了运算过程，减少了运算量，不仅不用将数学模型转化成标准型，减少了人工处理的工作量，而且减少了一些不必要的运算步骤，克服了隐枚举法中的一些缺陷。但是也存在一些问题，比较适用于决策变量较少的情况，以及变量系数为正的情况，局限性较大。21参考文献1运筹学教材编写组运筹学M北京清华大学出版社，20052苟格整数规划中的割平面法与分枝定界法比较J四川达县师范高等专科学校学报，2005（2）18213林斐求解一类整数规划问题最优解的算法J东莞理工学院学报自,2006（52）4王淑英整数规划在制定防灾预案中的应用J北京教育学院学报自,2007516235顾治萍

27、EXCEL在混合整数规划中的应用J上海交通大学，200829126李炯城，鲍江宏组合优化中整数规划的数论解法J计算机工程与设计，200957程继红,马颖亮,李高鹏基于混合整数规划模型的物流中心选址方法J海军航空工程学院学报,200722912948程冬时，张声年关于求解01型整数规划的若干问题J江西电力职业技术学院学报,2006331359李时求解01整数规划的一种新方法分层选优法J吉林工业大学学报，1993310刘晓惠,景清泉,霍俊爽基于01型整数规划的配送中心选址J物流与采购研究，2009214614811郜振华AHP和01整数规划方法在物流系统零售点选址中的应用研究J价值工程，20087798112丁小东,姚志刚,程高LINGO语言与01混合整数规划选址模型的再结合J物流工程和管理，200910727513AKAUFMANNINTEGERANDMIXEDPROGRAMMING,THEORYANDAPPLICATIONSMACADEMIEPRESS，INCLONDONLTD，198214DENNISJS,RICHAROAMAMETHODOFDECOMPOSITIONFORINTEGERPROGRAMSJOPNSRES,1979,273