运筹学案例分析三便民超的网点布设问题

1、运筹学案例分析报告 便民超市的网点布设 班级： 1516122 组号： 6 姓名、学号 （组长、分工） ：吴锴楠、建立数学模型 （组员、分工） ：张灿龙、编写 lingo 程序 （组员、分工） ：游泽锋、编写报告 一、案例描述 南平市规划在其远郊建一卫星城镇，下设 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 的街区 设一超市

2、点，它服务的街区为 1、2、3、4、6。由于受到经费限制，便民超市将在上述 20 个街区内先设两个点。 请提供你的建议：在哪两个街区设点，使其服务范围的居民人数为最多。 二、案例中关键因素及其关系分析 1、在某一街区设点，该点将服务于该街区及相邻街区（当街区 i 或街区 i 的相邻 街区设网点时，街区 i 受服务）。当街区 i 受服务时，受服务居民人数增加 ai ，各街区 居民数预期不同，具体见下表： 设网点的街 区编号 i 该街区居民数预 期ai （人） 受服务的街区编号 1 12000 1、2、3、4; 2 14000 1、2、3、6、9、11; 3 14000 1、2、3、4、 6; 4

3、 12000 1、4、3、6、 5; 5 14000 4、5、7、8; 6 15000 2、3、4、6、7、11 、13; 7 15000 5、6、7、8、13 、15; 8 14000 5、7、8、15; 9 12000 2、9、10 、11; 10 15000 9、10、11 、12、17; 11 14000 2、6、9、10、11、12 、 13 、 14; 12 15000 10、11、12、14、18 、17; 13 12000 6、7、11、13 、14、15; 14 14000 11、12、13、14、15、16 、18 、 20; 15 15000 7、8、13、14 、15、

4、16; 16 15000 14 、15 、16 、20; 17 12000 10 、12 、17 、18 、19; 18 15000 12、14、17、18、19 、20; 19 14000 17 、18 、19 、20; 20 12000 14 、16 、18 、19 、20; 2、由于受到经费限制，便民超市将在上述 20 个街区内先设两个点 3、要求两个街区设点，使其服务范围的居民人数为最多 三、模型构建 1、决策变量设置 同时每一个街区有受服务和不收服务两种状态 ,故每个街区可以设置一个 0-1 变量： 因为每一个街区有设为网点和不设为网点两种状态 , 故每个街区可以设置一个 0-1 变

5、 量： 2、目标函数的确定： 街区 i 受服务，受服务居民人数增加 ai ，该案例目标为使服务范围的居民人数为最多， 故目标函数可设为： 3、约束条件的确定 i) 便民超市将在 20 个街区内设两个点，由此可确定一个约束条件： ii )当街区 i 和它的相邻街区中设有一个或两个网点时，街区 i 受服务，即街区 i 和 它的相邻街区对应的各个 yi 加起来为 1或2，此时xi 应为1；当街区i 和它的相邻街 区中没有网点时，街区 i 不受服务，即街区 i 和它的相邻街区对应的各个 yi 加起来为 0，此时 xi 应为 0；用m表示不超过 m的最大整数，由此可确定 20 个约束条件： 4、数学模型

6、构建 综上，该案例的整个数学模型如下： s.t. 四、模型求解 1、求解工具及适应性分析 求解工具： Lingo11 。 2、求解过程分析 把上面的方程的用 lingo 写出来，然后在设置为全局最优解，最后运行求解，我 们的编程程序如下： max=x1*12+x2*14+x3*14+x4*12+x5*14+x6*15+x7*15+x8*14+x9*12+x10*15+x11*14+x1 2*15+x13*12+x14*14+x15*15+x16*15+x17*12+x18*15+x19*14+x20*12; y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12+y13+

7、y14+y15+y16+y17+y18+y19+y20=2; x1= floor (y1+y2+y3+y4+1)/2); x2= floor (y1+y2+y3+y6+y9+y11+1)/2); x3= floor (y1+y2+y3+y4+y6+1)/2); x4= floor (y1+y4+y3+y6+y5+1)/2); x5= floor (y4+y5+y7+y8+1)/2); x6= floor (y2+y3+y4+y6+y7+y11+y13+1)/2); x7= floor (y5+y6+y7+y8+y13+y15+1)/2); x8= floor (y5+y7+y8+y15+1)/

