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

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

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

4、。而每個街區中心的坐標具有形式(i0.5,j0.5),其中i,j是滿足條件：0i9,0j4的整數。如果不考慮障礙和水塘的影響，同應急車輛從設在(X,Y)點的應急設施到以(i0.5,j0.5)為中心的街區的行駛時間等于t(X,Y,i,j)15(Xi0.50.5)20(Yj0.50.5)15(X(i0.5)20Y(j0.5)17.5)秒記p(i,j)為以(i0.5,j0.5)為中心的街區的事故發生頻率(即在圖上該街區所標的數字)。如果應急設施設在(Xi，Yi),(X2，Y2)這兩點，總不妨設XiX2,則該設置方案的總響應時間為T(Xi,Yi,X2,Y2)p(i,j)mint(X1,Y1,i,j),

5、t(X2,Y2,i,j)i0j0讓Xi取遍010,X2取遍Xi10,丫1,丫2分別獨立地取遍04。依次對四數組(Xi,Yi,X2,Y2)的每一個值算出對應的總響應時間的最小值及對應的四數組。以上算法不難用計算機編程實現。由于數組的個數不算多(只有兩千多個)，計算機可很快得出答案。答案是：兩個應急設施分別設在點(2,3),(6,3)時最優這是在不考慮L形障礙區域和水塘的影響的假定下得出的最優解，但從這兩個點到任何街區都可避開L形障礙區域和水塘，故它們也就是原題所需的最優選址。2假定（II）下的模型在假定（II）下，由于允許應急設施設在街道上任何位置，這就有無窮多種可能位置，不能直接用計算機窮舉。

6、不過，我們可證明：應急設施仍應設在街角處，才能使總響應時間最少。對已選定的兩個應急設施的位置A和B,我們先來看總響應時間怎樣計算。首先，我們將街道上所有的點的集合劃分成兩個責任區Va,Vb,分別由A,B進行救助：街道上的點P如果由A點去救助比由B點去救助的路程更近，就將P劃進A的責任區Va,反之就劃進Vb,為敘述方便，我們將每個長方形街區的四條邊中的每一條稱為一條“街道”，街道的一段稱為“街段”。每條街道中屬于Va的點與屬于Vb的點各組成一個街段，分別稱為A的或B的“責任段”。一條街道最多被分成兩個責任段（也有可能整條街道屬于同一個責任區，因而本身就是一個責任段），責任地段只有有限多條，對每個

7、應急設施，我們分別算出它的每個責任段的總響應時間，將這些總響應時間求和就得到這個設施的責任區的總響應時間。將兩個責任區各自的總響應時間相加就得到這一選址方案的總響應時間。下面需要知道：任一設施A到它的一個責任段EF的總響應時間怎樣計算。按假定（II）,街區出現事故的頻率平均分布在它周圍的四條街道上，每條街段的事故發生頻率與它的長度成正比。將應急車輛每秒鐘行駛的路程作為長度單位，則當街區事故頻率為p、街段的長度為t時，這一街段的事故頻率為pt/70,70是街區的周長，即車輛繞街區行駛一周需70秒。在大多數情況下，一條街段同時與兩個街區相鄰，兩個街區的事故它都有份，它的事故頻率應為（pq）t/70

8、,p、q分別是兩個街區的事故的總頻率（即原題圖上標出的數）。當然可以用積分的方法。即插入分點將責任段EF分成許多微小街段i,對每一小段i按其長度計算出它的事故發生頻率pikds,其中dSi是i的長度，k是與i無關（但與EF的選取有關）的常數。取應急車輛人A到i中任意一點的行駛時問Ti作為A到i的時間，則微小街段i的響應時間近似地等于TidSi。對這些微小的響應時間求和即得到EF的總響應時間的近似值。讓每個dSi0,求和變成求積分即可。但在這里，問題比較簡單，可以不用積分。事實上，由于EF的每一小段的事故發生頻率只與這一小段的長度有關，換句話說：頻率密度是常數，只要求出EF到A的平均行駛時間T,

