1、1毕业论文开题报告数学与应用数学01整数规划在实际工作中的应用配送中心选址问题应用一、选题的背景与意义整数规划是规划论中研究决策变量取整数的一类较新、较特殊的线性规划。它在工业、商业、运输、经济管理和军事等领域中都有重要的应用,如决策变量为人数,机器的台数,商店的个数等,就要求决策变量的取值为整数,因此这些问题都属于整数规划,它的求解方法,目前来讲主要有割平面法和分枝定界法。01型整数规划是整数规划的特例，其数学模型的目标函数、约束条件与线性规划相同，不同的是其变量只能取0和1，分别表示两种截然相反的结果。01型整数规划应用很广，如土木工程系统的最优工程配置问题，城建规划中的居民点、给水点、加
2、油站和商业网点的最优布局问题，均可应用01型整数规划求得最优解。01混合整数规划法的主要优点是它能够把固定成本以最优的方式考虑进去，它是商业选址模型中最受欢迎的方法。用01混合整数规划来解决选址模型时，目标是使各种成本费用的总和最小，而用整数变量表示各种选择，用连续变量表示工厂的生产能力、各种资源的分配等，用约束表示物流平衡关系和供需关系等。其主要思想是将每一个备选配送中心（RDC）分别纳入目标函数中看各自对目标函数的影响程度，最后决定是否需要该RDC。我认为可以对01整数规划的各种算法和它们的改进算法进行归纳，通过对其分析、比较，找出各种算法的适用范围。对于不同类型的实际应用中的配送中心选址
3、问题套用不同算法，从而建立一套完善的解题模式。同时在现已有的结论的基础上推广01整数规划在解决其它的优化问题中的应用，并使之应用到更广泛的实际工作中。二、研究的基本内容与拟解决的主要问题01整数规划在实际工作中的应用2拟解决的主要问题1、归纳整数规划和01整数规划问题的相关算法2、利用01整数规划模型求解实际工作中的具体问题三、研究的方法与技术路线查阅相关资料，找出01整数规划的相关算法和其在实际工作中运用的实例。在指导老师的指导下完成论文。四、研究的总体安排与进度201012201101查阅相关资料，并做些准备工作。12月17日前完成文献综述和开题报告并交学院审批。201101201103完
4、成论文的基本思路和框架。2011032011044月4号前完成两篇外文的翻译完成毕业设计（论文）初稿，交指导老师审批、修改。201104201106毕业论文定稿、修改、打印。五、参考文献1运筹学教材编写组运筹学M北京清华大学出版社，20052苟格整数规划中的割平面法与分枝定界法比较J四川达县师范高等专科学校学报，2005（2）18213林斐求解一类整数规划问题最优解的算法J东莞理工学院学报自,2006（52）4王淑英整数规划在制定防灾预案中的应用J北京教育学院学报自,2007516235顾治萍EXCEL在混合整数规划中的应用J上海交通大学，200829126李炯城，鲍江宏组合优化中整数规划的数
5、论解法J计算机工程与设计，200957程继红,马颖亮,李高鹏基于混合整数规划模型的物流中心选址方法J海军航空工程学院学报,200722912948程冬时，张声年关于求解01型整数规划的若干问题J江西电力职业技术学院学报,20063313539李时求解01整数规划的一种新方法分层选优法J吉林工业大学学报，1993310刘晓惠,景清泉,霍俊爽基于01型整数规划的配送中心选址J物流与采购研究，2009214614811郜振华AHP和01整数规划方法在物流系统零售点选址中的应用研究J价值工程，20087798112丁小东,姚志刚,程高LINGO语言与01混合整数规划选址模型的再结合J物流工程和管理，2
6、00910727513AKAUFMANNINTEGERANDMIXEDPROGRAMMING,THEORYANDAPPLICATIONSMACADEMIEPRESS，INCLONDONLTD，198214DENNISJS,RICHAROAMAMETHODOFDECOMPOSITIONFORINTEGERPROGRAMSJOPNSRES,1979,2734毕业论文文献综述数学与应用数学01整数规划在实际工作中的应用配送中心选址问题应用整数规划是规划论中研究决策变量取整数的一类较新、较特殊的线性规划。它在工业、商业、运输、经济管理和军事等领域中都有重要的应用,如决策变量为人数,机器的台数,商店的个
7、数等,就要求决策变量的取值为整数,因此这些问题都属于整数规划,它的求解方法,目前来讲主要有割平面法和分枝定界法。苟格（2005）在他的整数规划中的割平面法与分枝定界法比较中认为整数规划是规划论中较新的一个分枝,它是研究决策变量取整数的一类线性规划,主要的解法有割平面法和分枝定界法两种。对它们进行介绍后,通过求解具体问题进行分析比较。林斐（2006）给出了求解一类整数规划问题所有最优解的两个算法。一个算法较为简单,其时间复杂性为ON。另一个算法求解较为快速，其时间复杂性为OLOGN。王淑英（2007）在对整数规划问题及其解法研究的基础上,介绍了整数规划方法在制定科学的防灾预案中的应用。应用整数规
8、划能使防灾决策中面临的单凭经验不能解决的复杂问题迎刃而解,使防灾预案制定得更科学、更可行,从而提高防灾能力和水平。顾治萍2008针对在管理中经常出现的决策问题介绍了一种解决方法克服了线性规划的局限性,建立混合整数规划模型并用EXCEL软件的规划求解工具进行求解,通过一个实例详细介绍了其求解过程结果表明该方法简单、实用,并容易掌握。李炯城，鲍江宏2009认为整数规划属于计算机组合优化中的重要方法。目前求解整数规划的方法主要有割平面法和分枝定界法。前者往往收敛很慢甚至不收敛，后者不适用自变量较多的问题。从一种全新的视角出发，使用数论中的不定方程理论，来提出一种有效的整数规划新解法。该方法先把目标函
9、数可能取5的整数值添加作一个新的约束条件，然后让依次增大。使用不定方程理论，并结合自变量的取值范围，能迅速发现没有意义的，而大大减少计算量。该方法还不用求解整数规划相应的松弛线性规划问题。因此这种基于数论的整数规划解法速度很快，是一种较有前途的方法。最后针对典型的问题给出算例进行分析验证。程继红,马颖亮,李高鹏2007物流中心是物流企业效益链的重点环节，物流中心的选址直接关系着企业的发展。文章讨论了在多元网点布局情况下，混合整数规划模型在选址过程中的应用，并对模型的算法和求解进行了讨论。01型整数规划是整数规划的特例，其数学模型的目标函数、约束条件与线性规划相同，不同的是其变量只能取0和1，分
10、别表示两种截然相反的结果。01型整数规划应用很广，如土木工程系统的最优工程配置问题，城建规划中的居民点、给水点、加油站和商业网点的最优布局问题，均可应用01型整数规划求得最优解。01混合整数规划法的主要优点是它能够把固定成本以最优的方式考虑进去，它是商业选址模型中最受欢迎的方法。用01混合整数规划来解决选址模型时，目标是使各种成本费用的总和最小，而用整数变量表示各种选择，用连续变量表示工厂的生产能力、各种资源的分配等，用约束表示物流平衡关系和供需关系等。其主要思想是将每一个备选配送中心（RDC）分别纳入目标函数中看各自对目标函数的影响程度，最后决定是否需要该RDC。程冬时，张声年（2006）介
11、绍了目前用于求解01型整数规划的几种通用的解法穷举法；隐枚举法I；隐枚举法II,探讨了它们各自的优点和缺陷。在此基础上，提出了一种新的解法隐枚举法III，并以实际算例验证了它的可行性。李时（1993）介绍了求解O一1整数规划的一种新方法，这种方法优于以往的隐杖举法，特别是在变量数较少时，效果尤为明显。经过多年的教学实践，总结出又一种较简捷通俗的隐枚举法，即分层选优法，而后通过例题分析比较其优劣。刘晓惠,景清泉,霍俊爽2009配送中心的合理选址有利于商品高效快速流通,降低物流成本和投资,缓解城市交通压力。在分析配送中心选址方法的基础上,他们根据吉林市的物流现状,建立01型整数规划数学模型,运用隐
12、枚举法求解,确定了吉林市配送中心合适的选址地点。6郜振华2008在论文中认为物流系统零售点选址所涉及的影响因素众多,这些因素中既有定性因素,又有定量因素。首先用层次分析法对这些影响因素进行处理,得到了各备选点的权值。针对层次分析法无法解决条件约束问题,提出了用层次分析法和01整数规划法相结合用于零售点选址的模型。最后,通过示例证明该模型能有效地处理物流系统零售点选址问题。丁小东,姚志刚,程高（2009）认为目前现有的将LINGO语言和O1整数规划模型结合解决物流配送中心选址的理论较多，但不完善，主要表现在建模时对费用的考虑不全面、编程时所使用的变量不统一和求解时使用的是算例，数据真实性不高。针
13、对以上问题，论文对LINGO语言与01混合整数规划选址模型进行再结合。首先把与配送相关的物流活动分为进货、仓储和送货三大物流环节，由此将配送中心选址中所涉及到的费用分为进货运输费用、仓储费用和送货配送费用；其次对建模所涉及到变量进行科学的规范，并成功建立O1整数规划模型；最后以邯郸交通运输集团物流配送中心选址为实例，运用所建立的01混合整数规划模型，编写相应LINGO求解程序，通过运行得出邯运集团在石家庄、北京、邯郸建立配送中心此时费用最少，最终到达LINGO语言与01混合整数规划选址模型的完美结合。通过以上的文献，我认为可以对01整数规划的各种算法和它们的改进算法进行归纳，通过对其分析、比较
14、，找出各种算法的适用范围。对于不同类型的实际应用中的配送中心选址问题套用不同算法，从而建立一套完善的解题模式。同时在现已有的结论的基础上推广01整数规划在解决其它的优化问题中的应用，并使之应用到更广泛的实际工作中。参考文献1运筹学教材编写组运筹学M北京清华大学出版社，20052苟格整数规划中的割平面法与分枝定界法比较J四川达县师范高等专科学校学报，2005（2）18213林斐求解一类整数规划问题最优解的算法J东莞理工学院学报自,2006（52）4王淑英整数规划在制定防灾预案中的应用J北京教育学院学报自,20075162375顾治萍EXCEL在混合整数规划中的应用J上海交通大学，20082912
15、6李炯城，鲍江宏组合优化中整数规划的数论解法J计算机工程与设计，200957程继红,马颖亮,李高鹏基于混合整数规划模型的物流中心选址方法J海军航空工程学院学报,200722912948程冬时，张声年关于求解01型整数规划的若干问题J江西电力职业技术学院学报,2006331359李时求解01整数规划的一种新方法分层选优法J吉林工业大学学报，1993310刘晓惠,景清泉,霍俊爽基于01型整数规划的配送中心选址J物流与采购研究，2009214614811郜振华AHP和01整数规划方法在物流系统零售点选址中的应用研究J价值工程，20087798112丁小东,姚志刚,程高LINGO语言与01混合整数规划
16、选址模型的再结合J物流工程和管理，200910727513AKAUFMANNINTEGERANDMIXEDPROGRAMMING,THEORYANDAPPLICATIONSMACADEMIEPRESS，INCLONDONLTD，198214DENNISJS,RICHAROAMAMETHODOFDECOMPOSITIONFORINTEGERPROGRAMSJOPNSRES,1979,2738本科毕业设计（20届）01整数规划算法分析配送中心选址应用【摘要】本文分析了几种求解01整数规划最优解的算法，包括常用的穷举法以及分支定界法，还分析了隐枚举法，同时，还有分层优选法，和一种当决策变量（N10）
17、的改进方法。对这些算法9用同一个例子进行了比较，分析。同时，还求得一种01整数规划的算法改进，使计算量大大减少。最后，将隐枚举法运用到配送中心选址应用上。【关键词】01整数规划；算法；配送中心选址；【ABSTRACT】THISPAPERANALYZESSEVERALSOLVE01INTEGERPROGRAMMINGOPTIMALSOLUTIONALGORITHM,INCLUDINGCOMMONEXHAUSTIVELYMETHODANDBRANCHANDBOUNDMETHODFOR,ANALYZETHEIMPLICITEMUMERATIONMETHOD，,ATTHESAMETIME,ANDTHA
18、T,ANDALAYEREDWORTHYASDECISIONVARIABLEN10IMPROVINGMETHODSWITHTHESAMEEXAMPLEOFTHESEALGORITHMSARECOMPAREDANDANALYZEDATTHESAMETIME,ALSOGETA01INTEGERPROGRAMMINGALGORITHMIMPROVEDGREATLYREDUCECOMPUTATIONFINALLY,IMPLICITEMUMERATIONLAWTOAPPLYTOTHEDISTRIBUTIONCENTERSSITESELECTIONAPPLICATION【KEYWORDS】01INTEGER
19、PROGRAMMINGALGORITHMSDISTRIBUTIONCENTERLOCATION10目录摘要8ABSTRACT错误未定义书签。目录10101整数规划的概念112解01整数规划的方法1121穷举法1122分支定界法1223隐枚举法14231隐枚举法I15232隐枚举法16233隐枚举法III目标排序法1824分层优选法1925对于变量数目很大的新的解法2226算法的改进243模型建立配送中心选址应用2531假设2532宁波市配送中心选址模型及求解254总结28参考文献29致谢20附录错误未定义书签。11101整数规划的概念整数规划是数学规划的重要方面之一，许多重要的组合数学问题实质
20、上都是从属于它，然而目前求解还存在许多困难，基本上是采用穷举法。01整数规划是整数规划中最简单的一种，取0和1两种的整数规划问题01型整数规划是整数规划的特例，其数学模型的目标函数、约束条件与线性规划相同，不同的是其变量只能取0和1，分别表示两种截然相反的结果。01型整数规划应用很广，如土木工程系统的最优工程配置问题，城建规划中的居民点、给水点、加油站和商业网点的最优布局问题，均可应用01型整数规划求得最优解。01型整数规划的数学模型如下2解01整数规划的方法21穷举法解01整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得
21、最优解，这就需要检查变量取值的2N个组合。由于01型整数规划的变量个数有限且取值非0即1，所以不难将解的集合找出来，再检验每个解的可行性，凡符合全部约束条件者均为可行解，通过比较目标函数的值便可找到最优解，这个解法称为穷举法。当变量和约束条件很多时，其工作量是非常大的。现有如下的01整数规划模型例1求解123MIN432ZXXX1MAXMIN,1,2,01,1,2,NJJJJIJZIMJNCXXBXNIJJ1目标函数或或约束条件或A12123123232534433101JSTXXXXXXXXX或（J1,2,3）利用穷举法求解列表如下点（123,XXX）条件满足条件（0,0,0）（0,0,1）
22、（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，若其可行，则此解即为最优解，计算终止否则，按所谓“距离”，选定其中某个变量为“固定变量”，令其分别为0和1，将问题分枝成两个问题，而后分别对它们进行检验，即令非固定变量称为自由变量全部为0，检查它们与固定变量所组成的解是否可行若其可行，则此解就是目前最好的可行解，不再分枝，其相应的目标函数值
23、就是原问题的一个下界；否则，在余下的自由变量中，再选定某个为固定变量，把子问题再分枝，继续上面的过程，直至全部子问题不需再分枝，或没有自由变量为止此中最大的下界值所对应的可行解即为最优解。图1是深度为3的满二叉树。13如果一个深度为N1的满二叉树按上述方法顺序排列，并对任一节点I存在。1当I1时，I是根；2当I1时，如果I是偶数，该节点存贮的数据是0，否则存贮的数据是1。那么，从根节点到叶子的一条路径以下简称路径是N个01整数的组合，因而01整数规划的完全枚举可等价于满二叉树的遍历。设路径的节点依次为0，1,N，节点I对应于二叉树的节点LAI，并将路径节点I存贮的数据赋给IX，令从路径节点1I
24、到2I1I0Z；对剩余未经查验的含K个1的N位二进制数，只须就目标函数值大于11Z的解，查验其是否可行，一旦可行，则记其对应的目标函数值为12Z,依此类推，直至所有台K个1的N位二进制数全部查验完为止，并把最后所得的可行解的目标函数值改记为1Z；若此层无可行解，则记1Z0Z，转44若K11Z，则转第二层筛选；否则，若K11，11KJJC1Z，转第三层筛选,若1111MAX,KKJJJJCC1Z，则计算终止,1Z即为最优值，对应的解即为21最优解。第二层筛选取所有含有K1个1的N位二进制数为待检验的解2X，仿照第一层筛选的第3步仅就目标函数值大于1Z的解查验其是否可行找出其中可行解所对应的最大目
25、标函数值后，记为2Z；若此层无目标函数值大于1Z的可行解，则记2Z1Z；若K11，11KJJC2Z，则转第三层筛选；否则，若K2，21KJJC2Z，则记3Z2Z，转第四层筛选；若MAX11KJJC,21KJJC2Z，则计算终止，2Z即为最优值，对应的解即为最优解第三层筛选取所有含有K1个1的N位二进制数为待检验的解3X，仿照第一层筛选的第3步，仅就日标函数值大于2Z的解查验其是否可行，找出其中可行解所对应的最大目标函数值后，记为3Z；若此层无目标函数值大于2Z的可行解，则记3Z2Z；若K2N，21KJJC3Z，则转第四层筛选；否则，若K21，21KJJC3Z，则记4Z3Z，转第五层筛选21KJ
26、JC,21KJJC3Z，则计算终止，3Z即为最优值，对应的解即为最优解。依此类推，第四层筛选取所有含K2个1的N位二进制数为待检验的解4X；第五层筛选取所有舍K2个1的N位二进制数为待检验的解5X；直至选出最优值及最优解；或把所有N位二进制数全部分层筛选完毕，仍无可行解，则原问题无最优解分层优选法一开始就从使目标函数取最大值的解出发来查验，求解顺序也基本上都是按目标函数从大到小的顺序排列的，一旦发现可行解，该层其余未经检验过的解绝大部分都可22被过滤掉。利用分层优选法解例1，可以得到100,0,0XX，得到的最优解为_10,0,1X，Z2。25对于变量数目很大的新的解法设有如下01整数规划问题
27、1122MAXNNZCXCXCX其中01,2,01,2,1,2,01,2,KIJIKNIMJNIMCAB。目前解决01整数规划问题的常用方法主要有类似于解一般整数规划的分枝定界法和隐枚举法，前者本质上也是一种隐枚举法。对于变量数目较小的01整数规划问题，这两种方法都有较好的适用性，但若变量数目很大，则其计算量相当大，即使借助于计算机，也需耗费大量的求解时间，往往影响许多实际工作的具体实施。考虑到上述规划问题的特殊性，我们设计了一种一定情况下比分枝定界法和隐枚举法更有效的方法，其基本思路与分枝定界法有相似之处。利用变量只能取0或1两个值的特性，构造如图1所示的一棵树，图中每个顶点表示一个子集，圆
28、点后面的数字表示已选人的取值为1的变量的下标，圆点前面的数字表示可能进入而又尚未进人计算的取值为0的变量的下标。例如，顶点23N1表示只含变量子集；又如顶点N123N1表示含变量1X至1NX的子集，圆点前面的N表示沿这个顶点往下去，进入计算的变量只可能是N。为了求得最优解，我们先在该树中找出一个可行解和非可行解,以此为参照可剔除一些可行解和非可行解，仅验算一部分较好的可行解，就能定出最优解，从而减少了不少工作量。其具体步骤如下1111221112122222112212,01NNNNMMMNNMNAXAXAXBAXAXAXBAXAXAXBXXX或23图21检验顶点23N1,3N2,N是否为可行
29、解，若均不可行，则该规划问题无可行域即无最优解；否则，不失一般性可设23N1为可行解。2按该树顶点水平位置以从上至下从左至右的次序“垂直”地一支一支地验算该树各顶点是否为可行解,即深度优先搜索。从图1可看到最左边一支诸顶点的圆点后面数字依次为1，12，123，123N，紧挨的第二支对应的数字为124,，124N，再过来一支诸顶点对应的数字为125,，125N。以此类推，把该树视为家族的家谱，从“树根”即“祖父”开始，沿“父亲”到“长子”方向，访问验算下去。3若一直访问到某一支的端点为可行解，或该端点为非可行解但其“父亲”为可行解，则将此可行解及其对应的目标函数值记录下来，然后再转到该点的“父亲
30、”的“大弟弟”继续进行验算；若访问到某个非端点的分支结点为非可行解，且该结点的“父亲”为可行解，则将此可行解及其目标函数值记录下来T然后再转到该结点的“太弟弟”继续进行验算。由于该结点的“后代”也为非可行解，故不必再验算了。依次下来，若端点的“父亲”的“大弟弟”或结点的“大弟弟”都已访问完，则转到端点或结点的“祖父”的“大弟弟。4若有待验算的顶点中圆点后面的所有数字是已验算为可行解的某个顶点中圆点后面的数字的一部分，则这样的顶点也为可行解，但其目标函数值较已验算并记录的可行解的目标函数值小，不会是最优解，故不必验算和记录，只需往下继续验算其“后代即可。5按照以上次序，当所有的支都访问完时，比较
31、所有已记录的可行解及其目标函数值，则可得最优解，计算结束。运用此法再次求解例1得到根据之前对于变量数目很大的新的解法，构造如图所示的树求解；24由图可知，最优解为3121,0,0XXX；最优值Z2其实，在231这里时可行下面的就不需要再算，所以实际之进行了12次运算。26算法的改进对于之前的7种01整数规划算法，都有优势的地方也有劣势，现就对01整数规划的算法稍作改进，以使计算更简便。继续应用隐枚举法中的将决策变量系数从小到大或者从大到小排列计算最大或者最小值的思路。然后只要任何一个解遇到一个不满足条件即停止运算，这样就会避免不必要的计算。利用递推的方法当遇到满足所有条件的可行解时即为最优解。
32、利用例1举例因为要求得最小值，而且决策变量系数是从大到小排列的，所以从1X，2X，3X都取最小的0开始，很显然如果（1X，2X，3X）（0，0，0）代入满足所有约束条件时必定为最小值。现将其代入并且当遇到一个不满足约束条件是停止运算点123,XXX条件满足条件Z值（0,0,0）0用递推的方法将其中一个决策变量换成1，则3X1，而1X2X0，如果此解可行则必定得到最小值，必为最优值，代入得到点条件满足条Z值25123,XXX件（0,0,1）22可以得到（1X，2X，3X）（0，0，1）为可行解，即可推断为得到的解即为最优解。,MIN20,0,1TZX。运用此改进的方法只需7次运算，计算5个约束条
33、件。比之前的几种方法在求解此类问题时更简便，运算量更小。3模型建立配送中心选址应用31假设在给定某一地区所有备选点的地址集合中选出一定数目的地址作为配送中心,为城市内用户服务,故可不考虑运费问题,使在选出点建立的配送中心与各需求点和供货点形成的配送体系利润最大即可。为便于模型求解,同时使模型具有使用价值,作如下假设仅在一定的备选范围内考虑设置新的配送中心。一个配送中心可由多个供货点供货,一个用户的需求也可由多个配送中心提供。配送中心的固定投资费用已知。运输费用不计。能够实现预计的利润回报的选址地点为最优解。32宁波市配送中心选址模型及求解根据宁波市配送中心现状调查,了解物流需求量、起讫地点、运
34、输费用等有关数据,给出一种合理的算法,满足宁波市特有的社会环境与地理交通环境。在宁波市东、南、北三个地区建设城市综合配送中心。拟建中有6个点IA（I1,2,6）供选择。规定在东区,由1A，2A两个点中至多选一个在南区,由3A,4A两个点中至多选一个；在北区，由5A,6A两个点中至多选一个。1A点在江东第二实验小学附近,投资估计为1B100万元,每年可获利润估计为1C300万元。2A点在江东中心小学附近,投资估计为2B80万元,每年可获利润估计为2C240万元,3A在天一广场附近,投资估计为3B120万元,每年可获利润估计为3C350万元。4A点在南站附近,投资估计4B110万元,每年可获利润估
35、计为4C320万元。5A点在宁波大学附近,投资估计为5B130万元,26每年可获利润估计为5C370万元。6A点在红梅新村附近,投资估计为6B90万元,每年可获利润估计为6C270万元。投资总额不能超过B400万元。选择的地点应使年利润最大。01型整数规划数学模型的建立设变量1,0IIIAXA当点被选用（I1,2,6），当点没被选用,年利润Z表示目标,并使目标函数利润最大化。宁波市配送中心选址的数学模型为61MAXIIIZCX61123456400111101,2,6IIIISTIBXXXXXXXX或，点条件满足条件Z值261435,XXXXXX（0,0,0,0,0,0）0（0,0,0,0,0
36、,1）370130001。（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）9400227（0,1,1,0,1,0）920310111920（0,1,1,1,0,0）890300111890（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用隐枚举法求解数学模型根据运筹学的理论和方
37、法,求解上述01型整数规划数学模型比较有效的方法是隐枚举法,求解如下261435MAX240270300320350370ZXXXXXX26143578090100110120130140400XXXXXXX121XX341XX561XX101,2,6IIX或，根据条件有点条件满足条件Z值261435,XXXXXX（0,0,0,0,0,0）0（0,0,0,0,0,1）370130001。（0,0,0,1,1,1）104002。（0,0,1,0,1,1）1020350111102028改进过滤条件2614352402703003203503701020XXXXXX代替，继续进行。点条件满足条件Z
38、值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,XXXXXX（0,0,1,0,1,1），最优值MAXZ1020万元。所以宁波市东、南、北三处建立配送中心，可获得最高利润1020万元。从而确定了宁波市配送中心合适的选址地点。4总结如今对于01整数规划问题的算法已经总结了很多，有最基本的穷举法，分支定界法，到
39、延伸的隐枚举法，以及分层优选法和对于变量数目很多时的方法，通过之前的各种算法用同一个例子进行比较得到一般穷举法的计算量是最大的，计算过程也较复杂。用穷举法来求解需要检验2N个变量的组合，当N值很大时,是不可行的。而分支定界法则相对有条理，运算相对简化。29比较常用的是隐枚举法，这类方法是解01整数规划最常用的方法，而且对于隐枚举法有三种不断递进的方法隐枚举法I比分支定界和穷举法所用的运算次数少，数学模型无须转化成标准型，减少了人工处理的工作量，但是含有两个不确定性因素，直接影响到本解法对减少工作量的有效性；对隐枚举法II来说,所需检验的方案较少，这是其优点但在检验之前必须通过人工处理将数学模型
40、标准化,当问题复杂时,人工处理的工作量很大，且易出差错,这是其缺点之一。在具体操作过程中还存在如下问题,即此解法有效性的关键在于检验前必须排出一个能体现各解点Z值大小顺序的对各变量取值0或1的各种组合的检验顺序，当变量个数较多的时候，这是相当困难的。隐枚举法III求解例1时运算次数减少，隐枚举法III是非常简便而效的，它无须将数学模型转化为标准型，它保留了隐枚举法I的优点而克服了隐枚举法II的缺陷，它不需要过滤条件，也略去了用过滤条件检验每个目标函数的工作，自然也就排除了两个不确定性因素的干扰。这种直接以Z值大小编排检验顺序的解法，保持了隐枚举法II按序检验的优点，同时又排除了迂回排序和重复检
41、验带来的困扰。这种新的解法省略了所有需要人工处理的环节，对实施电算极为有利。分层优选法不必将线性规划化为标准型，在每一层中选择了高起点的过滤条件，找到最优解较快，但是分层优选法一般用于变量数较少，约束条件较多时；运用变量个数较大的方法则运算次数减少，而且此方法不仅能运用于决策变量较小的数学模型，更解决了决策变量个数较多时的模型。最后通过对于之前几种的算法的总结得出了一种改进方法，这种方法明显简化了运算过程，减少了运算量，不仅不用将数学模型转化成标准型，减少了人工处理的工作量，而且减少了一些不必要的运算步骤，克服了隐枚举法中的一些缺陷。但是也存在一些问题，比较适用于决策变量较少的情况，以及变量系
42、数为正的情况，局限性较大。参考文献1运筹学教材编写组运筹学M北京清华大学出版社，20052苟格整数规划中的割平面法与分枝定界法比较J四川达县师范高等专科学校学报，2005（2）18213林斐求解一类整数规划问题最优解的算法J东莞理工学院学报自,2006（52）4王淑英整数规划在制定防灾预案中的应用J北京教育学院学报自,2007516235顾治萍EXCEL在混合整数规划中的应用J上海交通大学，20082912306李炯城，鲍江宏组合优化中整数规划的数论解法J计算机工程与设计，200957程继红,马颖亮,李高鹏基于混合整数规划模型的物流中心选址方法J海军航空工程学院学报,200722912948程
43、冬时，张声年关于求解01型整数规划的若干问题J江西电力职业技术学院学报,2006331359李时求解01整数规划的一种新方法分层选优法J吉林工业大学学报，1993310刘晓惠,景清泉,霍俊爽基于01型整数规划的配送中心选址J物流与采购研究，2009214614811郜振华AHP和01整数规划方法在物流系统零售点选址中的应用研究J价值工程，20087798112丁小东,姚志刚,程高LINGO语言与01混合整数规划选址模型的再结合J物流工程和管理，200910727513AKAUFMANNINTEGERANDMIXEDPROGRAMMING,THEORYANDAPPLICATIONSMACADEMIEPRESS，INCLONDONLTD，198214DENNISJS,RICHAROAMAMETHODOFDECOMPOSITIONFORINTEGERPROGRAMSJOPNSRES,1979,273