8、2); x9= floor (y2+y9+y10+y11+1)/2); x10= x11= floor floor (y9+y10+y11+y12+y17+1)/2); (y2+y6+y9+y10+y11+y12+y13+y14+1)/2); x12= x13= x14= x15= x16= x17= x18= floor floor floor floor floor floor floor (y10+y11+y12+y14+y18+y17+1)/2); (y6+y7+y11+y13+y14+y15+1)/2); (y11+y12+y13+y14+y15+y16+y18+y20+1)/2);

9、 (y7+y8+y13+y14+y15+y16+1)/2); (y14+y15+y16+y20+1)/2); (y10+y12+y17+y18+y19+1)/2); (y12+y14+y17+y18+y19+y20+1)/2); x19= x20= floor floor (y17+y18+y19+y20+1)/2); (y14+y16+y18+y19+y20+1)/2); 3、求解结果及分析 经过运行得到的结果为： 182，即服务范围内居民人数最多为 182*103； 其中 y6=y14=1, y1=y2=y3=y4=y5=y7=y8=y9=y10=y11=y12=y13=y15=y16y=

10、17=y18=y19=y20=0 即在第 6 和第 14街区设置网点； 其中 x2=x3=x4=x6=x7=x11=x12=x13=x14=x15=x16=x18=x20=1, x1=x5=x8=x9=x10=x17=x19=0 即第 2、3、4、6、7、11、12、13、14、15、16、18、20 街区的居民受服务，第 1、5、 8、9、10、17、19 街区的居民不受服务。 五、结论 1、决策效果（结果）的评价 通过严格的案例分析以及我们组全体成员的研究讨论、反思修正以及 lingo 软件的精 密的计算，本案例得出最佳决策结果，在第 6和第 14街区设置网点，使服务范围的居 民人数为最多

11、，为 182*103. 2、遇到的问题及解决方法 刚开始的时候我们遇到的第一个问题就是如何把 xi 和 yi 联系起来，使得满足当街区 i 和它的相邻街区中设有一个或两个网点时， 即街区 i 和它的相邻街区对应的各个 yi 有 为 1 的时候 xi=1 ，当街区 i 和它的相邻街区中没有网点时，即街区 i 和它的相邻街区 对应的各个 yi 都为 0 时， xi=0 ；于是我们想把目标规划的的最大化转变为最小化，利 用 yiM*xi 把 xi 和 yi 联系起来，于是我们利用三个服务人数中的 ai ，减去他们三个 中的最大值作为新的 ai ，这样就能求原规划的最大值就是求新规划的最小值了，但是

12、后来我们经过运算发现得出来的结果是错误的，我们重新讨论了一下，发现那样做的 话，新的目标规划里的 ai 的比例会与原来 ai 的比例不相同，而我们也没有找出能使 得到新的 ai 比例相同的方法，所以我们最终放弃了这种转变规划的方法。接着我们经 过讨论得出了另外一种方法，就是把每个 xi 能服务到的所能对应的选点列出来相加， 而得到下面原始的目标函数： Max z=(y1+y2+y3+y4+1)/2*x1*12+(y1+y2+y3+y6+y9+y11+1)/2*x2*14+(y1+y2+y3+y4+ y6+1)/2*x3*14+(y1+y4+y3+y6+y5+1)/2*x4*12+(y4+y5+

13、y7+y8+1)/2*x5*14+(y2 +y3+y4+y6+y7+y11+y13+1)/2*x6*15+(y5+y6+y7+y8+y13+y15+1)/2*x7*15+(y5+y7 +y8+y15+1)/2*x8*14+(y2+y9+y10+y11+1)/2*x9*12+(y9+y10+y11+y12+y17+1)/2 *x10*15+(y2+y6+y9+y10+y11+12+13+14+1)/2*x11*14+(y10+y11+y12+y14+y18+y17 +1)/2*x12*15+(y6+y7+y11+y13+y14+y15+1)/2*x13*12+(y11+y12+y13+y14+y15+y 16+y18+y20+1)/2*x14*14+(y7+y8+y13+y14+y15+y16+1)/2*x15*15+(y14+y15+y16 +y20+1)/2*x16*15+(y10+y12+y17+y18+y19+1)/2*x17*12+(y12+y14+y17+y18+y19 +y20+1)/2*x18*15+(y17+y18+y19+y20+