9、再乘以EF的總的事故頻率就行了。當A設在街角處時，平均行駛時間也就是A到EF的中點M的行駛時間Tma15Xm120Ym2秒，這里（X,Y）,（m1,m2）分別是A,M的坐標，而且不考慮障礙和水塘的影響。將Tma乘以EF的事故頻率，就得到EF的總響應時間。換句話說，就是將EF的事故頻率Pef集中到M點，認為M按頻率Pef發生事故，而EF的其他點都不發生事故。這樣不會改變EF的總響應時間，卻便于計算，如果應急設施A不是設在街角處，而是設在某條街道CD的兩個端點C、D之間，則可能出現這樣的情況：從A出發到EF中的某些點的最短救助路線應向C方向行駛，晚到另一些點去則應向D方向行駛。這時，平均時間就不等

10、于A到EF中點M的時間Tam,而是比Tam小。在這樣的情況下EF可以分成兩段EG、GF,從A到其中一段（比如EG）上的所有的點的最短救助路線應向C方向行駛，而到另一段（比如GF）上的所有的點的點則應向D方向行駛。分別計算EG、GF的事故發生頻率Peg,Pgf,將這兩個頻率分別集中在EG、GF各自的中點Mi,M2,就可分別算出EG、GF的總響應時間，再將它們相加就得到EF的總響應時間。下面證明：最短的總響應時間必可由設在街角處的應急設施A、B來實現。假定已選擇兩個應急設施A、B的位置使總響應時間最短，且至少有一個設施（比如A）不是設在街角處，而是設在某一條街道CD的兩個端點C、D之間。我們證明：

11、可以把這個設施從A移到C或D,使總響應時間不增加，（而且很可能減少）。證明的主要想法是：將設施遷移到街角后，它到某些街段縮短了一段路程，同時到另外某些街段增加同樣長的一段路程。如果路程縮短的那些街段的事故總頻率大于路程增加的那些街段的事故總頻率，則總響應時間縮短了，設施位置得到優化，說明原來的位置不是最優。先考慮與街道CD相鄰的街區，也就是與急救站A相鄰的街區。要使總響應時間最少，兩個急救站A,B的位置顯然不應當靠得太近。因此，可以假定與A相鄰的街區周界上所有的點到A的路程都小于它們到B的路程，因而都應當由A負責救助。這個街區的事故頻率p均勻分布在街區的周界上。我們指出：救助這個街區的事故頻率

12、p均勻分布在街區的周界上。我們指出：救助這個街區的事故的總響應時間與A在CD上的位置選取無關。事實上，無論A處于街道CD上哪一個位置，總存在一點A將街區周界分成路程相等的兩段，第一段由A經C到A,第二段由A經D到A,每一段的總行駛時間是7/2=35秒，事故總頻率是p/20由A出發去救助每一段上各點的平均行駛時間等于35/2秒，因而兩段的總響應時間為（p/2）（35/2）2秒，確實與A點位置的選取無關。因此，在討論A在CD上的位置選取時，不需考慮到CD相鄰的街區的事故的影響，不妨暫時假定這樣的街區的事故頻率為0,特別是街道CD上不發生事故，不需要救助。設P是A的責任區Va內需要救助的任一點，從A

13、出發到P,有兩種可能的最短救助路線AP:一種是沿AC、經由C點到P,另一種是沿AD、經由D點到P。凡是AP屬于前一種情況的，這樣的點P組成的集合記作Uc；凡是AP屬于后一種情況的，這樣的點P組成的集合記作Udo這樣就將A的責任區按最短救助路線出發時的兩個不同方向分成了兩個區域（各由一些街段組成）。比較Uc,Ud這兩個區域各自的事故總頻率Pc,Pd的大小。如果Pc比Pd大，我們就將設施從A移到C,向Uc靠攏（同時遠離Ud）；反之，當Pd比PC大時，將設施由A遷到D去靠近Ud（同時遠離Uc）；當PcPd時將設施任意遷到C或D都可以。我們證明：將設施經過這樣的遷移后，總響應時間只可能減少，不可能增加

