1、第17講應(yīng)急設(shè)施的優(yōu)化選址問題問題（AMCM-86題）里奧蘭翹鎮(zhèn)迄今還沒有自己的應(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)急車輛駛過一條南北向的街道平均要花15秒，而通過一條東西向的街道平均花20秒。你的任務(wù)是確定這兩個(gè)應(yīng)急設(shè)施的位置，使得總響應(yīng)時(shí)間最少。圖17-11985年里奧蘭翹每個(gè)長(zhǎng)方街區(qū)應(yīng)急事件的數(shù)目（I）假定需求集中在每個(gè)街區(qū)的中心，而應(yīng)急設(shè)施位于街角處。（II）假定需求是沿包圍每個(gè)街區(qū)的街道

2、上平均分布的，而應(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ū)，可以開始工作了。按假定(I),每個(gè)應(yīng)急設(shè)施選在街角處，可能的位置只有6X11=66個(gè)。兩個(gè)應(yīng)急設(shè)施的位置的可能的組合至多只有66X65/2=2145個(gè)。這個(gè)數(shù)目對(duì)計(jì)算機(jī)來說并不大，可用計(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)，則街角的坐標(biāo)(X,Y)是滿足

4、條件0MXM10,0MYM5的整數(shù)。而每個(gè)街區(qū)中心的坐標(biāo)具有形式(i+0.5,j+0.5),其中i,j是滿足條件：0Ei<9,0<jE4的整數(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(X-i-0.5-0.5)20(Y-j-0.5-0.5)=15(X-(i+0.5)+20Y(j+0.5)-17.5)秒記p(i,j)為以(i+0.5,j+0.5)為中心的街區(qū)的事故發(fā)生頻率(即在圖上該街區(qū)所標(biāo)的數(shù)字)。如果應(yīng)急設(shè)施設(shè)在(Xi，Yi),(X2，Y2)這兩點(diǎn)，總不妨設(shè)Xi<X2

5、,則該設(shè)置方案的總響應(yīng)時(shí)間為T(Xi,Yi,X2,Y2)94='p(i,j)mint(X1,Y1,i,j),t(X2,Y2,i,j)i=0j=e讓Xi取遍010,X2取遍Xi-10,丫1,丫2分別獨(dú)立地取遍04。依次對(duì)四數(shù)組(Xi,Yi,X2,Y2)的每一個(gè)值算出對(duì)應(yīng)的總響應(yīng)時(shí)間的最小值及對(duì)應(yīng)的四數(shù)組。以上算法不難用計(jì)算機(jī)編程實(shí)現(xiàn)。由于數(shù)組的個(gè)數(shù)不算多(只有兩千多個(gè))，計(jì)算機(jī)可很快得出答案。答案是：兩個(gè)應(yīng)急設(shè)施分別設(shè)在點(diǎn)(2,3),(6,3)時(shí)最優(yōu)這是在不考慮L形障礙區(qū)域和水塘的影響的假定下得出的最優(yōu)解，但從這兩個(gè)點(diǎn)到任何街區(qū)都可避開L形障礙區(qū)域和水塘，故它們也就是原題所需的最優(yōu)選址。

6、§2假定（II）下的模型在假定（II）下，由于允許應(yīng)急設(shè)施設(shè)在街道上任何位置，這就有無窮多種可能位置，不能直接用計(jì)算機(jī)窮舉。不過，我們可證明：應(yīng)急設(shè)施仍應(yīng)設(shè)在街角處，才能使總響應(yīng)時(shí)間最少。對(duì)已選定的兩個(gè)應(yīng)急設(shè)施的位置A和B,我們先來看總響應(yīng)時(shí)間怎樣計(jì)算。首先，我們將街道上所有的點(diǎn)的集合劃分成兩個(gè)責(zé)任區(qū)Va,Vb,分別由A,B進(jìn)行救助：街道上的點(diǎn)P如果由A點(diǎn)去救助比由B點(diǎn)去救助的路程更近，就將P劃進(jìn)A的責(zé)任區(qū)Va,反之就劃進(jìn)Vb,為敘述方便，我們將每個(gè)長(zhǎng)方形街區(qū)的四條邊中的每一條稱為一條“街道”，街道的一段稱為“街段”。每條街道中屬于Va的點(diǎn)與屬于Vb的點(diǎn)各組成一個(gè)街段，分別稱為A的或

7、B的“責(zé)任段”。一條街道最多被分成兩個(gè)責(zé)任段（也有可能整條街道屬于同一個(gè)責(zé)任區(qū)，因而本身就是一個(gè)責(zé)任段），責(zé)任地段只有有限多條，對(duì)每個(gè)應(yīng)急設(shè)施，我們分別算出它的每個(gè)責(zé)任段的總響應(yīng)時(shí)間，將這些總響應(yīng)時(shí)間求和就得到這個(gè)設(shè)施的責(zé)任區(qū)的總響應(yīng)時(shí)間。將兩個(gè)責(zé)任區(qū)各自的總響應(yīng)時(shí)間相加就得到這一選址方案的總響應(yīng)時(shí)間。下面需要知道：任一設(shè)施A到它的一個(gè)責(zé)任段EF的總響應(yīng)時(shí)間怎樣計(jì)算。按假定（II）,街區(qū)出現(xiàn)事故的頻率平均分布在它周圍的四條街道上，每條街段的事故發(fā)生頻率與它的長(zhǎng)度成正比。將應(yīng)急車輛每秒鐘行駛的路程作為長(zhǎng)度單位，則當(dāng)街區(qū)事故頻率為p、街段的長(zhǎng)度為t時(shí)，這一街段的事故頻率為pxt/70,70是街區(qū)的

8、周長(zhǎng)，即車輛繞街區(qū)行駛一周需70秒。在大多數(shù)情況下，一條街段同時(shí)與兩個(gè)街區(qū)相鄰，兩個(gè)街區(qū)的事故它都有份，它的事故頻率應(yīng)為（p+q）Mt/70,p、q分別是兩個(gè)街區(qū)的事故的總頻率（即原題圖上標(biāo)出的數(shù)）。當(dāng)然可以用積分的方法。即插入分點(diǎn)將責(zé)任段EF分成許多微小街段鳥，對(duì)每一小段W按其長(zhǎng)度計(jì)算出它的事故發(fā)生頻率pi=kdS,其中dSi是樂的長(zhǎng)度，k是與i無關(guān)（但與EF的選取有關(guān)）的常數(shù)。取應(yīng)急車輛人A到6i中任意一點(diǎn)的行駛時(shí)間Ti作為A到。的時(shí)間，則微小街段。的響應(yīng)時(shí)間近似地等于TidSio對(duì)這些微小的響應(yīng)時(shí)間求和即得到EF的總響應(yīng)時(shí)間的近似值。讓每個(gè)dSit0,求和變成求積分即可。但在這里，問題比

9、較簡(jiǎn)單，可以不用積分。事實(shí)上，由于EF的每一小段的事故發(fā)生頻率只與這一小段的長(zhǎng)度有關(guān)，換句話說：頻率密度是常數(shù)，只要求出EF到A的平均行駛時(shí)間T,再乘以EF的總的事故頻率就行了。當(dāng)A設(shè)在街角處時(shí)，平均行駛時(shí)間也就是A到EF的中點(diǎn)M的行駛時(shí)間Tma=15X-m1|+20Y-m2秒，這里（X,Y）,（m1，m2）分別是A,M的坐標(biāo)，而且不考慮障礙和水塘的影響。將Tma乘以EF的事故頻率，就得到EF的總響應(yīng)時(shí)間。換句話說，就是將EF的事故頻率PEF集中到M點(diǎn),認(rèn)為M按頻率Pef發(fā)生事故，而EF的其他點(diǎn)都不發(fā)生事故。這樣不會(huì)改變EF的總響應(yīng)時(shí)間，卻便于計(jì)算，如果應(yīng)急設(shè)施A不是設(shè)在街角處，而是設(shè)在某條街

10、道CD的兩個(gè)端點(diǎn)C、D之間，則可能出現(xiàn)這樣的情況：從A出發(fā)到EF中的某些點(diǎn)的最短救助路線應(yīng)向C方向行駛，崎到另一些點(diǎn)去則應(yīng)向D方向行駛。這時(shí)，平均時(shí)間就不等于A到EF中點(diǎn)M的時(shí)間Tam,而是比Tam小。在這樣的情況下EF可以分成兩段EG、GF,從A到其中一段（比如EG）上的所有的點(diǎn)的最短救助路線應(yīng)向C方向行駛，而到另一段（比如GF）上的所有的點(diǎn)的點(diǎn)則應(yīng)向D方向行駛。分別計(jì)算EG、GF的事故發(fā)生頻率Peg,Pgf,將這兩個(gè)頻率分別集中在EG、GF各自的中點(diǎn)Mi,M2,就可分別算出EG、GF的總響應(yīng)時(shí)間，再將它們相加就得到EF的總響應(yīng)時(shí)間。下面證明：最短的總響應(yīng)時(shí)間必可由設(shè)在街角處的應(yīng)急設(shè)施A、B

11、來實(shí)現(xiàn)。假定已選擇兩個(gè)應(yīng)急設(shè)施A、B的位置使總響應(yīng)時(shí)間最短，且至少有一個(gè)設(shè)施（比如A）不是設(shè)在街角處，而是設(shè)在某一條街道CD的兩個(gè)端點(diǎn)C、D之間。我們證明：可以把這個(gè)設(shè)施從A移到C或D,使總響應(yīng)時(shí)間不增加，（而且很可能減少）。證明的主要想法是：將設(shè)施遷移到街角后，它到某些街段縮短了一段路程，同時(shí)到另外某些街段增加同樣長(zhǎng)的一段路程。如果路程縮短的那些街段的事故總頻率大于路程增加的那些街段的事故總頻率，則總響應(yīng)時(shí)間縮短了，設(shè)施位置得到優(yōu)化，說明原來的位置不是最優(yōu)。先考慮與街道CD相鄰的街區(qū)，也就是與急救站A相鄰的街區(qū)。要使總響應(yīng)時(shí)間最少，兩個(gè)急救站A,B的位置顯然不應(yīng)當(dāng)靠得太近。因此，可以假定與A

12、相鄰的街區(qū)周界上所有的點(diǎn)到A的路程都小于它們到B的路程，因而都應(yīng)當(dāng)由A負(fù)責(zé)救助。這個(gè)街區(qū)的事故頻率p均勻分布在街區(qū)的周界上。我們指出：救助這個(gè)街區(qū)的事故頻率p均勻分布在街區(qū)的周界上。我們指出：救助這個(gè)街區(qū)的事故的總響應(yīng)時(shí)間與A在CD上的位置選取無關(guān)。事實(shí)上，無論A處于街道CD上哪一個(gè)位置，總存在一點(diǎn)A'將街區(qū)周界分成路程相等的兩段，第一段由A經(jīng)C到A',第二段由A經(jīng)D到A',每一段的總行駛時(shí)間是7/2=35秒，事故總頻率是p/20由A出發(fā)去救助每一段上各點(diǎn)的平均行駛時(shí)間等于35/2秒，因而兩段的總響應(yīng)時(shí)間為（p/2）x（35/2）x2秒，確實(shí)與A點(diǎn)位置的選取無關(guān)。因此，

13、在討論A在CD上的位置選取時(shí)，不需考慮到CD相鄰的街區(qū)的事故的影響，不妨?xí)簳r(shí)假定這樣的街區(qū)的事故頻率為0,特別是街道CD上不發(fā)生事故，不需要救助。設(shè)P是A的責(zé)任區(qū)Va內(nèi)需要救助的任一點(diǎn)，從A出發(fā)到P,有兩種可能的最短救助路線AP:一種是沿AC、經(jīng)由C點(diǎn)到P,另一種是沿AD、經(jīng)由D點(diǎn)到P。凡是AP屬于前一種情況的，這樣的點(diǎn)P組成的集合記作Uc；凡是AP屬于后一種情況的，這樣的點(diǎn)P組成的集合記作Udo這樣就將A的責(zé)任區(qū)按最短救助路線出發(fā)時(shí)的兩個(gè)不同方向分成了兩個(gè)區(qū)域（各由一些街段組成）。比較Uc,Ud這兩個(gè)區(qū)域各自的事故總頻率Pc,Pd的大小。如果Pc比Pd大，我們就將設(shè)施從A移到C,向Uc靠攏（

