【正文】 N＝ {2,8,9},M＝ {1,2,3,5,7,8,9},更新集合 A(i)和集合B(j)后如下表所示。由于無(wú)容量約束故依次指派 5,7,1,6,3,4點(diǎn)歸節(jié)點(diǎn) 4服務(wù)。 集合覆蓋模型啟發(fā)式算法 1○ 7○ 8○ 4○ 9○ 2○ 5○ 6○ 3○ 2 2 4 3 4 1 4 3 2 3 3 2 1 1 圖 小區(qū)居民點(diǎn)位置圖 3 FPD 選址模型 集合覆蓋模型啟發(fā)式算法 第一步，初始化 居民點(diǎn)號(hào) A(i) B(j) 1 1,2,3,4 1,2,3,4 2 1,2,3 1,2,3 3 1,2,3,4,5,6 1,2,3,4,5 4 1,3,4,5,6,7 1,3,4,5,7 5 3,4,5,6 3,4,5 6 3,4,5,7,8 7 4,6,7,8 4,7,8 8 6,7,8,9 7,8,9 9 8,9 8,9 第二步，確定一個(gè)設(shè)施點(diǎn)。問(wèn)應(yīng)如何規(guī)劃？ 解： N＝ {1,2,3,4,5,6,7,8,9}， M＝ {1,2,3,4,5, 7,8,9}，由圖兩點(diǎn)間的最短距離，根據(jù)最大服務(wù)半徑為 3km的約束及第 6居民點(diǎn)不適合建市場(chǎng)的要求，可確定集合 A(j)和B(i)。 ???? ?? iijjjiij CxxxCxFPD 選址模型 例：在某區(qū)域需規(guī)劃建設(shè)若干個(gè)農(nóng)貿(mào)市場(chǎng)為將來(lái)該區(qū) 9個(gè)主要居民點(diǎn)提供服務(wù)，除第 6居民點(diǎn)外，其他各點(diǎn)均有建設(shè)市場(chǎng)的條件，如下圖所示。 集合覆蓋模型啟發(fā)式算法 0?? ?? Mi ijixx })(max{)( iAiA ??1??ix }{\ iMM ? ijj CxD ???ijj CxD ??? 0, 39。其中對(duì)于j∈A(i’) 且， xjDj，將 j支配給 i’的方法為：若 ，則令xi’ j=Dj－ xj， Ci’ =Ci’ (Djxj)， xj＝ 1，在 A(i’ )和 N中剔除需求點(diǎn) j。在 M中選擇 yi＝ 0，且 A(i)的規(guī)模為最大的點(diǎn) i’為設(shè)施點(diǎn)，即 ，令 ，并在 M集合中剔除節(jié)點(diǎn)i’，即 第三步：確定節(jié)點(diǎn) i’的覆蓋范圍。 ??????????????????????????MiyNjMixNjDxMiyCxtsyiijjmiijiinjijmii},1,0{,0,..min111FPD 選址模型 集合覆蓋模型啟發(fā)式算法： 第一步：初始化。 覆蓋模型 FPD 選址模型 IV. 集合覆蓋模型 集合覆蓋模型的目標(biāo)是用盡可能少的設(shè)施去覆蓋所有的需求點(diǎn)。該模型適用于商業(yè)物流系統(tǒng)，如零售點(diǎn)的選擇問(wèn)題、加油站的選址、配送中心的選址問(wèn)題等。 覆蓋模型（ Covering） 覆蓋模型，是對(duì)于需求已知的一些需求點(diǎn)，確定一組服務(wù)設(shè)施來(lái)滿足這些需求點(diǎn)的需求。 對(duì)于離散點(diǎn)選址問(wèn)題，目前主要有兩種模型，分別是覆蓋模型和 P中值模型。 FPD 選址模型 離散點(diǎn)選址問(wèn)題指的是在有限的候選位置里面，選取最為合適的一個(gè)或一組位置為最優(yōu)方案，相應(yīng)的模型稱為離散點(diǎn)選址模型。 ???????????????????????????])()[()1(])()[()1(])()[()1(])()[()1(2/12242/12232/12222/1221ssssdddd1915)()2( ??????????ZFPD 選址模型 交叉中值模型與精確重心法 ? 城市距離（折線距離）； ? 適合于小范圍的城市內(nèi)選址問(wèn)題； ? 目標(biāo)使對(duì)加權(quán)的城市距離最小化； ? 屬于單一設(shè)施連續(xù)點(diǎn)選址問(wèn)題。 精確重心法 總費(fèi)用 %， % %， % %，% 相對(duì)差值 ， ， ， 絕對(duì)差值 坐標(biāo)點(diǎn)迭代差值 總費(fèi)用迭代差值 坐標(biāo)點(diǎn) 迭代 次數(shù) y x 絕對(duì)差值 % 1 % 2 % 3 相對(duì)差值 FPD 選址模型 補(bǔ)充例題：有四個(gè)零售點(diǎn)，其坐標(biāo)、物資需求量及運(yùn)輸費(fèi)用如下表所示，請(qǐng)用重心法為配送中心選址。 III. 精確重心法（ Exact Gravity） 交叉中值模型使用城市距離，適合小范圍城市內(nèi)選址問(wèn)題； 精確重心法使用直線距離，適合大范圍城市間選址問(wèn)題，目標(biāo)函數(shù)為， 精確重心法 ??????nisisii yyxxwZ12/122 ])()[(min—— 與第 i個(gè)點(diǎn)對(duì)應(yīng)的權(quán)重，例如需求； —— 需求點(diǎn)的總數(shù)目 iwn—— 第 i個(gè)需求點(diǎn)的坐標(biāo)； ii yx,—— 服務(wù)設(shè)施的坐標(biāo)； ss yx ,FPD 選址模型 精確重心法目標(biāo)函數(shù)為雙變量系統(tǒng)，分別對(duì) xs和 ys求偏導(dǎo)，并令導(dǎo)數(shù)為零，求得隱含最優(yōu)解的等式， 精確重心法 221111)()(sisiisni isini isiisni isini isiisyyxxddwdywydwdxwx??????????????FPD 選址模型 迭代法： 利用已知的點(diǎn)（ xs(k1), ys(k1)） ,求出 dis(k1)，再求出新的點(diǎn)（ xs(k), ys(k)） ,依次求解，直到求得符合要求的解。經(jīng)理希望通過(guò)這些信息來(lái)確定一個(gè)合適的報(bào)刊零售點(diǎn)的 位置，要求每個(gè)月顧客到報(bào)刊零售點(diǎn)所行走的距離總和最小。下圖坐標(biāo)系中確切地表達(dá)了這些需求點(diǎn)的位置，下表為各個(gè)需求點(diǎn)對(duì)應(yīng)的權(quán)重。 II. 交叉中值模型（ Cross Median） 通過(guò)交叉中值的方法對(duì)單一設(shè)施平面選址問(wèn)題的加權(quán)城市距離進(jìn)行最小化。 t0ab),( xtF ),( xtF xFPD 選址模型 定積分求導(dǎo)： 定積分求導(dǎo) ?? ba dtxtFbaJ ),(),(（ 2） ),(),(),(),(xaFxtFdadJxbFxtFdbdJatbt????????有微商公式： 定積分關(guān)于積分上限 b的導(dǎo)數(shù)等于被積函數(shù)在 t=b處的取值； 定積分關(guān)于積分下限 a的導(dǎo)數(shù)等于被積函數(shù)在 t=a處的取值的負(fù)數(shù)； tF0a b ),( xtF tF0a b ),( xtFFPD 選址模型 定積分求導(dǎo)： 定積分求導(dǎo) ?? )( ),()( xba dtxtFxK（ 3） )(]),([),()( xbxxbFdtxtFdxdK xba x ??? ?有微商公式： 右邊第一項(xiàng)來(lái)自對(duì)被積函數(shù)中變量的求導(dǎo)，右邊第二項(xiàng)來(lái)自對(duì)積分上限的求導(dǎo)，而且基于下列鏈?zhǔn)角髮?dǎo)： 其中 x不僅進(jìn)入被積函數(shù)，而且影響積分上限 dxxdbxdbdK )()( ?dtedxd x??20對(duì)以下函數(shù)求導(dǎo) xdxd t?32 dttdxd x?20 23FPD 選址模型 對(duì)目標(biāo)函數(shù)求導(dǎo)， 令一階導(dǎo)數(shù)為零，得： 簡(jiǎn)單模型 0)()(000??????????????LsxsxnsiisiidxxwdxxwdsdZorwwdsdZ求解結(jié)果表明，所開設(shè)的新店面需要設(shè)置在權(quán)重的中點(diǎn)，即兩面的權(quán)重都是 50%。 假設(shè)街道上顧客分布的概率（密度）為 則目標(biāo)函數(shù)為： 簡(jiǎn)單模型 ))(( xworw i ????????????????LsxsxnsiiisiiidxsxxwdxxsxwZorsxwxswZ))(())((min)()(min00—— 大街上第 i個(gè)位置到所選地址的距離 —— 選擇投資的位置 ixsFPD 選址模型 定積分求導(dǎo)： 定積分求導(dǎo) ?? ba dtxtFxI ),()(（ 1） 其中， 被假設(shè)為在時(shí)間區(qū)間 中具有連續(xù)導(dǎo)數(shù) 。 有兩種方法計(jì)算節(jié)點(diǎn)之間的距離： 直線距離，也叫歐幾里德距離（ Euclidean Metric）； 折線距離（ Rectilinear Metric），也叫城市距離（ Metropolitan Metric）。還可以根據(jù)因素對(duì)設(shè)施選址的重要性，分為：關(guān)鍵因素、重要因素、次要因素等 。地區(qū)選擇要考慮的是宏觀因素；地點(diǎn)選擇要考慮的是微觀因素。 設(shè)施數(shù)量 庫(kù)存成本 設(shè)施數(shù)量 運(yùn)輸成本 設(shè)施數(shù)量 設(shè)施成本 設(shè)施數(shù)量 總成本 響應(yīng)時(shí)間 FPD 選址的意義 ? 就供應(yīng)鏈系統(tǒng)而言，核心企業(yè)的選址決策會(huì)影響所有供應(yīng)商物流系統(tǒng)的選址決策。這些設(shè)施主要指物流