第6章多設施選址問題

1、第第6章章 多設施選址問題多設施選址問題主要內容 一、概論 二、折線距離多設施MINISUM選址問題 三、最小費用流方法 四、平方歐幾里得距離多設施MINISUM選址問題 五、歐幾里得距離多設施MINISUM選址問題 六、選址-分配問題一、概論一、概論一、概論 例6.1 設p1=(5,25),p2=(25,15),p3=(10,0),p4=(0,10).新設施1和已有設施1、3、4有運輸關系，新設施2和已有設施2、3有運輸關系，歐幾里得距離多設施MINISUM選址問題的最優(yōu)解是多少？折線距離問題的最優(yōu)解是多少？一、概論 答：歐幾里得距離 X*1=(8.8388,5.7922) X*2=(9.1

2、645,5.6370) f(X*1, X*2)=59.7402 折線距離： X*1=X*2=(10,10) f(X*1, X*2)=70一、概論 設P1,一般距離（歐幾里得距離、折線距離、 Tchebychev距離）為： Tchebychev距離是：用表格表示多設施選址問題的數(shù)據(jù)圖論的相關概念 頂點鄰接：兩個頂點有一條邊連接 道路： 連通圖：若圖的兩頂點之間存在一條道路，則稱此兩頂點是連通的。若圖的任意兩頂點連通，則稱圖G是連通的；否則是非連通的。非連通圖可分解為若干連通子圖。根據(jù)圖論分解原問題 構建G(V,W)圖，看其是否為連圖，若為非連通圖，則原問題可分解為幾個單一設施選址問題。 在G(V

3、,W)圖中去掉所有的已有設施點和與之相關的連線，構建G(V)圖，看其是否為連圖，若為非連通圖，則原問題可分解為幾個單一設施選址問題。一、概論 例6.2 已有設施： 混凝土（10，20） 鋼材加工場（7，6） 發(fā)貨場（13，0） 待定位設施： 電桿澆鑄場(X1) 安裝儲存場(X2) 生產定額為每天40根。輸入數(shù)據(jù) 每天計劃銷售40根電線桿 需要的原材料：10立方碼混凝土，8400磅鋼材 已有設施的坐標： 混凝土（10，20） 鋼材加工場（7，6） 發(fā)貨場（13，0）陰影部分表示待定位設施不能放入該區(qū)域用表格表示該選址問題的數(shù)據(jù)二、折線距離多設施MINISUM選址問題二、折線距離多設施MINISU

4、M選址問題 用變量替換解此問題。設rji為xj在ai右邊的位移量，sji為xj在ai左邊的位移量，則有：引入變量：pjk,表示xj位于xk左邊的偏移量， pjk,表示xj位于xk左邊的偏移量，（6.10)被替換為一個線性規(guī)劃問題：二、折線距離多設施MINISUM選址問題 例6.3 設n=2,m=3, p1=(10,15), p2=(20,25), p3=(40,5), 數(shù)據(jù)見表6.2。建立線性規(guī)劃模型，求解：二、折線距離多設施MINISUM選址問題 最優(yōu)解為(x*,15),10 x*20,即X1和X2重合，且為10到20之間的任意值。 最優(yōu)值為160+60=220。二、折線距離多設施MINIS

5、UM選址問題 NF和EF點重合時，可選附近點。如令： X1=(19,15),X2=(21,15),得f(X1, X2)=222.二、折線距離多設施MINISUM選址問題 Intersection point property: 過所有已定位點畫水平線和垂直線得一些交點，則有：至少存在一個最優(yōu)解其中每一個新設施都落在某一交點上。二、折線距離多設施MINISUM選址問題坐標下降法:省略x1x2項，運用兩次中值條件，得(x1,x2)的解。固定X2，變化X1，運用中值條件得X1的解固定X1，變化X2，運用中值條件得X2的解再到第2步，往復循環(huán)，直到得到兩個相同的(x1,x2)的解，且X1，X2不相同。

6、如果X1，X2相同，則不能判斷(x1,x2)是否為最優(yōu)解，用列舉法判斷交點中哪個為最優(yōu)二、折線距離多設施MINISUM選址問題 下面用例說明坐標下降法。 例6.4 設p1=(0,2),p2=(4,0),p3=(6,8),p4=(10,4)。數(shù)據(jù)見表6.3.二、折線距離多設施MINISUM選址問題 省略6x1x2項，運用兩次中值條件，得(x1,x2)=(0,6),f1(0,6)=66.開始點就是(0,6)，固定X26，X1為變量，最小化： 得x1 =4， f1(4,6)=50，固定X14，X2為變量，最小化： 得x2 =6， f1(4,6)=50。因為第二次得到同一點(4,6)，算法停止。二、折