14、同時(shí)遠(yuǎn)離Ud）；反之，當(dāng)Pd比PC大時(shí)，將設(shè)施由A遷到D去靠近Ud（同時(shí)遠(yuǎn)離Uc）；當(dāng)Pc=Pd時(shí)將設(shè)施任意遷到C或D都可以。我們證明：將設(shè)施經(jīng)過這樣的遷移后，總響應(yīng)時(shí)間只可能減少，不可能增加。因此，假如遷移前的方案最優(yōu)，遷移后一定還是最優(yōu)（事實(shí)上，當(dāng)Pc#Pd時(shí)，遷移后的方案一定比原來更優(yōu)，說明原來不可能最優(yōu)）。不妨先假定PC>PD,設(shè)施從A遷到C點(diǎn)。（PDAPC的情況同理）。為了便于比較遷移前后的總響應(yīng)時(shí)間的變化情況，我們先作下面兩個(gè)假設(shè)（其中所說的“舊”是指設(shè)施遷移前的情況，而“新”則是指遷移后的情況）：（1）應(yīng)急設(shè)施從A搬透到C后，兩個(gè)舊的責(zé)任區(qū)Va,Vb先仍分別由C和B負(fù)責(zé)救助

15、，暫不改變。如果在這樣不改變責(zé)任區(qū)的情況下都能證明總響應(yīng)時(shí)間不增加，則再進(jìn)一步合理調(diào)整C、B的責(zé)任區(qū)還可能進(jìn)一步縮短（至少不會(huì)增加）總響應(yīng)時(shí)間，更加說明搬遷方案的優(yōu)越。（2）搬遷后從新設(shè)施C到舊區(qū)域Uc中的任何一點(diǎn)P的救助路線為：從C出發(fā)離開CD,沿原先A的的舊的救助路線到P。從C到舊區(qū)域Ud的任何一點(diǎn)P的救助路線為：從C出發(fā)沿CD（經(jīng)過A）到D,再沿原先A的舊的救助路線到P。設(shè)應(yīng)急車輛從A到C的行駛時(shí)間為T。則按（2）的行駛路線，Uc的點(diǎn)到設(shè)施的路程都減少了AC,行駛時(shí)間減少T,總響應(yīng)時(shí)間減少®T;Ud的點(diǎn)則相反，路程都增加AC,行駛時(shí)間都增加T,總響應(yīng)時(shí)間增加PdT。由于Pc之P

