1、2022/8/17集美大學(xué)航海學(xué)院物流管理教研室物流系統(tǒng)規(guī)劃與設(shè)計第3章 選址模型及應(yīng)用2022/8/17集美大學(xué)航海學(xué)院物流管理教研室本章基本要求 了解選址的影響因素，掌握選址中的距離計算，理解和掌握實際選址問題的分析、模型的構(gòu)建和基本的求解算法。本章重點要求 掌握交叉中值模型、重心模型、覆蓋模型、P中值模型以及這些模型的應(yīng)用。物流系統(tǒng)規(guī)劃與設(shè)計第3章 選址模型及應(yīng)用2022/8/17集美大學(xué)航海學(xué)院物流管理教研室本章目錄3.1 選址的意義3.2 選址決策的影響因素3.3 選址模型的分類3.4 選址問題中的距離計算3.5 選址模型 3.5.1 連續(xù)點選址模型 3.5.2 離散點選址模型家樂福

2、選址實例剖析 本章小結(jié)物流系統(tǒng)規(guī)劃與設(shè)計第3章 選址模型及應(yīng)用2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.1 選址的意義 選址在整個物流系統(tǒng)中占有非常重要的地位，從圖1-11，物流縱向結(jié)構(gòu)圖看出，物流分為生產(chǎn)物流、商業(yè)物流、回歸物流三類。各類問題的特征各不相同，但每一類問題的不同環(huán)節(jié)都包含了選址問題，如供應(yīng)商、制造商、分銷商、零售商的選址問題，由此說明了選址在整個物流系統(tǒng)中的重要性，屬于物流管理戰(zhàn)略層的研究問題，是物流系統(tǒng)規(guī)劃的一大內(nèi)容。（該問題：小到倉庫中貨物存儲位置的分配）物流系統(tǒng)規(guī)劃與設(shè)計第3章 選址模型及應(yīng)用2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.1 選址的意義選址

3、決策的內(nèi)容：選址決策：確定物流系統(tǒng)中所要分配的設(shè)施（節(jié)點）的數(shù)量、位置以及分配方案（數(shù)學(xué)的方法）。（設(shè)施 節(jié)點）對單個企業(yè)，選址決定了整個物流系統(tǒng)及其他層次結(jié)構(gòu)。所以，選址、庫存、運輸成本之間存在著密切聯(lián)系。如：企業(yè)分布問題（二維選址） 其他層次（庫存、運輸?shù)龋┑囊?guī)劃。 物流系統(tǒng)規(guī)劃與設(shè)計第3章 選址模型及應(yīng)用2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.1 選址的意義選址與庫存、運輸成本之間的關(guān)系。降低成本的措施：合并減少設(shè)施數(shù)量，擴大設(shè)施規(guī)模是降低庫存成本的一個措施。確定設(shè)施的合理數(shù)量，也是選址規(guī)劃的主要任務(wù)之一。 物流系統(tǒng)規(guī)劃與設(shè)計第3章 選址模型及應(yīng)用2022/8/17集美大學(xué)航

4、海學(xué)院物流管理教研室3.1 選址的意義選址與庫存、運輸成本之間的關(guān)系。 就供應(yīng)鏈系統(tǒng)而言，核心企業(yè)的選址決策會影響所有供應(yīng)商物流系統(tǒng)的選址決策。如DELL、摩托羅拉實例本章內(nèi)容： 實際選址問題的分析、模型構(gòu)建、求解算法。物流系統(tǒng)規(guī)劃與設(shè)計第3章 選址模型及應(yīng)用2022/8/17集美大學(xué)航海學(xué)院物流管理教研室為什么目前我國很多城市熱衷于建物流園區(qū)、物流中心等大規(guī)模物流節(jié)點設(shè)施？ 物流系統(tǒng)規(guī)劃與設(shè)計討論2022/8/17集美大學(xué)航海學(xué)院物流管理教研室物流系統(tǒng)規(guī)劃與設(shè)計思考選址的影響因素有哪些？2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.2.1 選址決策的外部因素分析 宏觀政治、 經(jīng)濟(jì)因素

