本章基本要求了解選址的影響因素，掌握選址中的距離計(jì)算，理解和掌握實(shí)際選址問題的分析、模型的構(gòu)建和基本的求解算法。本章重點(diǎn)要求掌握交叉中值模型、重心模型、覆蓋模型、P——中值模型以及這些模型的應(yīng)用。第3章 選址模型及應(yīng)用2023/9/201集美大學(xué)航海學(xué)院物流管理教研室本章目錄選址的意義選址決策的影響因素選址模型的分類選址問題中的距離計(jì)算選址模型連續(xù)點(diǎn)選址模型離散點(diǎn)選址模型家樂福選址實(shí)例剖析本章小結(jié)第3章 選址模型及應(yīng)用2023/9/202集美大學(xué)航海學(xué)院物流管理教研室3.1

選址的意義選址在整個(gè)物流系統(tǒng)中占有非常重要的地位，從圖1-11，物流縱向結(jié)構(gòu)圖看出，物流分為生產(chǎn)物流、商業(yè)物流、回歸物流三類。各類問題的特征各不相同，但每一類問題的不同環(huán)節(jié)都包含了選址問題，如供應(yīng)商、制造商、分銷商、零售商的選

址問題，由此說明了選址在整個(gè)物流系統(tǒng)中的重要性，屬于物流管理戰(zhàn)略層的研究問題，是物流系統(tǒng)規(guī)劃的一大內(nèi)容。（該問題：小到倉(cāng)庫(kù)中貨物存儲(chǔ)位置的分配）第3章 選址模型及應(yīng)用2023/9/203集美大學(xué)航海學(xué)院物流管理教研室3.1

選址的意義⒈選址決策的內(nèi)容：選址決策：確定物流系統(tǒng)中所要分配的設(shè)施（節(jié)點(diǎn)）的數(shù)量、

位置以及分配方案（數(shù)學(xué)的方法）。（設(shè)施 節(jié)點(diǎn)）對(duì)單個(gè)企業(yè)，選址決定了整個(gè)物流系統(tǒng)及其他層次結(jié)構(gòu)。所以，選址、庫(kù)存、運(yùn)輸成本之間存在著密切聯(lián)系。如：企業(yè)分布問

題（二維選址） 其他層次（庫(kù)存、運(yùn)輸?shù)龋┑囊?guī)劃。第3章 選址模型及應(yīng)用2023/10/14集美大學(xué)航海學(xué)院物流管理教研室3.1

選址的意義⒉選址與庫(kù)存、運(yùn)輸成本之間的關(guān)系。降低成本的措施：①合并減少設(shè)施數(shù)量，擴(kuò)大設(shè)施規(guī)模是降低庫(kù)存成本的一個(gè)措施。②確定設(shè)施的合理數(shù)量，也是選址規(guī)劃的主要任務(wù)之一。第3章 選址模型及應(yīng)用2023/10/15集美大學(xué)航海學(xué)院物流管理教研室3.1

選址的意義⒉選址與庫(kù)存、運(yùn)輸成本之間的關(guān)系。就供應(yīng)鏈系統(tǒng)而言，核心企業(yè)的選址決策會(huì)影響所有供應(yīng)商物流系統(tǒng)的選址決策。如DELL、摩托羅拉實(shí)例本章內(nèi)容：實(shí)際選址問題的分析、模型構(gòu)建、求解算法。第3章 選址模型及應(yīng)用2023/10/16集美大學(xué)航海學(xué)院物流管理教研室

為什么目前我國(guó)很多城市熱衷于建物流園區(qū)、物流中心等大規(guī)模物流節(jié)點(diǎn)設(shè)施？討論2023/10/17集美大學(xué)航海學(xué)院物流管理教研室思考選址的影響因素有哪些？？2023/10/18集美大學(xué)航海學(xué)院物流管理教研室3.2.1

選址決策的外部因素分析⒈ 宏觀政治、 經(jīng)濟(jì)因素↓政權(quán)、法制、貿(mào)易集運(yùn)政策等↘稅收政策、關(guān)稅、匯率等↓是無(wú)法量化的指標(biāo),由企業(yè)主觀評(píng)價(jià)↓與企業(yè)選址決策直接相關(guān)

目標(biāo)：尋求最寬松的經(jīng)濟(jì)環(huán)境⒉基礎(chǔ)設(shè)施

