服務(wù)網(wǎng)點(diǎn)選址的數(shù)學(xué)模型2013(共12頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上青島科技大學(xué)第八屆“校長杯”數(shù)學(xué)知識競賽暨2013年全國研究生、大學(xué)生數(shù)學(xué)建模競賽選拔賽題 目 服務(wù)網(wǎng)點(diǎn)選址的數(shù)學(xué)模型 摘 要 隨著城鄉(xiāng)的迅速發(fā)展，需要為鄉(xiāng)鎮(zhèn)村落之間建立服務(wù)網(wǎng)點(diǎn)，以提供各種服務(wù)，服務(wù)網(wǎng)點(diǎn)的位置選擇的問題具有一定的意義。本文根據(jù)各個自然村的位置及人口分布狀況，采用無約束優(yōu)化、牛頓法、動態(tài)規(guī)劃等數(shù)學(xué)方法，建立了服務(wù)網(wǎng)點(diǎn)選址的數(shù)學(xué)模型，利用Matlab、Lingo、Excel等軟件進(jìn)行求解。對于問題一，本文的目標(biāo)是使更多的人民群眾得到更快捷的服務(wù)，將其目標(biāo)轉(zhuǎn)換為數(shù)學(xué)問題，由于不考慮交通問題，距離短，時間就短，人口數(shù)作為權(quán)重，人口多，相應(yīng)的權(quán)重大。以服務(wù)網(wǎng)點(diǎn)

2、到各個自然村之間的距離平方與權(quán)重乘積的總和作為目標(biāo)函數(shù)，即，建立了數(shù)學(xué)模型，利用無約束優(yōu)化的數(shù)學(xué)方法，應(yīng)用Matlab求得服務(wù)網(wǎng)點(diǎn)的最佳位置為。對于問題二，為將問題簡化，首先將12個自然村進(jìn)行分割，每個服務(wù)網(wǎng)點(diǎn)有固定的服務(wù)村落，對于分割方法可以有不同的分法，但是合理的分法使得兩個服務(wù)網(wǎng)點(diǎn)的服務(wù)人口盡量均衡，然后根據(jù)人口加倍后的人口數(shù)目，對兩個部分分別建立同問題一相同的目標(biāo)函數(shù)，分別求得兩個服務(wù)網(wǎng)點(diǎn)的坐標(biāo)。本模型采取了兩種分割方法，方法一為：自然村1、2、3、4、7、10為一組，此時求得的兩個網(wǎng)點(diǎn)坐標(biāo)為：和，其中；方法二為：自然村1、3、5、6、7、8、9為一組，此時求得的兩個網(wǎng)點(diǎn)的坐標(biāo)為：和，

3、其中，比較兩種分割方法，方法一更合理。 對于問題三，從其中一個服務(wù)網(wǎng)點(diǎn)出發(fā)，到各村分發(fā)銷售廣告，回到另一個服務(wù)網(wǎng)點(diǎn)，最佳的路線即用時最短的線路，用時最短可以轉(zhuǎn)化為距離最短，針對這個問題，采用動態(tài)優(yōu)化的數(shù)學(xué)方法，根據(jù)第二問得到的網(wǎng)點(diǎn)1和網(wǎng)點(diǎn)2以及各個自然村的坐標(biāo)等信息，將此過程分為13個階段，建立最佳行走路線的數(shù)學(xué)模型，利用Lingo編程求取得到最佳路線為： ，此時的最短距離為41.54184。關(guān)鍵詞：無約束優(yōu)化 牛頓法 動態(tài)規(guī)劃 Matlab Lingo專心-專注-專業(yè)一、問題重述某鄉(xiāng)鎮(zhèn)由12個主要的自然村組成，每個自然村的位置（用平面坐標(biāo)x,y表示，距離單位：km）和自然村的人口數(shù)（R）如下

4、表所示。 123456789101112X08.200.505.700.772.874.432.580.729.763.195.55Y00.504.905.006.498.763.269.329.963.167.207.88R6001000800140012007006008001000120010001100表1 12個自然村的位置及人口試根據(jù)需要解決如下問題：1 目前準(zhǔn)備在該鄉(xiāng)鎮(zhèn)建一個服務(wù)網(wǎng)點(diǎn)為各村提供各種服務(wù)，那么服務(wù)網(wǎng)點(diǎn)應(yīng)該建在何處？2 假設(shè)各村人口增長了一倍，需要建兩個服務(wù)網(wǎng)點(diǎn)，試確定其位置。3 從一個服務(wù)網(wǎng)點(diǎn)出發(fā)，到每個村發(fā)放銷售廣告，最后回到另一個服務(wù)網(wǎng)點(diǎn)，試確定最佳行

5、走路線。二、問題分析2.1問題一的分析針對問題一，為了達(dá)到使更多的人民在短時間內(nèi)得到服務(wù)的目的，將其轉(zhuǎn)化為數(shù)學(xué)問題，由于不考慮交通問題，距離短，時間就短，人口數(shù)可以作為權(quán)重，人口多，相應(yīng)的權(quán)重大。以服務(wù)網(wǎng)點(diǎn)到各個自然村之間的距離平方與權(quán)重乘積的總和作為目標(biāo)函數(shù)，建立了數(shù)學(xué)模型，利用無約束優(yōu)化的數(shù)學(xué)方法，應(yīng)用Matlab求解。 2.2 問題二的分析針對問題二，為了簡化問題，首先將12個自然村進(jìn)行分割，每個服務(wù)網(wǎng)點(diǎn)有固定的服務(wù)村落，對于分割方法可以有不同的分法，但是合理的分法使得兩個服務(wù)網(wǎng)點(diǎn)的服務(wù)人口盡量均衡，然后根據(jù)人口加倍后的人口數(shù)目，在兩個部分分別建立同問題一相同的目標(biāo)函數(shù)，分別求得兩個服務(wù)

6、網(wǎng)點(diǎn)的坐標(biāo)。本模型擬采取兩種分割方法，通過比較目標(biāo)函數(shù)的大小，對兩種方法進(jìn)行取舍。 2.3 問題三的分析針對問題三，從其中一個服務(wù)網(wǎng)點(diǎn)出發(fā)，到各村分發(fā)銷售廣告，回到另一個服務(wù)網(wǎng)點(diǎn)，最佳的路線即用時最短的線路，用時最短可以轉(zhuǎn)化為距離最短，針對這個問題，采用動態(tài)優(yōu)化的數(shù)學(xué)方法，由第二問得到的網(wǎng)點(diǎn)以及各個自然村的坐標(biāo)，將行走的過程分成13個階段，建立最優(yōu)路線的數(shù)學(xué)模型，利用Lingo編程求取最佳路線。三、模型假設(shè)與約定Ø 1. 各個自然村之間的道路四通八達(dá)，任意兩點(diǎn)之間可以直線相通，即服務(wù)網(wǎng)點(diǎn)到各自然村之間的距離為兩點(diǎn)間的距離；Ø 2. 各個自然村的人口年齡性別比重相似，各服務(wù)站

7、可以給予類似的服務(wù)，不會出現(xiàn)自然村之間的年齡性別差別比較大，使得服務(wù)站在某一方面的服務(wù)比較繁忙；Ø 3. 在理想情況下進(jìn)行選址，不考慮自然災(zāi)害；Ø 4. 人口增加一倍后，人口的年齡性別比例依舊不發(fā)生變化。四、符號說明自然村的坐標(biāo)自然村的人口數(shù)在總?cè)丝谥械臋?quán)重問題1服務(wù)網(wǎng)點(diǎn)的坐標(biāo)問題2方法一服務(wù)網(wǎng)點(diǎn)1的坐標(biāo)問題2方法一服務(wù)網(wǎng)點(diǎn)2的坐標(biāo)問題2方法二服務(wù)網(wǎng)點(diǎn)1的坐標(biāo)問題2方法二服務(wù)網(wǎng)點(diǎn)2的坐標(biāo)目標(biāo)函數(shù)五、模型建立與求解5.1 問題一的模型建立與求解針對問題一，要使更多的人民在短時間內(nèi)得到服務(wù)，將其轉(zhuǎn)化為數(shù)學(xué)問題。由于不考慮交通問題，距離短，時間就短，人口數(shù)可以作為權(quán)重，人口多，相

