應(yīng)急設(shè)施的優(yōu)化選址

1、1 實(shí)驗(yàn)案例1.1.1 案例：應(yīng)急設(shè)施的優(yōu)化選址 1.1.1.1 問題分析2.1.1.2 問題假設(shè)2.1.1.3 模型建立與求解 3.1.1.4 更進(jìn)一步結(jié)果分析 41.1.5 模型求解的Matlab程序 .51實(shí)驗(yàn)案例問題側(cè)重于線性規(guī)劃和非線性規(guī)劃方面的優(yōu)化問題。從這里的建模實(shí)例可以建立數(shù)學(xué)模型是最為關(guān)鍵和困難的一步， 當(dāng)看到這里建立起來的模型后，你會頓然覺得問題變得如此簡單。因 此，從這些實(shí)例中希望大家能夠掌握建模方法， 也不妨模仿這里的方 法以應(yīng)用到實(shí)際建模中去。1.1 案例：應(yīng)急設(shè)施的優(yōu)化選址問題(AMCM-86B )里奧蘭翹鎮(zhèn)迄今還沒有自己的應(yīng)急設(shè)施。 1986年該鎮(zhèn)得到了建立兩個應(yīng)

2、急設(shè)施的撥款，每個設(shè)施都把救護(hù)戰(zhàn)、 消防隊(duì)和警察所合在一起。圖(1)指出了 1985年每個長方形街區(qū)發(fā) 生應(yīng)急事件的次數(shù)。在北邊的 L形狀的區(qū)域是一個障礙，而在南邊 的長方形區(qū)域是一個右淺水池塘的公園。 應(yīng)急車輛駛過一條南北方向 的街道平均要花15秒，而通過一條東西向的街道平均花 20秒。你的 任務(wù)是確定這兩個應(yīng)急設(shè)施的位置，使得總響應(yīng)時間最少。52215032422333341304433340001204322013325321033N圖(1) 1985年里奧蘭翹鎮(zhèn)每個長方街區(qū)應(yīng)急事件的數(shù)目1.1.1 問題分析應(yīng)急設(shè)施的位置應(yīng)急發(fā)生位置應(yīng)急車運(yùn)行情況總相應(yīng)時間應(yīng)急設(shè)施到底修在每個街區(qū)的街角

3、處還是可以在街道的任何地方？對這個可以進(jìn)行假設(shè)，適當(dāng)簡化處理。先解決應(yīng)急設(shè)施在街角處 的情形。對于應(yīng)急設(shè)施可以在街道任何地方時，實(shí)際上可以證明：應(yīng) 急設(shè)施應(yīng)設(shè)在街角處，才能使總響應(yīng)時間最少。先在一定的假設(shè)條件 下，簡化問題，先解決簡單情形，再處理復(fù)雜情形。下面主要介紹窮舉法在求解這個問題的應(yīng)用。1.1.2 問題假設(shè)(1)假設(shè)需求集中在每個街區(qū)的中心(2)假設(shè)應(yīng)急設(shè)施位于街角處(3)圖中給出的1985年應(yīng)急次數(shù)有典型性，能夠反映該街區(qū)應(yīng) 急事件出現(xiàn)的概率的大?。?4)應(yīng)急車輛的響應(yīng)時間只考慮在街道上行駛時間，其他因素(如轉(zhuǎn)彎)可以忽略不計。(5)兩個應(yīng)急設(shè)施的功能完全相同。當(dāng)應(yīng)急事件出現(xiàn)時，只要