及↓交通設(shè)施、通信設(shè)施等環(huán)境↘自然環(huán)境、社會(huì)環(huán)境↓降低物流成本↓勞動(dòng)力的成本、素質(zhì)等3.2

選址決策的影響因素2023/10/19集美大學(xué)航海學(xué)院物流管理教研室3.2.1

選址決策的外部因素分析⒊競(jìng)爭(zhēng)對(duì)手競(jìng)爭(zhēng)對(duì)手的布局情況、自身產(chǎn)品或服務(wù)↘

↙靠近還是遠(yuǎn)離競(jìng)爭(zhēng)對(duì)手3.2

選址決策的影響因素2023/10/110集美大學(xué)航海學(xué)院物流管理教研室3.2.2

選址決策的內(nèi)部因素分析企業(yè)的內(nèi)部因素是最主要的。選址決策首先要與企業(yè)的發(fā)展戰(zhàn)略相適應(yīng)。3.2

選址決策的影響因素2023/10/111集美大學(xué)航海學(xué)院物流管理教研室思考臺(tái)灣的鞋廠到晉江、莆田開店，而電子產(chǎn)品則不會(huì)的原因？？2023/10/112集美大學(xué)航海學(xué)院物流管理教研室選址模型：用數(shù)學(xué)方法確定設(shè)施的數(shù)量、位置和規(guī)模以使物流成本最小。建選址模型前需弄清以下幾個(gè)問題：①選址的對(duì)象？②選址的目標(biāo)區(qū)域？③選址目標(biāo)和成本函數(shù)？④約束條件？①②③④選址問題 選址類型→選址模型→算法→選址方案目前可將選址問題分為以下幾類：3.3

選址模型的分類2023/10/113集美大學(xué)航海學(xué)院物流管理教研室3.3.1

根據(jù)定位設(shè)施的維數(shù)及數(shù)量分類⒈根據(jù)設(shè)施的維數(shù)體選址：定位三維物體，如：卡車、船舶的裝卸；面選址：定位二維物體，如：企業(yè)的部門布置；線選址：定位一維物體，如：配送中心分揀區(qū)傳送帶；點(diǎn)選址：定位零維物體，忽略物體的尺寸。（大多數(shù)選址問題和算法都基于此情況）動(dòng)態(tài)選址問題：+時(shí)間因素的四維選址問題。⒉根據(jù)設(shè)施選址的數(shù)量：?jiǎn)我辉O(shè)施選址：主要考慮運(yùn)輸成本多設(shè)施選址：運(yùn)輸成本、競(jìng)爭(zhēng)力、設(shè)施間需求的分配、設(shè)施成本與數(shù)量間的關(guān)系。3.3

選址模型的分類2023/10/114集美大學(xué)航海學(xué)院物流管理教研室3.3.2

據(jù)選址問題目標(biāo)區(qū)域的特征分類⒈連續(xù)選址待選區(qū)域?yàn)槠矫妫蛇x位置不限，選址模型為連續(xù)的。如：企業(yè)配送中心的初步選址。⒉網(wǎng)格選址待選區(qū)域?yàn)槠矫婢W(wǎng)格區(qū)域候選地址有限（相當(dāng)大）。↓許多相等面積的區(qū)域，如正方形如:倉(cāng)庫(kù)中不同貨物的存儲(chǔ)位置的分配或展覽中心展區(qū)的布置。⒊離散選址（最切合實(shí)際）待選區(qū)域是離散的候選位置集合，數(shù)量有限（甚少）。如：企業(yè)配送中心的詳細(xì)選址設(shè)計(jì)。3.3

選址模型的分類2023/10/115集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類根據(jù)選址成本，有幾種類型：尋求可行成本方案或最優(yōu)成本方案；尋求總成本最小或成本最大值的最小化；固定權(quán)重或可變權(quán)重；確定性的或隨機(jī)性的；被定位設(shè)施間有無(wú)相互聯(lián)系；靜態(tài)或是動(dòng)態(tài)的選址問題。⒈

可行性/最優(yōu)性即是尋求可行成本方案還是最優(yōu)成本方案？對(duì)于許多選址問題：第一目標(biāo)：得到一個(gè)可行的解決方案，即滿足所有約束的解決方案；（多個(gè)）第二目標(biāo)：找到一個(gè)更好的解決方案，即關(guān)于目標(biāo)函數(shù)的優(yōu)化。（一個(gè)）3.3

