4第17講應急設施的優(yōu)化選址問題要點

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

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

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

4、標(X, y) 是滿足條件0 X 10,0 y 5的整數(shù)。而每個街區(qū)中心的坐標具有形式 (i + 0.5, j + 0.5)，其中i,j是滿足條件：0 i 9,0 j 4的整數(shù)。如果不考慮障礙和水 塘的影響，同應急車輛從設在(X,y)點的應急設施到以(i + 0.5, j + 0.5)為中心的街區(qū)的 行駛時間等于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ū)所標的數(shù) 字)。如果應急設施設在(X , Y),(X , Y )這兩點，總不妨設X 匕，設施從A遷到C點。（Pd Pc 的情況同理）。為了便于比較遷移前后的總響應時間的變化情況，我們先作下面兩個假 設（其中所說的“舊”是指設施遷移前的情況，而“新”則是指遷移后的情況）：（1）應急設施從A搬透到C后，兩個舊的責任區(qū)匕，匕先仍分別由C和B負責救助， 暫不改變。如果在這樣不改變責任區(qū)的情況下都能證明總響應時間不增加，則再進一步 合理調(diào)整C、B的責任區(qū)還可能進一步縮短（至少不會增加）總響應時間，更加說明搬 遷方案的優(yōu)越。（2）搬遷后

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、的方案就不是最優(yōu)了。我們證明：當x豐X時一定 021是這樣。先設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)?？紤]將設施從舊位置 (x, y)移動到新位置(x +1, y)，則p(x)就是舊設施北面的事故總數(shù)，P - p(x +1)就是新 設施南面的事故總數(shù)。既然p(x) X +1 的情形，貝V p(X) P/2 p(X +1) p(x -1) P/2 P - p(x)， 將設施從(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)南面的事故多，將設施從(x, y)(即(X +1, y)向北移到(x, y)可以引 起優(yōu)化。這就在p( X) P/2的情況，同理可以證明同樣的結(jié)論。同理還可證明：當y u Y時(x,y)也一 定不是最優(yōu)，結(jié)果只剩下(X, Y)才有可能最優(yōu)，因而也就確實是最優(yōu)。現(xiàn)在回到原題條件，考慮設兩個應急設施的情形，假如按前面所說的算法2,指定 了兩個點氣,8作為應急設施的候選位置，這一組位置是否已經(jīng)最優(yōu)了？如果不是，有 什么方法較快地改進它，而不要一

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

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

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

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

30、大的南、 北兩塊（各含25個街區(qū)）U 1，V1，這樣做的理由是：可以使每塊內(nèi)部點與點之間的最遠 程不會太長，有利于降低總響應時間。分別計算這兩塊的頻率函數(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)點1的坐標為（2,3）。同理可算出南塊的最優(yōu)點為q（7,3）。再劃分A ,B的責任區(qū)；橫坐標為4的四個街區(qū)的中心離

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