5、政權(quán)、法制、貿(mào)易集運政策等 稅收政策、關(guān)稅、匯率等 是無法量化的指標(biāo), 與企業(yè)選址決策直接相關(guān) 由企業(yè)主觀評價 目標(biāo)：尋求最寬松的經(jīng)濟(jì)環(huán)境 基礎(chǔ)設(shè)施 及 環(huán)境 交通設(shè)施、通信設(shè)施等 自然環(huán)境、社會環(huán)境 降低物流成本 勞動力的成本、素質(zhì)等物流系統(tǒng)規(guī)劃與設(shè)計3.2 選址決策的影響因素2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.2.1 選址決策的外部因素分析競爭對手競爭對手的布局情況、自身產(chǎn)品或服務(wù) 靠近還是遠(yuǎn)離競爭對手 物流系統(tǒng)規(guī)劃與設(shè)計3.2 選址決策的影響因素2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.2.2 選址決策的內(nèi)部因素分析 企業(yè)的內(nèi)部因素是最主要的。選址決策首先要與企

6、業(yè)的發(fā)展戰(zhàn)略相適應(yīng)。物流系統(tǒng)規(guī)劃與設(shè)計3.2 選址決策的影響因素2022/8/17集美大學(xué)航海學(xué)院物流管理教研室物流系統(tǒng)規(guī)劃與設(shè)計思考臺灣的鞋廠到晉江、莆田開店，而電子產(chǎn)品則不會的原因？2022/8/17集美大學(xué)航海學(xué)院物流管理教研室 選址模型：用數(shù)學(xué)方法確定設(shè)施的數(shù)量、位置和規(guī)模以使物流成本最小。 建選址模型前需弄清以下幾個問題：選址的對象？選址的目標(biāo)區(qū)域？選址目標(biāo)和成本函數(shù)？約束條件？ 選址問題 選址類型選址模型算法選址方案目前可將選址問題分為以下幾類： 物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.1 根據(jù)定位設(shè)施的維數(shù)及數(shù)量分類根據(jù)設(shè)施

7、的維數(shù)體選址：定位三維物體，如：卡車、船舶的裝卸；面選址：定位二維物體，如：企業(yè)的部門布置；線選址：定位一維物體，如：配送中心分揀區(qū)傳送帶；點選址：定位零維物體，忽略物體的尺寸。 （大多數(shù)選址問題和算法都基于此情況）動態(tài)選址問題：+時間因素的四維選址問題。根據(jù)設(shè)施選址的數(shù)量：單一設(shè)施選址：主要考慮運輸成本多設(shè)施選址：運輸成本、競爭力、設(shè)施間需求的分配、設(shè)施成本與數(shù)量間的關(guān)系。物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.2 據(jù)選址問題目標(biāo)區(qū)域的特征分類連續(xù)選址 待選區(qū)域為平面，可選位置不限，選址模型為連續(xù)的。如：企業(yè)配送中心的初步選址。網(wǎng)格選址

8、 待選區(qū)域為平面網(wǎng)格區(qū)域候選地址有限（相當(dāng)大）。 許多相等面積的區(qū)域，如正方形如:倉庫中不同貨物的存儲位置的分配或展覽中心展區(qū)的布置。離散選址（最切合實際） 待選區(qū)域是離散的候選位置集合，數(shù)量有限（甚少）。如：企業(yè)配送中心的詳細(xì)選址設(shè)計。 物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 根據(jù)選址成本，有幾種類型：尋求可行成本方案或最優(yōu)成本方案；尋求總成本最小或成本最大值的最小化；固定權(quán)重或可變權(quán)重；確定性的或隨機性的；被定位設(shè)施間有無相互聯(lián)系；靜態(tài)或是動態(tài)的選址問題。 可行性/最優(yōu)性 即是尋求可行成本方案還是最優(yōu)成本方案？對于