16、d,PcT之PdT,總響應(yīng)時(shí)間減少量超過（或等于）增加量，總的效果是減少了（或不改變）總響應(yīng)時(shí)間，設(shè)施搬遷后的位置比原來更優(yōu)，至少同樣優(yōu)。假設(shè)（2）的路線不一定是最短路線。如果再進(jìn)一步選擇最短路線，則還有可能進(jìn)一步縮短新設(shè)施方案的總響應(yīng)時(shí)間，更加說明其優(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ī)窮舉算出答案來，對(duì)任一對(duì)候選的應(yīng)急設(shè)施位置A（

17、Xi,Yi）,B（X2,Y2）,（坐標(biāo)為整數(shù)），求出每一條街道CD的總響應(yīng)時(shí)間，將所有街道的總響應(yīng)時(shí)間相加就得到這一選址方案的總響應(yīng)時(shí)間。進(jìn)行比較就可得出最短的總響應(yīng)時(shí)間及對(duì)應(yīng)的選址方案。CD的總響應(yīng)時(shí)間的計(jì)算方法已在前面講過。并且由于設(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)行比較。首先，既

18、然已經(jīng)證明在假定（II）下應(yīng)急設(shè)施仍應(yīng)設(shè)在街角處，這就與假定（1）相同了，只是對(duì)每一對(duì)候選位置A、B計(jì)算總響應(yīng)時(shí)間時(shí)的算法不同。我們考慮每一個(gè)街區(qū)和它周圍的四條街道在兩種不同假設(shè)下算出的總響應(yīng)時(shí)間有何不同。注意大部分街道都是街區(qū)的分界線，屬于兩個(gè)街區(qū)共同所有，分擔(dān)兩個(gè)街區(qū)的事故頻率。但我們可以把這樣的街道順著街道方向剖開成為兩部分（左半部分和右半部分），認(rèn)為每半部分各只屬于一個(gè)街區(qū)，只承擔(dān)這一個(gè)街區(qū)的事故發(fā)生頻率，不用再將兩個(gè)相鄰街區(qū)的頻率相加。求出所有這些“半邊街道”的總響應(yīng)時(shí)間之和，也就是整個(gè)城鎮(zhèn)的總響應(yīng)時(shí)間了。現(xiàn)在我們來看在假設(shè)（II）下圍成每個(gè)街區(qū)的四條邊（“半邊街道”）的總響應(yīng)時(shí)間。

