第三章-選址模型及應用(ppt可編輯修改)課件

1、第三章 選址模型及應用雙擊添加標題文字3.1 選址的意義3.2 選址決策的影響因素3.3 選址模型的分類3.4 選址中的距離計算3.5 選址模型3.6 實例分析3.1 選址的意義選址在整個物流系統(tǒng)中占有非常重要的地位，主要屬于物流管理戰(zhàn)略層的研究問題。選址決策就是要確定所要分配的設施的數(shù)量、位置以及分配方案。這些設施主要指物流系統(tǒng)中的節(jié)點，如制造商、供應商、倉庫、配送中心、零售商網(wǎng)點等。3.1 選址的意義設施數(shù)量與客戶響應時間快速響應客戶需求是競爭因素之一快速響應客戶需求與節(jié)點設施設置的數(shù)量有關期望的響應時間設施數(shù)量3.1 選址的意義選址與庫存、運輸成本存在密切聯(lián)系，選址就是要在設施數(shù)量和成本

2、中求得最佳。設施數(shù)量庫存成本設施數(shù)量運輸成本設施數(shù)量設施成本設施數(shù)量總成本響應時間3.1 選址的意義就供應鏈系統(tǒng)而言，核心企業(yè)的選址決策會影響所有供應商物流系統(tǒng)的選址決策。3.2 選址的影響因素選址決策影響因素大致可分為外部因素及內(nèi)部因素兩大類選址決策影響因素外部因素宏觀政治因素政權、法制、政策等宏觀經(jīng)濟因素稅收、關稅、匯率等基礎設施交通設施、通信設施自然環(huán)境與社會環(huán)境如勞動力成本與質(zhì)量市場環(huán)境競爭對手、供應商、客戶等內(nèi)部因素企業(yè)發(fā)展戰(zhàn)略如制造業(yè)企業(yè)選擇勞動密集/技術密集發(fā)展戰(zhàn)略；如商業(yè)服務業(yè)選擇連鎖便利店/超市的發(fā)展戰(zhàn)略3.2 選址的影響因素選址決策包括地區(qū)選擇和地點選擇，二者需要考慮的因素

3、有所不同。地區(qū)選擇要考慮的是宏觀因素；地點選擇要考慮的是微觀因素。選址決策影響因素地區(qū)選擇（1）政策導向（2）市場情況（3）社會環(huán)境（4）資源條件（5）基礎設施和配套供應（6）上下游企業(yè)關系地點選擇（1）區(qū)域規(guī)劃 （2）地形地貌（3）面積與外形（4）外部銜接（5）地質(zhì)條件（6）氣象及輻射（7）地下水與洪水（8）地震3.2 選址的影響因素按照影響因素的性質(zhì)的不同，可把影響因素分成兩大類：即成本因素和非成本因素。還可以根據(jù)因素對設施選址的重要性，分為：關鍵因素、重要因素、次要因素等。3.3 選址模型的分類在建立一個選址模型之前，我們需要清楚以下問題：（1）選址的對象是什么？（2）選址的目標區(qū)域是怎

4、樣的？（3）選址目標和成本函數(shù)是什么？（4）有什么樣的一些約束？體選址面選址線選址高維選址單一設施選址多設施選址連續(xù)選址網(wǎng)絡選址離散選址可行性/最優(yōu)性Minisum/MinimaxMaximin高次目標函數(shù)確定性與隨機性靜態(tài)與動態(tài)有能力約束無能力約束有不可行區(qū)域無不可行區(qū)域設施維度及數(shù)量選址目標區(qū)域選址成本選址約束固定權重/可變權重3.4 選址問題中的距離計算在選址問題模型中，最基本的一個參數(shù)是各個節(jié)點之間的距離。有兩種方法計算節(jié)點之間的距離：直線距離，也叫歐幾里德距離（Euclidean Metric）；折線距離（Rectilinear Metric），也叫城市距離（Metropolitan

5、 Metric）。3.5 選址模型簡單模型：在一條直線上（街道）選擇一個有效位置（商店），即一種設施，讓這條街道上的所有顧客到達商店的平均距離最短。假設街道上顧客分布的概率（密度）為則目標函數(shù)為：簡單模型大街上第i個位置到所選地址的距離選擇投資的位置3.5 選址模型定積分求導：定積分求導（1）其中， 被假設為在時間區(qū)間 中具有連續(xù)導數(shù) 。萊布尼茲法則關于一個變量（它既不是積分變量，也不進入積分上下限）求導定積分，可以簡單地穿過積分符號直接關系該變量求導被積函數(shù)。3.5 選址模型定積分求導：定積分求導（2）有微商公式：定積分關于積分上限b的導數(shù)等于被積函數(shù)在t=b處的取值；定積分關于積分下限a的