9、許多選址問題：第一目標(biāo)：得到一個可行的解決方案，即滿足所有約束的解決方案；（多個）第二目標(biāo)：找到一個更好的解決方案，即關(guān)于目標(biāo)函數(shù)的優(yōu)化。（一個）物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 Minisum/Minimax/Maximin目標(biāo)函數(shù) Minisum目標(biāo)函數(shù)問題：尋求整個設(shè)施選址的成本總和為最小。目標(biāo)：優(yōu)化全部或者平均性能。適用：企業(yè)問題。故稱“經(jīng)濟(jì)效益性”或稱網(wǎng)絡(luò)上的中值問題。其中：X新的待定位設(shè)施物體的坐標(biāo)； j已存在且位置固定的物體編號； 對于已經(jīng)存在的物體j，新物體定位在X時的成本。 物流系統(tǒng)規(guī)劃與設(shè)計3

10、.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 Minisum/Minimax/Maximin目標(biāo)函數(shù) Minisum目標(biāo)函數(shù)物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 Minisum/Minimax/Maximin目標(biāo)函數(shù) Minimax目標(biāo)函數(shù)問題：尋求已存在設(shè)施的單個成本最大的成本值為最小。目標(biāo)：優(yōu)化最壞的情況。適用：軍隊、緊急情況和公共部門。稱作“經(jīng)濟(jì)平衡性”，也稱為網(wǎng)絡(luò)上的中心問題 （照顧到最邊遠(yuǎn)的地區(qū)）（離客戶到最近的設(shè)施的成本“最大值”最小的原則） 物流系統(tǒng)規(guī)劃

11、與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 Minisum/Minimax/Maximin目標(biāo)函數(shù)Maximin目標(biāo)函數(shù)問題：尋求已存在設(shè)施的單個成本最小的成本值為最大。目標(biāo)：使最壞的情況最優(yōu)化。適用：有害設(shè)施（廢水處理廠、軍工廠等）的選址。此時，物體被定位在使最小距離最大化的地方。稱作“經(jīng)濟(jì)平衡性”，也稱為網(wǎng)絡(luò)上的“反中心”問題。 物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 Minisum/Minimax/Maximin目標(biāo)函數(shù)例：設(shè)一直線上在0，5，6，7上有

12、4個點，成本與點到新設(shè)施間的距離成比例。注：中值點：minisum；中心點：minimax；反中心點：maximin物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室 Minisum/Minimax/Maximin目標(biāo)函數(shù)Minisum. 中值點 （成本只與距離有關(guān)） 解：設(shè)新點設(shè)在x，則： 當(dāng) 時，當(dāng) 時，當(dāng) 時， 的x的取值為注:在選址的左右側(cè)有同樣多的點。5和6間的點均為中值位置。物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 Minisum/Minimax/Maximin目標(biāo)函數(shù)

13、Minimax 中心點 ， ，選址位置到最左邊點和到最右邊點的距離是相等的。 （中心點唯一）物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 Minisum/Minimax/Maximin目標(biāo)函數(shù)擴展：若 ， 不變。（中值點左右側(cè)各點的實際位置不重要，只要兩側(cè)點的數(shù)目相同。）若在 、 之間增加1000個點， 不變。（中心選址是由那些極端位置決定的，即最左和最右兩點的中心。） 1）中值選址由固定位置的順序決定，非實際位置。 2）中心選址由那些極端位置決定，與內(nèi)部位置無關(guān)。 物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17

14、集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類 Minisum/Minimax/Maximin目標(biāo)函數(shù) Maximin ： 反中心點當(dāng) 物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室 Minisum/Minimax/Maximin目標(biāo)函數(shù) Maximin ： 反中心點當(dāng)選址位置為相鄰間距離最大兩點的中點。（反中心點唯一） 3）反中心選址由相鄰間距離最大的位置決定。 物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室物流系統(tǒng)規(guī)劃與設(shè)計討論建急救中心宜選用哪類選址目標(biāo)函數(shù)？建垃圾清潔樓宜選用哪類選址目標(biāo)函數(shù)？

