第6章多設(shè)施選址問(wèn)題

1、第第6章章 多設(shè)施選址問(wèn)題多設(shè)施選址問(wèn)題主要內(nèi)容 一、概論 二、折線距離多設(shè)施MINISUM選址問(wèn)題 三、最小費(fèi)用流方法 四、平方歐幾里得距離多設(shè)施MINISUM選址問(wèn)題 五、歐幾里得距離多設(shè)施MINISUM選址問(wèn)題 六、選址-分配問(wèn)題一、概論一、概論一、概論 例6.1 設(shè)p1=(5,25),p2=(25,15),p3=(10,0),p4=(0,10).新設(shè)施1和已有設(shè)施1、3、4有運(yùn)輸關(guān)系，新設(shè)施2和已有設(shè)施2、3有運(yùn)輸關(guān)系，歐幾里得距離多設(shè)施MINISUM選址問(wèn)題的最優(yōu)解是多少？折線距離問(wèn)題的最優(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一、概論 設(shè)P1,一般距離（歐幾里得距離、折線距離、 Tchebychev距離）為： Tchebychev距離是：用表格表示多設(shè)施選址問(wèn)題的數(shù)據(jù)圖論的相關(guān)概念 頂點(diǎn)鄰接：兩個(gè)頂點(diǎn)有一條邊連接 道路： 連通圖：若圖的兩頂點(diǎn)之間存在一條道路，則稱(chēng)此兩頂點(diǎn)是連通的。若圖的任意兩頂點(diǎn)連通，則稱(chēng)圖G是連通的；否則是非連通的。非連通圖可分解為若干連通子圖。根據(jù)圖論分解原問(wèn)題 構(gòu)建G(V,W)圖，看其是否為連圖，若為非連通圖，則原問(wèn)題可分解為幾個(gè)單一設(shè)施選址問(wèn)題。 在G(V

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

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

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

6、如果X1，X2相同，則不能判斷(x1,x2)是否為最優(yōu)解，用列舉法判斷交點(diǎn)中哪個(gè)為最優(yōu)二、折線距離多設(shè)施MINISUM選址問(wèn)題 下面用例說(shuō)明坐標(biāo)下降法。 例6.4 設(shè)p1=(0,2),p2=(4,0),p3=(6,8),p4=(10,4)。數(shù)據(jù)見(jiàn)表6.3.二、折線距離多設(shè)施MINISUM選址問(wèn)題 省略6x1x2項(xiàng)，運(yùn)用兩次中值條件，得(x1,x2)=(0,6),f1(0,6)=66.開(kāi)始點(diǎn)就是(0,6)，固定X26，X1為變量，最小化： 得x1 =4， f1(4,6)=50，固定X14，X2為變量，最小化： 得x2 =6， f1(4,6)=50。因?yàn)榈诙蔚玫酵稽c(diǎn)(4,6)，算法停止。二、折

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

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

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

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

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

12、得10 x1*=x2*20,同樣可得10 x*20?？芍苯佑?jì)算得到f1(x1*,x2*)=160. 第三種方法：用最小費(fèi)用流算出各節(jié)點(diǎn)N1、N2、N3的標(biāo)號(hào)分別為0,0,-10,由(6.13)式得：x1*=0-(-10)=10, x2*= 0-(-10)=10.三、最小費(fèi)用流方法 下面計(jì)算y值。 考慮y方向，如何作出網(wǎng)絡(luò)圖？三、最小費(fèi)用流方法 由圖6.4可得最小費(fèi)用為50+30=80。如何得出？ 所以，在y方向移動(dòng)的總費(fèi)用為140-80=60。140是什么的值？三、最小費(fèi)用流方法 由互補(bǔ)松弛條件得： y1*=b1=15.，y1*=y2*. 檢驗(yàn)計(jì)算得：f2(15,15)=60. 結(jié)果正確。 還

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

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

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

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

17、新設(shè)施坐標(biāo)：X1(0,5); X2=(3,2). 變動(dòng)前新設(shè)施坐標(biāo)：X1(0,5); X2=(2,2). 因?yàn)閄1坐標(biāo)沒(méi)變，所以重新給X1賦值(3,5)分配結(jié)果為：A1(P1,P2,P3); A2=(P4,P5,P6,P7)距離為：T111；T212保持分配結(jié)果不變：A1(P1,P2,P3); A2=(P4,P5,P6,P7)變動(dòng)新設(shè)施坐標(biāo)：X1(5,5); X2=(3,2). 距離為：T19；T212六、選址-分配問(wèn)題 實(shí)際上，初始點(diǎn)的選取對(duì)最終結(jié)果影響很大。如果令X1=(2,2),X2=(7,4),A1=P1,P4,P5,P6, A2=P2,P3,P7,則T1=9,T2=8,T=17。 所

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