4第17講應(yīng)急設(shè)施的優(yōu)化選址問(wèn)題要點(diǎn)

1、第17講應(yīng)急設(shè)施的優(yōu)化選址問(wèn)題問(wèn)題（AMCM-86B題）里奧蘭翹鎮(zhèn)迄今還沒(méi)有自己的應(yīng)急設(shè)施。1986年該鎮(zhèn)得到 了建立兩個(gè)應(yīng)急設(shè)施的撥款，每個(gè)設(shè)施都把救護(hù)站、消防隊(duì)和警察所合在一起。圖17-1 指出了 1985年每個(gè)長(zhǎng)方形街區(qū)發(fā)生應(yīng)急事件的次數(shù)。在北邊的L形狀的區(qū)域是一個(gè)障 礙，而在南邊的長(zhǎng)方形區(qū)域是一個(gè)有淺水池塘的公園。應(yīng)急車輛駛過(guò)一條南北向的街道 平均要花15秒，而通過(guò)一條東西向的街道平均花20秒。你的任務(wù)是確定這兩個(gè)應(yīng)急設(shè) 施的位置，使得總響應(yīng)時(shí)間最少。圖17-1 1985年里奧蘭翹每個(gè)長(zhǎng)方街區(qū)應(yīng)急事件的數(shù)目（I）假定需求集中在每個(gè)街區(qū)的中心，而應(yīng)急設(shè)施位于街角處。（II）假定需求是沿包

2、圍每個(gè)街區(qū)的街道上平均分布的，而應(yīng)急設(shè)施可位于街道的 任何地方。1若干假設(shè)1、圖17-1所標(biāo)出的1985年每個(gè)長(zhǎng)方形街區(qū)應(yīng)急事件的次數(shù)具有典型代表性，能 夠反映該街區(qū)應(yīng)急事件出現(xiàn)的概率的大小。2、應(yīng)急車輛的響應(yīng)時(shí)間只考慮在街道上行駛時(shí)間，其他因紗（如轉(zhuǎn)彎時(shí)間等）可 以忽略不計(jì)。3、兩個(gè)應(yīng)急設(shè)施的功能完全相同。在應(yīng)急事件出現(xiàn)時(shí)，只要從離事件發(fā)生地點(diǎn)最 近的應(yīng)急設(shè)施派出應(yīng)急車輛即可。4、執(zhí)行任何一次應(yīng)急任務(wù)的車輛都從某一個(gè)應(yīng)急設(shè)施出發(fā)，完成任務(wù)后回到原設(shè) 施。不出現(xiàn)從一個(gè)應(yīng)急事件點(diǎn)直接到另一事件點(diǎn)的情況。（這是因?yàn)?，每一個(gè)地點(diǎn)發(fā)生 事件的概率都很小，兩個(gè)地點(diǎn)同時(shí)發(fā)生事故的概率就更是小得可以忽略不計(jì)

3、）。2假定(I)下的模在假定(I)下，應(yīng)急需求集中在每個(gè)街區(qū)中心。我們可以進(jìn)一步假定應(yīng)急車輛只 要到達(dá)該街區(qū)四個(gè)街角中最近的一個(gè)，就認(rèn)為到達(dá)了該街區(qū)，可以開(kāi)始工作了。按假定 (I)，每個(gè)應(yīng)急設(shè)施選在街角處，可能的位置只有6x11=66個(gè)。兩個(gè)應(yīng)急設(shè)施的位置的 可能的組合至多只有66x65/2=2145個(gè)。這個(gè)數(shù)目對(duì)計(jì)算機(jī)來(lái)說(shuō)并不大，可用計(jì)算機(jī)進(jìn) 行窮舉，對(duì)每種組合一一算出所對(duì)應(yīng)的總響應(yīng)時(shí)間，依次比較得出最小的響應(yīng)時(shí)間及對(duì) 應(yīng)的選址方案。具體算法是：建立直角坐標(biāo)系，以該鎮(zhèn)的西北角為原點(diǎn)，從北到南為X -軸正方向，從西到東為y- 軸正方向，在南北、東西方向上分別以一個(gè)街區(qū)的長(zhǎng)作為單位長(zhǎng)，則街角的坐

