數(shù)學(xué)建模-鋪路問(wèn)題的最優(yōu)化模型

1、精選優(yōu)質(zhì)文檔-傾情為你奉上鋪路問(wèn)題的最優(yōu)化模型摘 要本文采用了兩種方法，一種是非線性規(guī)劃從而得出最優(yōu)解，另一種是將連續(xù)問(wèn)題離散化利用計(jì)算機(jī)窮舉取最優(yōu)的方法。根據(jù)A地與B地之間的不同地質(zhì)有不同造價(jià)的特點(diǎn)，建立了非線性規(guī)劃模型和窮舉取最優(yōu)解的模型，解決了管線鋪設(shè)路線花費(fèi)最小的難題。問(wèn)題一：在本問(wèn)題中，我們首先利用非線性規(guī)劃模型求解，我們用迭代法求出極小值（用Matlab實(shí)現(xiàn)），計(jì)算結(jié)果為總費(fèi)用最小為748.6244萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為15.6786km，3.1827 km，2.1839 km，5.8887km，13.0661km。然后，我們又用窮舉法另外建立了一個(gè)模型，

2、采用C語(yǔ)言實(shí)現(xiàn)，所得最優(yōu)解為最小花費(fèi)為748.萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為15.70km,3.20km,2.20km,5.90km,13.00km。 問(wèn)題二：本問(wèn)題加進(jìn)了一個(gè)非線性的約束條件來(lái)使轉(zhuǎn)彎處的角度至少為160度，模型二也是如此。非線性規(guī)劃模型所得計(jì)算結(jié)果為最小花費(fèi)為750.6084萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為14.4566km,4.3591km,2.5984km,6.5387km,12.0472km。遍歷模型所得最優(yōu)解為最小花費(fèi)為750.萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為14.10km,4.30km, 2.70km,6.70km,

3、12.20km。問(wèn)題三：因?yàn)楣芫€一定要經(jīng)過(guò)一確定點(diǎn)P，我們將整個(gè)區(qū)域依據(jù)P點(diǎn)位置分成兩部分，即以A點(diǎn)正東30km處為界，將沙土層分成兩部分。非線性規(guī)劃模型最小花費(fèi)為752.6432萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為21.2613km,3.3459km,2.2639km,3.1288km,2.4102km,7.5898km。遍歷模型最小花費(fèi)為752.萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為21.30km,3.30km,2.30km,3.10km,2.40km,7.60km。關(guān)鍵詞：非線性規(guī)劃 逐點(diǎn)遍歷 窮舉法一問(wèn)題重述準(zhǔn)備在A地與B地之間修建一條地下管線，B地位于A地正南面

4、26km和正東40km交匯處，它們之間有東西走向巖石帶。地下管線的造價(jià)與地質(zhì)特點(diǎn)有關(guān)，下圖給出了整個(gè)地區(qū)的大致地質(zhì)情況，顯示可分為三條沿東西方向的地質(zhì)帶，其寬度分別為：沙土地質(zhì)帶寬C1，C5；沙石地質(zhì)帶寬C2；沙石土地質(zhì)帶寬：C4；巖石地質(zhì)帶寬C3。在給定三種地質(zhì)條件上每千米的修建費(fèi)用的情況如下：地質(zhì)條件沙土沙石土沙石巖石費(fèi)用(萬(wàn)元/千米)12161828試解決以下幾個(gè)問(wèn)題：(1) 圖中直線AB顯然是路徑最短的，但不一定最便宜；而路徑ARSB過(guò)巖石和沙石的路徑最短，但是否是最好的路徑呢？試建立一個(gè)數(shù)學(xué)模型，確定最便宜的管線鋪設(shè)路線。（若C1=6，C2=4，C3=5，C4=6，C5=5，確定最便