選址模型的分類2023/10/116集美大學(xué)航海學(xué)院物流管理教研室；3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)①

Minisum目標(biāo)函數(shù)問題：尋求整個(gè)設(shè)施選址的成本總和為最小。

目標(biāo)：優(yōu)化全部或者平均性能。適用：企業(yè)問題。故稱“經(jīng)濟(jì)效益性”或稱網(wǎng)絡(luò)上的中值問題。其中：X——新的待定位設(shè)施物體的坐標(biāo)

j——已存在且位置固定的物體編號(hào)；——對(duì)于已經(jīng)存在的物體j，新物體定位在X時(shí)的成本。3.3

選址模型的分類2023/10/117集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)①

Minisum目標(biāo)函數(shù)3.3

選址模型的分類2023/10/118集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)②

Minimax目標(biāo)函數(shù)問題：尋求已存在設(shè)施的單個(gè)成本最大的成本值為最小。

目標(biāo)：優(yōu)化最壞的情況。適用：軍隊(duì)、緊急情況和公共部門。稱作“經(jīng)濟(jì)平衡性”，也稱為網(wǎng)絡(luò)上的中心問題 （照顧到最邊遠(yuǎn)的地區(qū)）（離客戶到最近的設(shè)施的成本“最大值”最小的原則）3.3

選址模型的分類2023/10/119集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)③Maximin目標(biāo)函數(shù)問題：尋求已存在設(shè)施的單個(gè)成本最小的成本值為最大。

目標(biāo)：使最壞的情況最優(yōu)化。適用：有害設(shè)施（廢水處理廠、軍工廠等）的選址。此時(shí)，物體被定位在使最小距離最大化的地方。稱作“經(jīng)濟(jì)平衡性”，也稱為

網(wǎng)絡(luò)上的“反中心”問題。3.3

選址模型的分類2023/10/120集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)例：設(shè)一直線上在0，5，6，7上有4個(gè)點(diǎn)，成本與點(diǎn)到新設(shè)施間的距離成比例。注：中值點(diǎn)：minisum；中心點(diǎn)：minimax；反中心點(diǎn)：maximin3.3

選址模型的分類2023/10/121集美大學(xué)航海學(xué)院物流管理教研室⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)①M(fèi)inisum.

——中值點(diǎn) （成本只與距離有關(guān)）

解：設(shè)新點(diǎn)設(shè)在x，則：當(dāng) 時(shí)，當(dāng) 時(shí)，當(dāng) 時(shí)，∴ 的x的取值為注:在選址的左右側(cè)有同樣多的點(diǎn)。5和6間的點(diǎn)均為中值位置。3.3

選址模型的分類2023/10/122集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)②

Minimax

——中心點(diǎn)，，∴——選址位置到最左邊點(diǎn)和到最右邊點(diǎn)的距離是相等的。（中心點(diǎn)唯一）3.3

選址模型的分類2023/10/123集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)擴(kuò)展：若

， 不變。（中值點(diǎn)左右側(cè)各點(diǎn)的實(shí)際位置不重要，只要兩側(cè)點(diǎn)的數(shù)目相同。）若在

、 之間增加1000個(gè)點(diǎn)， 不變。（中心選址是由那些極端位置決定的，即最左和最右兩點(diǎn)的中心。）中值選址由固定位置的順序決定，非實(shí)際位置。中心選址由那些極端位置決定，與內(nèi)部位置無(wú)關(guān)。3.3

選址模型的分類2023/10/124集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)③

Maximin

：

——反中心點(diǎn)當(dāng)3.3

選址模型的分類2023/10/125集美大學(xué)航海學(xué)院物流管理教研室⒉

Minisum/Minimax/Maximin目標(biāo)函數(shù)③

Maximin

：

——反中心點(diǎn)

當(dāng)——選址位置為相鄰間距離最大兩點(diǎn)的中點(diǎn)。（反中心點(diǎn)唯一）3）反中心選址由相鄰間距離最大的位置決定。3.3

選址模型的分類2023/10/126集美大學(xué)航海學(xué)院物流管理教研室討論2023/10/127集美大學(xué)航海學(xué)院物流管理教研室

建急救中心宜選用哪類

選址目標(biāo)函數(shù)？

建垃圾清潔樓宜選用哪類選址目標(biāo)函數(shù)？