14、。因此，假如遷移前的方案最優，遷移后一定還是最優（事實上，當PcPd時，遷移后的方案一定比原來更優，說明原來不可能最優）。不妨先假定PCPD,設施從A遷到C點。（PDPC的情況同理）。為了便于比較遷移前后的總響應時間的變化情況，我們先作下面兩個假設（其中所說的“舊”是指設施遷移前的情況，而“新”則是指遷移后的情況）：（1）應急設施從A搬透到C后，兩個舊的責任區Va,Vb先仍分別由C和B負責救助，暫不改變。如果在這樣不改變責任區的情況下都能證明總響應時間不增加，則再進一步合理調整C、B的責任區還可能進一步縮短（至少不會增加）總響應時間，更加說明搬遷方案的優越。（2）搬遷后從新設施C到舊區域Uc中

15、的任何一點P的救助路線為：從C出發離開CD,沿原先A的的舊的救助路線到P。從C到舊區域Ud的任何一點P的救助路線為：從C出發沿CD（經過A）到D,再沿原先A的舊的救助路線到P。設應急車輛從A到C的行駛時間為T。則按（2）的行駛路線，Uc的點到設施的路程都減少了AC,行駛時間減少T,總響應時間減少T;Ud的點則相反，路程都增加AC,行駛時間都增加T,總響應時間增加PdT。由于PcPd,PcTPdT,總響應時間減少量超過（或等于）增加量，總的效果是減少了（或不改變）總響應時間，設施搬遷后的位置比原來更優，至少同樣優。假設（2）的路線不一定是最短路線。如果再進一步選擇最短路線，則還有可能進一步縮短新

16、設施方案的總響應時間，更加說明其優越性，假設（1）的責任區的貢分不一定是合理的，可以再進行調整，將街道上的每一點劃給離它最近的設施的責任區，這樣又可能再減少新設施方案的總響應時間，再一次增加它的優越程度，這樣就證明了新設施比舊設施更優，或同樣優。因此，在假定（II）下，仍可設應急設施設在街角處。于是與假定（I）的情況類似地可用計算機窮舉算出答案來，對任一對候選的應急設施位置A（Xi,Yi）,B（X2,Y2）,（坐標為整數），求出每一條街道CD的總響應時間，將所有街道的總響應時間相加就得到這一選址方案的總響應時間。進行比較就可得出最短的總響應時間及對應的選址方案。CD的總響應時間的計算方法已在前

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

18、都是街區的分界線，屬于兩個街區共同所有，分擔兩個街區的事故頻率。但我們可以把這樣的街道順著街道方向剖開成為兩部分（左半部分和右半部分），認為每半部分各只屬于一個街區，只承擔這一個街區的事故發生頻率，不用再將兩個相鄰街區的頻率相加。求出所有這些“半邊街道”的總響應時間之和，也就是整個城鎮的總響應時間了?，F在我們來看在假設（II）下圍成每個街區的四條邊（“半邊街道”）的總響應時間。如果這四條邊處在同一個責任區中，我們稱這個街區為非邊界街區。在計算非邊界街區的四條邊的總響應時問時把它們所分擔的事故頻率各自集中在它們的中點。相對的兩條邊分擔的事故頻率相等，在求它們的響應時間之和時可以用這兩條邊各自的中

19、點到應急設施的行駛時間的平均值T乘上它們的事故頻率之和（即每一個的事故頻率的兩倍）來計算。但這個平均值T就是街區中心到應急設施的行駛時間，（想象有穿過街區中心的東西方向南北方向的道路供行駛）。因此，可以把相對兩邊的事故頻率集中在街區的中心，從而把整個街區的事故頻率集中到街區中心。設這個街區的中心M的坐標為（i0.5,j0.5）,（0i9,0j4是整數），而這個街區所屬的應急設施A的坐標為（X,Y）,則這個街區周圍的四條街道到A的平均行駛時間就等于15X（i0.5）20Y（j0.5）秒（2）將這一結果與假定（1）下從A（X,Y）到這個街區救助的行駛時間t（X,Y,i,j）（見前面（1）式）相比，

20、只相差一個常數17.5秒。換句話說，按假定（1）只要求應急車輛到達街區的最近的一個街角，而現在相當于要求車輛繼續行駛到街區的中心（假定存在著可供車輛行駛的穿過該中心的東西、南北兩條道路）。如果在假定（1）下也改為要求車輛行駛到街區中心，則每一種選址方案的總響應時間增加一個常數，最短的總響應時間也就增加一個常數，而方案的優劣不會因此改變，原來的最優方案仍然最優。但這樣一來在兩個假定下對非邊界街區的總響應時間的計算方法就完全相同了。唯一有區別的地方是被責任區分界線一分為二的街區。在假定（I）下是按該街區中心所在責任區將它整個劃歸這個責任區。按假定（II）則將街區分成兩部分，分別屬于兩個責任區，這樣

