數(shù)學(xué)建模競(jìng)賽

1、“井岡杯”題目：B題 最優(yōu)路線設(shè)計(jì)問題本科組 : 劉佳敏 10數(shù)學(xué)本（2） 100512010陳殷章 10數(shù)學(xué)本（2） 100512061奇 10電信本（1） 100916010學(xué)建模競(jìng)賽井岡山大學(xué)摘要 本論文根據(jù)題意，要求最優(yōu)管線鋪設(shè)路線，只要求出管線與各地質(zhì)層的交點(diǎn)即可，運(yùn)用數(shù)學(xué)規(guī)劃的思想，在已知管線與各地質(zhì)層的交點(diǎn)的情況下，每個(gè)地質(zhì)層間的直線鋪設(shè)無(wú)疑是最短的，因此對(duì)于問題一建立了規(guī)劃模型，運(yùn)用lingo軟件求出了滿足條件的最優(yōu)管線鋪設(shè)路線。問題二在問題一的基礎(chǔ)上進(jìn)行推廣，加入了管線轉(zhuǎn)彎時(shí)角度至少為160

2、6;的限制，在通過一系列的幾何計(jì)算后，將轉(zhuǎn)彎時(shí)角度的限制轉(zhuǎn)化為地質(zhì)層交界面與管線交點(diǎn)的橫坐標(biāo)X1的取值范圍的約束在問題一的模型的基礎(chǔ)上建立新的模型。對(duì)于問題三，要求管線經(jīng)過已知點(diǎn)，通過將原來(lái)點(diǎn)所在地質(zhì)層用平行于橫軸的直線重新劃分為兩個(gè)新的地質(zhì)層，將約束條件要求管線經(jīng)過已知點(diǎn)，轉(zhuǎn)化為管線與兩個(gè)新地質(zhì)層交面的交點(diǎn)為點(diǎn)，按照對(duì)之前對(duì)交點(diǎn)處理方法容易將約束條寫成表達(dá)式，加入新的約束條件后，對(duì)模型用lingo求解就可以得到最優(yōu)管線鋪設(shè)路線。最后本文還將模型推廣能到處理一般的地質(zhì)分布情況?！娟P(guān)鍵詞】線性規(guī)劃；條件轉(zhuǎn)化；lingo求解。1最優(yōu)路線設(shè)計(jì)問題一 問題的重述準(zhǔn)備在A地與B地之間修建一條地下管線，B

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

4、=5，確定最便宜的管線鋪設(shè)路線。）(2) 鋪設(shè)管線時(shí)，如果要求管線轉(zhuǎn)彎時(shí)，角度至少為1600，確定最便宜的管線鋪設(shè)路線。(3) 鋪設(shè)管線時(shí)，如果要求管線必須通過位于沙石地質(zhì)帶或巖石地質(zhì)帶中的某一已知點(diǎn)P（位于A地正南面18km和正東30km交匯處）時(shí)，確定最便宜的鋪設(shè)路線。二 問題的分析在修建地下或管線或者進(jìn)行公路建設(shè)時(shí)，由于地質(zhì)結(jié)構(gòu)復(fù)雜性，不同的地質(zhì)結(jié)構(gòu)將會(huì)有不同的造價(jià)，為了更好的節(jié)約資源，我們不得不對(duì)鋪設(shè)路線進(jìn)行規(guī)劃。2現(xiàn)準(zhǔn)備在A地與B地之間修建一條地下管線，B地位于A地正南面26km和正東40km交匯處，給出整個(gè)地區(qū)的大致地質(zhì)情況及各種地質(zhì)條件上每千米的修建費(fèi)用等，要求建立數(shù)學(xué)模型，求出

5、滿足條件下的最便宜的鋪設(shè)路線。 三 模型的假設(shè)與符號(hào)約定3.1模型的將基本假設(shè)（1）假設(shè)各地質(zhì)帶的交界呈直線走向。（2）假設(shè)各地質(zhì)帶內(nèi)部分布及特點(diǎn)呈理想化狀態(tài)，無(wú)空洞。（3）不考慮天氣狀況對(duì)施工的影響（所需費(fèi)用提升）。3.2 符號(hào)的約定；Z:管線總造價(jià)；。四 模型的建立與求解4.1.1問題一模型的建立 如圖1所示,對(duì)區(qū)域進(jìn)直角坐標(biāo)化:Y（0,0）X40km26km圖140km（0,0） 3從圖中可知直線AB是所有線路中最短的，但不一定最便宜；可是如果已知點(diǎn)與，顯然直線是最短的路線，而到段的總造價(jià)也是最低的。由圖1可知： AX1=c12+x12 X1X2=c22+(X2-X1)2 X2X3=c3

