1、超市選址模型小組成員：高才萱：經(jīng)濟(jì)與工商管理學(xué)院國際經(jīng)濟(jì)與貿(mào)易專業(yè)彭愛軍：經(jīng)濟(jì)與工商管理學(xué)院國際經(jīng)濟(jì)與貿(mào)易專業(yè)吳質(zhì)：經(jīng)濟(jì)與工商管理學(xué)院電子商務(wù)專業(yè)摘要正確選址對(duì)于超市的成功運(yùn)營至關(guān)重要，是運(yùn)營決策中需要解決的首要問題。作為一個(gè) 最優(yōu)化問題，選址問題的制約條件用分析的方法不易處理，用窮舉的方法又因?yàn)闈撛诘倪x址 點(diǎn)有無窮多個(gè)也不易實(shí)現(xiàn)。本文引入圖論將難以用分析的方法處理的制約條件加以簡(jiǎn)化處理， 通過適當(dāng)?shù)募僭O(shè)規(guī)避大規(guī)模的潛在選址點(diǎn)，將復(fù)雜的問題簡(jiǎn)單化。針對(duì)不同的假設(shè)，給出四 種不同的超市選址模型，利用計(jì)算機(jī)編程給出令人滿意的解。關(guān)鍵詞選址、最短路徑、無向圖、重心問題的背景及提出眾所周知，選址是關(guān)系

2、到零售門店成功關(guān)鍵的關(guān)鍵因素之一。曾經(jīng)有句名言叫做“連鎖超市 成功的關(guān)鍵有3個(gè)條件，那就是選址，選址，還是選址!”由此可見，選址在連鎖商業(yè)的日 常經(jīng)營中的地位是多么的舉足輕重。因?yàn)檫x址是門店的重要工作，所以選址工作受到每個(gè)超 市管理者的關(guān)注和重視。好又多公司計(jì)劃在四川省南充市城區(qū)修建一到兩個(gè)大型超市，為了更好的實(shí)現(xiàn)最大化的收益， 該集團(tuán)委托本小組協(xié)助他們實(shí)現(xiàn)超市的最佳選址。好又多公司希望我們的選址位置需要滿足 以下兩點(diǎn)：給顧客提供充足的便利，便利程度主要指顧客到達(dá)超市的路途長短以及要盡可能的選在交 通比較發(fā)達(dá)的干道旁。顧客在按照便利原則(路徑最短原則)選擇超市時(shí)到達(dá)所選超市的客流量要盡量的大，

3、因 為到達(dá)超市的客流量直接影響到超市的贏利。資料數(shù)據(jù)說明為完成此項(xiàng)選址工作我們找來了市區(qū)地圖(見附圖1)，直接在圖上進(jìn)行選址是不現(xiàn)實(shí)的，所 以我們根據(jù)好又多集團(tuán)的要求1，僅保留了市區(qū)主干道，并且以干道交叉點(diǎn)為頂點(diǎn)，以干道 長度(由南充市市政工程處提供)為邊，把市區(qū)交通圖簡(jiǎn)化為圖1，同時(shí)要計(jì)算到達(dá)超市的 客流量還需要知道南充市的人口分布情況，該資料由南充市公安局戶籍科提供?；炯僭O(shè)與符號(hào)說明3.1、基本假設(shè)準(zhǔn)備新建的超市可以容納所有到來的顧客，可以滿足所有人的需求；超市選擇的最佳地址只受路徑長短的影響，與其他因素?zé)o關(guān)；各個(gè)區(qū)居民平均分布于各區(qū)；居民出行方式都選擇公交汽車，而公交汽車站點(diǎn)設(shè)立在各個(gè)

4、主干道的交叉處；居民在主 干道交接點(diǎn)處換乘汽車的時(shí)間忽略不計(jì)；所建立的任意兩個(gè)超市沒有任何區(qū)別，其選址也只受總路徑長度的影響，與其他任何因 素?zé)o關(guān)，人們只選擇距離自己位置最近的超市進(jìn)行購物消費(fèi)；3.2、符號(hào)說明為南充市各個(gè)區(qū)人口數(shù)；為坐標(biāo)系中各個(gè)鄉(xiāng)鎮(zhèn)中心點(diǎn)的坐標(biāo);（3）為第i點(diǎn)位置的標(biāo)示；（4）為頂點(diǎn)、點(diǎn)之間的最短路徑長度；（5）為通過頂點(diǎn)到達(dá)超市的人口數(shù)；（6）為分布在街道 兩旁的人口數(shù)；（7）為各區(qū)域所有頂點(diǎn)按照最短路徑到達(dá)點(diǎn)的路徑之和.（8）為各區(qū)域所有頂點(diǎn)按照最短路徑到達(dá)或點(diǎn)的路徑之和;（9）為各區(qū)域所有頂點(diǎn)按照最短路徑到達(dá)點(diǎn)的人口數(shù)；四、模型的建立和求解實(shí)際上該問題是圖論中的選址問題

