【文章內(nèi)容簡介】 是在 y方向的對所有的權(quán)重的中值點(diǎn)。 考慮到 兩者可能同時是惟一值或某一范圍，最優(yōu)的位置也相應(yīng)的可能是一個點(diǎn)，或者是線，或者是一個區(qū)域。 ? ???????nisisii yyxxwZ1iw ii ，yx ssn式中： —— 與第 i個點(diǎn)對應(yīng)的權(quán)重（例如需求）； —— 第 i個需求點(diǎn)的坐標(biāo)； —— 服務(wù)設(shè)施點(diǎn)的坐標(biāo)； —— 需求點(diǎn)的總數(shù)目。 sxsy ss ，yx 例題 ： 一個冷凍食品公司想在一個地區(qū)開設(shè)一個新的冷食提貨點(diǎn)，其主要的服務(wù)對象是附近 5個住宅小區(qū)的居民。為了計算方便，把每個住宅小區(qū)的中心抽象成這個小區(qū)的需求點(diǎn)位置。權(quán)重表示每個月潛在的客戶需求總量，可以用每個小區(qū)中的總居民數(shù)量來近似代表。已知五個小區(qū)點(diǎn)的坐標(biāo)： A(3,2), B(4,3), C(5,1),D(1,4)和 E(2,5),權(quán)重分別為： 3， 1， 8， 3， 7。公司經(jīng)理希望通過這些信息來確定一個合適的冷食提貨點(diǎn)的位置，要求每個月顧客到這個冷食提貨點(diǎn)所行走的距離總和最小。 提示 ：先確定需求點(diǎn)的中值，再通過 x軸與 y軸分別進(jìn)行計算討論。 需求點(diǎn) X 坐標(biāo) Y坐標(biāo) 權(quán)重 Wi A 3 2 3 B 4 3 1 C 5 1 8 D 1 4 3 E 2 5 7 需求點(diǎn)對應(yīng)的權(quán)重 ? 首先，需要確定中值 ： 從上表中得到中值： ? 為了找到 x方向上的中值點(diǎn) x0， 在 x方向只能選擇一個有效的中值點(diǎn)： ? 接著尋找在 y方向上的中值點(diǎn) y0， 發(fā)現(xiàn)在需求點(diǎn) A、 B之間的范圍內(nèi)對于 y軸方向都是一樣的： ??? niiwW121? ?3 1 8 3 7 / 2 11W ? ? ? ? ? ?0 3?0 23?? 綜合考慮 x、 y方向的影響，于是最后可能的地址為(3,2)、 (3,3)之間的一條線段，見下圖。 0 1 2 3 4 5 6123456BACDE提 貨 點(diǎn) 選 址 的 最 后 方 案? 精確重心法 ? 前面介紹的交叉中值模型由于其本身的局限性，例如使用的是城市距離，只適合于解決一些小范圍的城市內(nèi)的選址問題。精確重心法在評價的過程中使用的是歐幾米德距離，即直線距離，它使選址問題變得復(fù)雜，但是有著更為廣闊的應(yīng)用范圍。 重心模型是選址問題中最常用的一種模型，可以解決連續(xù)區(qū)域直線距離的單點(diǎn)選址問題。重心模型的 基本假設(shè) ： (1)需求量集中于 某一個點(diǎn) 上； (2)選址區(qū)域不同地點(diǎn)物流節(jié)點(diǎn)的建設(shè)費(fèi)用和運(yùn)營費(fèi)用相同； (3)運(yùn)輸費(fèi)用隨運(yùn)輸距離 成正比例 增加，顯線性關(guān)系。 (4)運(yùn)輸路線為 空間直線 。 ? （ 1）問題描述 ? 設(shè)有 n個客戶（收貨單位） 分布在平面上，其坐標(biāo)分別為 ( )，客戶的需求量為 ，費(fèi)用函數(shù)為設(shè)施（配送中心）與客戶之間的直線距離乘以需求量。確定設(shè)施 的位置 ( ),使總運(yùn)輸費(fèi)用最小。 ? 這一類問題也稱為 Weber問題。 nPPP , 21 ?ii yx, i? 0P00,yx? （ 2）建立模型 ? —— 配送中心到收貨點(diǎn) 每單位量、單位距離所需運(yùn)費(fèi)。 ? —— 的需貨量。 ? —— 到 的直線距離。 ? 則總運(yùn)輸費(fèi) H為 : ? (45) 21202011])()[( jjnjjjnjjjj yyxxadaH ????? ??????ja jPj? jPjd 0jP? 求 H的 極小值點(diǎn) （ ）。由于式（ 45）為 凸函數(shù) ，最優(yōu)解的必要條件為滿足： ? , (46) ? 令 , ? 得 , ?? 00 ,yx 00????? xxxH 00????? yyyH ??????? nj jjjjdxxaxH1000)(???????? nj jjjjdyyayH1000)(???????nj jjjnj jjjjodadxax11????????nj jjjnj jjjjoadyay11??? 上式右端 中仍含未知數(shù) 故不能一次求得顯解，但可以導(dǎo)出關(guān)于 x和 y的迭代公式： ? (47) ? (48) ? 應(yīng)用上述迭代公式，可采用 逐步逼近算法 求得最優(yōu)解，該算法稱為 不動點(diǎn)算法 jd 00, yx 212)(2)(212)(2)1()1(])()[(])()[(iqiqIiiiiqiqIiiiiqyyxxayyxxxax???????????????212)(2)(212)(2)1()1(])()[(])()[(iqiqIiiiiqiqIiiiiqyyxxayyxxyay???????????????? （ 3）算法 （單一配送中心選址的不動點(diǎn)算法） ? 輸入： n—— 客戶數(shù)； ( ) —— 各客戶點(diǎn)的坐標(biāo)， ； —— 各客戶點(diǎn)的單位運(yùn)費(fèi)和運(yùn)量 。 ? 輸出： （ ） —— 設(shè)施坐標(biāo) 。 Ｈ ―― 總運(yùn)量． ii yx , 1 , 2 , ,in?iia ?, 1 , 2 , ,??? 00 , yx? 第一步： 選取一個初始的迭代點(diǎn) , ? 如： ， ，然后計算出 A到各客戶點(diǎn)的直線距離 和費(fèi)用 ： ),( 000 oyxA ???njjxnx1001 ??? nj jyny100 1jd 0H 21202300 ])()[( jjj yyxxd ????01nj j jjH a d???? 第二步 ，令 ， ? ? 及 ，轉(zhuǎn)第三步。 ? 第三步 ，若 ，運(yùn)費(fèi)已無法減小，輸出最優(yōu)解 和 ，否則，轉(zhuǎn)第四步。 ? 第四步 ：令 ， ， ，轉(zhuǎn)第二步。 ?????nj jjjnj jjjjdadxax1110 ????j jjjnj jjjjddyy110 ?21210210 ])()[( jjj yyxxd ???? ???njjjj daH11 ?10 HH ? ),( 0000 yx0 1000 x? 1000 yy ? 10 HH ?? 例 ： 運(yùn)用精確重心法，對前面的冷凍公司提貨點(diǎn)選址問題作一個假設(shè)，假設(shè)居民區(qū)以外的選址區(qū)域都是空地，使用歐幾米德距離進(jìn)行計算是合適的，然后我們就用精確重心法選擇一個最優(yōu)的位置。 ? 解： 從點(diǎn)（ ， ）開始進(jìn)行歐幾米德距離最優(yōu)的搜索，可采用 Excel軟件進(jìn)行計算，見教材 65頁。 ? 注意： 用精確重心法得到的最優(yōu)解只有一個點(diǎn)，而不會是一條線段或者一個區(qū)域。而且只有在十分偶然的情況下，才會出現(xiàn)用交叉中值法和精確重心法得到的最優(yōu)優(yōu)地址一致的情況。 多物流節(jié)點(diǎn)選址模型 物流區(qū)域規(guī)劃中，往往需要同時確定 兩個或者兩個以上設(shè)施的位置，問題就變成更為復(fù)雜。由于不能將這些物流設(shè)施看成經(jīng)濟(jì)上相互獨(dú)立的要素，而且可能存在向多的選址布局方式，尋求最優(yōu)解很困難，因此問題自然十分復(fù)雜，但更接近實(shí)際情況，在實(shí)際工作中 更普遍 。 多物流節(jié)點(diǎn)選址問題一般需要完成 如下決策 ： ? 如何組織貨流？各個物流節(jié)點(diǎn)的關(guān)系如何？運(yùn)輸路線和各物流節(jié)點(diǎn)的關(guān)系怎樣？ ? 網(wǎng)絡(luò)中應(yīng)該設(shè)幾個物流節(jié)點(diǎn)？分別處于什么位置 ? ? 物流節(jié)點(diǎn)服務(wù)于哪些顧客或者市場區(qū)域？規(guī)模多大？具有哪些功能？ ? 重點(diǎn)介紹： 多重心法、覆蓋模型、 P中值模型、鮑摩－瓦爾夫（ BaumolWolfe)模型 簡要介紹： 奎漢 哈姆勃茲（ kuehnHamburge）模型、CFLP模型、多樞紐站單一分派軸輻式網(wǎng)絡(luò)選址問題、多樞紐站多分派軸輻式網(wǎng)絡(luò)選址問題 多重心法 多重心法的 計算思路 ： ? 第一步：初步分組 。將需求點(diǎn)按照一定原則分成若干個群組，使分群組數(shù)等于物流節(jié)點(diǎn)的數(shù)量。 ? 第二步：選址計算 。針對每一個群組的單一物流節(jié)點(diǎn)選址問題，運(yùn)用精確重心法確定該群組新的物流節(jié)點(diǎn)的位置。 ? 第三步：調(diào)整分組 。對每個需求點(diǎn)分別計算到多有物流節(jié)點(diǎn)的運(yùn)輸費(fèi)用，并將每個需求點(diǎn)調(diào)整到運(yùn)輸費(fèi)用最低的那個物流節(jié)點(diǎn)負(fù)責(zé)服務(wù)。 ? 第四步：重復(fù)第二步 ，直到族群成員無變化為止。此時的物流節(jié)點(diǎn)的分配方案為最優(yōu)分配方案，物流節(jié)點(diǎn)的位置為最佳地址。 手工計算起來非常麻煩，我們一般采用軟件進(jìn)行計算。如Logware軟件的 MULTICOG功能。 ? 例 ：某公司計劃建立兩個藥品配送點(diǎn)向 10個藥品連鎖店送貨，各藥品連鎖店的地址坐標(biāo)和藥品每日需求量如表 42所示，運(yùn)價均為 1，試確定這兩個藥品配送點(diǎn)的地址，是運(yùn)輸費(fèi)用最低。 ? 計算過程見書本 67頁 店號 1 2 3 4 5 6 7 8 9 10 x 70 95 80 20 40 10 40 75 10 90 y 70 50 20 60 10 50 60 90 30 40 d 8 10 6 5 7 8 12 5 11 9 覆蓋模型 ? 覆蓋模型是一種離散點(diǎn)選址模型，即在有限的候選位置里，選擇最合適的若干設(shè)施位置為最優(yōu)方案。 ? 覆蓋模型 是指當(dāng)設(shè)施服務(wù)半徑一定時，對于需求已知的一些需求點(diǎn)，如何確定一組服務(wù)設(shè)施來滿足這些需求點(diǎn)的需求。在這個模型中需要確定設(shè)施的 最小數(shù)量和 合適的位置 。 ? 該模型適用于 商業(yè)物流系統(tǒng) ，如零售點(diǎn)的選址問題、加油站的選址、配送中心的選址等， 公用事業(yè)系統(tǒng) ，如急救中心、消防中心等，以及 計算機(jī)與通信系統(tǒng) ，如有線電視網(wǎng)的基站、無線通信網(wǎng)絡(luò)基站、計算機(jī)網(wǎng)絡(luò)中的集線器設(shè)置等。 ? 根據(jù)解決問題的方法的不同，可以分為兩種不同的主要模型： （ 1） 集合覆蓋模型 ，用最小數(shù)量的設(shè)施去覆蓋所有的需求點(diǎn)。 （ 2） 最大覆蓋模型 ，在給定數(shù)量的設(shè)施下，覆蓋盡可能多的需求點(diǎn)。 ? 兩類模型的區(qū)別： 集合覆蓋模型要滿足所有的需求點(diǎn)，而最大覆蓋模型則只覆蓋有限的需求點(diǎn) ，兩種模型的應(yīng)用情況取決于服務(wù)設(shè)施的資源充足與否。 ? （ 1）集合覆蓋模型 ? 集合覆蓋模型的目標(biāo)是用盡可能少的設(shè)施去覆蓋所有的需求點(diǎn)，相應(yīng)的目標(biāo)函數(shù)可以表達(dá)為： ? 約束條件為： ??Njjxmin????)(1iBjij N，iy???)(,jAijjiji NjxCyd? ? Nixj ?? ,1,0 jiy ij ? ,0—— 最小化設(shè)施的數(shù)目 —— 保證每個需求點(diǎn)的需求得到完全的滿足 —— 是對每個提供服務(wù)的服務(wù)網(wǎng)點(diǎn)的服務(wù)能力的限制 —— 保證一個地方最多只能投建一個設(shè)施 —— 允許一個設(shè)施只提供部分的需求 ? 對于此類帶有約束條件的極值問題，有兩大類方法可以進(jìn)行分解：一是精確的算法，應(yīng)用 分枝定界求解 的方法，能夠找到小規(guī)模問題的最優(yōu)解，由于運(yùn)算量方面的限制，一般也只適用于小規(guī)模問題的求解；二是 啟發(fā)式方法 ，所得到的結(jié)果不能保證是最優(yōu)解，但是可以保證是可行解，可以對大型問題進(jìn)行有效的分析、求解，可顯著減少計算量。 ? 例子： 鄉(xiāng)村醫(yī)療診所選址問題 ? 衛(wèi)生部門考慮到農(nóng)村地區(qū)的醫(yī)療條件的落后和匱乏，計劃在某一地區(qū)的 9個村增加一系列診所，以改善該地區(qū)的醫(yī)療衛(wèi)生水平。它希望在每