15、建物流配送中心宜選用哪類選址目標(biāo)函數(shù)？2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類3. 固定權(quán)重與可變權(quán)重 單純選址問題（固定權(quán)重）： 新設(shè)施和已存在設(shè)施間的關(guān)系與新設(shè)施的位置無關(guān),是固定的 選址分配問題（可變權(quán)重）： 這種權(quán)重或關(guān)系與新設(shè)施的位置相關(guān)。4. 被定位設(shè)施間有無相互聯(lián)系（一次or二次）（多設(shè)施選址）一次目標(biāo)函數(shù)：無二次或高次目標(biāo)函數(shù)：有物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.3 據(jù)選址成本分類5. 確定性與隨機性確定性：選址的成本或參數(shù)值是確定的。隨機性：選址的成本或參數(shù)是一個隨機分布的概率值。

16、 （如：客戶需求）6. 靜態(tài)與動態(tài) 成本或參數(shù)是否隨時間變化。 物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.3.4 選址約束1有能力約束與無能力約束：新設(shè)施的能力有否被限制。2不可行區(qū)域約束：在目標(biāo)區(qū)域內(nèi)有（無）不適合作為選址地點的區(qū)域。物流系統(tǒng)規(guī)劃與設(shè)計3.3 選址模型的分類2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.4.1 直線距離（歐幾里得距離） 適用：大范圍的選址問題，城市間配送問題和通信問題。 實際路線距離 （如在美國大陸 ， 在東南美洲 ） 分形理論物流系統(tǒng)規(guī)劃與設(shè)計3.4 選址問題中的距離計算2022/8/17集美大學(xué)航海學(xué)

17、院物流管理教研室3.4.2 折線距離（城市距離）適用：城市(道路較規(guī)則的)內(nèi)的配送問題，具有直線通道的工廠及倉庫內(nèi)的布置、物料搬運設(shè)備的順序移動等問題。 物流系統(tǒng)規(guī)劃與設(shè)計3.4 選址問題中的距離計算2022/8/17集美大學(xué)航海學(xué)院物流管理教研室選址模型的功能：選址定位：為設(shè)施找到一個最優(yōu)的位置；系統(tǒng)設(shè)計：是物流系統(tǒng)設(shè)計中的一個重要部分。*直線型設(shè)施選址模型：單距離因素情況：街上各個位置可能出現(xiàn)顧客的概率相同，取中心點。目標(biāo)：所有顧客到達(dá)新設(shè)施點的平均距離最小。（單點選址，minisum型，中值解。）加權(quán)重的離散模型：街上各個位置可能出現(xiàn)顧客的概率不一樣目標(biāo)：到目標(biāo)點的絕對距離的總和最小。（

18、單點選址，minisum型，中值解。）物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室加權(quán)重的離散模型：其中： 第i個位置的權(quán)重； 第i個位置的坐標(biāo)； 新設(shè)施選址的坐標(biāo)。物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室加權(quán)重的離散模型：求解： ( 的左、右側(cè)權(quán)重相等。)物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室加權(quán)重的連續(xù)模型：（屬minisum解，即中值解） 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室加權(quán)重的連續(xù)模型：（屬minisum解，即中值

19、解）求解： （s兩邊的權(quán)重都是50%，即權(quán)重的中點。） 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型 （在一條路徑或一個區(qū)域內(nèi)，無不可行區(qū)域）1. 交叉中值模型 （x，y方向的中值點）距離：城市距離（折線距離）類型：單一選址問題目標(biāo)：加權(quán)的城市距離總和最?。傎M用最?。＿m用：小范圍的城市內(nèi)的選址問題。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型 交叉中值模型其中： 與第i點相對應(yīng)的權(quán)重； 第i個需求點的坐標(biāo)； 新設(shè)施點的坐標(biāo)； n需求點的總數(shù)目。求解： 是在x方向

