4第17講應(yīng)急設(shè)施的優(yōu)化選址問題數(shù)學(xué)建模(編輯修改稿)
2025-05-01 02:48 本頁面
【文章內(nèi)容簡介】 在計(jì)算非邊界街區(qū)的四條邊的總響應(yīng)時(shí)間時(shí)把它們所分擔(dān)的事故頻率各自集中在它們的中點(diǎn)。相對的兩條邊分擔(dān)的事故頻率相等，在求它們的響應(yīng)時(shí)間之和時(shí)可以用這兩條邊各自的中點(diǎn)到應(yīng)急設(shè)施的行駛時(shí)間的平均值乘上它們的事故頻率之和（即每一個的事故頻率的兩倍）來計(jì)算。但這個平均值就是街區(qū)中心到應(yīng)急設(shè)施的行駛時(shí)間，（想象有穿過街區(qū)中心的東西方向南北方向的道路供行駛）。因此，可以把相對兩邊的事故頻率集中在街區(qū)的中心，從而把整個街區(qū)的事故頻率集中到街區(qū)中心。設(shè)這個街區(qū)的中心的坐標(biāo)為，而這個街區(qū)所屬的應(yīng)急設(shè)施的坐標(biāo)為，則這個街區(qū)周圍的四條街道到的平均行駛時(shí)間就等于 （2）將這一結(jié)果與假定（1）下從到這個街區(qū)救助的行駛時(shí)間（見前面（1）式）相比。換句話說，按假定（1）只要求應(yīng)急車輛到達(dá)街區(qū)的最近的一個街角，而現(xiàn)在相當(dāng)于要求車輛繼續(xù)行駛到街區(qū)的中心（假定存在著可供車輛行駛的穿過該中心的東西、南北兩條道路）。如果在假定（1）下也改為要求車輛行駛到街區(qū)中心，則每一種選址方案的總響應(yīng)時(shí)間增加一個常數(shù)，最短的總響應(yīng)時(shí)間也就增加一個常數(shù)，而方案的優(yōu)劣不會因此改變，原來的最優(yōu)方案仍然最優(yōu)。但這樣一來在兩個假定下對非邊界街區(qū)的總響應(yīng)時(shí)間的計(jì)算方法就完全相同了。唯一有區(qū)別的地方是被責(zé)任區(qū)分界線一分為二的街區(qū)。在假定（I）下是按該街區(qū)中心所在責(zé)任區(qū)將它整個劃歸這個責(zé)任區(qū)。按假定（II）則將街區(qū)分成兩部分，分別屬于兩個責(zé)任區(qū)，這樣可使這個街區(qū)的總響應(yīng)時(shí)間比按假定（I）略小一些。在假定（II）下，如果在計(jì)算時(shí)對所有的街區(qū)也按街區(qū)中心的歸屬將這個街區(qū)全部劃入一個責(zé)任區(qū)，這樣算出來的就是近似的總響應(yīng)時(shí)間，而按這樣的算法得出的最優(yōu)解就是近似的最優(yōu)。而這個近似的最優(yōu)解必定就是假定（I）下的最優(yōu)解（2，3）（6，3），無須重新計(jì)算。在假定（II）下精 確計(jì)算這個方案的總響應(yīng)時(shí)間，與前面用計(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），則每個街區(qū)都整個的在一個責(zé)任區(qū)中，沒有哪個街區(qū)被分割開來分別劃進(jìn)兩個責(zé)任區(qū)；而方案(2,3)，（7,3）卻將5個街區(qū)分割開了，這給應(yīng)急設(shè)施進(jìn)行救助帶來不方便，權(quán)衡利弊，我們得出下面的結(jié)論：按假定（II），方案（2,3），（7,3）比方案（2,3），（6,3）的總響應(yīng)時(shí)間約少1秒鐘，（、）。但考慮到實(shí)施救助的方便起見，寧肯采用方案（2,3），（6,3）。167。3 算法的進(jìn)一步討論以上算法是建立在用計(jì)算機(jī)進(jìn)行窮舉的基礎(chǔ)上，可以稱為：算法1 計(jì)算機(jī)窮舉法。窮舉的方法當(dāng)然可以說是笨辦法，它對一些明顯不優(yōu)的位置仍要一個個去驗(yàn)證，這實(shí)在顯得太笨。但窮舉的辦法也有一個好處，那就是：不用再證明最后答案的最優(yōu)性。這個答案已經(jīng)和所有的別的可能方案都比較過了，比它們都優(yōu)，最優(yōu)性已經(jīng)得到證明。本題的一個特點(diǎn)是需要窮舉的可能方案的數(shù)目不大，用計(jì)算機(jī)進(jìn)行窮舉所花的時(shí)間很少，因而是可行的，也是優(yōu)越的。但假如考慮更一般的城市，街道數(shù)目較多，且應(yīng)急設(shè)施的個數(shù)也可能不止兩個，而是更多，則計(jì)算機(jī)所花時(shí)間將會大大增加。能不能有一種非窮舉的有效算法呢？可以考慮采用如下的方法。算法2 逐次改進(jìn)法：它的基本想法是先從一個初始的方案（不一定最優(yōu)）出發(fā)，逐步加以改進(jìn)，直到得到一個不能再改進(jìn)的方案，就有可能是最優(yōu)方案，具體作法是：先任選兩個位置（坐標(biāo)為整數(shù)的點(diǎn)）作為應(yīng)急設(shè)施的最初的選址。比如可選，即選這個城鎮(zhèn)的西北角、東南角分別作為。（當(dāng)然也可一開始憑直覺將選得更好一些，更快地達(dá)到最后結(jié)果）。試考慮將設(shè)施向東、西、南或北四個方向各移動一個街區(qū)（即將的橫坐標(biāo)或縱坐標(biāo)增加或減少一個單位），暫時(shí)不動，看總響應(yīng)時(shí)間如何變化。（當(dāng)然，如果在某個方向上已經(jīng)不可能移動，即已經(jīng)處于城鎮(zhèn)的邊界，就不考慮這一方向上的移動）。如果向某一方向上的移動引起總響應(yīng)時(shí)間的增加（或不變），這一方向不是好方向，再換另一個方向試試。如果向某一方向的移動引起總響應(yīng)時(shí)間的減少，這一方向就是好方向，將向這一方向移動一個街區(qū)（從移到），以的新位置作為出發(fā)點(diǎn)重新向各個方向試探。如果向四個方向的移動都不能縮短總響應(yīng)時(shí)間，則將固定不動，再試的移動，直到向四個方向上的移動都不能縮短總響應(yīng)時(shí)間，再考慮的移動。這樣將兩個設(shè)施輪流移動以優(yōu)化方案，直到不能再優(yōu)化為止：即中任何一個向任何方向的移動都不能使總響應(yīng)時(shí)間再縮短。這時(shí)這個優(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í)間作為兩個應(yīng)急設(shè)施位置的四個坐標(biāo)的函數(shù)，用逐次改進(jìn)法所得到的是函數(shù)的極小值點(diǎn)，但不一定是最小值點(diǎn)。如果能證明這個函數(shù)只有一個極小值點(diǎn)，它也就是最小值點(diǎn)。但這一般是不成立的，即使成立也是很難證明的。比如本題。如果從（4,0），（4,5）這兩點(diǎn)出發(fā)，就會發(fā)現(xiàn)最后收斂于（4,1），（5,4）這兩個位置，不是最優(yōu)方案。（按假定（I）的算法，方案（4,1），（5,4）的總響應(yīng)時(shí)間為3355秒，而方案（2,3），（6,3）和（4,1），（5,4）。由于選擇的初始位置不同，逐次改進(jìn)后分別收斂于這兩組位置。初始的兩個點(diǎn)的橫坐
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1