19、如果這四條邊處在同一個(gè)責(zé)任區(qū)中，我們稱這個(gè)街區(qū)為非邊界街區(qū)。在計(jì)算非邊界街區(qū)的四條邊的總響應(yīng)時(shí)問時(shí)把它們所分擔(dān)的事故頻率各自集中在它們的中點(diǎn)。相對(duì)的兩條邊分擔(dān)的事故頻率相等，在求它們的響應(yīng)時(shí)間之和時(shí)可以用這兩條邊各自的中點(diǎn)到應(yīng)急設(shè)施的行駛時(shí)間的平均值T乘上它們的事故頻率之和（即每一個(gè)的事故頻率的兩倍）來計(jì)算。但這個(gè)平均值T就是街區(qū)中心到應(yīng)急設(shè)施的行駛時(shí)間，（想象有穿過街區(qū)中心的東西方向南北方向的道路供行駛）。因此，可以把相對(duì)兩邊的事故頻率集中在街區(qū)的中心，從而把整個(gè)街區(qū)的事故頻率集中到街區(qū)中心。設(shè)這個(gè)街區(qū)的中心M的坐標(biāo)為（i+0.5,j+0.5）,（0<i<9,0<jE4是整

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

21、最優(yōu)方案仍然最優(yōu)。但這樣一來在兩個(gè)假定下對(duì)非邊界街區(qū)的總響應(yīng)時(shí)間的計(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ū)，這樣算出來的就是近似的總響應(yīng)時(shí)間，而按這樣的算法得出的最優(yōu)解就是近似的最優(yōu)。而這個(gè)近似的最優(yōu)解必定就是假定（I）下的最優(yōu)解（2,3）（6,3）,無須重新計(jì)算。在假定（II）下精確計(jì)算這個(gè)方案的總響應(yīng)時(shí)間，與

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

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

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