4、標(biāo)(X, y) 是滿足條件0 X 10,0 y 5的整數(shù)。而每個(gè)街區(qū)中心的坐標(biāo)具有形式 (i + 0.5, j + 0.5)，其中i,j是滿足條件：0 i 9,0 j 4的整數(shù)。如果不考慮障礙和水 塘的影響，同應(yīng)急車輛從設(shè)在(X,y)點(diǎn)的應(yīng)急設(shè)施到以(i + 0.5, j + 0.5)為中心的街區(qū)的 行駛時(shí)間等于t(X, y, i, j) = 15(1 X - i - 0.5| - 0.5) + 20(y - j - 0.5| - 0.5)=15(1 X - (i + 0.5)| + 20|y - (j + 0.5)| -17.5) 秒 TOC o 1-5 h z 記p(i, j)為以(i +

5、 0.5, j + 0.5)為中心的街區(qū)的事故發(fā)生頻率(即在圖上該街區(qū)所標(biāo)的數(shù) 字)。如果應(yīng)急設(shè)施設(shè)在(X , Y),(X , Y )這兩點(diǎn)，總不妨設(shè)X 匕，設(shè)施從A遷到C點(diǎn)。（Pd Pc 的情況同理）。為了便于比較遷移前后的總響應(yīng)時(shí)間的變化情況，我們先作下面兩個(gè)假 設(shè)（其中所說(shuō)的“舊”是指設(shè)施遷移前的情況，而“新”則是指遷移后的情況）：（1）應(yīng)急設(shè)施從A搬透到C后，兩個(gè)舊的責(zé)任區(qū)匕，匕先仍分別由C和B負(fù)責(zé)救助， 暫不改變。如果在這樣不改變責(zé)任區(qū)的情況下都能證明總響應(yīng)時(shí)間不增加，則再進(jìn)一步 合理調(diào)整C、B的責(zé)任區(qū)還可能進(jìn)一步縮短（至少不會(huì)增加）總響應(yīng)時(shí)間，更加說(shuō)明搬 遷方案的優(yōu)越。（2）搬遷后

6、從新設(shè)施C到舊區(qū)域Uc中的任何一點(diǎn)P的救助路線為：從C出發(fā)離開(kāi) CD，沿原先A的的舊的救助路線到P。從C到舊區(qū)域Ud的任何一點(diǎn)P的救助路線為： 從C出發(fā)沿CD （經(jīng)過(guò)A）到D，再沿原先A的舊的救助路線到P。設(shè)應(yīng)急車輛從A到C的行駛時(shí)間為T(mén)。則按（2）的行駛路線，Uc的點(diǎn)到設(shè)施的路 程都減少了 AC，行駛時(shí)間減少T，總響應(yīng)時(shí)間減少PT U的點(diǎn)則相反，路程都增加 AC，行駛時(shí)間都增加T，總響應(yīng)時(shí)間增加PT。由于P P ,P TPT，總響應(yīng)時(shí)間 DC D C D減少量超過(guò)（或等于）增加量，總的效果是減少了（或不改變）總響應(yīng)時(shí)間，設(shè)施搬遷 后的位置比原來(lái)更優(yōu)，至少同樣優(yōu)。假設(shè)（2）的路線不一定是最短路

7、線。如果再進(jìn)一步選擇最短路線，則還有可能進(jìn) 一步縮短新設(shè)施方案的總響應(yīng)時(shí)間，更加說(shuō)明其優(yōu)越性，假設(shè)（1）的責(zé)任區(qū)的貢分不 一定是合理的，可以再進(jìn)行調(diào)整，將街道上的每一點(diǎn)劃給離它最近的設(shè)施的責(zé)任區(qū)，這 樣又可能再減少新設(shè)施方案的總響應(yīng)時(shí)間，再一次增加它的優(yōu)越程度，這樣就證明了新 設(shè)施比舊設(shè)施更優(yōu)，或同樣優(yōu)。因此，在假定（II）下，仍可設(shè)應(yīng)急設(shè)施設(shè)在街角處。于是與假定（I）的情況類似 地可用計(jì)算機(jī)窮舉算出答案來(lái)，對(duì)任一對(duì)候選的應(yīng)急設(shè)施位置A（X ,Y ）,B（X ,Y ），（坐1122標(biāo)為整數(shù)），求出每一條街道CD的總響應(yīng)時(shí)間，將所有街道的總響應(yīng)時(shí)間相加就得到這 一選址方案的總響應(yīng)時(shí)間。進(jìn)行比較就

8、可得出最短的總響應(yīng)時(shí)間及對(duì)應(yīng)的選址方案。CD 的總響應(yīng)時(shí)間的計(jì)算方法已在前面講過(guò)。并且由于設(shè)施都設(shè)在街角處，只要將CD分成 兩個(gè)責(zé)任段（在多數(shù)情形下實(shí)際上只有一個(gè)責(zé)任段）CE,ED，將這兩個(gè)責(zé)任段的事故 頻率分別集中在它們各自的中點(diǎn)計(jì)算就可以了。計(jì)算結(jié)果：應(yīng)急設(shè)施以設(shè)在點(diǎn)（2,3）,（7,3）時(shí)最優(yōu)。在假定（II）之下本題還有一種更簡(jiǎn)單一些的近似算法。按照這個(gè)算法，假定（II） 和假定（I）下得出同樣的答案。我們將假定（I）和假定（II）進(jìn)行比較。首先，既然 已經(jīng)證明在假定（II）下應(yīng)急設(shè)施仍應(yīng)設(shè)在街角處，這就與假定（1）相同了，只是對(duì)每 一對(duì)候選位置A、B計(jì)算總響應(yīng)時(shí)間時(shí)的算法不同。我們考慮