21、可使這個街區的總響應時間比按假定（I）略小一些。在假定（II）下，如果在計算時對所有的街區也按街區中心的歸屬將這個街區全部劃入一個責任區，這樣算出來的就是近似的總響應時間，而按這樣的算法得出的最優解就是近似的最優。而這個近似的最優解必定就是假定（I）下的最優解（2,3）（6,3）,無須重新計算。在假定（II）下精確計算這個方案的總響應時間，與前面用計算機求出的真正的最優方案（2,3）,（7,3）相比較,只相差1秒鐘。考慮到原始數據（街區的事故次數）本身并不能百分之百的代表今后的事故頻率，1秒鐘的誤差應該說是在允許范圍，并不能說明用近似算出的解就一定不是最優，在實際中完全可以當最優解來用。更何況

22、，即使在假定（II）下，如果采用方案（2，（6,3）,則每個街區都整個的在一個責任區中，沒有哪個街區被分割開來分別劃進兩個責任區；而方案（2,3）,（7,3）卻將5個街區分割開了，這給應急設施進行救助帶來不方便，權衡利弊，我們得出下面的結論：按假定（II）,方案（2,3）,（7,3）比方案（2,3）,（6,3）的總響應時間約少1秒鐘,（分別為5121.4秒、5122.5秒）。但考慮到實施救助的方便起見，寧肯采用方案（2,3）,（6,3）。3算法的進一步討論以上算法是建立在用計算機進行窮舉的基礎上，可以稱為：算法1計算機窮舉法。窮舉的方法當然可以說是笨辦法，它對一些明顯不優的位置仍要一個個去驗證

23、，這實在顯得太笨。但窮舉的辦法也有一個好處，那就是：不用再證明最后答案的最優性。這個答案已經和所有的別的可能方案都比較過了，比它們都優，最優性已經得到證明。本題的一個特點是需要窮舉的可能方案的數目不大，用計算機進行窮舉所花的時間很少，因而是可行的，也是優越的。但假如考慮更一般的城市，街道數目較多，且應急設施的個數也可能不止兩個，而是更多，則計算機所花時間將會大大增加。能不能有一種非窮舉的有效算法呢？可以考慮采用如下的方法。算法2逐次改進法：它的基本想法是先從一個初始的方案（不一定最優）出發，逐步加以改進，直到得到一個不能再改進的方案，就有可能是最優方案，具體作法是：先任選兩個位置（坐標為整數的

24、點）Ao,Bo作為應急設施A,B的最初的選址。比如可選Ao（0,0）,Bo（10,5）,即選這個城鎮的西北角、東南角分別作為Ao,B0。（當然也可一開始憑直覺將Ao,Bo選得更好一些，更快地達到最后結果）。試考慮將設施A向東、西、南或北四個方向各移動一個街區（即將A的橫坐標或縱坐標增加或減少一個單位），B暫時不動，看總響應時間如何變化。（當然，如果在某個方向上已經不可能移動，即已經處于城鎮的邊界，就不考慮這一方向上的移動）。如果向某一方向上的移動引起總響應時間的增加（或不變），這一方向不是好方向，再換另一個方向試試。如果向某一方向的移動引起總響應時間的減少，這一方向就是好方向，將A向這一方向移

25、動一個街區（從Ao移到A）,以A,B的新位置作為出發點重新向各個方向試探。如果A向四個方向的移動都不能縮短總響應時間，則將A固定不動，再試B的移動，直到B向四個方向上的移動都不能縮短總響應時間，再考慮A的移動。這樣將A,B兩個設施輪流移動以優化方案，直到不能再優化為止：即A,B中任何一個向任何方向的移動都不能使總響應時間再縮短。這時這個優化過程就收斂了，我們可以認為找到了最優方案。如果從我們剛才所說的兩點（0,0）,（10,5）出發，采用假定（I）的算法，進行逐次改進，最后就收斂于（2,3）,（6這兩點，已經知道它確實是最優方案。能否證明：從任意兩點出發都收斂于最優方案？從數學理論上講，這樣的