8、應(yīng)的權(quán)重大。表2為12個自然村的人口比重：各村編號123456X08.20.55.70.772.87Y00.54.956.498.76R600100080014001200700權(quán)重0.0.0.0.122810.105260.各村編號789101112X4.432.580.729.763.195.55Y3.269.329.963.167.27.88R6008001000120010001100權(quán)重0.0.0.0.105260.0.表2 12個自然村的人口權(quán)重要綜合考慮到距離與人口對服務(wù)網(wǎng)點(diǎn)選擇的影響，本文采用加權(quán)求和的方法，即以服務(wù)網(wǎng)點(diǎn)到各個自然村之間的距離平方與權(quán)重乘積的總和作為目標(biāo)函數(shù)。利

9、用無約束優(yōu)化的數(shù)學(xué)方法，采用牛頓法，應(yīng)用Matlab編寫程序求解， 得到最優(yōu)解為：服務(wù)網(wǎng)點(diǎn)的坐標(biāo)為：，具體位置如圖1所示：圖1 問題1服務(wù)網(wǎng)點(diǎn)示意圖由上圖可以看出，服務(wù)網(wǎng)點(diǎn)大致位于中間，由于左上部分的村子密集人口較多，服務(wù)網(wǎng)點(diǎn)稍向左上偏移，所以求出的服務(wù)網(wǎng)點(diǎn)坐標(biāo)是符合題目要求的。5.2 問題二的模型建立與求解針對問題二，為了簡化問題，首先將12個自然村進(jìn)行分割，每個服務(wù)網(wǎng)點(diǎn)有固定的服務(wù)村落，對于分割方法可以有不同的分法，但是合理的分法使得兩個服務(wù)網(wǎng)點(diǎn)的服務(wù)人口盡量均衡，本文采用了兩種分法：方法一：自然村1、2、3、4、7、10為一組，對應(yīng)于服務(wù)網(wǎng)點(diǎn)1； 自然村5、6、8、9、11、12為一組，