建物流配送中心宜選用哪類選址目標(biāo)函數(shù)？3.3.3

據(jù)選址成本分類固定權(quán)重與可變權(quán)重① 單純選址問題（固定權(quán)重）：新設(shè)施和已存在設(shè)施間的關(guān)系與新設(shè)施的位置無(wú)關(guān),是固定的② 選址——分配問題（可變權(quán)重）：這種權(quán)重或關(guān)系與新設(shè)施的位置相關(guān)。被定位設(shè)施間有無(wú)相互聯(lián)系（一次or二次）（多設(shè)施選址）①一次目標(biāo)函數(shù)：無(wú)②二次或高次目標(biāo)函數(shù)：有3.3

選址模型的分類2023/10/128集美大學(xué)航海學(xué)院物流管理教研室3.3.3

據(jù)選址成本分類確定性與隨機(jī)性①確定性：選址的成本或參數(shù)值是確定的。②隨機(jī)性：選址的成本或參數(shù)是一個(gè)隨機(jī)分布的概率值。（如：客戶需求）靜態(tài)與動(dòng)態(tài)成本或參數(shù)是否隨時(shí)間變化。3.3

選址模型的分類2023/10/129集美大學(xué)航海學(xué)院物流管理教研室3.3.4

選址約束1．有能力約束與無(wú)能力約束：新設(shè)施的能力有否被限制。

2．不可行區(qū)域約束：在目標(biāo)區(qū)域內(nèi)有（無(wú)）不適合作為選址地點(diǎn)的區(qū)域。3.3

選址模型的分類2023/10/130集美大學(xué)航海學(xué)院物流管理教研室3.4.1 直線距離（歐幾里得距離）適用：大范圍的選址問題，城市間配送問題和通信問題。↓實(shí)際路線距離 （如在美國(guó)大陸

，在東南美洲 ）

——分形理論3.4

選址問題中的距離計(jì)算2023/10/131集美大學(xué)航海學(xué)院物流管理教研室3.4.2 折線距離（城市距離）適用：城市(道路較規(guī)則的)內(nèi)的配送問題，具有直線通道的工廠

及倉(cāng)庫(kù)內(nèi)的布置、物料搬運(yùn)設(shè)備的順序移動(dòng)等問題。3.4

選址問題中的距離計(jì)算2023/10/132集美大學(xué)航海學(xué)院物流管理教研室選址模型的功能：①選址定位：為設(shè)施找到一個(gè)最優(yōu)的位置；②系統(tǒng)設(shè)計(jì)：是物流系統(tǒng)設(shè)計(jì)中的一個(gè)重要部分。*直線型設(shè)施選址模型：①單距離因素情況：街上各個(gè)位置可能出現(xiàn)顧客的概率相同，取中心點(diǎn)。目標(biāo)：所有顧客到達(dá)新設(shè)施點(diǎn)的平均距離最小。（單點(diǎn)選址，minisum型，中值解。）②加權(quán)重的離散模型：街上各個(gè)位置可能出現(xiàn)顧客的概率不一樣目標(biāo)：到目標(biāo)點(diǎn)的絕對(duì)距離的總和最小。（單點(diǎn)選址，minisum型，中值解。）3.5

選址模型2023/10/133集美大學(xué)航海學(xué)院物流管理教研室②加權(quán)重的離散模型：其中：——第i個(gè)位置的權(quán)重；——第i個(gè)位置的坐標(biāo)；——新設(shè)施選址的坐標(biāo)。3.5

選址模型2023/10/134集美大學(xué)航海學(xué)院物流管理教研室②加權(quán)重的離散模型：求解：( 的左、右側(cè)權(quán)重相等。)3.5

選址模型2023/10/135集美大學(xué)航海學(xué)院物流管理教研室③加權(quán)重的連續(xù)模型：（屬minisum解，即中值解）3.5

選址模型2023/10/136集美大學(xué)航海學(xué)院物流管理教研室③加權(quán)重的連續(xù)模型：（屬minisum解，即中值解）

求解：（s兩邊的權(quán)重都是50%，即權(quán)重的中點(diǎn)。）3.5

選址模型2023/10/137集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型（在一條路徑或一個(gè)區(qū)域內(nèi)，無(wú)不可行區(qū)域）1. 交叉中值模型

（x，y方向的中值點(diǎn)）