5、宜的管線鋪設(shè)路線。）(2) 鋪設(shè)管線時(shí)，如果要求管線轉(zhuǎn)彎時(shí)，角度至少為，確定最便宜的管線鋪設(shè)路線。(3) 鋪設(shè)管線時(shí)，如果要求管線必須通過(guò)位于沙石地質(zhì)帶或巖石地質(zhì)帶中的某一已知點(diǎn)P（位于A地正南面18km和正東30km交匯處）時(shí)，確定最便宜的鋪設(shè)路線。二.模型假設(shè)1、修建費(fèi)用僅與管線長(zhǎng)度和不同地質(zhì)的造價(jià)有關(guān)，不含其他費(fèi)用；2、在無(wú)特殊要求情況下，管線可以向任意方向延伸；3、不考慮管線寬度；4、所有管線都鋪設(shè)在同一水平面上；三.符號(hào)說(shuō)明 為修建總費(fèi)用 為管線與沙土層中東西方向上的投影長(zhǎng)度 為管線與沙石層中東西方向上的投影長(zhǎng)度 為管線與巖石層中東西方向上的投影長(zhǎng)度 為管線與沙石土層中東西方向上的投

6、影長(zhǎng)度（在問(wèn)題三中指在過(guò)P點(diǎn)的東西方向的直線上的P點(diǎn)以西的投影長(zhǎng)度） 為管線與沙土層中東西方向上的投影長(zhǎng)度（在問(wèn)題三中指在過(guò)P點(diǎn)的東西方向的直線上的P點(diǎn)以東的投影長(zhǎng)度） 為管線與沙土層中東西方向上的投影長(zhǎng)度 為沙土層每千米的修建費(fèi)用 為沙石層每千米的修建費(fèi)用 為巖石層每千米的修建費(fèi)用 為沙石土層每千米的修建費(fèi)用 為沙土層每千米的修建費(fèi)用(在問(wèn)題三中指在沙石土層每千米的修建費(fèi)用) 為問(wèn)題三中沙土層每千米的修建費(fèi)用 在問(wèn)題一、二中指沙石土層的寬度，在問(wèn)題三中指沙石土層P點(diǎn)以上的半層的寬度 在問(wèn)題一、二中指沙石土層的寬度，在問(wèn)題三中指沙石土層P點(diǎn)以下的半層的寬度 問(wèn)題三中最下面的沙土層的寬度四.問(wèn)題

7、分析41 問(wèn)題一: 本問(wèn)題主要圍繞由A點(diǎn)到B點(diǎn)鋪設(shè)管線展開(kāi)，要求花費(fèi)最少。根據(jù)不同地質(zhì)條件的花費(fèi)，確定在某一土層中鋪設(shè)管線的長(zhǎng)度。我們采用了兩種方法求得最少的花費(fèi)，分別為非線性規(guī)劃模型和逐點(diǎn)遍歷模型。411 方案一我們首先利用非線性規(guī)劃求解，可以得出一個(gè)關(guān)于工程總造價(jià)的目標(biāo)函數(shù)f(x)，而且可知f(x)在整個(gè)區(qū)域連續(xù)且可微，f(x)符合在某一點(diǎn)有局部極小點(diǎn)的條件。因此我們用迭代法求出極小值（用Matlab實(shí)現(xiàn)），我們分別選用了幾組不同的初始值來(lái)保證所得到的極小值也是整個(gè)區(qū)域上的最小值。412 方案二 我們又用窮舉法另外建立了一個(gè)模型，用來(lái)確保模型一的結(jié)果是最小值，采用C語(yǔ)言實(shí)現(xiàn)，我們先在每?jī)煞N

8、不同地質(zhì)間的交界線上每隔0.1km確定一個(gè)點(diǎn)，然后每條交界線都任取一點(diǎn)，連線，得出一條路徑。之后將每一條可能的路徑都遍歷一遍，將最小值和對(duì)應(yīng)的點(diǎn)保存，得出結(jié)果。42 問(wèn)題二 本問(wèn)題與問(wèn)題一相比，增加了約束條件“要求管線轉(zhuǎn)彎時(shí)，角度至少為”，我們?cè)趩?wèn)題一所建立的兩種模型的基礎(chǔ)上均增加相應(yīng)約束條件，通過(guò)求出管線轉(zhuǎn)彎處的管線角度的正切值，并利用反正切函數(shù)得出管線角度，從而對(duì)管線的鋪設(shè)方向加以限制，得出最少花費(fèi)的管線鋪設(shè)線路。43 問(wèn)題三 本問(wèn)題要求鋪設(shè)管線一定要經(jīng)過(guò)一確定點(diǎn)P，因此可以將此問(wèn)題分為兩步，即從A到P的路徑為第一步，從P到B的路徑為第二步。因?yàn)閺腁到P的路徑選擇及其花費(fèi)與從P到B的路徑選