25、總響應(yīng)時(shí)間如何變化。（當(dāng)然，如果在某個(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ū)（從Ao移到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)

26、時(shí)間再縮短。這時(shí)這個(gè)優(yōu)化過程就收斂了，我們可以認(rèn)為找到了最優(yōu)方案。如果從我們剛才所說的兩點(diǎn)（0,0）,（10,5）出發(fā)，采用假定（I）的算法，進(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í)間T作為兩個(gè)應(yīng)急設(shè)施位置的四個(gè)坐標(biāo)Xi,X,X2，的函數(shù)，用逐次改進(jìn)法所得到的是函數(shù)的極小值點(diǎn)，但不一定是最小值點(diǎn)。如果能證明這個(gè)函數(shù)只有一個(gè)極小值點(diǎn)，它也就是最小值點(diǎn)。但這一般是不成立的，即使成立也是很難證明的。比如本題。如果從(4,0

27、),(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ì)本題來說，由于城鎮(zhèn)的形狀是東西方向窄，南北方向?qū)?，從直觀上講，一開始選的兩個(gè)點(diǎn)應(yīng)該一個(gè)偏北，另一個(gè)偏南，這樣才使每個(gè)責(zé)任區(qū)中相距最遠(yuǎn)的點(diǎn)的距離都不大，總響應(yīng)時(shí)間才不會(huì)太大。如果選的兩個(gè)位置呈東西方向排列(即械坐標(biāo)很接近)，如上面所說的(4,0),

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

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

