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