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

1、-运筹学案例分析报告便民超市的网点布设班级：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、

2、3、4、6。由于受到经费限制，便民超市将在上述20个街区先设两个点。请提供你的建议：在哪两个街区设点，使其效劳围的居民人数为最多。二、案例中关键因素及其关系分析1、在*一街区设点，该点将效劳于该街区及相邻街区当街区i或街区i的相邻街区设网点时，街区i受效劳。当街区i受效劳时，受效劳居民人数增加ai，各街区居民数预期不同，具体见下表：设网点的街区编号i该街区居民数预期ai人受效劳的街区编号1120001、2、3、4;2140001、2、3、6、9、11;3140001、2、3、4、6;4120001、4、3、6、5;5140004、5、7、8;6150002、3、4、6、7、11、13;7150

3、005、6、7、8、13、15;8140005、7、8、15;9120002、9、10、11;10150009、10、11、12、17;11140002、6、9、10、11、12、13、14;121500010、11、12、14、18、17;13120006、7、11、13、14、15;141400011、12、13、14、15、16、18、20;15150007、8、13、14、15、16;161500014、15、16、20;171200010、12、17、18、19;181500012、14、17、18、19、20;191400017、18、19、20;201200014、16、18、1

4、9、20;2、由于受到经费限制，便民超市将在上述20个街区先设两个点。3、要求两个街区设点，使其效劳围的居民人数为最多三、模型构建1、决策变量设置同时每一个街区有受效劳和不收效劳两种状态,故每个街区可以设置一个0-1变量：因为每一个街区有设为网点和不设为网点两种状态,故每个街区可以设置一个0-1变量：2、目标函数确实定：街区i受效劳，受效劳居民人数增加ai，该案例目标为使效劳围的居民人数为最多，故目标函数可设为：3、约束条件确实定i)便民超市将在20个街区设两个点，由此可确定一个约束条件：ii当街区i和它的相邻街区中设有一个或两个网点时，街区i受效劳，即街区i和它的相邻街区对应的各个yi加起来

5、为1或2，此时*i应为1；当街区i和它的相邻街区中没有网点时，街区i不受效劳，即街区i和它的相邻街区对应的各个yi加起来为0，此时*i应为0；用m表示不超过m的最大整数，由此可确定20个约束条件：4、数学模型构建综上，该案例的整个数学模型如下：s.t.四、模型求解1、求解工具及适应性分析求解工具：Lingo11。2、求解过程分析把上面的方程的用lingo写出来，然后在设置为全局最优解，最后运行求解，我们的编程程序如下：ma*=*1*12+*2*14+*3*14+*4*12+*5*14+*6*15+*7*15+*8*14+*9*12+*10*15+*11*14+*12*15+*13*12+*14

6、*14+*15*15+*16*15+*17*12+*18*15+*19*14+*20*12;y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12+y13+y14+y15+y16+y17+y18+y19+y20=2;*1=floor(y1+y2+y3+y4+1)/2);*2=floor(y1+y2+y3+y6+y9+y11+1)/2);*3=floor(y1+y2+y3+y4+y6+1)/2);*4=floor(y1+y4+y3+y6+y5+1)/2);*5=floor(y4+y5+y7+y8+1)/2);*6=floor(y2+y3+y4+y6+y7+y11+y13+1

7、)/2);*7=floor(y5+y6+y7+y8+y13+y15+1)/2);*8=floor(y5+y7+y8+y15+1)/2);*9=floor(y2+y9+y10+y11+1)/2);*10=floor(y9+y10+y11+y12+y17+1)/2);*11=floor(y2+y6+y9+y10+y11+y12+y13+y14+1)/2);*12=floor(y10+y11+y12+y14+y18+y17+1)/2);*13=floor(y6+y7+y11+y13+y14+y15+1)/2);*14=floor(y11+y12+y13+y14+y15+y16+y18+y20+1)/

8、2);*15=floor(y7+y8+y13+y14+y15+y16+1)/2);*16=floor(y14+y15+y16+y20+1)/2);*17=floor(y10+y12+y17+y18+y19+1)/2);*18=floor(y12+y14+y17+y18+y19+y20+1)/2);*19=floor(y17+y18+y19+y20+1)/2);*20=floor(y14+y16+y18+y19+y20+1)/2);3、求解结果及分析经过运行得到的结果为：182，即效劳围居民人数最多为182*103；其中y6=y14=1,y1=y2=y3=y4=y5=y7=y8=y9=y10=y

9、11=y12=y13=y15=y16y=17=y18=y19=y20=0即在第6和第14街区设置网点；其中*2=*3=*4=*6=*7=*11=*12=*13=*14=*15=*16=*18=*20=1,*1=*5=*8=*9=*10=*17=*19=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街区设置网点，使效劳围的居民人数为最多，为18

10、2*103.2、遇到的问题及解决方法刚开场的时候我们遇到的第一个问题就是如何把*i和yi联系起来，使得满足当街区i和它的相邻街区中设有一个或两个网点时，即街区i和它的相邻街区对应的各个yi有为1的时候*i=1，当街区i和它的相邻街区中没有网点时，即街区i和它的相邻街区对应的各个yi都为0时，*i=0；于是我们想把目标规划的的最大化转变为最小化，利用yi<M*i把*i和yi联系起来，于是我们利用三个效劳人数中的ai，减去他们三个中的最大值作为新的ai，这样就能求原规划的最大值就是求新规划的最小值了，但是后来我们经过运算发现得出来的结果是错误的，我们重新讨论了一下，发现那样做的话，新的目标规

11、划里的ai的比例会与原来ai的比例不一样，而我们也没有找出能使得到新的ai比例一样的方法，所以我们最终放弃了这种转变规划的方法。接着我们经过讨论得出了另外一种方法，就是把每个*i能效劳到的所能对应的选点列出来相加，而得到下面原始的目标函数：Ma*z=(y1+y2+y3+y4+1)/2*1*12+(y1+y2+y3+y6+y9+y11+1)/2*2*14+(y1+y2+y3+y4+y6+1)/2*3*14+(y1+y4+y3+y6+y5+1)/2*4*12+(y4+y5+y7+y8+1)/2*5*14+(y2+y3+y4+y6+y7+y11+y13+1)/2*6*15+(y5+y6+y7+y8+

12、y13+y15+1)/2*7*15+(y5+y7+y8+y15+1)/2*8*14+(y2+y9+y10+y11+1)/2*9*12+(y9+y10+y11+y12+y17+1)/2*10*15+(y2+y6+y9+y10+y11+12+13+14+1)/2*11*14+(y10+y11+y12+y14+y18+y17+1)/2*12*15+(y6+y7+y11+y13+y14+y15+1)/2*13*12+(y11+y12+y13+y14+y15+y16+y18+y20+1)/2*14*14+(y7+y8+y13+y14+y15+y16+1)/2*15*15+(y14+y15+y16+y20+1)/2*16*15+(y10+y12+y17+y18+y19+1)/2*17*12+(y12+y14+y17+y18+y19+y20+1)/2*18*15+(y17+y18+y19+y20+1