10、對應(yīng)于服務(wù)網(wǎng)點(diǎn)2。方法二：自然村1、3、5、6、7、8、9為一組，對應(yīng)于服務(wù)網(wǎng)點(diǎn)1； 自然村2、4、10、11、12為一組，對應(yīng)于服務(wù)網(wǎng)點(diǎn)2。具體分法如圖2所示：圖2 兩種分割方法示意圖Ø 5.2.1 分割方法一人口翻倍后，對于兩個部分的自然村人口分別進(jìn)行權(quán)重分析，具體的權(quán)重如表3所示：部分一編號1234710總和人口12002000160028001200240011200權(quán)重0.0.0.0.250.0.1部分二編號56891112總和人口120070080010001000110011600比重0.0.120690.0.0.0.1表3 方法一兩部分的人口比重利用問題一的方法，建立

11、目標(biāo)函數(shù)為：通過編程解得最優(yōu)解為：所以服務(wù)網(wǎng)點(diǎn)1的坐標(biāo)為,服務(wù)網(wǎng)點(diǎn)2的坐標(biāo)為 ,。在坐標(biāo)系中，兩個服務(wù)網(wǎng)點(diǎn)的位置如圖3所示：圖3 分割方法1得到的服務(wù)網(wǎng)點(diǎn)位置示意圖Ø 5.2.2 分割方法二利用同分割方法一相同的方法，首先對各村人數(shù)進(jìn)行分析， 部分一編號24101112總和人口2000280024002000220011400權(quán)重0.0.0.0.0.1部分二編號1356789總和人口120016002400140012001600200011400權(quán)重0.0.0.0.0.0.0.1表4 方法二兩部分的人口比重然后建立目標(biāo)函數(shù)：求得最優(yōu)解為：服務(wù)網(wǎng)點(diǎn)1坐標(biāo)為，網(wǎng)點(diǎn)2坐標(biāo)為，。兩個網(wǎng)點(diǎn)的

12、位置如圖4所示：圖4 分割方法2得到的網(wǎng)點(diǎn)位置示意圖結(jié)合上述兩種分割方法，由于方法一的更小，所以，方法一要更加合理。5.3 問題三的模型建立與求解針對問題三，從其中一個服務(wù)網(wǎng)點(diǎn)出發(fā)，到各村分發(fā)銷售廣告，回到另一個服務(wù)網(wǎng)點(diǎn)，最佳的路線即用時最短的線路，用時最短可以轉(zhuǎn)化為距離最短，針對這個問題，根據(jù)第二問求得的兩個網(wǎng)點(diǎn)的坐標(biāo)：網(wǎng)點(diǎn)1：；網(wǎng)點(diǎn)2：，再結(jié)合各個自然村的坐標(biāo)，充分考慮網(wǎng)點(diǎn)與自然村、自然村與自然村之間的距離， 利用Matlab編寫程序，求得各點(diǎn)之間的距離，以下是各個自然村以及網(wǎng)點(diǎn)之間的距離的平方（截取部分，完整的見附錄5）：編號123456789101112X08.20.55.70.772