6、2+(X3-X2)2 X3X4=c42+X4-X32 X4B=c52+(40-X4)2(其中C1=6,C2=4,C3=5,C4=6,C5=5) 由于每段都是最低造價(jià)，所以總造價(jià)也是最低的，我們可以得出以下的規(guī)劃模型。 minZ=12（AX1+X4B）+18X1X2+28X2X3+16X3X4 Xi+1Xi s.t. X10 X4404.1.2 問題一模型的求解 問題一模型是一個(gè)線性規(guī)劃,利用lingo軟件可以容易求得結(jié)果。此時(shí)可得： X1=15.67886X2=18.86159X3=21.04549X4=26.93428Z=748.6244 4.2.1 問題二模型的建立 問題二是對(duì)問題一的一個(gè)

7、擴(kuò)展，增加了要求轉(zhuǎn)彎時(shí)要求轉(zhuǎn)角大于160°的限制，可通過如圖2所示方法，將轉(zhuǎn)角的限制轉(zhuǎn)化為坐標(biāo)上長(zhǎng)度的限制，對(duì)于有 .4圖2對(duì)于點(diǎn)通過計(jì)算可求得與相交于處夾角為20°兩條直線的方程，通過直線方程又可求得與的橫坐標(biāo)，具體做法如下： 直線的傾斜角為µ，tan µ= -C1X1，µ=-arctan (C1X1)，與直線相交于處夾角為20°的兩條直線的斜率為：k=tan（µ±20°），通過公式可求得兩條直線的方程。分別將兩直線方程與y=C3+C4+C5聯(lián)立解方程組就可求出與的橫坐標(biāo)。同理可求得與的橫坐標(biāo)，將轉(zhuǎn)角的

8、限制轉(zhuǎn)化為坐標(biāo)上長(zhǎng)度的限制, ,可得如下模型： min Z=12(AX1+X4B)+18X1X2+28X2X3+16X3X4 Xi+1Xi X10 s.t. X440 C1+C2+C3+C4+C5=26 AiXi+1Bi 4.2.2 問題二模型的求解對(duì)問題二模型求解同問題（1）進(jìn)行求解。4.3.1 問題三模型的建立問題三又是對(duì)問題的進(jìn)一步推廣，要求管線必須通過位于沙石地質(zhì)帶或巖石地質(zhì)帶中的某一已知點(diǎn)（30,8）。如圖3所示，過點(diǎn)作一個(gè)與軸平行的新的地質(zhì)層交界面，不過這個(gè)新的地質(zhì)層交界面兩邊都是沙石。新的地質(zhì)交界面圖3 5假設(shè)新地質(zhì)層交界面將之前寬為C2的f2沙石地質(zhì)層劃分為寬分別為C6和C7的

9、兩個(gè)地質(zhì)層，在對(duì)新地質(zhì)層交界面處理時(shí)，只需讓管線與新地質(zhì)層交界面交點(diǎn)為點(diǎn)就可以了，與其它地質(zhì)層交界面不同的是新地質(zhì)層交界面與管線的交點(diǎn)是確定的。在經(jīng)過轉(zhuǎn)換后我們可以得出以下模型。min Z=12(AX1+X4B)+18（X1P+PX2）+28X2X3+16X3X4 Xi+1Xi 30X10 X230 X440 s.t. C1+C2+C3+C4+C5=26 X1P= c62+(30-X1)2 PX2= c72+(X2-30)2 4.3.2 問題三模型的求解 對(duì)于問題三模型，可利用lingo求解,不妨取C1=12，C2=8，C3=1，C4=2，C5=3，C6=6，C7=2進(jìn)行計(jì)算，可以求得： X1