5、：給出一個(gè)無向賦權(quán)圖，其中頂點(diǎn)集V代表所有的可能選 址處，也就是所有的干道交叉點(diǎn)，E是每一條干道，為權(quán)重，其中，為賦權(quán)圖中的標(biāo)識(shí)長 度，為各干道兩旁居住的人口數(shù)。我們需要作的任務(wù)是，找到一頂點(diǎn)子集，（其中k是商家 擬建的超市個(gè)數(shù)，具體由商家決定）使得在此點(diǎn)集中每個(gè)點(diǎn)建立超市使目標(biāo)值最優(yōu)。4.1模型一為了模型（一）的簡(jiǎn)單方便易操作，所以我們暫先不考慮道路、建筑物等其他因素的影響， 任何兩點(diǎn)之間可以直線行走。另外暫考慮人口在各個(gè)區(qū)域內(nèi)均勻分布，所以我們可以在城區(qū) 各個(gè)區(qū)中分別找出幾何中心位置集中代表該區(qū)人口的居住地點(diǎn)，進(jìn)行建模。以過一區(qū)幾何中心（1）為x軸，過三區(qū)幾何中心（3）為y軸，建立二維直角

6、坐標(biāo)系。圖中各區(qū)的幾何中心坐標(biāo)：（1，0）、（1.43，1.06）、（0，1.631）、（1.83，1.83）、（0.77，2.8）、（0.57，3.2）、（2.28，3.25）、（3.03，4.7）。各區(qū)所居住人口數(shù)：=2.18、=3.4379、=3.5561、=6.24808=4.4873、=3.4252、=7.7711、=4.4282（6）（7）（5）（3）（4）（2）（1）4.1.1模型建立目標(biāo)函數(shù)為：約束函數(shù)：4.1.2模型的求解 根據(jù)數(shù)學(xué)分析中關(guān)于多元函數(shù)最值的知識(shí)，最值只可能在邊界和極值點(diǎn)處達(dá)到，而本問題的 最優(yōu)解顯然不應(yīng)在邊界取到，另一方面我們可以看到函數(shù)的駐點(diǎn)是唯一的，而實(shí)際

7、問題的最 優(yōu)解又是必然存在的，所以我們下面求得的駐點(diǎn)一定是最優(yōu)值對(duì)應(yīng)的最優(yōu)值點(diǎn)：解得代入得：（X，y）=1.5499，2.5461 從實(shí)際情況上看我們這個(gè)點(diǎn)是1.5499, 2.5461，對(duì)應(yīng)與地圖上五星花園和儀鳳街之間，而 這一段恰恰是南充市最繁華的商業(yè)街區(qū)，可見我們的結(jié)果和現(xiàn)在的實(shí)際情況非常吻合。從上面的公式和數(shù)學(xué)分析的關(guān)于重心坐標(biāo)的計(jì)算的知識(shí)我們看出，在平面上選址實(shí)際上就是 找出所謂的“重心”位置，那么當(dāng)平面上各個(gè)點(diǎn)人口分布不均勻的時(shí)候，這個(gè)時(shí)候上面的公 式將不適用，而且通過數(shù)學(xué)推導(dǎo)也很難得到一個(gè)通用的公式，但是我們可以根據(jù)物理學(xué)的知 識(shí)采用的“懸掛法”來求重心位置。具體方法如下：首先，

8、根據(jù)實(shí)際的南充市地圖作一個(gè)均勻的、輕質(zhì)的摸板，然后根據(jù)人口分布的情況，在各 個(gè)居民點(diǎn)放置對(duì)應(yīng)成比例的砝碼，最后通過懸掛法找到我們的實(shí)物模型的重心，再對(duì)應(yīng)于實(shí) 際地點(diǎn)，這就是我們需要找到的選址點(diǎn)。模型的優(yōu)點(diǎn)：思路比較簡(jiǎn)單、計(jì)算比較方便，有個(gè)計(jì)算器即可，推廣之后的模型也不需要復(fù) 雜的計(jì)算和計(jì)算機(jī)編程。模型的缺點(diǎn)：首先地圖上的任何兩點(diǎn)之間不可能都能以直線的路徑行走;而且如果得到的“最 優(yōu)解”不在要求的干道交叉點(diǎn)，雖然我們可以把離該“最優(yōu)解”最近的路口作為一個(gè)近似解， 但可信度并不十分理想。為此我們建立模型二4.2模型二注意到問題本身兼有離散和連續(xù)的特征:可行點(diǎn)的選取是有限個(gè)的，只能選在干道的交叉處，

9、 這是離散的特征；人口均勻的分布在各個(gè)區(qū)，這又是連續(xù)的特征，所以這是一個(gè)既有離散又 有連續(xù)的混合模型。這方面的研究比較少，解決起來難度比較大。所以我們需要對(duì)問題加以 一定的簡(jiǎn)化。首先我們考慮到“人口均勻的分布在各區(qū)內(nèi)”這個(gè)條件直接處理起來比較麻煩，但是由于每 個(gè)人選擇乘公交車到達(dá)超市那么他們首先需要到達(dá)干道，然后按照到最近的路口乘公交車， 那么我們可以把從頂點(diǎn)乘公交車的人口作為的一個(gè)權(quán)值，這樣我們就把一個(gè)混合的規(guī)劃問 題轉(zhuǎn)化成一個(gè)離散的規(guī)劃問題。的計(jì)算：由于我們只有南充各個(gè)區(qū)的人口情況，所以我們只能假設(shè)南充各個(gè)區(qū)的人口均勻分 布在干道兩旁，另外一方面每一個(gè)人按照最近路徑選擇乘車點(diǎn)，所以我們可以

