【正文】 problem)。例如，倉庫與所服務(wù)的顧客之間的選址與分配問題，去掉一個倉庫不僅增加了顧客的距離，還要將這些顧客到其他倉庫。 ? 這些分類與不同的距離結(jié)合起來，就得到不同的選址模型 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 距離 ? 直角距離（ Rectilinear distance），指沿著相互成直角的路徑進(jìn)行測量得到的距離。它也稱為曼哈頓距離，由來是因為曼哈頓的許多街道不是垂直的就是平行的。例如，工廠的物料搬運車輛沿著直角通道前進(jìn)就屬于這種情況。 ? 直線距離（ Euclidean distance，也稱為歐氏距離），指沿著兩點之間的直線進(jìn)行測量得到的距離。例如一條連接兩個工作臺的直線輸送機就是直線距離的實例。 ? 流程距離（ Flow path distance），指沿著兩點之間實際穿越的路線進(jìn)行測量得到的距離，也稱為契巴雪夫距離（Chebychev distance）。例如，自動導(dǎo)引車系統(tǒng)中一輛承擔(dān)了運輸任務(wù)的小車必須沿著導(dǎo)軌路徑前進(jìn)，因此，流程距離是從縱橫坐標(biāo)的差值中取最大的，可能比直角距離和歐氏距離都要長 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 選址問題模型應(yīng)用 ? 為緊急服務(wù)設(shè)施選址，如醫(yī)院、消防站； ? 確定工廠內(nèi)工具室、機器、維修室、飲水處、盥洗室、急救站的“最佳”位置； ? 為倉庫和配送中心選址； ? 選擇合同商并分配工作； ? 選擇供應(yīng)商并確定采購項目； ? 最不期望位置的確定。 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 132 單設(shè)施選址問題與模型 ? 最早探討選址問題是韋伯 1909年提出的單一倉庫選址如何使得到達(dá)多個顧客的總距離最短問題，這種問題后來被歸結(jié)為 p中值問題 （韋伯問題）。 ? 自 20世紀(jì) 60年代以來選址問題的研究迅猛發(fā)展，其他經(jīng)常探討的選址問題還有覆蓋問題、 p中心問題、選址 分配問題、有容量限制的設(shè)施選址問題、選址路徑問題、網(wǎng)絡(luò)選址問題和二次分配問題等。 ? 例如在物流網(wǎng)絡(luò)中，配送中心居于重要的樞紐地位，它的選址問題十分重要，常用定量的分析模型，如重心法、鮑姆爾 沃爾夫法、覆蓋模型、混合整數(shù)規(guī)劃法等，以充分考慮物流網(wǎng)絡(luò)中各個環(huán)節(jié)的費用，在一定的物流報務(wù)水平下，根據(jù)不同的模型和算法求出物流總成本最低的最優(yōu)解或滿意解，以獲得選址方案。由于配送中心服務(wù)于供應(yīng)和銷售雙方，多配送中心選址還要考慮服務(wù)范圍問題，這就是更復(fù)雜的選址 分配問題。 ??? mi ii PXdwXfMin 1 ),()(基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 133 直角距離單設(shè)施選址問題 ? X =(x, y) 新設(shè)施的位置 ? Pi =(ai, bi) 現(xiàn)有設(shè)施 i 的位置， i=1, 2, …, m ? wi 在新設(shè)施和現(xiàn)有設(shè)施 i 之間物料運輸“權(quán)值”（單位成本） ? d (X, Pi) 新設(shè)施和現(xiàn)有設(shè)施 i 之間的距離 ? 假設(shè)新設(shè)施和現(xiàn)有設(shè)施 i 之間的年運輸成本與點 X 和 Pi 之間的距離成正比， wi 為比例常數(shù)。 ? 則目標(biāo)函數(shù)為： ? ? 直角距離 將兩點的橫、縱坐標(biāo)之差的絕對值相加： ??? mi ii PXdwXfMin 1 ),()( ???miii PXdwXfMin1),()(( , ) | | | |i i id X P x a y b? ? ? ?基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 134 例：求解權(quán)距和最小選址問題 ? 假設(shè)需要在工廠的維修部布置一臺新設(shè)備，維修部現(xiàn)在已經(jīng)有 5臺設(shè)備，且這 5臺設(shè)備與新設(shè)備之間存在物料搬運作業(yè)。現(xiàn)有設(shè)備分別位于 P1=(1, 1)， P2=(5, 2)， P3=(2, 8)，P4=(4, 4)， P5=(8, 6)。在新設(shè)備和每臺現(xiàn)有設(shè)備之間的搬運成本相同。每天在新設(shè)備與現(xiàn)有設(shè)備之間的搬運行程數(shù)分別為 5， 6，2， 4， 8。 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 135 利用結(jié)論：新設(shè)施的 x坐標(biāo)一定與某個現(xiàn)有設(shè)施的 x坐標(biāo)相同；而且 x坐標(biāo)的最優(yōu)值具備以下特性：該點左邊的權(quán)值和小于總權(quán)值的 1/2，該點右邊的權(quán)值和大于總權(quán)值的 1/2。 ? 對現(xiàn)有設(shè)施的 x 坐標(biāo)進(jìn)行排序，順序為 1, 2, 4, 5, 8, 相應(yīng)的權(quán)值順序為 5, 2, 4, 6, 8, 權(quán)值和為 25。如下表 1所示， i =2時，權(quán)值部分和大于權(quán)值總和的 1/2，因此 x* =a2=5。同樣 y 的最優(yōu)解在 y* =b4=4 得到（見表 2）。因此， X* =(5, 4)為新設(shè)施最優(yōu)地址。下圖用直角折線繪出了新址與現(xiàn)有設(shè)施地址之間的直線距離。 1087654321876543203P32w ?5P58w ?4P44w ?1P15w ?2P26w ?基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 WinQSB求解 ? (1) 打開 WinQSB的 Facility Location and Layout（設(shè)施選址與布置）模塊，建立一個新問題，在彈出的 Problem Specification（問題說明）對話框中選擇第一類 Facility Location，并輸入上例 Example 43，已有設(shè)施數(shù) 新設(shè)施坐標(biāo)維數(shù) 2，如左圖所示。完成后單擊 OK。 ? (2) 在出現(xiàn)的表格中輸入 P1~ P5各點坐標(biāo)數(shù)據(jù)和至新設(shè)備的行程數(shù)據(jù)，如右圖所示。 ? 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 WinQSB求解 ? (3) 選擇“ Solve and Analysis”菜單的“ Solve the Problem”命令（或直接單擊工具欄最右邊的“ Run and Solve the Problem”按鈕），彈出如圖左所示的“ Facility Location Solution”對話框。在“ Solution Option”（求解選項）中當(dāng)然選擇“ Solve the Optimal New Location(s)”（新址的最優(yōu)解）。在“ Distance Measure”（距離度量）中選擇“ Rectilinear Distance”（直角距離）。 ? (4)單擊 OK，即可得到右所示的表格結(jié)果（可以與前面的對比）。選擇“ Results”菜單的“ Show Location in Graph”即可得到右上所示的圖形結(jié)果。 ? ? 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 138 第六節(jié) 多設(shè)施選址問題與物流網(wǎng)絡(luò) ? 隨著企業(yè)運營網(wǎng)絡(luò)的擴(kuò)大 ， 在多地設(shè)置工廠和其他物流與運營設(shè)施時 ， 不但要考慮自己的產(chǎn)供銷物流 ， 還要考慮到供應(yīng)鏈系統(tǒng) ， 這時就出現(xiàn)多設(shè)施選址問題或物流網(wǎng)絡(luò)設(shè)計 ， 乃至供應(yīng)鏈設(shè)計問題 。 ? 多設(shè)施選址和物流網(wǎng)絡(luò)問題成為大中型制造企業(yè) 、銷售企業(yè) 、 物流企業(yè)需要考慮的問題 ， 包括多工廠 、 多倉庫 、 多配送中心等設(shè)施網(wǎng)絡(luò)的選址問題 。 ? 除前面小節(jié)介紹的 p中值模型外 ， 還有運輸問題規(guī)劃法 、 覆蓋問題 、 有容量限制的選址問題和BaumolWolfe法等 。 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 139 某汽車廠設(shè)施網(wǎng)絡(luò) ?配送中心 B ?配送中心 N ?配送中心 A ?43S/4S店 1 ?3S/4S店 2 ?3S/4S店 N … … … … … … … … … … … … … … ?產(chǎn)品調(diào)撥 ?產(chǎn)品調(diào)撥 ?采購、部品處 ?（零部件物流） ?營業(yè)部（整車物流） ?財務(wù)處（結(jié)算中心） ?整車庫房 ?部品庫房 ?整車工廠 ?整車入庫 ?原料供應(yīng)商 A ?原料供應(yīng)商 B ?原料、部品供應(yīng)商 N ?原料供應(yīng)商 C … … … ?原料、部品采集 ?部品車間 ?部品入庫 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 140 運輸模型法 ? 如果幾個備選方案的各種影響因素的作用程度差不多，可以不予考慮的話，此時費用就成為唯一的決策因素，線性規(guī)劃方法成為處理這類選址決策的理想工具。 ? 線性規(guī)劃方法是一種廣泛使用的最優(yōu)化技巧，它在考慮特定的約束條件下，從許多可用的選擇中挑選出最佳方案。對于復(fù)合選址問題，即一家公司設(shè)有多個工廠供應(yīng)多個銷售點，當(dāng)產(chǎn)量不足時，需要增建工廠，一般已知數(shù)個待選廠址方案，要求確定一個廠址，使已有設(shè)施的生產(chǎn)運輸費用最小。運輸模型法的分析目標(biāo)是在給定有限原料位置點的供給和特定的需求要求后，尋找出在最低可能運輸成本下滿足所有的需要。 ? 運輸模型法已有成熟的解法，如表上作業(yè)法或用 Lindo、Excel等軟件求解。 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 142 多設(shè)施選址問題基本問題及物流網(wǎng)絡(luò) ? 對于離散點選址，新設(shè)施的可選點是有限集合，這時最簡單的問題是要選擇 p個設(shè)施，使得滿足全部顧客需求的物流總成本最少（即 p中值問題），并假設(shè)所有備選點的設(shè)置成本相同，否則目標(biāo)函數(shù)中就要考慮各點的設(shè)置成本。 ? 另一假設(shè)是備選點容量無限，稱為 UFLP (Uncapacitated facility location problem)。 ? 對 p 中值和 UFLP問題，每一個現(xiàn)有設(shè)施都可能與備選設(shè)施有物料運輸，使得總的運輸成本最小，目標(biāo)函數(shù)一般形式為 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 ? 1）直角距離（ Rectilinear Distance）計算方法 ? 直角距離指沿著相互成直角的路徑進(jìn)行測量得到的距離，即： （ ） （ ） ? 2）直線距離（ Euclidian Distance）計算方法 （ ） （ ） ? 如果使用絕對值對上述表達(dá)式進(jìn)行轉(zhuǎn)換，則多設(shè)施直線距離選址問題可以用線性規(guī)劃方法求解。如果考慮直線距離，由于求最小值的目標(biāo)函數(shù)是沿 x軸和 y軸連續(xù)不可微函數(shù)，所以求解過程困難得多。 ( , )j k j k j kd X X x x y y? ? ? ?( , )j i j i j id X P x a y b? ? ? ?22( , ) ( ) ( )j k j k j kd X X x x y y? ? ? ?( , ) ( ) ( )j i j i j id P x a y b? ? ? ?基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 ? 多設(shè)施選址問題的主要應(yīng)用之一是物流網(wǎng)絡(luò)規(guī)劃，或稱為供應(yīng)鏈設(shè)施選址。物流網(wǎng)絡(luò)規(guī)劃不僅僅是一個設(shè)施選址的問題，它的主要任務(wù)是確定產(chǎn)品從原材料起點到市場終點的整個流通渠道的結(jié)構(gòu)，包括物流設(shè)施的類型、數(shù)量與位置，設(shè)施所服務(wù)的顧客群體與產(chǎn)品類型，以及產(chǎn)品在設(shè)施之間的運輸方式。 ? 物流網(wǎng)絡(luò)規(guī)劃主要解決的問題是：倉庫數(shù)量、選址、所的權(quán)及規(guī)模；顧客需求在多個供應(yīng)點（倉庫或工廠）之間的分配；各地的庫存量、使用的運輸服務(wù)類型和顧客服務(wù)水平等。 ? 由于供應(yīng)商及顧客數(shù)量較大，倉庫和工廠可選地址太多、運輸方式選擇多等原因，設(shè)計最優(yōu)的物流網(wǎng)絡(luò)結(jié)構(gòu)是一個相當(dāng)復(fù)雜的任務(wù)。 ? 如果有足夠的信息，可以借助一些數(shù)學(xué)與計算機模型，如圖表模型、仿真模型、優(yōu)化模型、啟發(fā)式模型和專家系統(tǒng)模型來確定滿意的設(shè)計方案。 ? 對于多設(shè)施選址問題，如果還要確定每個新設(shè)施要為哪些客戶（現(xiàn)有設(shè)施）服務(wù)，這個問題就是選址 分配問題（ locationallocation problem, LAP） ? 物流網(wǎng)絡(luò)的進(jìn)一步發(fā)展就是供應(yīng)鏈決策，除了選址 分配決策之外，還包括容量、庫存、采購、生產(chǎn)、運輸方式和路徑規(guī)劃等決策問題，以及逆向物流、金融、風(fēng)險管理等。 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 145 覆蓋模型 ? 對于需求已知的一些需求點，如何確定一組服務(wù)設(shè)施來滿足這些需求點的需求。 ? 要確定服務(wù)設(shè)施的最小數(shù)量和合適的位置。 ? 適用于社會物流系統(tǒng)、公用事業(yè)系統(tǒng)和計算機與信息系統(tǒng)等，如零售點、加油站、配送中心、急救中心、消防站的選址，以及有線電視網(wǎng)的基站、無線通信基站、計算機網(wǎng)絡(luò)中的集線器設(shè)置等。 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 146 ? 集合覆蓋 模型：用最小數(shù)量的設(shè)施去所有的需求點 – 用最小數(shù)量的設(shè)施去覆蓋所有的需求點 ? 最大覆蓋 模型：在給定數(shù)量的設(shè)施下，覆蓋盡可能多的需求點 – 在給定數(shù)量的設(shè)施下，覆蓋盡可能多的需求點。 ? 應(yīng)用取決于服務(wù)設(shè)施的資源充足與否。 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 Set covering or max covering? ?最大覆蓋 ?集合覆蓋 基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 148 集合覆蓋模型 ? 集合覆蓋模型的目標(biāo)是用盡可能少的設(shè)施去覆蓋所有的需求點，目標(biāo)函數(shù) ?： ? cj為在結(jié)點設(shè)置一個設(shè)施時的固定成本， ? Ni為在結(jié)點可接受的最大服務(wù)距離 (時間 )S范圍內(nèi)設(shè)施結(jié)點 j的集合， Ni={ j | dij≤S} ??jjj xczMin????iNjj ix ,1 jxj ?? }1,0{基礎(chǔ)工業(yè)工程 設(shè)施規(guī)劃 149 ? 對此類帶有約束條件的極值問題，有兩大類方法可以進(jìn)行求解。 ? 一是應(yīng)用分枝定界求解的方法，能夠找到小規(guī)模問題的最優(yōu)解，由于運算量方面