運籌學(xué),案例分析三：便民超市的網(wǎng)點布設(shè)問題

1、-運籌學(xué)案例分析報告便民超市的網(wǎng)點布設(shè)班級：1516122組號：6、*組長、分工：吳鍇楠151612219、建立數(shù)學(xué)模型組員、分工：燦龍151612220、編寫lingo程序組員、分工：游澤鋒151612222、編寫報告一、案例描述市規(guī)劃在其遠郊建一衛(wèi)星城鎮(zhèn)，下設(shè)20個街區(qū)，如下列圖。各街區(qū)居民數(shù)預(yù)期為1、4、9、13、17、20各12000人；2、3、5、8、11、14、19各14000人；6、7、10、12、15、16、18各15000人。便民超市準(zhǔn)備在上述街區(qū)進展布點。根據(jù)方便就近的原則，在*一街區(qū)設(shè)點，該點將效勞于該街區(qū)及相鄰街區(qū)。例如在編號為3的街區(qū)設(shè)一超市點，它效勞的街區(qū)為1、2、

2、3、4、6。由于受到經(jīng)費限制，便民超市將在上述20個街區(qū)先設(shè)兩個點。請?zhí)峁┠愕慕ㄗh：在哪兩個街區(qū)設(shè)點，使其效勞圍的居民人數(shù)為最多。二、案例中關(guān)鍵因素及其關(guān)系分析1、在*一街區(qū)設(shè)點，該點將效勞于該街區(qū)及相鄰街區(qū)當(dāng)街區(qū)i或街區(qū)i的相鄰街區(qū)設(shè)網(wǎng)點時，街區(qū)i受效勞。當(dāng)街區(qū)i受效勞時，受效勞居民人數(shù)增加ai，各街區(qū)居民數(shù)預(yù)期不同，具體見下表：設(shè)網(wǎng)點的街區(qū)編號i該街區(qū)居民數(shù)預(yù)期ai人受效勞的街區(qū)編號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、由于受到經(jīng)費限制，便民超市將在上述20個街區(qū)先設(shè)兩個點。3、要求兩個街區(qū)設(shè)點，使其效勞圍的居民人數(shù)為最多三、模型構(gòu)建1、決策變量設(shè)置同時每一個街區(qū)有受效勞和不收效勞兩種狀態(tài),故每個街區(qū)可以設(shè)置一個0-1變量：因為每一個街區(qū)有設(shè)為網(wǎng)點和不設(shè)為網(wǎng)點兩種狀態(tài),故每個街區(qū)可以設(shè)置一個0-1變量：2、目標(biāo)函數(shù)確實定：街區(qū)i受效勞，受效勞居民人數(shù)增加ai，該案例目標(biāo)為使效勞圍的居民人數(shù)為最多，故目標(biāo)函數(shù)可設(shè)為：3、約束條件確實定i)便民超市將在20個街區(qū)設(shè)兩個點，由此可確定一個約束條件：ii當(dāng)街區(qū)i和它的相鄰街區(qū)中設(shè)有一個或兩個網(wǎng)點時，街區(qū)i受效勞，即街區(qū)i和它的相鄰街區(qū)對應(yīng)的各個yi加起來

5、為1或2，此時*i應(yīng)為1；當(dāng)街區(qū)i和它的相鄰街區(qū)中沒有網(wǎng)點時，街區(qū)i不受效勞，即街區(qū)i和它的相鄰街區(qū)對應(yīng)的各個yi加起來為0，此時*i應(yīng)為0；用m表示不超過m的最大整數(shù)，由此可確定20個約束條件：4、數(shù)學(xué)模型構(gòu)建綜上，該案例的整個數(shù)學(xué)模型如下：s.t.四、模型求解1、求解工具及適應(yīng)性分析求解工具：Lingo11。2、求解過程分析把上面的方程的用lingo寫出來，然后在設(shè)置為全局最優(yōu)解，最后運行求解，我們的編程程序如下：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、求解結(jié)果及分析經(jīng)過運行得到的結(jié)果為：182，即效勞圍居民人數(shù)最多為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街區(qū)設(shè)置網(wǎng)點；其中*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街區(qū)的居民受效勞，第1、5、8、9、10、17、19街區(qū)的居民不受效勞。五、結(jié)論1、決策效果結(jié)果的評價通過嚴(yán)格的案例分析以及我們組全體成員的研究討論、反思修正以及l(fā)ingo軟件的精細的計算，本案例得出最正確決策結(jié)果，在第6和第14街區(qū)設(shè)置網(wǎng)點，使效勞圍的居民人數(shù)為最多，為18

10、2*103.2、遇到的問題及解決方法剛開場的時候我們遇到的第一個問題就是如何把*i和yi聯(lián)系起來，使得滿足當(dāng)街區(qū)i和它的相鄰街區(qū)中設(shè)有一個或兩個網(wǎng)點時，即街區(qū)i和它的相鄰街區(qū)對應(yīng)的各個yi有為1的時候*i=1，當(dāng)街區(qū)i和它的相鄰街區(qū)中沒有網(wǎng)點時，即街區(qū)i和它的相鄰街區(qū)對應(yīng)的各個yi都為0時，*i=0；于是我們想把目標(biāo)規(guī)劃的的最大化轉(zhuǎn)變?yōu)樽钚』?，利用yi<M*i把*i和yi聯(lián)系起來，于是我們利用三個效勞人數(shù)中的ai，減去他們?nèi)齻€中的最大值作為新的ai，這樣就能求原規(guī)劃的最大值就是求新規(guī)劃的最小值了，但是后來我們經(jīng)過運算發(fā)現(xiàn)得出來的結(jié)果是錯誤的，我們重新討論了一下，發(fā)現(xiàn)那樣做的話，新的目標(biāo)規(guī)

11、劃里的ai的比例會與原來ai的比例不一樣，而我們也沒有找出能使得到新的ai比例一樣的方法，所以我們最終放棄了這種轉(zhuǎn)變規(guī)劃的方法。接著我們經(jīng)過討論得出了另外一種方法，就是把每個*i能效勞到的所能對應(yīng)的選點列出來相加，而得到下面原始的目標(biāo)函數(shù)：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