10、認(rèn)為每條街道 的人口數(shù)又平均分配在該干道的兩個(gè)頂點(diǎn)。所以其中為第j區(qū)的人口數(shù)。由此問題簡(jiǎn)化為：給出一個(gè)無向賦權(quán)圖。我們需要作的任務(wù)是，找到一頂點(diǎn)集，（其中k 是商家擬建的超市個(gè)數(shù)，具體由商家決定）使得在此點(diǎn)集中每個(gè)點(diǎn)建立超市使目標(biāo)值最優(yōu)。 下面的模型取4.2.1模型的建立 選擇下標(biāo)，使得=minLP其中， 為頂點(diǎn)、點(diǎn)之間的最短路徑長度; 為通過頂點(diǎn)到達(dá)超市的人口數(shù)。4.2.2模型求解求解這個(gè)模型關(guān)鍵在于兩個(gè)矩陣L和P的求法，具體算法如下：（1）任意兩點(diǎn)之間的最短通路構(gòu)成的矩陣L首先，將賦權(quán)圖中的長標(biāo)志為矩陣L=，如下：其次，令=出發(fā)，依次構(gòu)造出N個(gè)矩陣，。其中第k個(gè)矩陣=的元素 表示 從到而中

11、間點(diǎn)僅屬于到的k個(gè)點(diǎn)的所有通路中的最短通路長。已知=，第k個(gè)矩陣=定義如下：運(yùn)算過程從k=1開始，讓i、j分別取遍從1到N的所有值，然后k增加1，反復(fù)進(jìn)行，直到k=N時(shí)終止。這時(shí)=的元素就是從到的最短通路長。算法流程圖如下：（2）各個(gè)端點(diǎn)所擁有的人口數(shù)構(gòu)成的列矩陣P由公式我們可以得到矩陣求所有人到點(diǎn)最短路徑之和的算法流程圖是非是非結(jié)束（3）運(yùn)用計(jì)算機(jī)，得到 （20， 58） （20， 38） （20， 29） 其中（21，58）是所有點(diǎn)中的最優(yōu)解，“”表示優(yōu)先級(jí)數(shù)前者大于后者。由此，我們認(rèn)為其中（21，58）更具有合理性。模型的優(yōu)點(diǎn)：此模型考慮了建立多個(gè)超市情況，對(duì)于超市選址問題的解決。模型的

12、缺點(diǎn)：一個(gè)城市中的任何經(jīng)濟(jì)行為不可能沒有競(jìng)爭(zhēng)，而此模型中建立兩個(gè)超市必然要 有競(jìng)爭(zhēng)，我們忽略競(jìng)爭(zhēng)問題，是此模型的一大缺點(diǎn)。實(shí)際生活中，在南充市城區(qū)市場(chǎng)領(lǐng)域進(jìn)行經(jīng)濟(jì)行為的時(shí)候，市區(qū)內(nèi)已經(jīng)擁有一個(gè)或多個(gè)成熟 經(jīng)營的規(guī)模超市，在、點(diǎn)已經(jīng)存在這樣的超市。面對(duì)這樣實(shí)際背景，我們給出模型四。 4.4模型四根據(jù)好又多公司的要求我們?cè)凇Ⅻc(diǎn)已經(jīng)存在超市的情況下尋找建立“一個(gè)”超市的最優(yōu) 點(diǎn)，實(shí)際上使用我們下面的方法結(jié)合模型三，只需要對(duì)我們的模型稍加改動(dòng)，我們就可以得 到同時(shí)建立多個(gè)超市的最優(yōu)點(diǎn)。據(jù)假設(shè)（5），任何兩個(gè)超市之間沒有影響，也就是說在居民的眼里不存在區(qū)別。假定超市建 立在點(diǎn)：根據(jù)假設(shè)（5），對(duì)于點(diǎn)的人們來說，他們只會(huì)到?jīng)Q定的超市消費(fèi)。則點(diǎn)的居民到超市購物所走的路程為。4.4.1模型的建立選擇下標(biāo)，使得4.4.2、模型的求解 求解的算法流程圖是非是非結(jié)束通過計(jì)算機(jī)運(yùn)算得出如下幾個(gè)可以選擇的結(jié)果：通過分析，最終我們選定41模型的優(yōu)點(diǎn)：在這個(gè)模型中我們引入了競(jìng)爭(zhēng)，更加符合實(shí)際。模型的缺點(diǎn)：由于對(duì)超市的選址不僅僅依賴與路徑長短，還和交通、選址地點(diǎn)周圍人口的經(jīng) 濟(jì)狀況等有關(guān)，由于缺乏相關(guān)的數(shù)據(jù)，我們?cè)谶@個(gè)模型中都沒有涉及，相信如果有了相關(guān)的 數(shù)據(jù)我們可以做