距離：城市距離（折線距離）類型：?jiǎn)我贿x址問題目標(biāo)：加權(quán)的城市距離總和最小（總費(fèi)用最小）。適用：小范圍的城市內(nèi)的選址問題。3.5

選址模型2023/10/138集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型1.

交叉中值模型其中：

——與第i點(diǎn)相對(duì)應(yīng)的權(quán)重；——第i個(gè)需求點(diǎn)的坐標(biāo)；——新設(shè)施點(diǎn)的坐標(biāo)；

n——需求點(diǎn)的總數(shù)目。求解：是在x方向?qū)λ袡?quán)重

是在y方向?qū)λ袡?quán)重的中值點(diǎn)；的中值點(diǎn)。最優(yōu)解：可能是一個(gè)點(diǎn)，或是線，或是一個(gè)區(qū)域。3.5

選址模型2023/10/139集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型1.

交叉中值模型

例1：報(bào)刊亭選址。3.5

選址模型2023/10/140集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型1.

交叉中值模型

例

1：

報(bào)刊亭選址。：第個(gè)月潛在的顧客需求總量，近似為i區(qū)中的總的居民數(shù)量或戶數(shù)。問題（目標(biāo)）：每個(gè)月顧客到報(bào)刊點(diǎn)所走距離的總和為最小。

解：①模型選擇：城市距離，交叉中值選址方法。②確定中值：3.5

選址模型2023/10/141集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型1.

交叉中值模型:例1：報(bào)刊亭選址。③求

,

：在x方向：左→右：右→左：3.5

選址模型2023/10/142集美大學(xué)航海學(xué)院物流管理教研室，，，，3.5.1

連續(xù)點(diǎn)選址模型1.

交叉中值模型:例1：報(bào)刊亭選址。在y方向：上→下：

（即

）下→上：

（即

）最優(yōu)解為AB（A=(3,3),

B=(4,3)）3.5

選址模型2023/10/143集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型1.

交叉中值模型:例1：報(bào)刊亭選址。比較A，B兩個(gè)位置的加權(quán)距離；A：B：根據(jù)實(shí)際情況，選址為A、B之間的任何一點(diǎn)。(交叉中值法可為決策提供更多的選擇和靈活性。)作業(yè)：P58 習(xí)題2-7，13.5

選址模型2023/10/144集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2.

精確重心法距離：直線距離類型：?jiǎn)吸c(diǎn)的選址問題問題（目標(biāo)）：尋求加權(quán)的直線距離總和最小（總費(fèi)用最小）。適用：平面上大范圍的選址，無(wú)受限區(qū)域。（連續(xù)區(qū)域、直線距離的單點(diǎn)選址）（最優(yōu)解唯一）其中：各變量的含義同交叉中值模型。3.5

選址模型2023/10/145集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2.

精確重心法求解：其中：

(含xs,ys,無(wú)法一次求得顯式解)∴只能用迭代的方法對(duì)上式求近似解。3.5

選址模型2023/10/146集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2.

精確重心法求解：迭代公式：（j為迭代次數(shù)）其中：應(yīng)用上述迭代公式，可采用逐步逼近算法求得最優(yōu)解。3.5

選址模型2023/10/147集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2.

精確重心法求解：算法（單一選址的不動(dòng)點(diǎn)算法）：輸入：n——客戶數(shù)；——各客戶點(diǎn)的坐標(biāo)，——各客戶點(diǎn)對(duì)應(yīng)的權(quán)重，；;(包括運(yùn)費(fèi)和運(yùn)量)輸出：——設(shè)施坐標(biāo)；

Z——總運(yùn)費(fèi)。，步驟：①選取初始迭代點(diǎn)

，如：或以交叉中值模型選址的結(jié)果之一作為。3.5

選址模型2023/10/148集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2.

精確重心法求解：算法（單一選址的不動(dòng)點(diǎn)算法）：計(jì)算A到各客戶點(diǎn)的直線距離

和：3.5

選址模型2023/10/149集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2. 精確重心法求解：算法（單一選址的不動(dòng)點(diǎn)算法）：②令計(jì)算：3.5

選址模型2023/10/150集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2. 精確重心法求解：算法（單一選址的不動(dòng)點(diǎn)算法）：③若 ，運(yùn)費(fèi)已無(wú)法減小；輸出最優(yōu)解 、Z和迭代次數(shù)j，結(jié)束。，