9、每一個(gè)街區(qū)和它周圍的四 條街道在兩種不同假設(shè)下算出的總響應(yīng)時(shí)間有何不同。注意大部分街道都是街區(qū)的分界 線，屬于兩個(gè)街區(qū)共同所有，分擔(dān)兩個(gè)街區(qū)的事故頻率。但我們可以把這樣的街道順著 街道方向剖開(kāi)成為兩部分（左半部分和右半部分），認(rèn)為每半部分各只屬于一個(gè)街區(qū)， 只承擔(dān)這一個(gè)街區(qū)的事故發(fā)生頻率，不用再將兩個(gè)相鄰街區(qū)的頻率相加。求出所有這些 “半邊街道”的總響應(yīng)時(shí)間之和，也就是整個(gè)城鎮(zhèn)的總響應(yīng)時(shí)間了?，F(xiàn)在我們來(lái)看在假 設(shè)（II）下圍成每個(gè)街區(qū)的四條邊（“半邊街道”）的總響應(yīng)時(shí)間。如果這四條邊處在同 一個(gè)責(zé)任區(qū)中，我們稱這個(gè)街區(qū)為非邊界街區(qū)。在計(jì)算非邊界街區(qū)的四條邊的總響應(yīng)時(shí) 間時(shí)把它們所分擔(dān)的事故頻率

10、各自集中在它們的中點(diǎn)。相對(duì)的兩條邊分擔(dān)的事故頻率相 等，在求它們的響應(yīng)時(shí)間之和時(shí)可以用這兩條邊各自的中點(diǎn)到應(yīng)急設(shè)施的行駛時(shí)間的平 均值T乘上它們的事故頻率之和（即每一個(gè)的事故頻率的兩倍）來(lái)計(jì)算。但這個(gè)平均值 T就是街區(qū)中心到應(yīng)急設(shè)施的行駛時(shí)間，（想象有穿過(guò)街區(qū)中心的東西方向南北方向的 道路供行駛）。因此，可以把相對(duì)兩邊的事故頻率集中在街區(qū)的中心，從而把整個(gè)街區(qū) 的事故頻率集中到街區(qū)中心。設(shè)這個(gè)街區(qū)的中心M的坐標(biāo)為（i + 0.5, j + 0.5）， （0 i 9,0 j 4是整數(shù)），而這個(gè)街區(qū)所屬的應(yīng)急設(shè)施A的坐標(biāo)為（X, K），則這個(gè)街區(qū) 周圍的四條街道到A的平均行駛時(shí)間就等于15|X -

11、 （i + 0.5）| + 20|Y - （j + 0.5）|秒（2）將這一結(jié)果與假定（1）下從A（X,Y）到這個(gè)街區(qū)救助的行駛時(shí)間t（X,Y,i, j）（見(jiàn)前面（1） 式）相比，只相差一個(gè)常數(shù)17.5秒。換句話說(shuō)，按假定（1）只要求應(yīng)急車輛到達(dá)街區(qū) 的最近的一個(gè)街角，而現(xiàn)在相當(dāng)于要求車輛繼續(xù)行駛到街區(qū)的中心（假定存在著可供車 輛行駛的穿過(guò)該中心的東西、南北兩條道路）。如果在假定（1）下也改為要求車輛行駛 到街區(qū)中心，則每一種選址方案的總響應(yīng)時(shí)間增加一個(gè)常數(shù)，最短的總響應(yīng)時(shí)間也就增 加一個(gè)常數(shù)，而方案的優(yōu)劣不會(huì)因此改變，原來(lái)的最優(yōu)方案仍然最優(yōu)。但這樣一來(lái)在兩 個(gè)假定下對(duì)非邊界街區(qū)的總響應(yīng)時(shí)間的