20、對所有權(quán)重 的中值點； 是在y方向?qū)λ袡?quán)重 的中值點。最優(yōu)解：可能是一個點，或是線，或是一個區(qū)域。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型 交叉中值模型例1：報刊亭選址。物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型 交叉中值模型例1：報刊亭選址。 ：第個月潛在的顧客需求總量，近似為i區(qū)中的總的居民數(shù)量或戶數(shù)。問題（目標(biāo)）：每個月顧客到報刊點所走距離的總和為最小。解：模型選擇：城市距離，交叉中值選址方法。確定中值：物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/

21、17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型 交叉中值模型:例1：報刊亭選址。求 , ：在x方向：左右： 右左：物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型 交叉中值模型:例1：報刊亭選址。在y方向：上下： （ ， ， 即 ） 下上： （ ， ， 即 ） 最優(yōu)解為AB （A=(3,3), B=(4,3)） 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型 交叉中值模型:例1：報刊亭選址。比較A，B兩個位置的加權(quán)距離；A： B： 根據(jù)實際情況，選址為A、B之

22、間的任何一點。 (交叉中值法可為決策提供更多的選擇和靈活性。)作業(yè)：P58 習(xí)題2-7，1物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法距離：直線距離類型：單點的選址問題問題（目標(biāo)）：尋求加權(quán)的直線距離總和最小（總費用最?。＿m用：平面上大范圍的選址，無受限區(qū)域。 （連續(xù)區(qū)域、直線距離的單點選址） （最優(yōu)解唯一）其中：各變量的含義同交叉中值模型。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法求解：其中： (含xs,ys,無法一次求得顯式解

23、)只能用迭代的方法對上式求近似解。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法求解：迭代公式： （j為迭代次數(shù)） 其中：應(yīng)用上述迭代公式，可采用逐步逼近算法求得最優(yōu)解。物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：輸入：n客戶數(shù)； 各客戶點的坐標(biāo)， ； 各客戶點對應(yīng)的權(quán)重， ;(包括運費和運量)輸出： 設(shè)施坐標(biāo)； Z總運費。步驟：選取初始迭代點 ，如： ，或以交叉中值模型選址的結(jié)果之一作為 。物流系統(tǒng)

24、規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：計算A到各客戶點的直線距離 和 ： 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：令 計算：物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：若 ，運費已無法減小；輸出最優(yōu)解 、Z和迭代次數(shù)j，結(jié)束。 ， ， （可能迭代無限

25、次）否則，轉(zhuǎn)注1：若工廠到設(shè)施的運費包含在成本中，則可將工廠視為一個客戶點Pi；注2：若直線距離與實際距離有差異，可用一定的修正系數(shù) 來修正差異。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法求解：算法（單一選址的不動點算法）：終止準(zhǔn)則：(1)根據(jù)經(jīng)驗和以前的試驗結(jié)果，設(shè)置迭代次數(shù)N； 若jN, 則輸出 和Z，結(jié)束。否則，轉(zhuǎn)。(2)取閾值 ， （較合理，常用）若則迭代過程結(jié)束。 若 ， 則輸出 、Z和迭代次數(shù)j，結(jié)束；否則，轉(zhuǎn)(3)求得最優(yōu)解。不動點算法步驟。物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美

26、大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法例1：取 ， （即A(3,3)開始）則 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法例1：物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.1 連續(xù)點選址模型2. 精確重心法例1：取 ， 則 ， ， （選 or ，由Z決定。)注：精確重心法得到的最優(yōu)解只有一個點，且交叉中值法和精確重心法得到的最優(yōu)解一般不一致。作業(yè)：P58 習(xí)題2-7，2(用歐幾米得距離計算時取初值點(7,7),閾值0.15)物流系統(tǒng)規(guī)劃與設(shè)