， （可能迭代無(wú)限次）否則，轉(zhuǎn)②注1：若工廠到設(shè)施的運(yùn)費(fèi)包含在成本中，則可將工廠視為一個(gè)

客戶點(diǎn)Pi；注2：若直線距離與實(shí)際距離有差異，可用一定的修正系數(shù)

來(lái)修正差異。3.5

選址模型2023/10/151集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2. 精確重心法求解：算法（單一選址的不動(dòng)點(diǎn)算法）：終止準(zhǔn)則：根據(jù)經(jīng)驗(yàn)和以前的試驗(yàn)結(jié)果，設(shè)置迭代次數(shù)N；③若j>N, 則輸出 和Z，結(jié)束。否則，轉(zhuǎn)②。取閾值

， （較合理，常用）若則輸出 、Z和則迭代過程結(jié)束。③若

，迭代次數(shù)j，結(jié)束；否則，轉(zhuǎn)②

(3)求得最優(yōu)解。不動(dòng)點(diǎn)算法步驟③。3.5

選址模型2023/10/152集美大學(xué)航海學(xué)院物流管理教研室（即A(3,3)開始）3.5.1

連續(xù)點(diǎn)選址模型2.

精確重心法例1’：取

，則3.5

選址模型2023/10/153集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2.

精確重心法

例1’：3.5

選址模型2023/10/154集美大學(xué)航海學(xué)院物流管理教研室3.5.1

連續(xù)點(diǎn)選址模型2.

精確重心法例1’：取

，則

，， （選or ，由Z決定。)注：精確重心法得到的最優(yōu)解只有一個(gè)點(diǎn)，且交叉中值法和精確

重心法得到的最優(yōu)解一般不一致。作業(yè)：P58 習(xí)題2-7，2(用歐幾米得距離計(jì)算時(shí)取初值點(diǎn)(7,7),閾值0.15)3.5

選址模型2023/10/155集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型離散點(diǎn)選址問題：在有限的候選位置里，選取最為合適的一個(gè)或一組位置為最優(yōu)方案，相應(yīng)的模型叫離散點(diǎn)選址模型。1.覆蓋模型問題：對(duì)于需求已知的一些需求點(diǎn)，如何確定一組服務(wù)設(shè)施來(lái)滿足這些需求點(diǎn)的需求。在該模型中，需要確定服務(wù)設(shè)施的最小數(shù)量和合適的位置。適用范圍：①商業(yè)物流系統(tǒng)：零售點(diǎn)、加油站或配送中心等的選址。②公用事業(yè)系統(tǒng)：急救中心、預(yù)防中心等的選址。③計(jì)算機(jī)與通信系統(tǒng)：有線電視網(wǎng)的基站、無(wú)線通信網(wǎng)絡(luò)基站、計(jì)算機(jī)網(wǎng)絡(luò)中的集線器設(shè)置等。3.5

選址模型2023/10/156集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型1）集合覆蓋模型

（由解決問題的方法不同分為兩種。）問題:已知需求點(diǎn)的位置、需求量和候選點(diǎn)的位置，求滿足各需求點(diǎn)的服務(wù)需求的條件下，使所投建的設(shè)施點(diǎn)的數(shù)目為最小。

目標(biāo):用最小數(shù)量的設(shè)施去覆蓋所有需求點(diǎn)。(覆蓋全部需求點(diǎn))模型：

(教材上：M=N)s.t

(各需求點(diǎn)的需求得到100%的滿足)

(各設(shè)施點(diǎn)服務(wù)能力的限制)(一個(gè)地方最多只能建一個(gè)設(shè)施)

(允許一個(gè)設(shè)施只提供部分需求)3.5

選址模型2023/10/157集美大學(xué)航海學(xué)院物流管理教研室1）集合覆蓋模型3.5.2

離散點(diǎn)選址模型其中：；N——需求點(diǎn)的集合，M——可建設(shè)施的候選點(diǎn)集合，；——第i個(gè)需求點(diǎn)的需求量；——設(shè)施節(jié)點(diǎn)j的容量；A(j)