30、找到的方法不能將它改進(jìn)，這一條件比較操作，前提是必須盡量找到一些方法，使得用你的方法不能改進(jìn)的解很少。下面就給出一個(gè)這樣的方法。先將問題簡(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,Y)。我們的基本想法是：如果A點(diǎn)北面(即橫坐標(biāo)<X)的街區(qū)與南面(即橫坐標(biāo)>X)的街區(qū)的事故發(fā)生的頻率懸殊很大，則將設(shè)施向事故較多的那個(gè)方向移動(dòng)就可以減少總響應(yīng)時(shí)間，從而將方案改進(jìn)。因此，最優(yōu)位置A應(yīng)使得它的北面和南面發(fā)生事故的頻率盡可能相等，換句話

31、說，北面發(fā)生的事故應(yīng)當(dāng)盡可能接近整個(gè)城鎮(zhèn)事故總數(shù)的一半。同理，它的東面和西面的事故頻率也應(yīng)該盡可能相等，西面發(fā)生的事故應(yīng)盡可能接近事故總數(shù)的一半。為此，對(duì)橫坐標(biāo)0Wx<10的每個(gè)整數(shù)值定義x-事故頻率函數(shù)p(x),它等于所有滿足條件iEx的街區(qū)(i,j)的事故頻率的總和。這里，我們用每個(gè)街區(qū)東南角的坐標(biāo)(i,j)來代表這個(gè)街區(qū)。這樣，p(x)是單調(diào)遞增函數(shù)。p(0)=0。當(dāng)x±1時(shí)p(x)-p(x-1)就是橫坐標(biāo)等于x的5個(gè)街區(qū)的事故頻率之和。因此p(x)-p(x-1)>00而且，這本題的數(shù)據(jù)而言，p(x)-p(x-1)>0對(duì)=1,2,招/。成立，p(x)是嚴(yán)格單調(diào)