26、逐次改進的方法達到的是“極好值點”,而不一定是“最好值點”。即：將總響應時間T作為兩個應急設施位置的四個坐標Xi,X,X2，的函數，用逐次改進法所得到的是函數的極小值點，但不一定是最小值點。如果能證明這個函數只有一個極小值點，它也就是最小值點。但這一般是不成立的，即使成立也是很難證明的。比如本題。如果從（4,0）,（4,5）這兩點出發，就會發現最后收斂于（4,1）,（5,4）這兩個位置，不是最優方案。（按假定（I）的算法，方案（4,1）,（5,4）的總響應時間為3355秒，而方案（2,3）,（6,3）和（4,1）,（5,4）。由于選擇的初始位置不同，逐次改進后分別收斂于這兩組位置。初始的兩個點

27、的橫坐標比較接近的，容易收斂于后一組解。反之一般收斂于前一組解。對本題來說，由于城鎮的形狀是東西方向窄，南北方向寬，從直觀上講，一開始選的兩個點應該一個偏北，另一個偏南，這樣才使每個責任區中相距最遠的點的距離都不大，總響應時間才不會太大。如果選的兩個位置呈東西方向排列（即械坐標很接近），如上面所說的（4,0）,（4,5）兩點，則兩個責任區都是南北方向上的長條，責任區西北端的點和東南端的點相距很遠，總響應時間顯然不會小，因而一開始就是不合理的，收斂過程也就容易誤入歧途。由此可見，上述的逐次改進法在理論上是不完善的，但在實用上卻是可行的，只要最初的兩個位置不是選的太不合理，實際上仍能得出最優解。當

28、然也可以從不同的初始位置出發多試幾次，如果經過收斂得到若干個不同的解，再通過比較從這些解中選出一個最優的就行了。不過，就本題來說，計算機窮舉法計算量本來就不大，在理論上又沒有漏洞。逐次改進法雖然可以提高一些速度，但仍然不能用手工計算，反而帶來理論上的缺陷，似乎還是得不償失，不如計算機窮舉法來得干凈利落。4最優解滿足的條件上述的逐次改進法，試圖改進計算機窮舉發不管好壞一概窮舉的“窮舉”之處，但它自己也同樣笨拙：一開始的初始位置隨便亂選，也是不管好壞；試探的時候不管怎樣只走一步，而不敢向好的方向大踏步的改進。能不能將它再改進一下，使得能比較容易判斷方案？為此，先來考察一下最優解到底應該滿足什么樣的

29、條件，即使不能得出充分條件，哪怕得出一些操作方便的必要條件也行。說起來也簡單，最優滿足的必要充分的條件是：用任何方法都不能將它改進。當然，“任何方法”是難以操作的；誰也不好擔保他所找到的方法已經窮盡了所有的方法。但是，如果找到一種方法將它改進，就足以說明它不是最優。因此，最優解滿足的必要條件：用你所找到的方法不能將它改進，這一條件比較操作，前提是必須盡量找到一些方法，使得用你的方法不能改進的解很少。下面就給出一個這樣的方法。先將問題簡化，改為：只設一個應急設施。此是存在非窮舉的有效算法如下。這個方法有些類似于求質點系統的力學重心(但只是類似而并不完全相同)，為敘述方便，不妨稱為“重心法”。設應

30、急設施的最優位置在A點，其坐標為(X,Y)。我們的基本想法是：如果A點北面(即橫坐標X)的街區與南面(即橫坐標X)的街區的事故發生的頻率懸殊很大，則將設施向事故較多的那個方向移動就可以減少總響應時間，從而將方案改進。因此，最優位置A應使得它的北面和南面發生事故的頻率盡可能相等，換句話說，北面發生的事故應當盡可能接近整個城鎮事故總數的一半。同理，它的東面和西面的事故頻率也應該盡可能相等，西面發生的事故應盡可能接近事故總數的一半。為此，對橫坐標0x10的每個整數值定義x事故頻率函數p(x),它等于所有滿足條件ix的街區(i,j)的事故頻率的總和。這里，我們用每個街區東南角的坐標(i,j)來代表這個