6、導數(shù)等于被積函數(shù)在t=a處的取值的負數(shù)；3.5 選址模型定積分求導：定積分求導（3）有微商公式：右邊第一項來自對被積函數(shù)中變量的求導，右邊第二項來自對積分上限的求導，而且基于下列鏈式求導：其中x不僅進入被積函數(shù)，而且影響積分上限對以下函數(shù)求導3.5 選址模型對目標函數(shù)求導，令一階導數(shù)為零，得：簡單模型求解結果表明，所開設的新店面需要設置在權重的中點，即兩面的權重都是50%。3.5 選址模型連續(xù)點選址問題指的是在一條路徑或者一個區(qū)域里面的任何位置都可以作為選址的問題。交叉中值模型（Cross Median）通過交叉中值的方法對單一設施平面選址問題的加權城市距離進行最小化。其目標函數(shù)為：交叉中值模

7、型第i個點對應的權重，例如需求；需求點的總數(shù)目第i個需求點的坐標；服務設施的坐標；3.5 選址模型交叉中值模型的目標函數(shù)可以用兩個互不相干的部分來表達：交叉中值模型是x方向所有權重的中值點；是y方向所有權重的中值點；惟一值某一范圍惟一值點線段某一范圍線段區(qū)域3.5 選址模型例1 報刊亭選址一個報刊連鎖公司想在一個地區(qū)開設一個新的報刊亭零售點，主要的服務對象是附近的5個住宿小區(qū)的居民，他們是新開設報刊亭零售點的主要顧客源。下圖坐標系中確切地表達了這些需求點的位置，下表為各個需求點對應的權重。權重代表每個月潛在的顧客需求總量，基本可以用小區(qū)中總的居民數(shù)量來近似。經(jīng)理希望通過這些信息來確定一個合適的

8、報刊零售點的 位置，要求每個月顧客到報刊零售點所行走的距離總和最小。交叉中值模型需求點x坐標y坐標權重131125273433424351563.5 選址模型首先，確定中值，需求點沿x軸的位置w從左到右516426+3=9136+3+1=103425從右到左257347+3=10134251交叉中值模型需求點沿y軸的位置w從上到下556446+3=9336+3+3=122211從下到上111221+7=8331+7+3=1144553.5 選址模型選址結果：交叉中值模型位置A（3，3）位置B（4，3）需求點距離權重總和需求點距離權重總和12121313237212271431333030423

9、64339546245563056563.5 選址模型連續(xù)點選址問題指的是在一條路徑或者一個區(qū)域里面的任何位置都可以作為選址的問題。精確重心法（Exact Gravity）交叉中值模型使用城市距離，適合小范圍城市內(nèi)選址問題；精確重心法使用直線距離，適合大范圍城市間選址問題，目標函數(shù)為，精確重心法與第i個點對應的權重，例如需求；需求點的總數(shù)目第i個需求點的坐標；服務設施的坐標；3.5 選址模型精確重心法目標函數(shù)為雙變量系統(tǒng)，分別對xs和ys求偏導，并令導數(shù)為零，求得隱含最優(yōu)解的等式，精確重心法3.5 選址模型迭代法：利用已知的點（xs(k-1), ys(k-1)）,求出dis(k-1)，再求出新

10、的點（xs(k), ys(k)）,依次求解，直到求得符合要求的解。精確重心法迭代公式：(1)其中：(2)3.5 選址模型精確重心法迭代法步驟：（1）初始值的確定；（2）迭代；（3）中止準則；初始值的確定：a、任意選擇一個點作為初始值；b、按照簡化公式選擇初始值；3.5 選址模型中止準則的確定：a、直接設置一個確定的迭代次數(shù)N；b、判斷兩次迭代的差值是否小于設定的閾值；C、判斷總費用是否減小或兩次迭代差值小于設定值精確重心法3.5 選址模型精確重心法應用于報刊亭選址問題：精確重心法第一次迭代初始位置(x0,y0)33需求點12345(xi,yi)3152432415權重wi17336距離dis(

11、0)22.23606797711.4142135622.828427125wixi/dis(0)；wiyi/dis(0)1.50.515.652486.260991294.24268.48522.121310.606wi/dis(0)；wi/dis(0)0.531213203442.121320344迭代位置(x1,y1)3.2664391713.205411382中止判斷（Z1）41.865679283.5 選址模型精確重心法應用于報刊亭選址問題：精確重心法第二次迭代初始位置(x1,y1)3.2664391713.205411382需求點12345(xi,yi)31