9、擇及其花費(fèi)無(wú)關(guān)，所以求出第一步從A到P的最優(yōu)解，以及第二步求從P到B的最優(yōu)解，這兩的最優(yōu)解之和便為整個(gè)管線鋪設(shè)的最優(yōu)解。五.模型建立與求解51 問(wèn)題一511 方案一.根據(jù)題意，在第個(gè)土層中的管線長(zhǎng)度為所以，在該層中的修建花費(fèi)為則總花費(fèi)為因此得到目標(biāo)函數(shù) 然后所要修建的地區(qū)為A地正南面26km和正東40km所表示的區(qū)域，在每個(gè)土層中管線在東西方向的投影長(zhǎng)度應(yīng)大于0km小于40km，且所有土層中管線在東西方向上的投影長(zhǎng)度之和小于40km，因此可確定約束條件： 運(yùn)用MATLAB軟件編程，得到計(jì)算結(jié)果為總費(fèi)用最小為748.6244萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為15.6786km，3.

10、1827 km，2.1839 km，5.8887km，13.0661km。 512方案二先在每?jī)煞N不同土層的交界線上每隔0.1km確定一個(gè)點(diǎn)，然后在每條交界線上都任取一點(diǎn)，并連線，得出一條可能路徑。再將每一條可能的路徑按公式逐一計(jì)算花費(fèi)，找到花費(fèi)的最小值和其對(duì)應(yīng)的點(diǎn)，確定最優(yōu)路徑。在此方案中，采用C語(yǔ)言編程進(jìn)行遍歷，所得最優(yōu)解為最小花費(fèi)為748.萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為15.70km,3.20km,2.20km,5.90km,13.00km。52 問(wèn)題二 本題也為確定最便宜的管線鋪設(shè)路線，所以與問(wèn)題一有相同的目標(biāo)函數(shù)及約束條件：;根據(jù)本題中所要求的管線轉(zhuǎn)彎角度大于，利用

11、管線在各土層中在東西方向上的投影長(zhǎng)度與相應(yīng)土層寬度得出管線轉(zhuǎn)彎所形成的角的正切值，即，再利用反正切函數(shù)算出具體角度。由此得到新的約束條件： ;在問(wèn)題一建立的模型的基礎(chǔ)上，依據(jù)本題中新增非線性約束條件，建立新的模型，利用MATLAB編程，所得計(jì)算結(jié)果為最小花費(fèi)為750.6084萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為14.4566km,4.3591km,2.5984km,6.5387km,12.0472km。利用相同的約束條件，利用C語(yǔ)言編程遍歷，所得最優(yōu)解為最小花費(fèi)為750.萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為14.10km,4.30km, 2.70km,6.70km,12

12、.20km。53 問(wèn)題三根據(jù)本題中管線必須通過(guò)已知點(diǎn)P（位于A地正南面18km和正東30km交匯處）的約束條件，我們將整個(gè)區(qū)域依據(jù)P點(diǎn)位置分成兩部分，即以A點(diǎn)正東30km處為界，將沙土層分成兩部分，使整個(gè)修建區(qū)域變成6個(gè)土層。在問(wèn)題一所建立的模型上加以改進(jìn)，使目標(biāo)函數(shù)變?yōu)椋翰⒓s束條件改為：;利用非線性規(guī)劃模型，MATLAB編程，所得最優(yōu)解為:最小花費(fèi)為752.6432萬(wàn)元，管線在各土層中在東西方向上的投影長(zhǎng)度分別為21.2613km,3.3459km,2.2639km,3.1288km,2.4102km,7.5898km利用遍歷模型，C語(yǔ)言編程，所得最優(yōu)解為：最小花費(fèi)為752.萬(wàn)元，管線在各