31、街區。這樣，p(x)是單調遞增函數。p(0)0。當x1時p(x)p(x1)就是橫坐標等于x的5個街區的事故頻率之和。因此p(x)p(x1)00而且，這本題的數據而言，p(x)p(x1)0對1,2,9,10成立，p(x)是嚴格單調遞增函數。Pp(10)就是整個城鎮的事故頻率總和，本題中P109。按照上面的說法，最優解A(X,Y)的橫坐標X應使p(X)P/2最小。這樣的X最多只有兩個(分別大于和小于P/2)。就本題的數據而言，計算得：i010時p(i)依次為0,15,28,38,47,65,78,85,92,99,109p(4)47最接近P/254.5,故X4。同樣，對縱坐標0y5的每個整數值定義

32、q(y)為滿足條件jy的街區(i,j)的事故頻率總和，本題為：j05時q(j)依次為0,25,40,57,83,100同樣找出Y使q(Y)P/2最小，得Y3,(q(3)57與109/254.5最接近)。因此，如果不考慮障礙和水塘的影響，確實就是所求的最優位置。下面證明這個方法的正確性。最優位置顯然存在，只要證明其他的位置都可以改進，不是最優，則(X,Y)當然就是最優了?？紤]應急設施的任一其他位置(*一)。先考察乂的橫坐標x。過M作一條東西方向的直線li將城鎮分為兩部分。將事故頻率小的那一部分稱為Ui,事故頻率較大的那部分稱為U2(兩部分事故頻率相等時，任意指定一個為Ui,另一個為U2,不過本題

33、并不出現這一情況)?？紤]將M向U2那一側移動一個街我到N點(縱坐標仍為y,橫坐標變為x1或x1)。過N點再作一條東西方向的直線12(與11平行)，12將事故較多的這一區域U2再分成兩部分，其中11,12之間的那部分記為U。，另一部分記為V1,我們來看U1,U0,V1這三部分到設施的路程的變化及由此引起的總響應時間的變化，結果是：U0中的街區到新舊設施的路程相等，對總響應時間沒有影響。U1中的街區到新設施N的路程比到舊設施M增加1個街區，引起總響應時間增加15Xp1秒，5是U1的事故總頻率。V1中的街區到新設施N的路程比到M減少1個街區，引起總響應時間減少15XP2秒，P2是V1的事故總頻率。容

34、易看出，只要P2P1,則移動設施的總效果是總響應時間減少，方案優化，原7T案不仇io如果設U0的事故總頻率為P0,則按照原來的假設，U2(由Uo,V1組成)中的事故頻率P2P0大于U1中的事故頻率P1。如果P2P0比P1大得太多，以至于從P2P0中減去P0后所得的P2仍大于R,原來的方案就不是最優了。我們證明：當XX時一定是這樣。先設P(X)P/2。(比如本題P(4)4754.5,就是這樣。)如果xX,則x1X,P(x)P(x1)p(X)P/2,P(x)P/2PP(x1)?？紤]將設施從舊位置(x,y)移動到新位置(x1,y),則P(x)就是舊設施北面的事故總數，PP(x1)就是新設施南面的事故

35、總數。既然P(x)PP(x1),新設施就比舊設施優，舊設施不優。再考慮xX1的情形，則p(X)P/2p(X1)P(x1)P(x),P(x1)P/2PP(x),將設施從(x,y)移到(x1,y)可以優化。除xX,xX1外，xX的唯一可能是xX1,p(X)P/2p(X1)p(x)。如果p(X1)P/2P/2p(X),則p(X1)與p（X）同樣接近P/2,X1也可以取來作為X,（X1,Y）與（X,Y）同樣優。假設不是這樣的情況（如本題），則p（x1）P/2P/2p（X）.P（X）Pp（x1）,即（x,y）北面的事故比（X1,y）南面的事故多，將設施從（x,y）（即（X1,y）向北移到（x,y）可以引