13、.874.432.580.729.763.195.55Y00.54.956.498.763.269.329.963.167.27.88網(wǎng)點(diǎn)172.93689.83914.8519.5336.02410.4654927.1931.39586.80876.221.2438.8385684.97596.63620.51622.1479.5629032.6840.39776.062578.8322.5367.9568893.519109.3823.86328.39711.2850.397740.14603.869289.4984.866510.894999.72145.4425.65249.40212

14、.0436.062558.6543.86920127.9613.71927.655542.71391.0852.60126.52509.562923.82911.28512.04391.9096.360524.78表5 各點(diǎn)之間的距離然后將此過程分為13個階段，采用動態(tài)規(guī)劃的數(shù)學(xué)方法，利用Lingo編寫程序，得到最優(yōu)化的路徑為：（如圖5所示）服務(wù)網(wǎng)點(diǎn)16號村8號村9號村5號村11號村12號村3號村1號村2號村10號村4號村7號村服務(wù)網(wǎng)點(diǎn)2服務(wù)網(wǎng)點(diǎn)19號村圖 5 最佳行走路線此時計算得到最佳行走路線各階段行走的距離為：（如表6所示）各階段終點(diǎn)689511123距離平方0.465490.39773

15、.869212.0436.36056.03234.383距離0.0.1.3.2.2.5.各階段終點(diǎn)121047網(wǎng)點(diǎn)2總和距離平方24.2667.499.509219.8694.64051.2407距離4.8.215233.4.2.1.41.54184表6 各階段距離由上表可以計算出最佳路線總的距離為：41.54184。六、模型的評價與改進(jìn)6.1模型的優(yōu)點(diǎn)Ø 1. 本模型對于實(shí)際問題進(jìn)行了適當(dāng)?shù)募僭O(shè)，簡化了模型的建立以及問題的求解；Ø 2. 通過多種方法進(jìn)行求解，二者比較，更加增加了模型的正確性與可靠性；Ø 3. 本題根本上主要利用了一種思想作為主要解題思路，并使所

16、有問題得到了較好的解決，整體上提高了模型的內(nèi)在連貫性、延展性和解題思路的簡明性與可讀性；Ø 4. 模型的計算采用專業(yè)的數(shù)學(xué)軟件，可信度較高。6.2 模型的缺點(diǎn)² 1. 模型對于復(fù)雜的實(shí)際問題進(jìn)行了簡化，在計算網(wǎng)點(diǎn)到村落的距離時直接采用了兩點(diǎn)間的距離，可能有一定的偏差；² 2. 在問題二中，將12個自然村進(jìn)行了分割，兩個網(wǎng)點(diǎn)只能服務(wù)于特定的村落，但是在實(shí)際情況中，兩個網(wǎng)點(diǎn)的服務(wù)不會嚴(yán)格分割開來；6.3 模型的改進(jìn)由于問題本身的復(fù)雜度很高，所以3個問題的模型都做了數(shù)學(xué)處理，首先使用建立的模型得到網(wǎng)點(diǎn)位置，再由網(wǎng)點(diǎn)與各村子之間的距離得到分發(fā)銷售廣告的最佳路線，這種做法雖

17、然給解答帶來了很大的方便，但是卻使精度受到了一定的影響雖然這種影響很小，所以模型應(yīng)盡可能的向提高精度方面做適當(dāng)改進(jìn)，以利于實(shí)際問題的解決。參考文獻(xiàn)：1 姜啟源，數(shù)學(xué)模型（第二版）. 北京：高等教育出版社，2002，6.2 費(fèi)培之， 數(shù)學(xué)模型實(shí)用教程， 成都， 四川大學(xué)出版社， 1998附錄附錄1：問題1求取服務(wù)網(wǎng)點(diǎn)的程序f='(x(1)2+(x(2)2)*0.+(x(1)-8.2)2+(x(2)-0.5)2)*0.+(x(1)-0.5)2+(x(2)-4.9)2)*0.+(x(1)-5.7)2+(x(2)-5)2)*0.12281+(x(1)-0.77)2+(x(2)-6.49)2)*