10、=25.46401X2=31.50348X3=31.92227X4=33.75698Z=675.1242五 模型的進(jìn)一步討論及分析5.1 模型的評(píng)價(jià)本論文運(yùn)用數(shù)學(xué)規(guī)劃的思想，從問題出發(fā)，運(yùn)用代數(shù)語(yǔ)言抽象出規(guī)劃模型，不僅很好的解決了本題中的問題，而且具有很好的移植性,能很好的解決同類的問題，數(shù)學(xué)推導(dǎo)嚴(yán)謹(jǐn)，理論性強(qiáng)。但是由于是基于本題中的問題，本題中還有許多因素沒有考慮，在用這個(gè)模型處理其它問題時(shí)難免要加入不少的限制條件，才能滿足要求。5.2 模型的推廣本論文的模型是基于本題中的條件而建立模型的，本題中的地質(zhì)層是呈帶狀直線走向，對(duì)于地質(zhì)層不是呈帶狀直線走向而是彎曲的曲線（而這更合乎實(shí)際），只需將本

11、模型稍加推廣即可解決。6如圖4所示，首先將鋪設(shè)區(qū)域劃分為一個(gè)個(gè)小的矩形區(qū)域，地質(zhì)層交界的曲線將被這些小矩形分許多小段，每小段曲線可以通過求均值或其它方式求得一條平行于橫軸的直線，用直線段代替原曲線段，如有多個(gè)地質(zhì)層做同樣的處理，在用原有模型求解時(shí)只需用每一小段線段所在的直線代替原模型的地質(zhì)層交界直線，運(yùn)用編程搜索求解，只要求出的解都在小線段橫軸范內(nèi)并且相對(duì)最優(yōu)就是要求的解，但這不是最優(yōu)的解，要得到更優(yōu)的解可對(duì)所求出解所在的小線段細(xì)分再求解。雖然不一定能求出最優(yōu)解，但對(duì)于生產(chǎn)實(shí)際來(lái)說已達(dá)到優(yōu)化可行的要求。取兩小段計(jì)算,并把的取值限制在兩段線段之內(nèi)再求解.圖4六 參考文獻(xiàn)1 劉桂真等，運(yùn)籌學(xué)，山東

12、，山東大學(xué)出版社，1999年2 刁在筠等，數(shù)學(xué)規(guī)劃，濟(jì)南，山東教育出版社，1997年3 施光艷等，最優(yōu)化方法（第二版），北京，高等教育出版社，2007年4 錢頌迪等，運(yùn)籌學(xué)，北京：清華大學(xué)出版社，2005年9月七 附錄7.1模型一的lingo求解 Lingo編程 model:min=12*(sqrt(36+x12)+sqrt(25+(40-x4)2)+18*(sqrt(16+(x2-x1)2)+16*sqrt(36+(x4-x3)2)+28*sqrt(25+(x3-x2)2);x2>=x1;x3>=x2;x4>=x3;x1>=0;x4<=40;end結(jié)果輸出 Lo

13、cal optimal solution found. Objective value: 748.6244 Extended solver steps: 57 Total solver iterations: 192 Variable Value Reduced Cost X1 15.67886 0.000000 X4 26.93428 0.000000 X2 18.86159 0.000000 X3 21.04549 0.000000 Row Slack or Surplus Dual Price 1 748.6244 -1.000000 2 3.182732 0.000000 3 2.18

14、3895 0.000000 4 5.888798 0.000000 5 15.67886 0.000000 6 13.06572 0.0000007.2模型二的lingo求解如，模型一7.3模型三的lingo求解Lingo編程 model:min=12*(sqrt(144+x12)+sqrt(9+(40-x4)2)+18*(sqrt(36+(30-x1)2)+sqrt(4+(x2-30)2)+16*sqrt(4+(x4-x3)2)+28*sqrt(1+(x3-x2)2);x2>=x1;x3>=x2;x4>=x3;x1<=30;x2>=30;x1>=0;x4<=40;end結(jié)果輸出 Local optimal solution found. Objective value: 675.1242 Extended solver steps: 5 Total solver iterations: 160 Variable Value Reduced Cost X1 25.46401 0.000000 X4 33.75698 0.000000 X2 31.5