12、計(jì)算方法就完全相同了。唯一有區(qū)別的地方是被 責(zé)任區(qū)分界線一分為二的街區(qū)。在假定（I）下是按該街區(qū)中心所在責(zé)任區(qū)將它整個(gè)劃 歸這個(gè)責(zé)任區(qū)。按假定（II）則將街區(qū)分成兩部分，分別屬于兩個(gè)責(zé)任區(qū)，這樣可使這 個(gè)街區(qū)的總響應(yīng)時(shí)間比按假定（I）略小一些。在假定（II）下，如果在計(jì)算時(shí)對(duì)所有的 街區(qū)也按街區(qū)中心的歸屬將這個(gè)街區(qū)全部劃入一個(gè)責(zé)任區(qū)，這樣算出來(lái)的就是近似的總 響應(yīng)時(shí)間，而按這樣的算法得出的最優(yōu)解就是近似的最優(yōu)。而這個(gè)近似的最優(yōu)解必定就 是假定（I）下的最優(yōu)解（2，3）（6，3），無(wú)須重新計(jì)算。在假定（II）下精確計(jì)算這 個(gè)方案的總響應(yīng)時(shí)間，與前面用計(jì)算機(jī)求出的真正的最優(yōu)方案（2, 3），（7,

13、 3）相比較， 只相差1秒鐘?？紤]到原始數(shù)據(jù)（街區(qū)的事故次數(shù)）本身并不能百分之百的代表今后的 事故頻率，1秒鐘的誤差應(yīng)該說(shuō)是在允許范圍，并不能說(shuō)明用近似算出的解就一定不是 最優(yōu)，在實(shí)際中完全可以當(dāng)最優(yōu)解來(lái)用。更何況，即使在假定（II）下，如果采用方案（2,3），（6,3），則每個(gè)街區(qū)都整個(gè)的在一個(gè)責(zé)任區(qū)中，沒(méi)有哪個(gè)街區(qū)被分割開(kāi)來(lái)分別劃 進(jìn)兩個(gè)責(zé)任區(qū)；而方案（2,3），（7,3）卻將5個(gè)街區(qū)分割開(kāi)了，這給應(yīng)急設(shè)施進(jìn)行救助帶 來(lái)不方便，權(quán)衡利弊，我們得出下面的結(jié)論：按假定（II），方案（2,3），（7,3）比方案（2,3），（6,3）的總響應(yīng)時(shí)間約少1秒鐘， （分別為5121.4秒、5122.5秒

14、）。但考慮到實(shí)施救助的方便起見(jiàn)，寧肯采用方案（2,3），（6,3）。3算法的進(jìn)一步討論以上算法是建立在用計(jì)算機(jī)進(jìn)行窮舉的基礎(chǔ)上，可以稱為：算法1計(jì)算機(jī)窮舉法。窮舉的方法當(dāng)然可以說(shuō)是笨辦法，它對(duì)一些明顯不優(yōu)的位置仍要一個(gè)個(gè)去驗(yàn)證，這 實(shí)在顯得太笨。但窮舉的辦法也有一個(gè)好處，那就是：不用再證明最后答案的最優(yōu)性。 這個(gè)答案已經(jīng)和所有的別的可能方案都比較過(guò)了，比它們都優(yōu)，最優(yōu)性已經(jīng)得到證明。 本題的一個(gè)特點(diǎn)是需要窮舉的可能方案的數(shù)目不大，用計(jì)算機(jī)進(jìn)行窮舉所花的時(shí)間很 少，因而是可行的，也是優(yōu)越的。但假如考慮更一般的城市，街道數(shù)目較多，且應(yīng)急設(shè) 施的個(gè)數(shù)也可能不止兩個(gè)，而是更多，則計(jì)算機(jī)所花時(shí)間將會(huì)大大

15、增加。能不能有一種 非窮舉的有效算法呢？可以考慮采用如下的方法。算法2逐次改進(jìn)法：它的基本想法是先從一個(gè)初始的方案（不一定最優(yōu)）出發(fā)， 逐步加以改進(jìn)，直到得到一個(gè)不能再改進(jìn)的方案，就有可能是最優(yōu)方案，具體作法是：先任選兩個(gè)位置（坐標(biāo)為整數(shù)的點(diǎn)）氣,8。作為應(yīng)急設(shè)施A,B的最初的選址。比如 可選A （0,0）,B （10,5），即選這個(gè)城鎮(zhèn)的西北角、東南角分別作為A ,B。（當(dāng)然也可一開(kāi) 0000始憑直覺(jué)將A。,B0選得更好一些，更快地達(dá)到最后結(jié)果）。試考慮將設(shè)施A向東、西、南 或北四個(gè)方向各移動(dòng)一個(gè)街區(qū)（即將A的橫坐標(biāo)或縱坐標(biāo)增加或減少一個(gè)單位），B暫 時(shí)不動(dòng)，看總響應(yīng)時(shí)間如何變化。（當(dāng)然，如