——設(shè)施節(jié)點(diǎn)j所覆蓋的需求節(jié)點(diǎn)i的集合；（候選設(shè)施點(diǎn)j覆蓋的需求點(diǎn)集。）B(i)——可以覆蓋需求點(diǎn)i的設(shè)施節(jié)點(diǎn)j的集合；（覆蓋i的候選設(shè)施點(diǎn)集。）xj——yij——節(jié)點(diǎn)i需求中被分配給節(jié)點(diǎn)j的部分。3.5

選址模型2023/10/158集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型1）集合覆蓋模型（3）求解：① 精確算法：規(guī)模較小時(shí)可用分枝定界求解法（整數(shù)規(guī)劃中的一個(gè)重要解法）求模型的最優(yōu)解，但運(yùn)算量很大；② 近似算法：實(shí)際問題中，n和m一般較大（也可能n=m），故需設(shè)計(jì)近似算法來(lái)求解。——啟發(fā)式方法。（結(jié)果為可行解。）集合覆蓋啟發(fā)式算法步驟：

（該算法最常用，也最簡(jiǎn)單。）①確定A(j)，B(i)；②簡(jiǎn)化問題。若A(j1) A(j2)，則省去A(j1)，即匆略

j1作為候選點(diǎn)，M′=M-{j1}，最后得M*③

確定合適的組合解。3.5

選址模型2023/10/159集美大學(xué)航海學(xué)院物流管理教研室：3.5.2

離散點(diǎn)選址模型1）集合覆蓋模型例2．鄉(xiāng)村醫(yī)療診所選址問題：?jiǎn)栴}：如圖9個(gè)村，希望在每一個(gè)村周邊30km內(nèi)至少有一個(gè)診所，

不考慮診所服務(wù)能力的限制。除第6村外，其他村均可作為候選點(diǎn)。3.5

選址模型2023/10/160集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型1）集合覆蓋模型解：①求A(j)，B(i)，，，（候選點(diǎn)j覆蓋的需求點(diǎn)集合）（覆蓋i的候選點(diǎn)集合）②簡(jiǎn)化問題：若A(j1) A(j2)，則省去A(j1)，即忽略在j1村建，其提供的可能

服務(wù)已含在j2村的范圍。3.5

選址模型2023/10/161集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型1）集合覆蓋模型（盡可能少地建設(shè)施。）3.5

選址模型村編號(hào)1×(1,2,3,4)1,2,3,42×(1,2,3)1,2,331,2,3,4,51,2,3,4,541,3,4,5,6,71,3,4,5,75×（3,4,5,6）3,4,56×4,5,7,874,6,7,84,7,886,7,8,97,8,99×（8,9）8,92023/10/162集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型1）集合覆蓋模型③

確定合適的組合解。可行解：{3,4,7,8}、{3,4,8}、{3,8}最優(yōu)解：{3,8}∵{3,4,7,8}中，2唯一∈A(3)，9唯一∈A(8)，且A(3)∪A(8)覆

蓋全部需求點(diǎn)，即N-A(3)∪A(8)=Ф。（若N-A(3)∪A(8)≠Ф，再用唯一∈的方法找。）3.5

選址模型2023/10/163集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型1）集合覆蓋模型擴(kuò)展解題算法思路： （貪婪法，一般只得到可行解。）如： ，保留 ，省去 的子集，

得A(4)，對(duì)N-A(4)={2,8,9}中的每個(gè)i，尋找包含i的最大的=A(8)，并省去 的子集A(9)，，得：{4,8,2}or

{4,8,3}*or{4,8,1}3.5

選址模型2023/10/164集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2）最大覆蓋模型問題：已知需求點(diǎn)的位置和需求量，候選點(diǎn)的位置和所建設(shè)施的數(shù)量中p，選擇p個(gè)設(shè)施位置，使盡可能多地滿足需求點(diǎn)的服務(wù)。目標(biāo)：對(duì)有限的服務(wù)網(wǎng)點(diǎn)進(jìn)行選址，為盡可能多的對(duì)象提供服務(wù)。建立模型(最大可能地滿足需求)s.t.(i需求的滿足不超過100%)(服務(wù)能力的限制)3.5

選址模型2023/10/165集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2）最大覆蓋模型其中：N——M——(最多建p個(gè)設(shè)施)(一處最多建一個(gè)設(shè)施)

(允許一個(gè)設(shè)施只提供部分需求)，需求點(diǎn)集；

（i），可建設(shè)施的候選點(diǎn)集；

（j）3.5