18、0.10526+(x(1)-2.87)2+(x(2)-8.76)2)*0.+(x(1)-4.43)2+(x(2)-3.26)2)*0.+(x(1)-2.58)2+(x(2)-9.32)2)*0.+(x(1)-0.72)2+(x(2)-9.96)2)*0.+(x(1)-9.76)2+(x(2)-3.16)2)*0.10526+(x(1)-3.19)2+(x(2)-7.2)2)*0.+(x(1)-5.55)2+(x(2)-7.88)2)*0.'x,fval,exitflag,output=fminsearch(f, 0 0)附錄2：問題1圖像繪制程序x=08.200.505.700.772

19、.874.432.580.729.763.195.55;y=00.504.905.006.498.763.269.329.963.167.207.88;plot(x,y,'rx','LineWidth',5)xlabel('x')ylabel('y')title('自然村位置')grid;hold onplot(4.032,5.647 ,'b*','LineWidth',10)hold off附錄3：問題2服務(wù)網(wǎng)點(diǎn)求取及圖像繪制1. 方法一網(wǎng)點(diǎn)1：f='(x(1)-0.77)

20、2+(x(2)-6.49)2)*0.+(x(1)-2.87)2+(x(2)-8.76)2)*0.+(x(1)-2.58)2+(x(2)-9.32)2)*0.+(x(1)-0.72)2+(x(2)-9.96)2)*0.+(x(1)-3.19)2+(x(2)-7.2)2)*0.+(x(1)-5.55)2+(x(2)-7.88)2)*0.'x,fval,exitflag,output=fminsearch(f, 0 0)網(wǎng)點(diǎn)2：f='(x(1)2+x(2)2)*0.+(x(1)-8.2)2+(x(2)-0.5)2)*0.+(x(1)-0.5)2+(x(2)-4.9)2)*0.+(x(

21、1)-5.7)2+(x(2)-5)2)*0.25+(x(1)-4.43)2+(x(2)-3.26)2)*0.+(x(1)-9.76)2+(x(2)-3.16)2)*0.'x,fval,exitflag,output=fminsearch(f, 0 0)圖像繪制：x=08.200.505.700.772.874.432.580.729.763.195.55;y=00.504.905.006.498.763.269.329.963.167.207.88;plot(x,y,'rx','LineWidth',5)xlabel('x')ylabel

22、('y')title('分割法1')grid;hold onplot(2.5883,8.1386,'b*','LineWidth',10)plot(5.5268,3.0657,'g*','LineWidth',10)hold off2. 方法二網(wǎng)點(diǎn)1：f='(x(1)2+x(2)2)*0.+(x(1)-0.5)2+(x(2)-4.9)2)*0.+(x(1)-0.77)2+(x(2)-6.49)2)*0.+(x(1)-2.87)2+(x(2)-8.76)2)*0.+(x(1)-4.43)2+(

23、x(2)-3.26)2)*0.+(x(1)-2.58)2+(x(2)-9.32)2)*0.+(x(1)-0.72)2+(x(2)-9.96)2)*0.'x,fval,exitflag,output=fminsearch(f, 0 0)網(wǎng)點(diǎn)2：f='(x(1)2+x(2)2)*0.+(x(1)-0.5)2+(x(2)-4.9)2)*0.+(x(1)-0.77)2+(x(2)-6.49)2)*0.+(x(1)-2.87)2+(x(2)-8.76)2)*0.+(x(1)-4.43)2+(x(2)-3.26)2)*0.+(x(1)-2.58)2+(x(2)-9.32)2)*0.+(x(

24、1)-0.72)2+(x(2)-9.96)2)*0.'x,fval,exitflag,output=fminsearch(f, 0 0)圖像繪制：x=08.200.505.700.772.874.432.580.729.763.195.55;y=00.504.905.006.498.763.269.329.963.167.207.88;plot(x,y,'rx','LineWidth',5)xlabel('x')ylabel('y')title('分割法2')grid;hold onplot(6.524,4

25、.7649,'b*','LineWidth',10)plot(1.5395,6.5284,'g*','LineWidth',10)hold off附錄4：各點(diǎn)之間的距離計算程序x=08.200.505.700.772.874.432.580.729.763.195.55;y=00.504.905.006.498.763.269.329.963.167.207.88;for i=1:12 z(i)=(2.5883-x(i)2+(8.1386-y(i)2end附錄5：各點(diǎn)之間的距離編號123456789101112X08.20.55.70.772.874.432.580.729.763.195.55Y00.54.956.498.763.269.329.963.167.27.88網(wǎng)點(diǎn)172.93689.83914.8519.5336.02410.4654927.1931.39586.80876.221.2438.8385684.97596.63