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

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

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

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

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

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

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

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

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

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

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

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

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

13、土層中在東西方向上的投影長度分別為21.30km,3.30km,2.30km,3.10km,2.40km,7.60km。六.模型的評價與改進對于模型一，存在的缺點是用Matlab中的fmincon函數(shù)所求最優(yōu)解可能只是局部最優(yōu)解，必須代入幾組不同的初始迭代值，來確定所求解為全局最優(yōu)解，但仍有可能遺漏。對于模型二，缺點是精度不夠小，當精度取到0.1時，計算機要用幾分鐘才能得出結(jié)果，精度更小時所需時間更長，而且在問題二中，模型二因為精度太低而跳過了最優(yōu)路徑，所以與模型一所得結(jié)果有一定差距。但模型二的結(jié)果可用于檢驗模型一所得結(jié)果是否為最優(yōu)解。 附 件附件一：問題一的Matlab語言源代碼：先建立目標

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)運算結(jié)果：x = 15.6786 3.1827 2.1839 5.8887 13.0661

15、z = 748.6244附件二：問題一的C語言源代碼：#include#include#define JD 0.1 /取精度為0.1main()double x6=0,0,0,0,0,40,s=0,min=,best5; /s用來臨時保存每一條路徑的價格，x用來臨時保存每一條路徑int i,j,k,l,n,c5=6,4,5,6,5,p5=12,18,28,16,12,D; /min 用來記錄最小價格，best用來記錄最佳路徑 D=40/JD; /D為每一條交界線上可分的段數(shù)for (i=0;iD;i+) /用五個循環(huá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比上一次最小的價格更小，/則將其存在min中，同時路徑保存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(最少花費為%fn,min);for(i=0;i5;i+)printf(在第%d條交界線上的位置為%fn,i,besti);運算結(jié)果：最少花費為748.在第0條交界線上的位置為0.

17、在第1條交界線上的位置為15.在第2條交界線上的位置為18.在第3條交界線上的位置為21.在第4條交界線上的位置為27.附件三：問題二的Matlab語言源代碼：先建立目標函數(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)運算結(jié)果：x = 14.4566 4.3591 2.5984 6.5387 12.0472z = 750.6084附件四問題二的C語言源代碼：#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用來臨時保存每一條路徑的價格，x用來臨時保存每一條路徑int i,j,k,l,n,c5=6,4,5,6

21、,5,p5=12,18,28,16,12,D; /min 用來記錄最小價格，best用來記錄最佳路徑 D=40/JD; /D為每一條交界線上可分的段數(shù)for (i=0;iD;i+) /用五個循環(huá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比上一次最小的價格更小， /且滿足轉(zhuǎn)彎處不小于160度的條件，min=s; /則將其存在min中，同時路徑保存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(最少花費為%fn,min);for(i=0;i5;i+)printf(在第%d條交界線上的位置為%fn,i,besti);運算結(jié)果：最少花費為750.在第0條交界線上的位置為0.在第1條交界線上的位置為14.在第2條交界線上的位置為18.在第3條交界線上的位置為21.在第4條交界線上的位置為27.附件五：問題三的Matlab語言源代碼：先建立目標函數(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)運算結(jié)果：x = 21.2613 3.3459 2.2639 3.1288 2.4102 7.5898z = 752.6432附件六：問題三的C語言源代碼：#include#include#define JD 0.1 /取精度為0.1main()double x7=0,0,0,0,30,30,40,s=0,min,min1=,min2=,best6; /s用來臨時保存每一條路徑的價格，x用來臨時保存每一條路徑int i,j,k,n,c6=6,4,5,3,3,5,p6=12,18,28,16,16,12,D; /min 用來記錄