7、線距離多設施MINISUM選址問題 因為46，我們已最小化f1。再最小化f2,開始點為(2,8)， f2 (2,8) =66，固定Y28，變化Y1，最小化： 得y1=2, f2 (2,8) =66。固定Y12，變化Y2，最小化： 得y2 =4， f2 (2,4) =54。最小化：二、折線距離多設施MINISUM選址問題 得y1=2，再一次得f2 (2,4) =54，停止。 我們得到最優(yōu)解：X*1=(4,2)，X*2=(6,4)， 最優(yōu)值是50+54=104。二、折線距離多設施MINISUM選址問題 例6.5 設m=2, p1=(0,0),p2=(4,4),數(shù)據(jù)見表6.4。 我們有：二、折線距離

8、多設施MINISUM選址問題 開始點為(4,0)， f1(4,0)=88，最小化： 得x1=0,結果為（0，0），接下來最小化： 得x2=0, 結果為（0，0），f1(0,0)=24. 停止。但0=0，不能確定是否得到最優(yōu)解。 通過枚舉各交點的橫坐標組合，函數(shù)值f1(0,0)=24， f1(4,0)=88， f1(0,4)=52， f1(4,4)=36，得(0,0)是最優(yōu)解。二、折線距離多設施MINISUM選址問題 再最小化f2,開始點為(4,4)， f2 (4,4) =36，最小化： 得y1=4，最小化： 得y2=4，停止。但4=4，不能確定是否得到最優(yōu)解。 通過枚舉各交點函數(shù)值f2(0,0

9、)=24， f2(4,0)=88， f2(0,4)=52， f2(4,4)=36，得(0,0)是最優(yōu)解。二、折線距離多設施MINISUM選址問題練習：練習：工廠內部有五臺機器，位置分別為：P1=(8,20), P2=(10,10), P3=(16,30), P4=(30,10), P5=(40,20).有兩臺新的機器待安裝。工廠內部走折線距離。根據(jù)估計，兩臺新機器之間每天會有4趟往返的物料搬運。新機器和已有機器之間每天的往返物料搬運次數(shù)如下：求新機器的最優(yōu)放置位置。86543W23467三、最小費用網絡流方法 在x方向移動的總成本是： 采用變量替換得線性規(guī)劃：minimize三、最小費用流方法

10、 構造此線性規(guī)劃的對偶問題得一最小費用流問題。該問題構造方法如下：三、最小費用流方法5.n+1等于矩陣W中所有值的和。定義節(jié)點Nn+1為終點，需求為n+1,用有向弧連接節(jié)點Ei和Nn+1，容量為無窮大，費用為ai. 容易驗證：設n=2,m=3, p1=(10,15), p2=(20,25), p3=(40,5), 數(shù)據(jù)見表6.2。三、最小費用流方法三、最小費用流方法 設z*為最小費用流的最優(yōu)值，f1*為x方向的移動最小值，則有：三、最小費用流方法 采用對偶算法,設j為節(jié)點Nj的勢,計算： 則xj*為新設施j的最優(yōu)地址的x坐標。 要計算y坐標只需將上面的a替換成b,x換成y，f1換成f2。設z(

11、Nj,Nk)為(Nj,Nk)弧上的最優(yōu)流， z(Nj,Ei)為(Nj,Ei)弧上的最優(yōu)流，則互補松弛條件如下：現(xiàn)重新計算例6.3。設n=2,m=3, p1=(10,15), p2=(20,25), p3=(40,5), 數(shù)據(jù)見表6.2。三、最小費用流方法三、最小費用流方法 這里 a=106+201+405=280。網絡構造見圖6.4。容易驗證：z*=1012=120,而a=280，所以： f1*=280-120=160,此為在x方向移動的最小費用。 上述算法可采用表格形式。三、最小費用流方法 由互補松弛條件知x1*=x2*=x*,所以 由中值條件知10 x*20. 第二種方法: 由互補松弛條件

12、得10 x1*=x2*20,同樣可得10 x*20。可直接計算得到f1(x1*,x2*)=160. 第三種方法：用最小費用流算出各節(jié)點N1、N2、N3的標號分別為0,0,-10,由(6.13)式得：x1*=0-(-10)=10, x2*= 0-(-10)=10.三、最小費用流方法 下面計算y值。 考慮y方向，如何作出網絡圖？三、最小費用流方法 由圖6.4可得最小費用為50+30=80。如何得出？ 所以，在y方向移動的總費用為140-80=60。140是什么的值？三、最小費用流方法 由互補松弛條件得： y1*=b1=15.，y1*=y2*. 檢驗計算得：f2(15,15)=60. 結果正確。 還