12、52432415權重wi17336距離dis(1)2.2214475452.1114567830.761777741.4950716532.890898619wixi/dis(1)；wiyi/dis(1)1.35040.450116.5766.630415.75211.8144.01318.02632.075410.37wi/dis(1)；wi/dis(1)0.4501569273.3152466373.9381565542.0065927912.075479216迭代位置(x2,y2)3.3742776423.16477612中止判斷（Z2）41.117584923.5 選址模型精確重心法應

13、用于報刊亭選址問題：精確重心法第三次迭代初始位置(x2,y2)3.3742776423.16477612需求點12345(xi,yi)3152432415權重wi17336距離dis(2)2.1968931251.9999191470.6470545871.6081784633.000873375wixi/dis(2)；wiyi/dis(2)1.36550.455117.5007.000218.54513.9093.73097.46181.99949.997wi/dis(2)；wi/dis(2)0.4551882793.5001414994.6363939931.8654646041.9994

14、17919迭代位置(x3,y3)3.4633988113.116707741中止判斷（Z3）40.967266553.5 選址模型中止準則的使用：若（1）N=2；（2）坐標值閾值為0.2；坐標值變化幅度小于4%；（3）總費用閾值為0.2；總費用相對變化幅度小于1%。精確重心法總費用2.64%，-1.52%3.30%，-1.27%8.88%，6.85%相對差值40.843840.967341.117641.86570.0891，-0.04810.1078，-0.04060.2664，0.2054絕對差值坐標點迭代差值總費用迭代差值坐標點迭代次數(shù)3.11673.16483.2054y3.46343

15、.37433.2664x0.12350.15030.7481絕對差值1.79%10.37%20.30%3相對差值3.5 選址模型補充例題：有四個零售點，其坐標、物資需求量及運輸費用如下表所示，請用重心法為配送中心選址。零售點物資需求量qi運輸費用ri坐標xiyi1252223511332.5510841549精確重心法第一步，按照簡化公式確定初始值，3.5 選址模型 精確重心法第二步，以點（7.8，4.9）作為配送中心，計算距離與總費用，第三步，計算改善的配送中心選址，3.5 選址模型 精確重心法第四步，以點（8.6，5.1）作為配送中心，計算距離與總費用，第五步，計算改善的配送中心選址，3.

16、5 選址模型 精確重心法第六步，以點（9.0，5.2）作為配送中心，計算距離與總費用，此時，Z(2)=Z(1)=191，雖然結果是取小數(shù)而得，但二者已經(jīng)非常接近，所以可認為最佳點為（9.0，5.2）或（8.6，5.1）。3.5 選址模型交叉中值模型與精確重心法交叉中值模型精確重心法城市距離（折線距離）；適合于小范圍的城市內(nèi)選址問題；目標使對加權的城市距離最小化；屬于單一設施連續(xù)點選址問題。歐幾米德距離（直線距離）；適合于大范圍城市間選址問題；目標是使加權的直線距離最小化；屬于單一設施的連續(xù)點選址問題。3.5 選址模型離散點選址問題指的是在有限的候選位置里面，選取最為合適的一個或一組位置為最優(yōu)方

17、案，相應的模型稱為離散點選址模型。離散點選址模型與連續(xù)點選址模型的區(qū)別在于：它所擁有的候選方案只有有限個元素。對于離散點選址問題，目前主要有兩種模型，分別是覆蓋模型和P-中值模型。覆蓋模型常用的又有集合覆蓋模型和最大覆蓋模型兩種。覆蓋模型（Covering） 覆蓋模型，是對于需求已知的一些需求點，確定一組服務設施來滿足這些需求點的需求。在這個模型中，需要確定服務設施的最小數(shù)量和合適的位置。該模型適用于商業(yè)物流系統(tǒng)，如零售點的選擇問題、加油站的選址、配送中心的選址問題等。離散點選址問題3.5 選址模型根據(jù)解決問題的方法的不同，覆蓋模型可以分為兩種不同的主要模型：集合覆蓋模型，用最小數(shù)量的設施去覆