36、起優化。這就在p（X）P/2的情況下證明：當xX時（x,y）一定不是最優。對p（X）P/2的情況，同理可以證明同樣的結論。同理還可證明：當yY時（x,y）也一定不是最優，結果只剩下（X,Y）才有可能最優，因而也就確實是最優。現在回到原題條件，考慮設兩個應急設施的情形，假如按前面所說的算法2,指定了兩個點Ao,Bo作為應急設施的候選位置，這一組位置是否已經最優了？如果不是，有什么方法較快地改進它，而不要一步一步地試探著前進？我們可以先按設施的兩個候選位置Ao,Bo劃定它們的責任區Vao,Vbo的范圍，將每個街區（按假定（I）或街道上的每個點（按假定（II）劃給離它最近的設施的責任區。到兩個設施的

37、路程相等的，任意劃給一個責任區。然后，在每個責任區內可以按前述的“重心法”各找到一個的最佳位置A,B1o用A1,B1分別取代Ao,Bo,即使在不調整責任區的情形下已經能夠說明方案被優化了。如果A1,B1的位置與Ao,Bo不完全相同，責任區也可能發生變化。按設施的新位置A,B1重新劃定責任區。在兩個新的責任區范圍內再一次用“重心法”各選一個新位置。這樣，調整責任區范圍和在每個責任區內尋找最優位置交替進行，每進行一次都使方案得到優化。這個過程必定收斂（因為方案不能無窮地優化下去），即設施位置及責任區范圍都不能再改變。這就達到了這個方法所能找到的最優方案。以上方法可以作為算法3,仍稱為“重心法”（因

38、為它是在兩個責任區內分別用重心法求最優位置）。而且，在實際計算時，可以顛倒一下順序：第一步不先選兩點位置，而先按某種方案將所有街區劃分成兩個區域，作為最初的責任區，要在責任區內分別用重心法求出兩個點。重心法通常都比算法2的一步一步改進要快，很快就可收斂到一組不能再改進的方案，收斂后是否就得到了最優解？與算法2的情形類似，仍然不能肯定，很可能與一開始劃定責任區范圍的方式有關。使用重心法時，還應當考慮到這樣的情況：如果不改變責任區，A1,B1在各自的責任區內當然是最優位置，一移動就會使總響應時間增加，設增加量為t-但如果移動后引起責任區改變，則調整責任區可再使總響應時間減少某個t2,假如移動的方式

39、選得適當，使t2ti,則方案仍然獲得改進。這說明，在用重心法達到收斂后，還應該用算法2再試探一下，看是否還有改進的余地。不過，不需要具體計算出總響應時間，只要考察總響應時間的增減情況就行了。由于試探時設施只移動一步（一個街區的長度），引起的責任區改變只有半步，t2一般都很小，實際上很難使t2ti,要使ti比t2更小，將責任區內已經達到最優位置（X,Y）的點的坐標X（或Y）變動為X1（或Y1）時應盡量使頻率函數值P（X1）（或q（Y1）仍很接近P1/2,這里R是該責任區內的事故頻率總數。但要p（X）P2與p（X1）R/2（或q（Y）P1/2與q（Y1）R/2）都很接近于0,只有它們符號相反時才有

40、可能。也就是說：只考慮（X,Y）向事故多的方向上的移動。下面用重心法來計算本題的最優解。由于收斂速度很快，可以用手算實現，只要第一步的責任區劃分得不是太不合理，求出的也的確是最優解。先在假定（I）下計算：考慮到城鎮是長方形，很自然先用沿東西方向的直線x5將城鎮分成同樣大的南、北兩塊（各含25個街區）U1W1,這樣做的理由是：可以使每塊內部點與點之間的最遠程不會太長，有利于降低總響應時間。分別計算這兩塊的頻率函數得：北塊：x頻率函數值：0,15,28,38,47,65;y頻率函數值；0,16,23,36,50,66南塊：x頻率函數值：0,13,20,27,34,44;y頻率函數化0,9,17,21,33,44北塊：x頻率函數值最接近65/2=32.5的是28,y頻率函數值最接近65/2=32.5的是36。最優點A1的坐標為（2,3）。同理可算出南塊的最優點為B1（7,3）O再劃分A1，B1的責任區；橫坐標為4的四個街區的中心離A,B!的路程相等，劃給A或B1都可以。如果劃給A,則就是原來的責任區方案U1N1,設施位置不能再優化?？紤]將它們劃給B1