4、 從離事件發(fā)生地點(diǎn)最近的應(yīng)急設(shè)施派出應(yīng)急車輛即可。(6)執(zhí)行任何一次應(yīng)急任務(wù)的車輛都從某一個應(yīng)急設(shè)施出發(fā)， 完成任務(wù)后回到原設(shè)施。不出現(xiàn)從一個應(yīng)急事件點(diǎn)直接到另一個應(yīng)急 事件發(fā)生點(diǎn)的情況(這是由于每個地點(diǎn)發(fā)生事件的概率都很小，因此兩個地點(diǎn)同時發(fā)生事故的概率就更小，因此可以忽略這種情況。)1.1.3模型建立與求解根據(jù)假設(shè)2,每個應(yīng)急設(shè)施選在街角處，可能的位置至多有6X11=66個，則兩個應(yīng)急設(shè)施的組合就至多有 C266=66X65/2=2145個， 因此可以考慮用窮舉法進(jìn)行求解，即一一計算出每個選址方案的總響 應(yīng)時間，然后從中選出具有最小總響應(yīng)時間的方案。建立直角坐標(biāo)系，以該鎮(zhèn)西北角街角為原點(diǎn)(

5、即圖的左下角)，從北到南方向?yàn)閄軸正向，從西到東為 Y軸正向，并分別以南北、 東西方向上的一個街區(qū)長度作為單位長，則街角的坐標(biāo)(x,y)滿足如下條件：0WxW 10,0 WyW5,x,y 均為整數(shù)。0<x<10,0< y <5, x, y均為整數(shù)。而每個街區(qū)中心的坐標(biāo)可定義為(i +0.5, j +0.5),其中i, j滿足如 下條件：0 < i < 9,0 < j < 4 , i, j均為整數(shù)。如何計算應(yīng)急設(shè)施在點(diǎn)(x, y)處到以(i+0.5, j+0.5)點(diǎn)為街區(qū)中心的行駛時間t(x,y,i,j)?當(dāng)不考慮障礙合池塘的影響時，行駛時間為：如

6、何計算應(yīng)急設(shè)施在點(diǎn)(x,y)處到以(i+0.5,j+0.5)點(diǎn)為街區(qū)中心的行駛時間t(x,y,i,j)?當(dāng)不考慮障礙合池塘的影響時，行駛時間為：t(x,y,i,j)=15(|x-i-0.5|-0.5) + 20(|y-j-0.5|-0.5)=15|x-i-0.5| + 20|y-j-0.5|-17.5t(x, y,i, j) = 15(| x-i -0.5| -0.5) 20(| y- j - 0.5| -0.5)= 15|x-(i 0.5) 1201y -(j 0.5) |-17.5單位：秒記p(i, j)為以(i+0.5, j十0.5)為中心的街區(qū)的事故發(fā)生頻率。如果應(yīng)急設(shè)施設(shè)在(x1,y

7、)(x2,y2)兩點(diǎn),則總響應(yīng)時間為：記p(i,j)為以(i+0.5,j+0.5)為中心的街區(qū)的事故發(fā)生頻率。如果應(yīng)急設(shè)施設(shè)在(xi,yi),(x2,y2)兩點(diǎn),則總響應(yīng)時間為：94T(x,y,x2,y2) = " ' p(i, j)mint(K,y,i, j),t(x2,y2,i, j) i =0 j =0以上模型求解不難用計算機(jī)編程實(shí)現(xiàn)。運(yùn)用MATLAB編程得到如下結(jié)果為最優(yōu)：兩個應(yīng)急設(shè)施應(yīng)設(shè)在點(diǎn)(2, 2), (6, 2)處。以上結(jié)論是在沒有考慮障礙區(qū)域和池塘的影響的前提下得到的最優(yōu)解，實(shí)際上即使考慮這兩個影響，從這兩個點(diǎn)到任何街區(qū)都可以 避開L形障礙區(qū)域和池塘，所求的

8、這兩點(diǎn)就是最優(yōu)選址。1.1.4 更進(jìn)一步結(jié)果分析選址地點(diǎn)多余2個呢?1.1.5 模型求解的Matlab 程序以上模型求解的Matlab 程序如下：function mymain%應(yīng)急設(shè)施的優(yōu)化選址程序p=.5 2 2 1 5 0 3 2 4 2;2 3 33 34 13 04;4 3 30 34 00 00;1 2 00 43 22 01;3 3 25 32 10 33'%計算頻數(shù)p=p/sum(sum(p)optvalue=inf;% 初始化為無窮大for x1=0:10,for y1=0:5,for x2=0:10,for y2=0:5,% 計算每個方案的總響應(yīng)時間curvalue=0;%當(dāng)前方案的總響應(yīng)時間初始化for i=0:9,for j=0:4,curvalue=curvalue + p(i+1,j+1)* min(caltime(x1,y1,i,j),caltime(x2,y2,i,j);endendif curvalue<optvalue, goodidea=x1 y1 x2 y2; optvalue=curvalue;endendendendend%顯