18、蓋所有的需求點；最大覆蓋模型，在給定數(shù)量的設施下，覆蓋盡可能多的需求點。覆蓋模型3.5 選址模型集合覆蓋模型集合覆蓋模型的目標是用盡可能少的設施去覆蓋所有的需求點。數(shù)學模型為：集合覆蓋模型N區(qū)域中的需求點（客戶）集合，N=1,2,n；M區(qū)域中可建設設施的候選點集合，M=1,2,m；di第i個需求點的需求量；Dj設施點j的服務能力；A(j)設施節(jié)點j可以覆蓋的需求點i的集合；B(i)可以覆蓋需求節(jié)點i的設施節(jié)點j的集合；Xj為0-1變量，xj=1,在j點建立設施；xj=0,不在j點建立設施，jMyij節(jié)點i需求中被分配給設施點j的部分(比例)。3.5 選址模型集合覆蓋模型啟發(fā)式算法：第一步：初始

19、化。令所有的yi0，xj0， （已分配的需求），并確定集合A(j)和集合B(i)；第二步：選擇下一個設施點。在M中選擇xj0，且A(j)的規(guī)模為最大的點j為設施點，即 ，令 ，并在M集合中剔除節(jié)點j，即第三步：確定節(jié)點j的覆蓋范圍。將A(j)中的元素按B(i)的規(guī)模從小到大的順序指派給j，直至j的容量為Dj0或A(j)為空。其中對于iA(j)且，yi1，將i支配給j的方法為：若 ，則令yij=1yi，Dj=Dj-di(1-yi)，yi1，在A(j)和N中剔除需求點i。若 ，則令第四步：若N或M為空，停止；否則，更新集合A(j)和集合B(i)，轉第二步。集合覆蓋模型啟發(fā)式算法3.5 選址模型例：

20、在某區(qū)域需規(guī)劃建設若干個農(nóng)貿(mào)市場為將來該區(qū)9個主要居民點提供服務，除第6居民點外，其他各點均有建設市場的條件，如下圖所示。已知市場的最大服務直徑為3km，為保護該區(qū)域的環(huán)境，希望盡可能少地建造農(nóng)貿(mào)市場。問應如何規(guī)劃？解：N1,2,3,4,5,6,7,8,9，M1,2,3,4,5, 7,8,9，由圖兩點間的最短距離，根據(jù)最大服務半徑為3km的約束及第6居民點不適合建市場的要求，可確定集合A(j)和B(i)。如下表所示，值得指出的是本問題沒有需求量和容量，故無需考慮服務能力約束式。 集合覆蓋模型啟發(fā)式算法17849256322434143233211 圖 小區(qū)居民點位置圖33.5 選址模型 集合覆

21、蓋模型啟發(fā)式算法第一步，初始化居民點號A(j)B(i)11,2,3,41,2,3,421,2,31,2,331,2,3,4,5,61,2,3,4,541,3,4,5,6,71,3,4,5,753,4,5,63,4,563,4,5,7,874,6,7,84,7,886,7,8,97,8,998,98,9 第二步，確定一個設施點。因為A(4)=1,3,4,5,6,7，|A(4)|=6為最大，故首先選取j4。由于無容量約束故依次指派5,7,1,6,3,4點歸節(jié)點4服務。 第三步，更新。此時，N2,8,9,M1,2,3,5,7,8,9,更新集合A(j)和集合B(i)后如下表所示。3.5 選址模型 集合

22、覆蓋模型啟發(fā)式算法居民點號A(j)B(i)12221,2,3324567888,97,8,998,98,9 第四步，確定一個設施點。因為A(8)8,9，|A(8)|2為最大，故首先選取j8，并且8，9兩點歸節(jié)點8服務。 第五步，更新。此時，N2,M1,2,3,5,7,9,更新集合A(j)和集合B(i)后如下表所示。3.5 選址模型 集合覆蓋模型啟發(fā)式算法居民點號A(j)B(i)122223245679 第六步，確定一個設施點。因為A(2)2，|A(2)|1為最大，故首先選取j2，并且2點歸節(jié)點2服務。 第七步，更新。此時，N,M1,3,5,7,9,結束。 因此，計算結果為（4,8,2）。3.5

23、 選址模型集合覆蓋模型整數(shù)規(guī)劃N區(qū)域中的需求點（客戶）集合，N=1,2,n；M區(qū)域中可建設設施的候選點集合，M=1,2,m；di第i個需求點的需求量；Dj設施點j的服務能力；A(j)設施節(jié)點j可以覆蓋的需求點i的集合；B(i)可以覆蓋需求節(jié)點i的設施節(jié)點j的集合；Xj為0-1變量，xj=1,在j點建立設施；xj=0,不在j點建立設施，jMyij節(jié)點i需求中被分配給設施點j的部分(比例)。居民點號A(j)B(i)11,2,3,41,2,3,421,2,31,2,331,2,3,4,5,61,2,3,4,541,3,4,5,6,71,3,4,5,753,4,5,63,4,563,4,5,7,874