32、遞增函數(shù)。P=p(10)就是整個(gè)城鎮(zhèn)的事故頻率總和，本題中P=109。按照上面的說法，最優(yōu)解A(X,Y)的橫坐標(biāo)X應(yīng)使|p(X)-P/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)0My<5的每個(gè)整數(shù)值定義q(y)為滿足條件jWy的街區(qū)(i,j)的事故頻率總和，本題為：j=05時(shí)q(j)依次為0,25,40,57,83,109同樣找出Y使q(Y)-P/2最小，得Y=3,(q(3)=57與109/2=5

33、4.5最接近)。因此，如果不考慮障礙和水塘的影響，確實(shí)就是所求的最優(yōu)位置。下面證明這個(gè)方法的正確性。最優(yōu)位置顯然存在，只要證明其他的位置都可以改進(jìn)，不是最優(yōu)，則(X,Y)當(dāng)然就是最優(yōu)了?？紤]應(yīng)急設(shè)施的任一其他位置(*一)。先考察乂的橫坐標(biāo)x。過M作一條東西方向的直線li將城鎮(zhèn)分為兩部分。將事故頻率小的那一部分稱為Ui,事故頻率較大的那部分稱為U2(兩部分事故頻率相等時(shí)，任意指定一個(gè)為Ui,另一個(gè)為U2,不過本題并不出現(xiàn)這一情況)?？紤]將M向U2那一側(cè)移動(dòng)一個(gè)街我到N點(diǎn)(縱坐標(biāo)仍為y,橫坐標(biāo)變?yōu)閬V+1或乂-1)。過N點(diǎn)再作一條東西方向的直線12(與11平行)，12將事故較多的這一區(qū)域U2再分成兩

34、部分，其中11,12之間的那部分記為U。，另一部分記為V1,我們來看U1,U0,V1這三部分到設(shè)施的路程的變化及由此引起的總響應(yīng)時(shí)間的變化，結(jié)果是：U0中的街區(qū)到新舊設(shè)施的路程相等，對(duì)總響應(yīng)時(shí)間沒有影響。U1中的街區(qū)到新設(shè)施N的路程比到舊設(shè)施M增加1個(gè)街區(qū)，引起總響應(yīng)時(shí)間增加15Xp1秒，5是U1的事故總頻率。V1中的街區(qū)到新設(shè)施N的路程比到M減少1個(gè)街區(qū)，引起總響應(yīng)時(shí)間減少15XP2秒，P2是V1的事故總頻率。容易看出，只要P2>P1,則移動(dòng)設(shè)施的總效果是總響應(yīng)時(shí)間減少，方案優(yōu)化，原7T案不仇io如果設(shè)U0的事故總頻率為P0,則按照原來的假設(shè)，U2(由Uo,V1組成)中的事故頻率P2+

35、P0大于U1中的事故頻率P1。如果P2+P0比P1大得太多，以至于從P2+P0中減去P0后所得的P2仍大于P1,原來的方案就不是最優(yōu)了。我們證明：當(dāng)X#X時(shí)一定是這樣。先設(shè)P(X)<P/2o(比如本題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)o考慮將設(shè)施從舊位置(x,y)移動(dòng)到新位置(x+1,y),則P(x)就是舊設(shè)施北面的事故總數(shù)，P-P(x+1)就是新設(shè)施南面的事故總數(shù)。既然P(x)<P-P(x+1),新設(shè)施就比舊設(shè)施優(yōu)，舊設(shè)施不優(yōu)。

36、再考慮xX+1的情形,則p(X)<P/2<p(X+1)<P(x-1)<P(x),P(x-1)>P/2>P-P(x),將設(shè)施從(x,y)移到(x-1,y)可以優(yōu)化。除x<X,x>X+1b,x#X的唯一可能是x=X+1,p(X)MP/2Mp(X+1)=p(x)0如果p(X+1)P/2=P/2p(X),WJp(X+1)與p（X）同樣接近P/2,X+1也可以取來作為X,（X+1,丫）與（X,Y）同樣優(yōu)。假設(shè)不是這樣的情況（如本題）,貝Up（x+1）-P/2>P/2-p（X）.P（X）>P-p（x+1）,即（x,y）北面的事故比（X+1,y）南