16、果在某個(gè)方向上已經(jīng)不可能移動(dòng)，即已經(jīng) 處于城鎮(zhèn)的邊界，就不考慮這一方向上的移動(dòng)）。如果向某一方向上的移動(dòng)引起總響應(yīng) 時(shí)間的增加（或不變），這一方向不是好方向，再換另一個(gè)方向試試。如果向某一方向 的移動(dòng)引起總響應(yīng)時(shí)間的減少，這一方向就是好方向，將A向這一方向移動(dòng)一個(gè)街區(qū)（從 A0移到A，以A,B的新位置作為出發(fā)點(diǎn)重新向各個(gè)方向試探。如果A向四個(gè)方向的移 動(dòng)都不能縮短總響應(yīng)時(shí)間，則將A固定不動(dòng)，再試B的移動(dòng)，直到B向四個(gè)方向上的移 動(dòng)都不能縮短總響應(yīng)時(shí)間，再考慮A的移動(dòng)。這樣將A,B兩個(gè)設(shè)施輪流移動(dòng)以優(yōu)化方案， 直到不能再優(yōu)化為止：即A,B中任何一個(gè)向任何方向的移動(dòng)都不能使總響應(yīng)時(shí)間再縮 短。這時(shí)

17、這個(gè)優(yōu)化過(guò)程就收斂了，我們可以認(rèn)為找到了最優(yōu)方案。如果從我們剛才所說(shuō) 的兩點(diǎn)（0,0），（10,5）出發(fā)，采用假定 的算法，進(jìn)行逐次改進(jìn)，最后就收斂于（2,3），（6.3）這兩點(diǎn)，已經(jīng)知道它確實(shí)是最優(yōu)方案。能否證明：從任意兩點(diǎn)出發(fā)都收斂于最優(yōu)方案？從數(shù)學(xué)理論上講，這樣的逐次改進(jìn) 的方法達(dá)到的是“極好值點(diǎn)”，而不一定是“最好值點(diǎn)”。即：將總響應(yīng)時(shí)間廣作為兩個(gè) 應(yīng)急設(shè)施位置的四個(gè)坐標(biāo)x ,y,x ,y的函數(shù)，用逐次改進(jìn)法所得到的是函數(shù)的極小值1122點(diǎn)，但不一定是最小值點(diǎn)。如果能證明這個(gè)函數(shù)只有一個(gè)極小值點(diǎn)，它也就是最小值點(diǎn)。 但這一般是不成立的，即使成立也是很難證明的。比如本題。如果從（4,0）

18、，（4,5）這 兩點(diǎn)出發(fā)，就會(huì)發(fā)現(xiàn)最后收斂于（4,1），（5,4）這兩個(gè)位置，不是最優(yōu)方案。（按假定（I） 的算法，方案（4,1），（5,4）的總響應(yīng)時(shí)間為3355秒，而方案（2,3），（6,3）和（4,1），（5.4）。由于選擇的初始位置不同，逐次改進(jìn)后分別收斂于這兩組位置。初始的兩個(gè)點(diǎn) 的橫坐標(biāo)比較接近的，容易收斂于后一組解。反之一般收斂于前一組解。對(duì)本題來(lái)說(shuō)， 由于城鎮(zhèn)的形狀是東西方向窄，南北方向?qū)?，從直觀上講，一開(kāi)始選的兩個(gè)點(diǎn)應(yīng)該一個(gè) 偏北，另一個(gè)偏南，這樣才使每個(gè)責(zé)任區(qū)中相距最遠(yuǎn)的點(diǎn)的距離都不大，總響應(yīng)時(shí)間才 不會(huì)太大。如果選的兩個(gè)位置呈東西方向排列（即械坐標(biāo)很接近），如上面所說(shuō)的（

19、4,0），（4.5）兩點(diǎn)，則兩個(gè)責(zé)任區(qū)都是南北方向上的長(zhǎng)條，責(zé)任區(qū)西北端的點(diǎn)和東南端的點(diǎn)相 距很遠(yuǎn)，總響應(yīng)時(shí)間顯然不會(huì)小，因而一開(kāi)始就是不合理的，收斂過(guò)程也就容易誤入歧 途。由此可見(jiàn)，上述的逐次改進(jìn)法在理論上是不完善的，但在實(shí)用上卻是可行的，只要 最初的兩個(gè)位置不是選的太不合理，實(shí)際上仍能得出最優(yōu)解。當(dāng)然也可以從不同的初始 位置出發(fā)多試幾次，如果經(jīng)過(guò)收斂得到若干個(gè)不同的解，再通過(guò)比較從這些解中選出一 個(gè)最優(yōu)的就行了。不過(guò)，就本題來(lái)說(shuō)，計(jì)算機(jī)窮舉法計(jì)算量本來(lái)就不大，在理論上又沒(méi) 有漏洞。逐次改進(jìn)法雖然可以提高一些速度，但仍然不能用手工計(jì)算，反而帶來(lái)理論上 的缺陷，似乎還是得不償失，不如計(jì)算機(jī)窮舉