13、可用最小費用流算出各節(jié)點N1、N2、N3的標號分別為0,0,-15,由(6.13)式得：y1*=0-(-15)=15, y2*= 0-(-15)=10.四、平方歐幾里得距離多設施MINISUM選址問題 把 (6.6)式各項分別用下面項代替： 得平方歐幾里得距離多設施MINISUM選址問題f2(X1, ,Xn).它是嚴格凸函數(shù)，令各項偏導數(shù)為零得最優(yōu)解。關于NF t的項為：由于由于Vtj=Vjt,進而得到：進而得到：求偏導：令偏導等于零： 定義矩陣A，它的第t行的各項(除了第t項,即對角線上的元素)為-1乘以V的第t行，第t項等于V的第t行的和加上W的第t行的和。則對所有t都有： 所以，偏導數(shù)等

14、于零等同于下面的線性方程： 用此式解例6.1數(shù)據(jù)問題如下：用表格表示多設施選址問題的數(shù)據(jù)525100a得到：得到：把把A, Wa, Wb放在一起得到（放在一起得到（A|Wa|Wb），然后），然后進行矩陣變換得到：進行矩陣變換得到：得到：得到：五、歐幾里得距離多設施MINISUM選址問題 把 (6.6)式各項分別用下面項代替： 得歐幾里得距離多設施MINISUM選址問題HAP。定義下面的式子：則：則：迭代過程：迭代過程：Weiszfeld算法： 求得初始解的坐標 作為候選點坐標 求下一組候選點的坐標 比較前后兩個候選點橫坐標，若折線距離在允許的精度范圍內，則結束計算。否則，轉到上一步。(0)(0

15、)(0)12(,.,)nXXX(1)(1)(1)12(,.,)nXXX六、選址-分配問題 如果各新設施的類型都相同，同樣，所有已定位設施類型都相同，且每一新設施都可服務任一已定位設施，則權重和新設施的地址一樣是決策變量。這類問題稱為選址-分配問題。六、選址-分配問題例6.7 設新設施1至7的坐標分別為(0,5),(8,5),(5,4),(2,2,),(3,2),(0,0),和(7,0)，要求每個已定位設施由離它最近的新設施提供服務，使各設施間折線距離最小化。該問題有兩方面要求：一是新設施選址；二是分配新設施給已定位設施。用啟發(fā)式算法解此問題。過程見圖6.7。六、選址-分配問題用啟發(fā)式算法解此問

16、題：給定新設施的坐標把已有設施分配給最近的新設施。對2步確定的分配，變動新設施坐標(把新設施坐標作為自變量)，使新設施和分配給該設施的已有設施之間的距離最小。如果得到的新設施坐標變化，則回到步驟2，否則回到步驟1。重復步驟1至4直到沒有總的新設施到已有設施距離的減少為止。過程見圖6.7。給定新設施坐標：X1(0,5); X2=(2,2). 分配結果為：A1(P1,P2); A2=(P3,P4,P5,P6,P7)距離為：T18；T217保持分配結果不變：A1(P1,P2); A2=(P3,P4,P5,P6,P7)變動新設施坐標：X1(0,5); X2=(3,2). 距離為：T18；T216變動后

17、新設施坐標：X1(0,5); X2=(3,2). 變動前新設施坐標：X1(0,5); X2=(2,2). 因為X1坐標沒變，所以重新給X1賦值(3,5)分配結果為：A1(P1,P2,P3); A2=(P4,P5,P6,P7)距離為：T111；T212保持分配結果不變：A1(P1,P2,P3); A2=(P4,P5,P6,P7)變動新設施坐標：X1(5,5); X2=(3,2). 距離為：T19；T212六、選址-分配問題 實際上，初始點的選取對最終結果影響很大。如果令X1=(2,2),X2=(7,4),A1=P1,P4,P5,P6, A2=P2,P3,P7,則T1=9,T2=8,T=17。 所

18、以要嘗試多個不同的初始點。六、選址-分配問題 淺海鉆井平臺問題：平臺平臺油井油井油井油井油井油井六、選址-分配問題 淺海鉆井平臺問題： 鉆探和完成成本與鉆探角度和鉆探長度有關 平臺成本：25萬至1000萬美元。與平臺所在地的水深和分配到該平臺的井的數(shù)目有關 目的是確定平臺的數(shù)目，大小和井到平臺的分配，以最小化總成本。六、選址-分配問題 淺海鉆井平臺問題：目標函數(shù):最小化平臺的建設成本，和鉆探成本約束1：每個油井只分配到一個平臺上約束2：每個平臺分配的油井數(shù)目一定六、選址-分配問題 其中：平臺與油井之間的水平距離：六、選址-分配問題用alternative-location-allocation(ALA)啟發(fā)式算法解此問題：給定新設施的坐標把已有設施分配給最近的新設施。對1步確定的分配，變動新設施坐標，使新設施和分配給該設施的已有設施之間的距離最小。如果得