27、計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型離散點選址問題：在有限的候選位置里，選取最為合適的一個或一組位置為最優(yōu)方案，相應(yīng)的模型叫離散點選址模型。1.覆蓋模型問題：對于需求已知的一些需求點，如何確定一組服務(wù)設(shè)施來滿足這些需求點的需求。在該模型中，需要確定服務(wù)設(shè)施的最小數(shù)量和合適的位置。適用范圍：商業(yè)物流系統(tǒng)：零售點、加油站或配送中心等的選址。公用事業(yè)系統(tǒng)：急救中心、預(yù)防中心等的選址。計算機與通信系統(tǒng)：有線電視網(wǎng)的基站、無線通信網(wǎng)絡(luò)基站、計算機網(wǎng)絡(luò)中的集線器設(shè)置等。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研

28、室3.5.2 離散點選址模型1）集合覆蓋模型 （由解決問題的方法不同分為兩種。）(1)問題:已知需求點的位置、需求量和候選點的位置，求滿足各需求點的服務(wù)需求的條件下，使所投建的設(shè)施點的數(shù)目為最小。目標(biāo):用最小數(shù)量的設(shè)施去覆蓋所有需求點。(覆蓋全部需求點)(2)模型： (教材上：M=N) (各需求點的需求得到100%的滿足) (各設(shè)施點服務(wù)能力的限制) (一個地方最多只能建一個設(shè)施) (允許一個設(shè)施只提供部分需求)物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型其中： N需求點的集合， ； M可建設(shè)施的候選點集合， ；

29、 第i個需求點的需求量； 設(shè)施節(jié)點j的容量； A(j) 設(shè)施節(jié)點j所覆蓋的需求節(jié)點i的集合； （候選設(shè)施點j覆蓋的需求點集。） B(i)可以覆蓋需求點i的設(shè)施節(jié)點j的集合； （覆蓋i的候選設(shè)施點集。） xj yij節(jié)點i需求中被分配給節(jié)點j的部分。物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型（3）求解： 精確算法：規(guī)模較小時可用分枝定界求解法（整數(shù)規(guī)劃中的一個重要解法）求模型的最優(yōu)解，但運算量很大； 近似算法：實際問題中，n和m一般較大（也可能n=m），故需設(shè)計近似算法來求解。啟發(fā)式方法。（結(jié)果為可行解。）集合覆

30、蓋啟發(fā)式算法步驟： （該算法最常用，也最簡單。）確定A(j)，B(i)；簡化問題。若A(j1) A(j2)，則省去A(j1)，即匆略j1作為候選點，M=M-j1，最后得M* 確定合適的組合解。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型例2鄉(xiāng)村醫(yī)療診所選址問題：問題：如圖9個村，希望在每一個村周邊30km內(nèi)至少有一個診所，不考慮診所服務(wù)能力的限制。除第6村外，其他村均可作為候選點。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型解：

31、求A(j)，B(i)， ， ， （候選點j覆蓋的需求點集合） （覆蓋i的候選點集合）簡化問題：若A(j1) A(j2)，則省去A(j1)，即忽略在j1村建，其提供的可能服務(wù)已含在j2村的范圍。物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型 （盡可能少地建設(shè)施。） 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型8,9（8,9）97,8,96,7,8,984,7,84,6,7,874,5,7,863,4,5（3,4,5,6）51,3,4,5,71,3,4,5,6,741,2,3,4,51,2,3,4,531,2,3(1,2,3)2

32、1,2,3,4(1,2,3,4)1村編號2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型 確定合適的組合解。可行解：3,4,7,8、3,4,8、3,8最優(yōu)解：3,83,4,7,8中，2唯一A(3)，9唯一A(8)，且A(3)A(8)覆蓋全部需求點，即N-A(3)A(8)=。 （若N-A(3)A(8)，再用唯一的方法找。） 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 1）集合覆蓋模型擴展解題算法思路： （貪婪法，一般只得到可行解。）如： ，保留 ，省去 的子集，得A(4)，對N-A(4)