20、法來(lái)得干凈利落。4最優(yōu)解滿足的條件上述的逐次改進(jìn)法，試圖改進(jìn)計(jì)算機(jī)窮舉發(fā)不管好壞一概窮舉的“窮舉”之處，但 它自己也同樣笨拙：一開(kāi)始的初始位置隨便亂選，也是不管好壞；試探的時(shí)候不管怎樣 只走一步，而不敢向好的方向大踏步的改進(jìn)。能不能將它再改進(jìn)一下，使得能比較容易 判斷方案？為此，先來(lái)考察一下最優(yōu)解到底應(yīng)該滿足什么樣的條件，即使不能得出充分 條件，哪怕得出一些操作方便的必要條件也行。說(shuō)起來(lái)也簡(jiǎn)單，最優(yōu)滿足的必要充分的條件是：用任何方法都不能將它改進(jìn)。當(dāng)然， “任何方法”是難以操作的；誰(shuí)也不好擔(dān)保他所找到的方法已經(jīng)窮盡了所有的方法。但 是，如果找到一種方法將它改進(jìn)，就足以說(shuō)明它不是最優(yōu)。因此，最優(yōu)

21、解滿足的必要條 件：用你所找到的方法不能將它改進(jìn)，這一條件比較操作，前提是必須盡量找到一些方 法，使得用你的方法不能改進(jìn)的解很少。下面就給出一個(gè)這樣的方法。先將問(wèn)題簡(jiǎn)化，改為：只設(shè)一個(gè)應(yīng)急設(shè)施。此是存在非窮舉的有效算法如下。這個(gè) 方法有些類似于求質(zhì)點(diǎn)系統(tǒng)的力學(xué)重心(但只是類似而并不完全相同)，為敘述方便， 不妨稱為“重心法”。設(shè)應(yīng)急設(shè)施的最優(yōu)位置在A點(diǎn)，其坐標(biāo)為(X, K)。我們的基本想法是：如果A點(diǎn)北 面(即橫坐標(biāo)X)的街區(qū)的事故發(fā)生的頻率懸殊很大， 則將設(shè)施向事故較多的那個(gè)方向移動(dòng)就可以減少總響應(yīng)時(shí)間，從而將方案改進(jìn)。因此， 最優(yōu)位置A應(yīng)使得它的北面和南面發(fā)生事故的頻率盡可能相等，換句話說(shuō)

22、，北面發(fā)生的 事故應(yīng)當(dāng)盡可能接近整個(gè)城鎮(zhèn)事故總數(shù)的一半。同理，它的東面和西面的事故頻率也應(yīng) 該盡可能相等，西面發(fā)生的事故應(yīng)盡可能接近事故總數(shù)的一半。為此，對(duì)橫坐標(biāo)0 x 10的每個(gè)整數(shù)值定義x-事故頻率函數(shù)p(x)，它等于所有滿 足條件， 1時(shí)p(x) - p(x -1)就是橫 坐標(biāo)等于x的5個(gè)街區(qū)的事故頻率之和。因此p(x) - p(x-1) 0。而且，這本題的數(shù)據(jù) 而言，p(x) - p(x -1) 0對(duì)=1，2,9,10成立，p(x)是嚴(yán)格單調(diào)遞增函數(shù)。P = p(10)就 是整個(gè)城鎮(zhèn)的事故頻率總和，本題中P = 109。按照上面的說(shuō)法，最優(yōu)解4(X,K)的橫坐 標(biāo)X應(yīng)使|p(X)-P/

23、2|最小。這樣的X最多只有兩個(gè)(分別大于和小于P/2 )。就本題 的數(shù)據(jù)而言，計(jì)算得：i = 0 -10 時(shí) p(i)依次為 0,15,28,38,47,65,78,85,92,99,109。p(4) = 47最接近P/2 = 54.5，故X = 4。同樣，對(duì)縱坐標(biāo)0 y 5的每個(gè)整數(shù)值定 義q (y)為滿足條件j H，則移動(dòng)設(shè)施的總效果是總響應(yīng)時(shí)間減少，方案優(yōu)化，原 方案不優(yōu)。如果設(shè)U的事故總頻率為p，則按照原來(lái)的假設(shè)，U (由U，V組成)中的事 00201故頻率p + p大于U中的事故頻率p。如果p + p比p大得太多，以至于從p + p中 201120120減去p后所得的p仍大于p，原來(lái)