37、面的事故多,將設(shè)施從（x,y）（即（X+1,y）向北移到（x,y）可以引起優(yōu)化。這就在p（X）WP/2的情況下證明：當(dāng)x#X時(shí)（x,y）一定不是最優(yōu)。對(duì)p（X）P/2的情況，同理可以證明同樣的結(jié)論。同理還可證明：當(dāng)y¥丫時(shí)（x,y）也一定不是最優(yōu)，結(jié)果只剩下（X,Y）才有可能最優(yōu)，因而也就確實(shí)是最優(yōu)?，F(xiàn)在回到原題條件，考慮設(shè)兩個(gè)應(yīng)急設(shè)施的情形，假如按前面所說的算法2,指定了兩個(gè)點(diǎn)Ao,Bo作為應(yīng)急設(shè)施的候選位置，這一組位置是否已經(jīng)最優(yōu)了？如果不是，有什么方法較快地改進(jìn)它，而不要一步一步地試探著前進(jìn)？我們可以先按設(shè)施的兩個(gè)候選位置A°,B。劃定它們的責(zé)任區(qū)Vao,Vbo的范圍

38、，將每個(gè)街區(qū)（按假定（I）或街道上的每個(gè)點(diǎn)（按假定（II）劃給離它最近的設(shè)施的責(zé)任區(qū)。到兩個(gè)設(shè)施的路程相等的，任意劃給一個(gè)責(zé)任區(qū)。然后，在每個(gè)責(zé)任區(qū)內(nèi)可以按前述的“重心法”各找到一個(gè)的最佳位置A,B1。用A1,B1分別取代Ao,B°,即使在不調(diào)整責(zé)任區(qū)的情形下已經(jīng)能夠說明方案被優(yōu)化了。如果AhB1的位置與Ao,Bo不完全相同，責(zé)任區(qū)也可能發(fā)生變化。按設(shè)施的新位置A,B1重新劃定責(zé)任區(qū)。在兩個(gè)新的責(zé)任區(qū)范圍內(nèi)再一次用“重心法”各選一個(gè)新位置。這樣，調(diào)整責(zé)任區(qū)范圍和在每個(gè)責(zé)任區(qū)內(nèi)尋找最優(yōu)位置交替進(jìn)行，每進(jìn)行一次都使方案得到優(yōu)化。這個(gè)過程必定收斂（因?yàn)榉桨覆荒軣o窮地優(yōu)化下去），即設(shè)施位置及

39、責(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的情形類似，仍然不能肯定，很可能與一開始劃定責(zé)任區(qū)范圍的方式有關(guān)。使用重心法時(shí)，還應(yīng)當(dāng)考慮到這樣的情況：如果不改變責(zé)任區(qū)，A,B1在各自的責(zé)任區(qū)內(nèi)當(dāng)然是最優(yōu)位置，一移動(dòng)就會(huì)使總響應(yīng)時(shí)間

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

41、很接近Pi/2,這里Pi是該責(zé)任區(qū)內(nèi)的事故頻率總數(shù)。但要p（X）-P1/2與p（X±1）-F/2（或q（Y）-P1/2與q（Y±1）-R/2）都很接近于0,只有它們符號(hào)相反時(shí)才有可能。也就是說：只考慮（X,Y）向事故多的方向上的移動(dòng)。下面用重心法來計(jì)算本題的最優(yōu)解。由于收斂速度很快，可以用手算實(shí)現(xiàn)，只要第一步的責(zé)任區(qū)劃分得不是太不合理，求出的也的確是最優(yōu)解。先在假定（I）下計(jì)算：考慮到城鎮(zhèn)是長(zhǎng)方形，很自然先用沿東西方向的直線x=5將城鎮(zhèn)分成同樣大的南、北兩塊（各含25個(gè)街區(qū)）U1W1,這樣做的理由是：可以使每塊內(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)A的坐標(biāo)為（2,3）。同理可算出南塊的最優(yōu)點(diǎn)為B1（7,3）O再劃分A1,B1的責(zé)任區(qū)；橫坐標(biāo)為4的四個(gè)街區(qū)的中心離A1,B1的路程相等，劃給A或B都可以。如果劃給A,則就是原來的責(zé)任區(qū)方案U1,M