13、土層中在東西方向上的投影長(zhǎng)度分別為21.30km,3.30km,2.30km,3.10km,2.40km,7.60km。六.模型的評(píng)價(jià)與改進(jìn)對(duì)于模型一，存在的缺點(diǎn)是用Matlab中的fmincon函數(shù)所求最優(yōu)解可能只是局部最優(yōu)解，必須代入幾組不同的初始迭代值，來(lái)確定所求解為全局最優(yōu)解，但仍有可能遺漏。對(duì)于模型二，缺點(diǎn)是精度不夠小，當(dāng)精度取到0.1時(shí)，計(jì)算機(jī)要用幾分鐘才能得出結(jié)果，精度更小時(shí)所需時(shí)間更長(zhǎng)，而且在問(wèn)題二中，模型二因?yàn)榫忍投^(guò)了最優(yōu)路徑，所以與模型一所得結(jié)果有一定差距。但模型二的結(jié)果可用于檢驗(yàn)?zāi)Ｐ鸵凰媒Y(jié)果是否為最優(yōu)解。 附 件附件一：?jiǎn)栴}一的Matlab語(yǔ)言源代碼：先建立目標(biāo)

14、函數(shù)的M文件：function f=fun(x);f=12*sqrt(x(1)2+36)+18*sqrt(x(2)2+16)+28*sqrt(x(3)2+25)+16*sqrt(x(4)2+36)+12*sqrt(x(5)2+25)主程序：x0=0;0;0;0;0;A=1 0 0 0 0;0 1 0 0 0;0 0 1 0 0;0 0 0 1 0;0 0 0 0 1;b=40 40 40 40 40;Aeq=1 1 1 1 1;beq=40;x,z=fmincon(fun,x0,A,b,Aeq,beq)運(yùn)算結(jié)果：x = 15.6786 3.1827 2.1839 5.8887 13.0661

15、z = 748.6244附件二：?jiǎn)栴}一的C語(yǔ)言源代碼：#include#include#define JD 0.1 /取精度為0.1main()double x6=0,0,0,0,0,40,s=0,min=,best5; /s用來(lái)臨時(shí)保存每一條路徑的價(jià)格，x用來(lái)臨時(shí)保存每一條路徑int i,j,k,l,n,c5=6,4,5,6,5,p5=12,18,28,16,12,D; /min 用來(lái)記錄最小價(jià)格，best用來(lái)記錄最佳路徑 D=40/JD; /D為每一條交界線上可分的段數(shù)for (i=0;iD;i+) /用五個(gè)循環(huán)對(duì)每一條可能的路徑進(jìn)行遍歷 for(j=i;jD;j+)for(k=j;kD;

16、k+)for(l=k;lD;l+)for(n=1;n6;n+) s+=sqrt(xn-xn-1)*(xn-xn-1)+cn-1*cn-1)*pn-1;if(smin) /如果s比上一次最小的價(jià)格更小，/則將其存在min中，同時(shí)路徑保存min=s;/在best中。for(n=0;n5;n+)bestn=xn;s=0;x4+=JD;x3+=JD;x4=x3;x2+=JD;x3=x2;x1+=JD;x2=x1;printf(最少花費(fèi)為%fn,min);for(i=0;i5;i+)printf(在第%d條交界線上的位置為%fn,i,besti);運(yùn)算結(jié)果：最少花費(fèi)為748.在第0條交界線上的位置為0.

17、在第1條交界線上的位置為15.在第2條交界線上的位置為18.在第3條交界線上的位置為21.在第4條交界線上的位置為27.附件三：?jiǎn)栴}二的Matlab語(yǔ)言源代碼：先建立目標(biāo)函數(shù)的M文件：function f=fun(x);f=12*sqrt(x(1)2+36)+18*sqrt(x(2)2+16)+28*sqrt(x(3)2+25)+16*sqrt(x(4)2+36)+12*sqrt(x(5)2+25)然后建立非線性約束條件的M文件：functionc,ceq=mycon(x)c(1)=pi*70/180-pi*0.5+atan(x(1)/6)-atan(x(2)/4);c(2)=pi*70/18