選址模型2023/10/166集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2）最大覆蓋模型di——第i個(gè)需求點(diǎn)的需求量；Cj

——j設(shè)施節(jié)點(diǎn)的相應(yīng)容量；A(j)

——設(shè)施節(jié)點(diǎn)j所覆蓋的需求點(diǎn)i的集合；

B(i)——可以覆蓋需求點(diǎn)i的設(shè)施節(jié)點(diǎn)j的集合；

p——允許投建的設(shè)施數(shù)目；xj

——yij——節(jié)點(diǎn)i需求中被分配給節(jié)點(diǎn)j的部分。3.5

選址模型2023/10/167集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2）最大覆蓋模型（3）模型的求解——貪婪算法（近似算法）貪婪方法：逐步構(gòu)造最優(yōu)解的方法。每一步都在一定的準(zhǔn)則下作出最優(yōu)的決策，決策一旦作出，就不可更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則。步驟：①設(shè)解集

，

；②若

， 點(diǎn)設(shè)施具有最大的滿足能力，則

，

；③若|S|=p或全部需求得到滿足，結(jié)束。否則，轉(zhuǎn)②。3.5

選址模型2023/10/168集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2）最大覆蓋模型例2’

建醫(yī)療站問題,仍不考慮服務(wù)能力的限制。P=2解：①

,由前得②③,結(jié)束。注：第2個(gè)需求點(diǎn)沒覆蓋。（由最大覆蓋法得到的解集非最優(yōu)解，

此仍啟發(fā)式算法的特點(diǎn)。）3.5

選址模型2023/10/169集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2．P—中值模型（1）問題：已知數(shù)量和位置的需求集合，候選設(shè)施位置集合，①分別為p個(gè)設(shè)施選址，②并指派每一需求點(diǎn)到一個(gè)特定的設(shè)施，使之達(dá)到在設(shè)施和需求點(diǎn)之間的運(yùn)輸費(fèi)用最低。目標(biāo)：p個(gè)設(shè)施選址并確定各設(shè)施的服務(wù)對(duì)象，使總運(yùn)輸成本最少。（適用于工廠、倉(cāng)庫(kù)或配送中心的選址。）3.5

選址模型2023/10/170集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2．P—中值模型（2）建立模型s.t.(客戶的需求獲得100%的滿足)(投建的總設(shè)施數(shù)為p)(無(wú)設(shè)施的點(diǎn)無(wú)客戶對(duì)應(yīng))3.5

選址模型2023/10/171集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2．P—中值模型（2）建立模型(一處最多建一個(gè)設(shè)施)(一客戶只由一設(shè)施服務(wù))其中：N，M，di，p，xj同前；Cij——從點(diǎn)i到點(diǎn)j的單位運(yùn)輸費(fèi)用；yij——3.5

選址模型2023/10/172集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型（總費(fèi)用最小。）2．P—中值模型（3）模型的求解：求解P—中值模型需解決兩方面問題：①選擇合適的設(shè)施位置（x變量）；②指派客戶到相應(yīng)的設(shè)施中去。求解方法：①精確計(jì)算法（只能求解規(guī)模較小的P—中值問題）；②啟發(fā)式算法。3.5

選址模型2023/10/173集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型2．P—中值模型（3）模型的求解：貪婪取走啟發(fā)式算法：①令當(dāng)前選中設(shè)施點(diǎn)數(shù)k=m；

(即將所有m個(gè)候選位置都選中)②將每個(gè)客戶指派給(k個(gè)設(shè)施中)離其最近的設(shè)施點(diǎn)，求出總運(yùn)費(fèi)Z；③若k=p,輸出k個(gè)設(shè)施點(diǎn)及各客戶的指派結(jié)果,結(jié)束;否則,轉(zhuǎn)④;④從k個(gè)候選點(diǎn)中確定一個(gè)取走點(diǎn)，滿足：若將它取走并將它的客戶重新指派后，總費(fèi)用增加量最小。⑤從候選點(diǎn)集中刪去取走點(diǎn)，令k:=k-1，轉(zhuǎn)②。3.5

選址模型2023/10/174集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)選址模型例3：某飲料公司的倉(cāng)庫(kù)選址問題。

N=8，m=4，p=2目標(biāo)：運(yùn)輸成本最低。3.5

選址模型2023/10/175集美大學(xué)航海學(xué)院物流管理教研室3.5.2

離散點(diǎn)