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

1、-運(yùn)籌學(xué)案例分析報(bào)告便民超市的網(wǎng)點(diǎn)布設(shè)班級(jí)：1516122組號(hào)：6、*組長(zhǎng)、分工：吳鍇楠151612219、建立數(shù)學(xué)模型組員、分工：燦龍151612220、編寫lingo程序組員、分工：游澤鋒151612222、編寫報(bào)告一、案例描述市規(guī)劃在其遠(yuǎn)郊建一衛(wèi)星城鎮(zhèn)，下設(shè)20個(gè)街區(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ìn)展布點(diǎn)。根據(jù)方便就近的原則，在*一街區(qū)設(shè)點(diǎn)，該點(diǎn)將效勞于該街區(qū)及相鄰街區(qū)。例如在編號(hào)為3的街區(qū)設(shè)一超市點(diǎn)，它效勞的街區(qū)為1、2、

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

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

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

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