18、0-pi*0.5+atan(x(2)/4)-atan(x(3)/5)c(3)=pi*70/180-pi*0.5+atan(x(3)/5)-atan(x(4)/6);c(4)=pi*70/180-pi*0.5+atan(x(4)/6)-atan(x(5)/5);c(5)=pi*0.5-atan(x(1)/6)+atan(x(2)/4)-pi*110/180;c(6)=pi*0.5-atan(x(2)/4)+atan(x(3)/5)-pi*110/180;c(7)=pi*0.5-atan(x(3)/5)+atan(x(4)/6)-pi*110/180;c(8)=pi*0.5-atan(x(4)/6

19、)+atan(x(5)/5)-pi*110/180; ceq=; 主程序：x0=0.1;0.1;0.1;0.1;0.1;A=1 0 0 0 0;0 1 0 0 0;0 0 1 0 0;0 0 0 1 0;0 0 0 0 1;b=40,40,40,40,40;Aeq=1 1 1 1 1;beq=40;x,z=fmincon(fun,x0,A,b,Aeq,beq,mycon)運(yùn)算結(jié)果：x = 14.4566 4.3591 2.5984 6.5387 12.0472z = 750.6084附件四問(wèn)題二的C語(yǔ)言源代碼：#include#include#define JD 0.1 /取精度為0.1int

20、 tj(double a,double b,double c1,double d,double e) /滿足轉(zhuǎn)彎處至少為160度的條件int n,f,c5=6,4,5,6,5;double x6=0,a,b,c1,d,e;for(n=1;n=1.&3.1416*0.5-atan(xn-xn-1)/cn-1)+atan(xn+1-xn)/cn)=1.)f=1;elsereturn 0;return f;main()double x6=0,0,0,0,0,40,s=0,min=,best5; /s用來(lái)臨時(shí)保存每一條路徑的價(jià)格，x用來(lái)臨時(shí)保存每一條路徑int i,j,k,l,n,c5=6,4,5,6

21、,5,p5=12,18,28,16,12,D; /min 用來(lái)記錄最小價(jià)格，best用來(lái)記錄最佳路徑 D=40/JD; /D為每一條交界線上可分的段數(shù)for (i=0;iD;i+) /用五個(gè)循環(huán)對(duì)每一條可能的路徑進(jìn)行遍歷 for(j=i;jD;j+)for(k=j;kD;k+)for(l=k;lD;l+)for(n=1;n6;n+) s+=sqrt(xn-xn-1)*(xn-xn-1)+cn-1*cn-1)*pn-1;if(smin&tj(x1,x2,x3,x4,x5) /如果s比上一次最小的價(jià)格更小， /且滿足轉(zhuǎn)彎處不小于160度的條件，min=s; /則將其存在min中，同時(shí)路徑保存for

22、(n=0;n5;n+) /在best中。bestn=xn;s=0;x4+=JD;x3+=JD;x4=x3;x2+=JD;x3=x2;x1+=JD;x2=x1;printf(最少花費(fèi)為%fn,min);for(i=0;i5;i+)printf(在第%d條交界線上的位置為%fn,i,besti);運(yùn)算結(jié)果：最少花費(fèi)為750.在第0條交界線上的位置為0.在第1條交界線上的位置為14.在第2條交界線上的位置為18.在第3條交界線上的位置為21.在第4條交界線上的位置為27.附件五：?jiǎn)栴}三的Matlab語(yǔ)言源代碼：先建立目標(biāo)函數(shù)的M文件：function f=fun3(x);f=12*sqrt(x(1)

23、2+36)+18*sqrt(x(2)2+16)+28*sqrt(x(3)2+25)+16*sqrt(x(4)2+9)+16*sqrt(x(5)2+9)+12*sqrt(x(6)2+25)主程序：x0=0;0;0;0;0;0;A=1 0 0 0 0 0;0 1 0 0 0 0;0 0 1 0 0 0;0 0 0 1 0 0;0 0 0 0 1 0;0 0 0 0 0 1;b=30 30 30 30 10 10;Aeq=1 1 1 1 0 0;0 0 0 0 1 1;beq=30;10;x,z=fmincon(fun3,x0,A,b,Aeq,beq)運(yùn)算結(jié)果：x = 21.2613 3.3459 2.2639 3.1288 2.4102 7.5898z = 752.6432附件六：?jiǎn)栴}三的C語(yǔ)言源代碼：#include#include#define JD 0.1 /取精度為0.1main()double x7=0,0,0,0,30,30,40,s=0,min,min1=,min2=,best6; /s用來(lái)臨時(shí)保存每一條路徑的價(jià)格，x用來(lái)臨時(shí)保存每一條路徑int i,j,k,n,c6=6,4,5,3,3,5,p6=12,18,28,16,16,12,D; /min 用來(lái)記錄