【正文】 基礎工業(yè)工程 設施規(guī)劃 Set covering or max covering? ?最大覆蓋 ?集合覆蓋 基礎工業(yè)工程 設施規(guī)劃 148 集合覆蓋模型 ? 集合覆蓋模型的目標是用盡可能少的設施去覆蓋所有的需求點，目標函數(shù) ?： ? cj為在結(jié)點設置一個設施時的固定成本， ? Ni為在結(jié)點可接受的最大服務距離 (時間 )S范圍內(nèi)設施結(jié)點 j的集合， Ni={ j | dij≤S} ??jjj xczMin????iNjj ix ,1 jxj ?? }1,0{基礎工業(yè)工程 設施規(guī)劃 149 ? 對此類帶有約束條件的極值問題，有兩大類方法可以進行求解。 基礎工業(yè)工程 設施規(guī)劃 146 ? 集合覆蓋 模型：用最小數(shù)量的設施去所有的需求點 – 用最小數(shù)量的設施去覆蓋所有的需求點 ? 最大覆蓋 模型：在給定數(shù)量的設施下，覆蓋盡可能多的需求點 – 在給定數(shù)量的設施下，覆蓋盡可能多的需求點。 ? 要確定服務設施的最小數(shù)量和合適的位置。 ? 對于多設施選址問題，如果還要確定每個新設施要為哪些客戶（現(xiàn)有設施）服務，這個問題就是選址 分配問題（ locationallocation problem, LAP） ? 物流網(wǎng)絡的進一步發(fā)展就是供應鏈決策，除了選址 分配決策之外，還包括容量、庫存、采購、生產(chǎn)、運輸方式和路徑規(guī)劃等決策問題，以及逆向物流、金融、風險管理等。 ? 由于供應商及顧客數(shù)量較大，倉庫和工廠可選地址太多、運輸方式選擇多等原因，設計最優(yōu)的物流網(wǎng)絡結(jié)構是一個相當復雜的任務。物流網(wǎng)絡規(guī)劃不僅僅是一個設施選址的問題，它的主要任務是確定產(chǎn)品從原材料起點到市場終點的整個流通渠道的結(jié)構，包括物流設施的類型、數(shù)量與位置，設施所服務的顧客群體與產(chǎn)品類型，以及產(chǎn)品在設施之間的運輸方式。如果考慮直線距離，由于求最小值的目標函數(shù)是沿 x軸和 y軸連續(xù)不可微函數(shù)，所以求解過程困難得多。 ? 另一假設是備選點容量無限，稱為 UFLP (Uncapacitated facility location problem)。 ? 運輸模型法已有成熟的解法，如表上作業(yè)法或用 Lindo、Excel等軟件求解。對于復合選址問題，即一家公司設有多個工廠供應多個銷售點，當產(chǎn)量不足時，需要增建工廠，一般已知數(shù)個待選廠址方案，要求確定一個廠址，使已有設施的生產(chǎn)運輸費用最小。 基礎工業(yè)工程 設施規(guī)劃 139 某汽車廠設施網(wǎng)絡 ?配送中心 B ?配送中心 N ?配送中心 A ?43S/4S店 1 ?3S/4S店 2 ?3S/4S店 N … … … … … … … … … … … … … … ?產(chǎn)品調(diào)撥 ?產(chǎn)品調(diào)撥 ?采購、部品處 ?（零部件物流） ?營業(yè)部（整車物流） ?財務處（結(jié)算中心） ?整車庫房 ?部品庫房 ?整車工廠 ?整車入庫 ?原料供應商 A ?原料供應商 B ?原料、部品供應商 N ?原料供應商 C … … … ?原料、部品采集 ?部品車間 ?部品入庫 基礎工業(yè)工程 設施規(guī)劃 140 運輸模型法 ? 如果幾個備選方案的各種影響因素的作用程度差不多，可以不予考慮的話，此時費用就成為唯一的決策因素，線性規(guī)劃方法成為處理這類選址決策的理想工具。 ? 多設施選址和物流網(wǎng)絡問題成為大中型制造企業(yè) 、銷售企業(yè) 、 物流企業(yè)需要考慮的問題 ， 包括多工廠 、 多倉庫 、 多配送中心等設施網(wǎng)絡的選址問題 。選擇“ Results”菜單的“ Show Location in Graph”即可得到右上所示的圖形結(jié)果。在“ Distance Measure”（距離度量）中選擇“ Rectilinear Distance”（直角距離）。 ? 基礎工業(yè)工程 設施規(guī)劃 WinQSB求解 ? (3) 選擇“ Solve and Analysis”菜單的“ Solve the Problem”命令（或直接單擊工具欄最右邊的“ Run and Solve the Problem”按鈕），彈出如圖左所示的“ Facility Location Solution”對話框。完成后單擊 OK。下圖用直角折線繪出了新址與現(xiàn)有設施地址之間的直線距離。同樣 y 的最優(yōu)解在 y* =b4=4 得到（見表 2）。 ? 對現(xiàn)有設施的 x 坐標進行排序，順序為 1, 2, 4, 5, 8, 相應的權值順序為 5, 2, 4, 6, 8, 權值和為 25。每天在新設備與現(xiàn)有設備之間的搬運行程數(shù)分別為 5， 6，2， 4， 8?，F(xiàn)有設備分別位于 P1=(1, 1)， P2=(5, 2)， P3=(2, 8)，P4=(4, 4)， P5=(8, 6)。 ??? mi ii PXdwXfMin 1 ),()(基礎工業(yè)工程 設施規(guī)劃 133 直角距離單設施選址問題 ? X =(x, y) 新設施的位置 ? Pi =(ai, bi) 現(xiàn)有設施 i 的位置， i=1, 2, …, m ? wi 在新設施和現(xiàn)有設施 i 之間物料運輸“權值”（單位成本） ? d (X, Pi) 新設施和現(xiàn)有設施 i 之間的距離 ? 假設新設施和現(xiàn)有設施 i 之間的年運輸成本與點 X 和 Pi 之間的距離成正比， wi 為比例常數(shù)。 ? 例如在物流網(wǎng)絡中，配送中心居于重要的樞紐地位，它的選址問題十分重要，常用定量的分析模型，如重心法、鮑姆爾 沃爾夫法、覆蓋模型、混合整數(shù)規(guī)劃法等，以充分考慮物流網(wǎng)絡中各個環(huán)節(jié)的費用，在一定的物流報務水平下，根據(jù)不同的模型和算法求出物流總成本最低的最優(yōu)解或滿意解，以獲得選址方案。 基礎工業(yè)工程 設施規(guī)劃 132 單設施選址問題與模型 ? 最早探討選址問題是韋伯 1909年提出的單一倉庫選址如何使得到達多個顧客的總距離最短問題，這種問題后來被歸結(jié)為 p中值問題 （韋伯問題）。 ? 流程距離（ Flow path distance），指沿著兩點之間實際穿越的路線進行測量得到的距離，也稱為契巴雪夫距離（Chebychev distance）。 ? 直線距離（ Euclidean distance，也稱為歐氏距離），指沿著兩點之間的直線進行測量得到的距離。它也稱為曼哈頓距離，由來是因為曼哈頓的許多街道不是垂直的就是平行的。例如，倉庫與所服務的顧客之間的選址與分配問題，去掉一個倉庫不僅增加了顧客的距離，還要將這些顧客到其他倉庫。 ? 可變權重 。 基礎工業(yè)工程 設施規(guī)劃 ? 固定權重 。 ? 如果在點 5和 6之間再增加 1000個點，最優(yōu)中心選址的位置同樣不會改變。這種目標通常在軍隊、緊急情況和公共部門中使用，也稱作“經(jīng)濟平衡性” (Economic Equity)，問題也叫做網(wǎng)絡上的 中心問題 。 m in ( )()jXjjCXXjC X j X??????????? 新 的 待 定 位 設 施 物 體 的 坐 標已 存 在 且 位 置 固 定 的 物 體 的 標 號對 于 已 經(jīng) 存 在 的 物 體 ， 新 物 體 定 位 在 時 的 成 本基礎工業(yè)工程 設施規(guī)劃 Minisum/Minimax ? Minimax目標由已存在設施的單個成本最大的組分組成。這種目標通常在企業(yè)問題中應用，所以被叫做“經(jīng)濟效率性” (Economic Efficiency)。這種問題的目標由已有設施中成本最小的個體組成，目的是使最壞的情況最優(yōu)化，結(jié)果常被稱為“反中心”，在緊急情況和公用設施選址中使用。中心是指選址位置到最左邊和最右邊的距離是相等的，中心選址由那些極端位置決定的，其他內(nèi)部點的位置對它沒有影響。這種問題的目標是考慮新設施和其他現(xiàn)有設施之間最大距離的下限。這是尋求新設施和其他現(xiàn)有設施之間的加權距離總和最小，也稱為權距和最小選址問題，或網(wǎng)絡上的中值問題，中值是指左邊和右邊有同樣多的點。離散選址更便于定量分析，常用于詳細選址（定址），各候選點的實際距離可以在目標函數(shù)和約束條件中應用。 ? 網(wǎng)格選址 的待選區(qū)域也是平面，但被分為等方塊的網(wǎng)格，例如倉庫中標準儲位的分配。 基礎工業(yè)工程 設施規(guī)劃 二、按選址目標區(qū)域的特征分類 ? 連續(xù)選址 的待選址區(qū)域是平面，不考慮其他因素，理論上的選址位置數(shù)量是無限的。 ? 如果需求點的體積不能忽略不計，而是一個區(qū)域時，為簡化問題，可以選求出這些區(qū)域的重心，然后以這些重心代表對應區(qū)域，就可以當作點選址。大多數(shù)選址問題和算法都是這種情況，如重心法 – 線選址 是一維的選址問題，如沿通道布置設備。 ? 在分析選址問題、建立模型之前，需要弄清楚這幾個基本問題： – (1) 選址的對象是什么？ – (2) 選址的目標區(qū)域是怎樣的？ – (3) 選址的目標和成本函數(shù)是什么？ – (4) 有什么樣的約束？ 基礎工業(yè)工程 設施規(guī)劃 選址問題分類的基礎 ? 一、按選址對象的特征和數(shù)量分類 ? 按設施的維數(shù)，通?？紤]的是點選址、線選址和面選址。在工廠、倉庫等的選址中，選取最佳位置后可能還需要確定設施的服務范圍，并分配顧客。 – 當然，這里說的是一般情況，如果你經(jīng)營的非常好或非常差，在老顧客中造成了很大的聲譽差距，情況就會發(fā)生變化。若想生意做得好，必須從顧客的心理去考慮。下表列出了服務設施和生產(chǎn)設施選址的對比。 ? 管理水平 1. 企業(yè)經(jīng)營策略 ? 服務部門在所規(guī)劃地區(qū)的服務和形象的兼容性。 – 麥當勞與肯德基： “ 不是臉對臉，就是肩并肩 ” 服務企業(yè) —— 目標客戶群所在區(qū)域存在競爭對手 第 1章 緒論 115 ?服務設施選址的因素和方法 服務設施選址過程主要考慮 業(yè)務和收入 的決定因素，而影響服務部門業(yè)務量和收入大小的主要有以下幾個因素： ? 該地區(qū)的競爭強度 ? 企業(yè)的獨特性及競爭對手的選址 ? 該地區(qū)及其鄰近地區(qū)商業(yè)和設施的質(zhì)量。在這種情況下，可能會形成 “ 聚集效應 ” ，即受聚集在某地的幾個公司所吸引而來的顧客總數(shù)，大于分布在不同地方的這幾個公司的顧客總數(shù)。 ? 服務業(yè)企業(yè)在進行設施選址時不僅必須考慮競爭者的現(xiàn)有位置，還需要估計他們對新選設施地址的反應。 ? 那些需要與顧客直接接觸的服務企業(yè)，其服務質(zhì)量的提高有賴于對最終市場的接近與分散程度，因此服務設施必須靠近顧客群。 ? 制造業(yè)選址著重 成本最小 化，服務業(yè)選址著重 收入最大化 。試用線性規(guī)劃 運輸法選擇一個最佳廠址。 基礎工業(yè)工程 設施規(guī)劃 工 廠 倉 庫 能 力 U V W 虛擬倉庫 A 10 24 36 0 2800 B 20 16 14 0 2023 Y 40 30 8 0 2400 需 求 2200 1400 2600 1000 2200 1400 200 2400 600 400 基礎工業(yè)工程 設施規(guī)劃 作業(yè)： 某企業(yè)通過兩家工廠 F1和 F2向 A、 B、 C、 D四個售貨點供貨。現(xiàn)有兩個備選廠址 X和 Y，位于不同城市，基本條件如下，請做出選擇。 基礎工業(yè)工程 設施規(guī)劃 [例 ] 某彩電公司有兩個工廠 A和 B,三個倉庫 U、 V、 W，分別位于不同的城市。運輸模型法的分析目標是在給定有限原料位置點的供給和特定的需求要求后，尋找出在最低可能運輸成本下滿足所有的需要。 ? 線性規(guī)劃方法是一種廣泛使用的最優(yōu)化技巧，它在考慮特定的約束條件下，從許多可用的選擇中挑選出最佳方案。 j=1,2,… ,n), 又假設產(chǎn)銷平衡 , 即 問如何安排運輸可使總運費最小 ? ?????njjmii ba11基礎工業(yè)工程 設施規(guī)劃 運輸問題的模型 Xij:從 Ai到 Bj的運量 . Z:總運輸費用 . ?????????????????????? ???? ?),...,2,1。 ? 例如 ， 一家生產(chǎn)工業(yè)清潔劑的公司向全國 2023個縣銷售產(chǎn)品 ， 使用 80個倉庫 ， 全國有 5家生產(chǎn)廠 ， 問可能的工廠－倉庫－客戶物流方案 ？ ? 例 倉庫選址問題包括： ?需設置的倉庫數(shù)量 、 規(guī)模及位置； ?各個倉庫負責供應哪些客戶 ， 接收哪些工廠和供應商的貨物； ?各個倉庫的產(chǎn)品庫存配置或直接運輸?shù)?。實際重心可能為高山、湖泊等不可用地址，計算中距離為直線距離，不符合實際情況；且考慮運輸費率后很繁瑣，但運輸費率數(shù)據(jù)往往是估算的。 基礎工業(yè)