24、,6,7,84,7,886,7,8,97,8,998,98,9整數(shù)規(guī)劃模型求解：3.5 選址模型 集合覆蓋模型整數(shù)規(guī)劃整數(shù)規(guī)劃模型：3.5 選址模型 集合覆蓋模型整數(shù)規(guī)劃Lingo軟件求解：3.5 選址模型最大覆蓋模型已知若干個需求點（客戶）的位置和需求量，需從一組候選的地點中選擇p個位置作為物流設施網(wǎng)點（如配送中心、倉庫等），使得盡可能多地滿足需求點的服務。最大覆蓋模型的目標是對有限的服務網(wǎng)點進行選址，為盡可能多的對象提供服務，如下圖所示。最大覆蓋模型最大覆蓋模型3.5 選址模型最大覆蓋數(shù)學模型為：最大覆蓋模型N區(qū)域中的需求點（客戶）集合，N=1,2,n；M區(qū)域中可建設設施的候選點集合，M=

25、1,2,m；di第i個需求點的需求量；Dj設施點j的服務能力；p 允許建設的設施的數(shù)目；A(j)設施節(jié)點j可以覆蓋的需求點i的集合；B(i)可以覆蓋需求節(jié)點i的設施節(jié)點j的集合；Xj為0-1變量，xj=1,在j點建立設施；xj=0,不在j點建立設施，jMyij節(jié)點i需求中被分配給設施點j的部分(比例)。3.5 選址模型集合覆蓋模型與最大覆蓋模型數(shù)學模型比較最大覆蓋模型集合覆蓋模型最大覆蓋模型3.5 選址模型 最大覆蓋模型整數(shù)規(guī)劃3.5 選址模型 集合覆蓋模型整數(shù)規(guī)劃Lingo軟件求解：3.5 選址模型P中值模型P中值模型是指在一個給定數(shù)量和位置的需求集合和一個給數(shù)量和候選位置的設施集合的前提下

26、，分別為P個設施找到合適的位置并指派每個需求點到一個特定的設施，使之達到在設施與需求點之間的運輸費用最低。如下圖所示。P中值模型3.5 選址模型P中值數(shù)學模型為：P中值模型N區(qū)域中的需求點（客戶）集合，N=1,2,n；M區(qū)域中可建設設施的候選點集合，M=1,2,m；di第i個需求點的需求量；cij從需求點i到設施點j的單位運輸費用；p 允許建設的設施的數(shù)目，pm；xj為0-1變量，xj=1,在j點建立設施；xj=0,不在j點建立設施，jMyij為0-1變量，yij=1,表示需求點i由節(jié)點j提供服務；yij=0,表示需求點i不由節(jié)點j提供服務； 。3.5 選址模型例3：某飼料公司的倉庫選址問題某

27、飼料公司在某新地區(qū)經(jīng)過一段時間的宣傳廣告后，得到了8個超市的定單，由于該新地區(qū)離總部較遠，該公司擬在該地區(qū)新建2個倉庫，用最低的運輸成本來滿足該地區(qū)的需求。經(jīng)過一段時間的實地調(diào)查之后，已有4個候選地址，如下圖所示；各候選地址到不同超市的運輸成本、各個超市的需求量如下表所示。P中值模型123456781234ijdi1234cij14122061002210251050334161412046592805181273200614249707203021160824126221003.5 選址模型P中值貪婪取走啟發(fā)式算法（Greedy Dropping Heuristic Algorithm）:P

28、中值模型貪婪取走啟發(fā)式算法第一步，初始化，令循環(huán)數(shù)k=m，將所有m個候選位置都選中，然后將每個需求點分配給離其最近的一個侯選位置。123456781234400100360600160140120600設施點費用1860214037204760總費用24803.5 選址模型 P中值模型貪婪取走啟發(fā)式算法第二步，選擇并取走一個位置點，滿足以下條件：假如將它取走并將它的客戶重新指派后，總費用增加量最小，然后令k=k-1。12345678234600160140120600需求點移走位置1后總費用增加量1+2002+4003+120總費用增加量+7206005004803.5 選址模型 P中值模型貪婪取走啟發(fā)式算法12345678134400100360600160280120600需求點移走位置2后總費用增加量6+140總費用增加量+140移走位置2：3.5 選址模型 P中值模型貪婪取走啟發(fā)式算法需求點移走位置2后總費用增加量7+5408+600總費用增加量+1140移走位置3：123456781244001003606001601