下载文档原格式
运筹学案例分析报告—便民超市的网点布设班级：1516122组号：6姓名、学号（组长、分工）：吴锴楠151612219、建立数学模型（组员、分工）：张灿龙151612220、编写lingo程序（组员、分工）：游泽锋151612222、编写报告一、案例描述南平市规划在其远郊建一卫星城镇，下设20个街区，如图所示。
各街区居民数预期为1、4、9、13、17、20各12000人；2、3、5、8、11、14、19各14000人；6、7、10、12、15、16、18各15000人。
便民超市准备在上述街区进行布点。
根据方便就近的原则，在某一街区设点，该点将服务于该街区及相邻街区。
例如在编号为3的街区设一超市点，它服务的街区为1、2、3、4、6。
由于受到经费限制，便民超市将在上述20个街区内先设两个点。
请提供你的建议：在哪两个街区设点，使其服务范围的居民人数为最多。
二、案例中关键因素及其关系分析1、在某一街区设点，该点将服务于该街区及相邻街区（当街区i 或街区i 的相邻街区设网点时，街区i 受服务）。
当街区i 受服务时，受服务居民人数增加3、要求两个街区设点，使其服务范围的居民人数为最多三、模型构建 1、决策变量设置同时每一个街区有受服务和不收服务两种状态,故每个街区可以设置一个0-1变量：20），……1,2=（i 个街区不收服务i ，第0个街区受服务i ，第1xi ⎩⎨⎧=因为每一个街区有设为网点和不设为网点两种状态,故每个街区可以设置一个0-1变量：20），……1,2=（i 个街区不设网点i ，第0个街区设网点i ，第1yi ⎩⎨⎧= 2、目标函数的确定：街区i 受服务，受服务居民人数增加ai ，该案例目标为使服务范围的居民人数为最多，故目标函数可设为：∑==201* ax ixi ai z M 3、约束条件的确定i)便民超市将在20个街区内设两个点，由此可确定一个约束条件：∑==201i 20），……1,2=（i 2yiii ）当街区i 和它的相邻街区中设有一个或两个网点时，街区i 受服务，即街区i 和它的相邻街区对应的各个yi 加起来为1或2，此时xi 应为1；当街区i 和它的相邻街区中没有网点时，街区i 不受服务，即街区i 和它的相邻街区对应的各个yi 加起来为0，此时xi 应为0；用[m]表示不超过m 的最大整数，由此可确定20个约束条件：1)/2]+y20+y19+y18+y16+[(y14=x201)/2]+y20+y19+y18+[(y17=x191)/2]+y20+y19+y18+y17+y14+[(y12=x181)/2]+y19+y18+y17+y12+[(y10=x171)/2]+y20+y16+y15+[(y14=x161)/2]+y16+y15+y14+y13+y8+[(y7=x151)/2]+y20+y18+y16+y15+y14+y13+y12+[(y11=x141)/2]+y15+y14+y13+y11+y7+[(y6=x131)/2]+y17+y18+y14+y12+y11+[(y10=x121)/2]+14+13+12+y11+y10+y9+y6+[(y2=x111)/2]+y17+y12+y11+y10+[(y9=x101)/2]+y11+y10+y9+[(y2=x91)/2]+y15+y8+y7+[(y5=x81)/2]+y15+y13+y8+y7+y6+[(y5=x71)/2]+y13+y11+y7+y6+y4+y3+[(y2=x61)/2]+y8+y7+y5+[(y4=x51)/2]+y5+y6+y3+y4+[(y1=x41)/2]+y6+y4+y3+y2+[(y1=x31)/2]+y11+y9+y6+y3+y2+[(y1=x21)/2]+y4+y3+y2+[(y1=x14、数学模型构建综上，该案例的整个数学模型如下：∑==201* ax ixi ai z M s.t.⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎧=∑=20），……1,2=（i0或1=0或1，yi =xi 1)/2]+y20+y19+y18+y16+[(y14=x201)/2]+y20+y19+y18+[(y17=x191)/2]+y20+y19+y18+y17+y14+[(y12=x181)/2]+y19+y18+y17+y12+[(y10=x171)/2]+y20+y16+y15+[(y14=x161)/2]+y16+y15+y14+y13+y8+[(y7=x151)/2]+y20+y18+y16+y15+y14+y13+y12+[(y11=x141)/2]+y15+y14+y13+y11+y7+[(y6=x131)/2]+y17+y18+y14+y12+y11+[(y10=x121)/2]+14+13+12+y11+y10+y9+y6+[(y2=x111)/2]+y17+y12+y11+y10+[(y9=x101)/2]+y11+y10+y9+[(y2=x91)/2]+y15+y8+y7+[(y5=x81)/2]+y15+y13+y8+y7+y6+[(y5=x71)/2]+y13+y11+y7+y6+y4+y3+[(y2=x61)/2]+y8+y7+y5+[(y4=x51)/2]+y5+y6+y3+y4+[(y1=x41)/2]+y6+y4+y3+y2+[(y1=x31)/2]+y11+y9+y6+y3+y2+[(y1=x21)/2]+y4+y3+y2+[(y1=x120），……1,2=（i2yi 201i四、模型求解1、求解工具及适应性分析求解工具：Lingo11。
基于运筹学方法解物流配送中心选址问题刘倩;丁小妹【摘要】基于运筹学方法,提出了解决物流配送中心选址问题的模型,并结合实例提出了如何选址的方法.【期刊名称】《佳木斯大学学报（自然科学版）》【年(卷),期】2016(034)003【总页数】3页(P452-453,472)【关键词】运筹学;配送中心;0-1整数规划;Dijkstra方法【作者】刘倩;丁小妹【作者单位】武夷学院数学与计算机学院,福建武夷山354300;武夷学院数学与计算机学院,福建武夷山354300【正文语种】中文【中图分类】O232配送中心是集货物仓储、包装以及装卸等等服务功能为一身的现代物流设施，它是以货物配送为主要职能的物流据点。
在物流系统中，其连接着供货点和需求点，是两者之间的纽带，在物流网络中起着举足轻重的作用。
所谓物流配送中心选址问题指的是在一个具有若干供应点及若干需求点的经济区域内，如何选择一个理想的地址设置配送中心的问题[1]。
由于运筹学中的一部分理论与方法就是为了解决物流中的一些问题而发展起来的，因此在配送中心的建设过程中，我们应该重视运筹学的理论与方法的应用。
运筹学方法寻求以最少的人力和物力的投入而获得最优的经济效益的途径。
随着信息技术与计算机科学的发展和普及，以及物流运筹学的应用软件日趋成熟，这些都为解决配送中心选址问题提供了强有力的技术支持。
本文主要阐述了运用运筹学方法解决配送中心选址问题。
配送中心的布局及选址，对配2送中心功能的发挥以及综合效益的影响很大，因此科学合理的选址就显得尤为重要，这里提出的配送中心选址方法，是在依据了选址的一般原则的基础上，确定备选地址，把获得最优效益为目标，建立选址模型，并求解模型从而获得最佳配送中心的位置。
以某市为例，物流配送中心与货物的出发地和货物的消费地构成的系统图如图1，在图1中物流配送中心是货物供应地与消费点之间的货物集散点。
假设配送中心可以选择的地址有R个，分别用A1,A2,…,AR表示，它们的库存量分别为e1,e2,…,eR；货物的供应地有N个，分别用D1,D2,…,DN表示，它们的供应量分别是d1,d2,…,dN；产品的销售地共有M个，分别用C1,C2,…,CM表示，它们的销售量分别是c1,c2,…,cM. 所谓选址问题就是从这R个地址中选择若刚个最佳的地址建立配送中心，使得物流的费用达到最低。
（三）物流配送中心选址的主要方法与类型令狐采学1.选址方法类型近年来，随着选址理论迅速发展，各种各样的选址越来越多，层出不穷。
特别是计算机技术的发展与应用，促进了物流系统选址的理论发展，对不同方案的可行性分析提供了强有力的工具。
但是现阶段选址的理论方法大体上有以下几类:（1）运筹法运筹法是通过数学模型进行物流网点布局的方法。
采用这种方法首先根据问题的特征、己知条件以及内在的联系建立数学模型或者是图论模型。
然后对模型求解获得最佳布局方案。
采用这种方法的优点是能够获得较为精确的最优解缺乏是对一些复杂问题建立适当的模型比较困难，因而在实际应用中受到很大的限制。
解析法中最常用的有重心法和线性规划法。
（2）专家意见法专家意见法是以专家为索取信息的对象，运用专家的知识和经验考虑选址对象的社会环境和客观背景，直观地对选址对象进行综合分析研究寻求其特点和发展规律并进行选择的一类选址方法是专家选择法，其中最常用的有因素评分法和德尔菲法。
（3）仿真法仿真法是将实际问题用数学方法和逻辑关系表示出来然后通过模拟计算及逻辑推理确定最佳布局方案。
这种方法的优化是比较简单，缺点是选用这种方法进行选址，分析者必须提供预定的各种网点组合力案以供分析评价，从中找出最佳组合。
因此，决策的效果依赖于分析者预定的组合方案是否接近最佳方案该法是针对模型的求解而言的，是种逐次逼近的方法。
对这种方法进行反复判断实践修正直到满意为止。
该方法的优点是模型简单，需要进行方案组合的个数少，因而，容易寻求最佳的答案。
缺点是这种方法得出的答案很难保证是最优化的一般情况下只能得到满意的近似解用启发式进行选址，一般包括以下步骤:①定义一个计算总费用的方法；②制定评判准则；③规定方案改进的途径；④给出初始方案；⑤迭代求解。
2.典型物流中心选址决策方法（1）单点物流中心选址方法所谓单点网点选址，就是指在规划区域内设置网点的数目惟一的物流设施的选点问题，其中主要包含以下几种方法：①交叉中值法选址在城市内建立物流设施，不可能不受限制任意选址，可能的情况是只能沿着相互交叉的街道选择某一处地点。
连续点选址模型(1)交叉中值模型(Cross Median)交叉中值模型是用来解决连续点选址问题的一种十分有效的模型,它是利用选址距离进行计算的.通过交叉中值的方法可以对单一的选址问题在一个平面上的加权的选址距离进行最小化.其相应的目标函数为:Z=式中wn---需求点的总数目需要注意的是,这个目标函数可以用两种互不相干的部分来表达.在这个问题里面,最优位置也就是如下坐标组成的点考虑到或者同时两者可能是唯一或某一范围,最优的位置也相应的可能是一个点、或者是线、或者是一个区域。
（2）一元节点选址的重心法和微分法1、重心法重心法是一种模拟方法。
这种方法将物流系统中的需求点和资源点看成是分布在某一平面范围内的物流系统，各点的需求量和资源量分别看成物体的重量，物体系统的重心作为物流网点的最佳设置点，利用求物体系统的方法来确定物流网点的位置。
现仅讨论用重心法在计划区域内设置一个网点简单情况。
在某计划区内，有n个资源点和需求点，各点的资源量或需求量为它们各自的坐标是。
需设置一个网点，设网点的坐标为（x,y），网点至资源点或需求点的运费率为根据求平面中物体系统重心的方法有：代入数字，实现求得（x,y）的值即为所求物流中心网点位置的坐标，记为重心法的最大特点是计算方法较简单，但这种方法并不能求出精确的最佳网点位置（当然这种精确位置有时可能是没有实用价值的）。
因为这一方法将纵向和横向的距离视为相互独立的量，与实际是不相符的，往往其结果在现实环境中不能实现,因此只能作为一种参考结果。
2、微分法现举例说明选址问题模型的建立方法。
某公司准备建流通加工型配送中心，向各客户供应商品，现需确定配送中心建在什么位置，才能使配送中心向各客户供应商品的费用最低。
设配送中心向第i个客户的商品供应量为；单位商品的运费为采用笛卡尔坐标系，设配送中心位置的坐标为p(x,y),各客户位置的坐标为，则第i个客户与配送中心的距离可由解析几何的两点间距离公式求得：配送中心向第i个客户供应商品的运费为：配送中心向各个客户供应商品的总运费为：因此，该问题的目标函数为：根据该模型，选择适当的x、y就可使C达到最小。
图上的路选址问题与连通p-中心和p-中位问题选址问题是运筹学中重要的问题之一.设施选址问题的应用十分广泛,从城市,产业带,经济技术开发区到机场,水利设施,销售网点以及仓库都涉及到选址问题,涉及经济,政治,社会,管理,心理及工程地质等多门学科.本文主要研究了一些特殊图上路选址问题,连通p-中心和p-中位选址问题.人们已经证明路选址问题和连通p-中心和p-中位选址问题在一般图上都是NP-困难问题,因此考虑这些问题在某些图类上的多项式算法就成为有意义的问题.本文着重讨论了树(tree),区间图(interval graph),圆弧图(circular-arc graph)和块图(block-graph)等重要图类上的算法设计问题.首先,我们介绍了选址问题的背景和本文涉及的相关记号及术语,并提出了本文研究的主要问题.本文所做的主要研究工作如下：第二章,研究了树上的半厌恶型p-路选址问题.当p=2时,即树上的半厌恶型2-路选址问题,对该问题的MWD模型和WMD模型,分别设计了O(n2)和O(n3)时间算法.对p>2时,考虑相交p-路和不相交p-路这两种特殊的情形.树上的半厌恶型相交p-路问题的MWD模型和WMD模型都可以转化为树上的k-子树核心问题,由此可证明该问题可以在多项式时间内求解.对树上的半厌恶型不相交p-路选址问题的MWD模型,我们设计了O(np+1)时间算法；而对于该问题的WMD模型,给出了其最优解得一些性质.第三章,应用鲁棒优化理论研究了带区间权重的树上的鲁棒核心选址问题,其中允许顶点的权重为负数.对绝对鲁棒核心选址问题设计了O(n2)时间算法.对偏差鲁棒核心选址问题,证明了该问题的计算复杂性为O(n3).第四章,讨论区间图和圆弧图上的连通p-中心和p-中位选址问题.在区间图上,证明了连通p-中心问题和连通p-中位问题的计算复杂性都是O(n).在圆弧图上,证明了连通p-中心问题可以在O(n)时间内求解,而连通p-中位问题可以在O(n2)时间内求解.第五章,讨论了块图上的连通p-中心和p-中位选址问题.对连通p-中心问题给出了O(mn logn)时间算法,对连通p-中位问题,证明了该问题线性时间可解.对双目标规划：连通p-中心-中位问题,证明了该问题的计算复杂性为O(n2),并且帕雷托最优解的个数不超过n个.对厌恶型连通p-中心和p-中位问题分别给出了O(mn)时间算法和O(p2mn)的拟多项式时间算法.最后给出了需要进一步研究的问题.。