33、=2,8,9中的每個i，尋找包含i的最大的 =A(8)，并省去 的子集A(9)， ，得：4,8,2or 4,8,3*or 4,8,1物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型（1）問題：已知需求點的位置和需求量，候選點的位置和所建設(shè)施的數(shù)量中p，選擇p個設(shè)施位置，使盡可能多地滿足需求點的服務(wù)。目標(biāo)：對有限的服務(wù)網(wǎng)點進(jìn)行選址，為盡可能多的對象提供服務(wù)。（2）建立模型 (最大可能地滿足需求). (i需求的滿足不超過100%) (服務(wù)能力的限制) 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物

34、流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型 (最多建p個設(shè)施) (一處最多建一個設(shè)施) (允許一個設(shè)施只提供部分需求)其中：N ，需求點集； （i） M ，可建設(shè)施的候選點集； （j）物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型 di第i個需求點的需求量； Cj j設(shè)施節(jié)點的相應(yīng)容量； A(j) 設(shè)施節(jié)點j所覆蓋的需求點i的集合； B(i)可以覆蓋需求點i的設(shè)施節(jié)點j的集合； p允許投建的設(shè)施數(shù)目； xj yij 節(jié)點i需求中被分配給節(jié)點j的部分。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/1

35、7集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型（3）模型的求解貪婪算法（近似算法）貪婪方法：逐步構(gòu)造最優(yōu)解的方法。每一步都在一定的準(zhǔn)則下作出最優(yōu)的決策，決策一旦作出，就不可更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則。步驟：設(shè)解集 ， ；若 ， 點設(shè)施具有最大的滿足能力，則 ， ；若|S|=p或全部需求得到滿足，結(jié)束。否則，轉(zhuǎn)。物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2）最大覆蓋模型例2 建醫(yī)療站問題,仍不考慮服務(wù)能力的限制。P=2解： ,由前得 ,結(jié)束。注：第2個需求點沒覆蓋。（由最大覆蓋法得到的解集

36、非最優(yōu)解，此仍啟發(fā)式算法的特點。）物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2P中值模型（1）問題：已知數(shù)量和位置的需求集合，候選設(shè)施位置集合，分別為p個設(shè)施選址，并指派每一需求點到一個特定的設(shè)施，使之達(dá)到在設(shè)施和需求點之間的運輸費用最低。目標(biāo)：p個設(shè)施選址并確定各設(shè)施的服務(wù)對象，使總運輸成本最少。（適用于工廠、倉庫或配送中心的選址。）物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2P中值模型（2）建立模型 . (客戶的需求獲得100%的滿足) (投建的總設(shè)施數(shù)為

37、p) (無設(shè)施的點無客戶對應(yīng))物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2P中值模型（2）建立模型 (一處最多建一個設(shè)施) (一客戶只由一設(shè)施服務(wù))其中：N，M，di，p，xj同前；Cij從點i到點j的單位運輸費用；yij物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2P中值模型（3）模型的求解：求解P中值模型需解決兩方面問題：選擇合適的設(shè)施位置（x變量）； （總費用最小。）指派客戶到相應(yīng)的設(shè)施中去。求解方法：精確計算法（只能求解規(guī)模較小的P中值問題）；啟發(fā)式算法

38、。物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型 2P中值模型 （3）模型的求解：貪婪取走啟發(fā)式算法：令當(dāng)前選中設(shè)施點數(shù)k=m； (即將所有m個候選位置都選中)將每個客戶指派給(k個設(shè)施中)離其最近的設(shè)施點，求出總運費Z； 若k=p,輸出k個設(shè)施點及各客戶的指派結(jié)果,結(jié)束;否則,轉(zhuǎn);從k個候選點中確定一個取走點，滿足：若將它取走并將它的客戶重新指派后，總費用增加量最小。從候選點集中刪去取走點，令k:=k-1，轉(zhuǎn)。 物流系統(tǒng)規(guī)劃與設(shè)計3.5 選址模型2022/8/17集美大學(xué)航海學(xué)院物流管理教研室3.5.2 離散點選址模型例3：某飲料公司的倉庫選址問題。N=8，m=4，p=2 目標(biāo)