24、的方案就不是最優(yōu)了。我們證明：當(dāng)x豐X時(shí)一定 021是這樣。先設(shè)p(X) P/2。(比如本題p(4) = 47 54.5，就是這樣。)如果x X，則 x +1 X,p(x) p(x +1) p(X) P/2, p(x) P/ 2 P 一 p(x +1)?？紤]將設(shè)施從舊位置 (x, y)移動(dòng)到新位置(x +1, y)，則p(x)就是舊設(shè)施北面的事故總數(shù)，P - p(x +1)就是新 設(shè)施南面的事故總數(shù)。既然p(x) X +1 的情形，貝V p(X) P/2 p(X +1) p(x -1) P/2 P - p(x)， 將設(shè)施從(x, y)移到(x -1, y)可以優(yōu)化。除x X +1外，xu X的

25、唯一可能是 x = X +1,p(X) P/2 P/2 - p (X ).P (X) P - p (x +1)，即(x, y)北面 的事故比(X +1, y)南面的事故多，將設(shè)施從(x, y)(即(X +1, y)向北移到(x, y)可以引 起優(yōu)化。這就在p( X) P/2的情況，同理可以證明同樣的結(jié)論。同理還可證明：當(dāng)y u Y時(shí)(x,y)也一 定不是最優(yōu)，結(jié)果只剩下(X, Y)才有可能最優(yōu)，因而也就確實(shí)是最優(yōu)?，F(xiàn)在回到原題條件，考慮設(shè)兩個(gè)應(yīng)急設(shè)施的情形，假如按前面所說(shuō)的算法2,指定 了兩個(gè)點(diǎn)氣,8作為應(yīng)急設(shè)施的候選位置，這一組位置是否已經(jīng)最優(yōu)了？如果不是，有 什么方法較快地改進(jìn)它，而不要一

26、步一步地試探著前進(jìn)？我們可以先按設(shè)施的兩個(gè)候選 位置氣,氣劃定它們的責(zé)任區(qū)匕0,匕。的范圍，將每個(gè)街區(qū)(按假定(I)或街道上的每 個(gè)點(diǎn)(按假定(II)劃給離它最近的設(shè)施的責(zé)任區(qū)。到兩個(gè)設(shè)施的路程相等的，任意劃 給一個(gè)責(zé)任區(qū)。然后，在每個(gè)責(zé)任區(qū)內(nèi)可以按前述的“重心法”各找到一個(gè)的最佳位置 A ,B。用A ,B分別取代A ,B，即使在不調(diào)整責(zé)任區(qū)的情形下已經(jīng)能夠說(shuō)明方案被優(yōu)111100化了。如果A ,B的位置與A ,B不完全相同，責(zé)任區(qū)也可能發(fā)生變化。按設(shè)施的新位置 1100A、B1重新劃定責(zé)任區(qū)。在兩個(gè)新的責(zé)任區(qū)范圍內(nèi)再一次用“重心法”各選一個(gè)新位置。 這樣，調(diào)整責(zé)任區(qū)范圍和在每個(gè)責(zé)任區(qū)內(nèi)尋找最

27、優(yōu)位置交替進(jìn)行，每進(jìn)行一次都使方案 得到優(yōu)化。這個(gè)過(guò)程必定收斂(因?yàn)榉桨覆荒軣o(wú)窮地優(yōu)化下去)，即設(shè)施位置及責(zé)任區(qū) 范圍都不能再改變。這就達(dá)到了這個(gè)方法所能找到的最優(yōu)方案。以上方法可以作為算法3,仍稱為“重心法”(因?yàn)樗窃趦蓚€(gè)責(zé)任區(qū)內(nèi)分別用重心 法求最優(yōu)位置)。而且，在實(shí)際計(jì)算時(shí)，可以顛倒一下順序：第一步不先選兩點(diǎn)位置， 而先按某種方案將所有街區(qū)劃分成兩個(gè)區(qū)域，作為最初的責(zé)任區(qū)，要在責(zé)任區(qū)內(nèi)分別用 重心法求出兩個(gè)點(diǎn)。重心法通常都比算法2的一步一步改進(jìn)要快，很快就可收斂到一組不能再改進(jìn)的方 案，收斂后是否就得到了最優(yōu)解？與算法2的情形類似，仍然不能肯定，很可能與一開(kāi) 始劃定責(zé)任區(qū)范圍的方式有關(guān)。

28、使用重心法時(shí)，還應(yīng)當(dāng)考慮到這樣的情況：如果不改變責(zé)任區(qū)，AB1在各自的責(zé) 任區(qū)內(nèi)當(dāng)然是最優(yōu)位置，一移動(dòng)就會(huì)使總響應(yīng)時(shí)間增加，設(shè)增加量為，1。但如果移動(dòng)后 引起責(zé)任區(qū)改變，則調(diào)整責(zé)任區(qū)可再使總響應(yīng)時(shí)間減少某個(gè)12，假如移動(dòng)的方式選得適 當(dāng)，使七 ，則方案仍然獲得改進(jìn)。這說(shuō)明，在用重心法達(dá)到收斂后，還應(yīng)該用算法 2再試探一下，看是否還有改進(jìn)的余地。不過(guò)，不需要具體計(jì)算出總響應(yīng)時(shí)間，只要考 察總響應(yīng)時(shí)間的增減情況就行了。由于試探時(shí)設(shè)施只移動(dòng)一步（一個(gè)街區(qū)的長(zhǎng)度），引 起的責(zé)任區(qū)改變只有半步，t 一般都很小，實(shí)際上很難使t t，要使t比t更小，將22112責(zé)任區(qū)內(nèi)已經(jīng)達(dá)到最優(yōu)位置（X, Y）的點(diǎn)的坐標(biāo)

29、X （或Y）變動(dòng)為X 土 1 （或Y 土 1）時(shí)應(yīng) 盡量使頻率函數(shù)值p （X 土 1）（或q （Y 土 1）仍很接近P/2，這里p是該責(zé)任區(qū)內(nèi)的事故 頻率總數(shù)。但要 p（X） - P/2與（X 土 1） - P/2 （或 q（Y） - P/2與q（Y 土 1） - P/2）都很接 1111近于0，只有它們符號(hào)相反時(shí)才有可能。也就是說(shuō)：只考慮（X, Y）向事故多的方向上的 移動(dòng)。下面用重心法來(lái)計(jì)算本題的最優(yōu)解。由于收斂速度很快，可以用手算實(shí)現(xiàn)，只要第 一步的責(zé)任區(qū)劃分得不是太不合理，求出的也的確是最優(yōu)解。先在假定（I）下計(jì)算：考慮到城鎮(zhèn)是長(zhǎng)方形，很自然先用沿東西方向的直線x = 5將城鎮(zhèn)分成同樣

30、大的南、 北兩塊（各含25個(gè)街區(qū)）U 1，V1，這樣做的理由是：可以使每塊內(nèi)部點(diǎn)與點(diǎn)之間的最遠(yuǎn) 程不會(huì)太長(zhǎng)，有利于降低總響應(yīng)時(shí)間。分別計(jì)算這兩塊的頻率函數(shù)得：北塊：x-頻率函數(shù)值：0,15,28,38,47,65； y -頻率函數(shù)值；0,16,23,36,50,65。南塊：x-頻率函數(shù)值：0,13,20,27,34,44； y -頻率函數(shù)值：0,9,17,21,33,44。北塊：x-頻率函數(shù)值最接近65/2=32.5的是28，y -頻率函數(shù)值最接近65/2=32.5 的是36。最優(yōu)點(diǎn)1的坐標(biāo)為（2,3）。同理可算出南塊的最優(yōu)點(diǎn)為q（7,3）。再劃分A ,B的責(zé)任區(qū)；橫坐標(biāo)為4的四個(gè)街區(qū)的中心離

31、A ,B的路程相等，劃給A11111或B都可以。如果劃給A，則就是原來(lái)的責(zé)任區(qū)方案U ,V，設(shè)施位置不能再優(yōu)化?？?1111慮將它們劃給，則新的責(zé)任區(qū)U2,V分別由北面的20個(gè)街區(qū)（橫坐標(biāo) 3的）和南面 的30個(gè)街區(qū)（橫坐標(biāo) 4的）組成。對(duì)這兩塊重新選最優(yōu)點(diǎn)。U2的最優(yōu)點(diǎn)仍是A1（2,3）.V2 的最優(yōu)點(diǎn)變成B2 （6,3）。A ,B的責(zé)任區(qū)仍只能分為U ,V，各自的最優(yōu)點(diǎn)當(dāng)然還是A ,B，已不能再優(yōu)化，122212將它們作為最終答案。（與算法1的結(jié)果比較知它們確實(shí)是最優(yōu)）。再在假定（II）下計(jì)算：第一步：仍先平均分成南、弱兩個(gè)相等的區(qū)域U ,V，最優(yōu)點(diǎn)仍分別為A （2,3）,B （7,3）1111第二步：A1,B1的責(zé)任區(qū)的邊界為直線x = 4.5，它將橫坐標(biāo)為4的5個(gè)街區(qū)都沿東 西方向剖為兩半，各屬于一個(gè)責(zé)任區(qū)，這些街區(qū)的事故頻率總和18也被這兩半所平分， 各占9。仍將A的責(zé)任區(qū)記為U ,B的責(zé)任區(qū)記為V。則U的x-頻率函數(shù)值為 121220,15,28,38,4