碎石運(yùn)輸方案設(shè)計(jì)

1、道路改造項(xiàng)目中碎石運(yùn)輸?shù)脑O(shè)計(jì)編號：4325摘要本文建立了道路改造項(xiàng)目中碎石運(yùn)輸?shù)脑O(shè)計(jì)模型。該模型是一個雙重優(yōu)化模型， 先用 0-1 線性規(guī)劃，求出建碼頭個數(shù)及臨時道路的分布，再用非線性規(guī)劃進(jìn)一步減少 費(fèi)用，經(jīng)計(jì)算我們求得：最少總費(fèi)用是 16,5027,2857（元）從S1所取的碎石量是1043609 m3從S2所取的碎石量是580816 m3模型中將碼頭、臨時道路等看成一個運(yùn)輸系統(tǒng)，它有自己的整體結(jié)構(gòu)與局部結(jié) 構(gòu)。整體結(jié)構(gòu)是指碼頭個數(shù)、道路條數(shù)等。局部結(jié)構(gòu)是指碼頭和道路的精確位置等。 在確定該系統(tǒng)的整體結(jié)構(gòu)時，我們用將連續(xù)變量離散化的思想引入了 0-1 線性規(guī)劃， 即將AB分成若干等長度的段，

2、碼頭和 AB上臨時道路的入口則看成一些離散的點(diǎn)。該 0-1 線性規(guī)劃模型可以求出很好的整體結(jié)構(gòu)。我們用人工找出的三碼頭情形的 整體結(jié)構(gòu)經(jīng)非線性規(guī)劃優(yōu)化后的總費(fèi)用為： 17,2501,1687 （元） 。比以 0-1 線性規(guī)劃經(jīng) 非線性規(guī)劃優(yōu)化后的總費(fèi)用多了 7473,8830 （元），可見我們的模型對工程實(shí)踐中的科 學(xué)決策具有十分重要的指導(dǎo)意義。在模型檢驗(yàn)中我們進(jìn)一步討論了人工增刪臨時道路對總費(fèi)用的影響.通過計(jì)算我們發(fā)現(xiàn)增刪臨時道路均會使總費(fèi)用增大，從而驗(yàn)證了當(dāng)前解趨近最優(yōu)。當(dāng)臨時道路出現(xiàn) 岔路時，我們計(jì)算得總費(fèi)用并不會有所減少，故驗(yàn)證了我們關(guān)于“臨時道路為直線且 無岔路”的假設(shè)。關(guān)鍵詞：雙重

3、優(yōu)化 運(yùn)輸系統(tǒng) 0-1 規(guī)劃 非線性規(guī)劃1、問題重述與分析1.1 問題背景的理解1. 模型構(gòu)建的重點(diǎn)：由計(jì)算我們發(fā)現(xiàn)修公路 AB 所用碎石材料費(fèi)用僅為 9000 萬元，僅占到估算總費(fèi)用 的 1/16 左右，而大量的費(fèi)用消耗在臨時道路建設(shè)及碎石運(yùn)輸上，而影響此兩部分的關(guān) 鍵在于確定碼頭個數(shù)、位置及臨時道路的長度。故在下模型建立與求解中我們將以此 三點(diǎn)為重點(diǎn)進(jìn)行分析與建模。2運(yùn)輸系統(tǒng)的結(jié)構(gòu)我們將所有用于運(yùn)輸?shù)拇a頭，臨時道路及其分布稱為運(yùn)輸系統(tǒng)，它們都是為運(yùn)輸 碎石服務(wù)的。整個系統(tǒng)包括兩個層次結(jié)構(gòu)：第一層次：修建碼頭的個數(shù)，臨時路線的拓?fù)浣Y(jié)構(gòu)。我們稱這部分結(jié)構(gòu)為整體結(jié) 構(gòu)；第二層次是精確的碼頭及臨時

4、道路的位置（ AB 上運(yùn)進(jìn)碎石的點(diǎn)稱為進(jìn)料點(diǎn)） ,我們 稱這部分結(jié)構(gòu)為局部結(jié)構(gòu)。整體結(jié)構(gòu)很難用連續(xù)變量表示，而局部結(jié)構(gòu)可以用連續(xù)變量來描述。意即只有當(dāng) 整體結(jié)構(gòu)確定了以后，總費(fèi)用才可表示為連續(xù)變量的函數(shù)，從而可以規(guī)劃求解得到在 保持某一整體結(jié)構(gòu)不變的前提下的最優(yōu)局部結(jié)構(gòu)。故此題目轉(zhuǎn)化為依次確定運(yùn)輸系統(tǒng) 二個層次的最優(yōu)結(jié)構(gòu)。1.2 關(guān)于運(yùn)輸系統(tǒng)結(jié)構(gòu)的幾點(diǎn)基本結(jié)論：1. 從Si不應(yīng)修出直達(dá)AB的臨時道路：V通過計(jì)算我們發(fā)現(xiàn)從Si修出直達(dá)AB的臨時道路以利用陸路運(yùn)輸?shù)馁M(fèi)用相比從 Si 修建臨時道路至河邊以利用水路運(yùn)輸?shù)馁M(fèi)用大很多，故我們認(rèn)為在現(xiàn)有題目條件下Si不應(yīng)再修出直達(dá)AB的臨時道路，而應(yīng)就近建

5、碼頭以充分利用水路的廉價(jià)運(yùn)力。2. 從S2不會修出跨AB至河下游碼頭的臨時道路： V顯然S2不可能修建臨時道路至河下游以利用水路，分析如下：1）此舉修臨時道路過長，耗費(fèi)很大；2）如此長的臨時道路運(yùn)輸費(fèi)用昂貴；3）若逆流運(yùn)輸則費(fèi)用較高。3. 具體運(yùn)輸流程：由前1、2知，從Si運(yùn)出的碎石必然只能經(jīng)水路調(diào)配到 n個碼頭，再由各碼頭修建 臨時道路至AB以運(yùn)輸碎石，而從S2就必然直接修建臨時道路至 AB。可見，在這種情 況下，各碼頭與S2功能等效，在此我們不妨將各碼頭及 S2統(tǒng)一等效為出料點(diǎn)，則問題 轉(zhuǎn)化為從各出料點(diǎn)到公路AB運(yùn)輸碎石的調(diào)配問題。4. 碼頭修建范圍的限制：由費(fèi)用平衡點(diǎn)的思想，我們總能在

6、AB上找到一進(jìn)料點(diǎn)X，使修建該段所需碎石 從Si、S2分別進(jìn)料的費(fèi)用相等，我們將此進(jìn)料點(diǎn) X記為Si與S2的費(fèi)用平衡點(diǎn)。即在公路AX，XB兩分部碎石分別由Si、S2單獨(dú)提供。經(jīng)計(jì)算我們發(fā)現(xiàn)，當(dāng)x大于i20時，從S2進(jìn)料的最小費(fèi)用小于從Si進(jìn)料的最小費(fèi) 用，從而得證應(yīng)建碼頭的修建范圍（橫坐標(biāo)）：0空x乞i20（在此我們縮小了碼頭的修建范圍，提高了后續(xù)大規(guī)模規(guī)劃模型的計(jì)算精度及速 度）5各臨時道路均為連接出料點(diǎn)與進(jìn)料點(diǎn)兩點(diǎn)間的直線段且互不相交。由反證法顯然得證。2、問題假設(shè)1、車輛運(yùn)輸碎石回程時不計(jì)運(yùn)輸費(fèi)用；2、臨時公路所鋪碎石不能再重復(fù)利用于公路施工；3、鋪設(shè)道路的工程費(fèi)用為常數(shù)，在此不予考慮；

7、4、S1，S2 無碎石容量限制；5、忽略河流的自然環(huán)境因素對碼頭建造，水路運(yùn)輸?shù)闹萍s，即碼頭可建在河流兩岸任 意地點(diǎn)；6、各臨時道路為連接出料點(diǎn)與進(jìn)料點(diǎn)兩點(diǎn)的直線段且互不相交；7、各臨時道路均無岔路分支；8、公路建設(shè)期間施工車輛可以通行；9、忽略碎石在裝卸，配送過程中的自然損失；10、河上、下游點(diǎn)精確的分布在拋物線上；11、S1, S2運(yùn)出的碎石已滿足工程需要，不必再進(jìn)一步進(jìn)行粉碎。 (以上僅給出全局性假設(shè)，其后還會按情況給出一些局部假設(shè))3、符號說明1. (xy)第i號出料點(diǎn)(包括碼頭及S2)的坐標(biāo);2. (Zi,100)公路上第j號進(jìn)料點(diǎn)的坐標(biāo)；3. (ri,100)將公路分段后第i號分界

8、點(diǎn)坐標(biāo).(以上僅給出全局性變量，局部變量在使用時另行說明)4、模型的建立與求解：首先我們建立起在整體結(jié)構(gòu)確定的情況下，用以尋求最優(yōu)局部結(jié)構(gòu)的非線性規(guī) 劃算法。因?yàn)榇朔蔷€性規(guī)劃算法的具體形式依賴于整體結(jié)構(gòu)，故我們接下來以初步分 析得到的較合理的三碼頭方案的整體結(jié)構(gòu)為例，以引出用以尋求最優(yōu)局部結(jié)構(gòu)的非線 性規(guī)劃算法。上述三碼頭方案的整體結(jié)構(gòu)如下圖：4.1基于3碼頭的初等非線性規(guī)劃：4.1.1模型準(zhǔn)備1. Si距河流的最短路及對應(yīng)的固定碼頭位置：最短路長S=4.367（ km）固定碼頭位置坐標(biāo)（18.926, 115.767）（注：此碼頭為固定碼頭，位置不變，即此模型中除了此碼頭外我們還需修建三個碼

9、 頭）2. 河流上任意一點(diǎn)與固定碼頭（18.926, 115.767）間的距離函數(shù):36.22-2 ilndi =36.22+ 25 16 -.25-0.5X :26-0.5X :、25-0.5x i ji(26-0.5x iIn , 0.24Xj-12, 0.24Xj -11 亠 0.24x120.24x11Xi _50Xi503. 臨時道路修建費(fèi)用：設(shè)第i號碼頭至固定碼頭水路距離為 di, （i=1,2,3），臨時道路長度分別為 Li（i=1 , 2, 3）（單位：km），則有如下關(guān)系：從S2引出的臨時公路的修建費(fèi)用（COStA）=臨時道路所需碎石成本（COSt1） +臨 時道路建設(shè)過程中

10、所需碎石的運(yùn)輸費(fèi)用（cost2）易得：cost 1=4 0.1 Lj 103 60 = 24000L 元由簡單積分：cost 2 = Li 4 0.1 20 10“ L dL=4000L2i 元cost A, =cost 1+cost 2=4000匕 +24000Li 元由Si引出的臨時公路的修建費(fèi)用同理計(jì)算，只需加上臨時道路所需的碎石從S1f固定碼頭臨時道路旁碼頭的運(yùn)輸費(fèi)用。同理得：cost Bj = 4000L：+24000L +4 0.1 Li 103 20S 6di=4000L2j+（14.734+0.6d1 （元）4 河流曲線方程判定：通過驗(yàn)算分別由mi （i=1, ,7）確定了上游

11、和下游的近似拋物線方程。在此不妨設(shè) 河流上所有點(diǎn)均精確地分布在拋物線上。2上游拋物線方程：（y-100 ） =8（50-x）2下游拋物線方程：y-100 =16.67 x-504.1.2目標(biāo)函數(shù)設(shè)各碼頭坐標(biāo)為（Xi , yi）（i=1,2,3），公路AB上各進(jìn)料點(diǎn)位置為（zi, 100）（i=1,2,3）,在三碼頭情形下，整條公路按照對應(yīng)出料點(diǎn)的不同被分為4段，則設(shè)各段分界點(diǎn)坐標(biāo)為（n,100） （i=1,2,3）。（注：不妨設(shè)各出料點(diǎn)只有一條臨時道路至對應(yīng)的進(jìn)料點(diǎn)）由前分析，目標(biāo)函數(shù)（總費(fèi)用）=臨時道路的總建設(shè)費(fèi)用+各臨時道路上通過的碎石的總運(yùn)輸 費(fèi)用+公路建設(shè)所需碎石的成本費(fèi)用+部分常量成

12、本具體如下：1. 對13號碼頭:總費(fèi)用=臨時道路修建費(fèi)用（costBi） +各臨時道路上通過的碎石的總運(yùn)輸費(fèi)用6di 20L4.3672+7500 zi-rij6di 20 Li 4.3675 2r=»10 4000 L i+ 14.734+0.6di Li7500 仃-乙i 4-2. 同理對S2：7500 L - 乙 20 L422jZ4 3總費(fèi)用=4000 L 4+6L47500 乙 - r320 L4 333. 公路建設(shè)所需碎石的成本費(fèi)用 =15 0.5 200 1060 = 9000（萬元）4. 部分常量成本=Si固定碼頭的臨時道路建設(shè)費(fèi)用+固定碼頭修建費(fèi)用=181109.4

13、+100000=281109.4元）總費(fèi)用即為上述四部分之和。4.1.3約束條件1. 臨時路長等式約束：2 2 2L2i =(人k )十W 100)(i=1,2,3,4)2. 水路長度約束：36.22-2 In25-0.5x、26-0.5Xj25-0.5xi26-0.5xi為乞 50di=f I36.22+25 In (Jo.24Xi-12+Jo.24Xi 11 )+J(0.24Xi 12)(0.24Xi 11)1 (x>50)L 6 -3. Xi，Zi，ri位置約束:P蘭Xi蘭5050乞X2乞X3X3 乞 200X4 =100,y4 =157” -J <0r° = 0,

14、仃=200z z 01Zi約束：i i +Zi _0,Z4 空 2001 Xi約束：d.ri約束：0=0,123,4)Q =123,4)4、碼頭位置約束：2y, -1008 50 - 為2y -10016.67 Xi -50i = 2,34.1.4結(jié)果分析總費(fèi)用：17,2501,1687(元)表1:出料點(diǎn)、進(jìn)料點(diǎn)、分界點(diǎn)位置表編號出料點(diǎn)位置 （橫坐標(biāo)/km）編號進(jìn)料點(diǎn)位置 （橫坐標(biāo)/km）編號分界點(diǎn)位置 （橫坐標(biāo)/km）118.926117.265131.1392502502105.19393.7683111.83139.3741804173.374上述結(jié)果對應(yīng)的最優(yōu)運(yùn)輸系統(tǒng)結(jié)構(gòu)如下圖2：具體

15、方案為3碼頭，3條臨時道路，總費(fèi)用為17,2501,1687 （元）。雖然該模型采用了非線性規(guī)劃模型，但由于在實(shí)現(xiàn)算法時整體結(jié)構(gòu)由人為確 定，主觀性太大，故不可能達(dá)到最優(yōu)。為了避免人工決定整體結(jié)構(gòu)帶來的盲目性，我 們進(jìn)一步提出了以下先從宏觀上確定整體結(jié)構(gòu)然后再用上述非線性規(guī)劃算法從微觀上 確定最優(yōu)局部結(jié)構(gòu)的雙重規(guī)劃模型。4.2 雙重規(guī)劃模型基于先離散再連續(xù)的思想，我們進(jìn)一步建立了可進(jìn)行雙重優(yōu)化的兩層規(guī)劃模型：第一層： 0-1 線性規(guī)劃第二層：非線性規(guī)劃4.2.1 模型闡釋：此模型精髓在于“先離散再連續(xù)”的思想。所謂離散，是指將公路、河流長度均等分為 n段（故有n-1個分界點(diǎn)），碼頭、進(jìn) 料點(diǎn)的

16、可能位置均處于這些離散的分界點(diǎn)上，則由 0-1 線性規(guī)劃可得出最終碼頭和進(jìn)料 點(diǎn)的確定數(shù)目和位置。如此必然可得在該分段情況下總費(fèi)用的較優(yōu)解及碼頭、臨時道 路的宏觀布局。 n 越大，分段越密，碼頭和進(jìn)料點(diǎn)的位置就趨近于連續(xù)變化，則結(jié)果就 必然越趨近于最優(yōu)解。所謂連續(xù)，是在 0-1 規(guī)劃后整體結(jié)構(gòu)已確定的情況下，利用 4.1 中的非線性規(guī)劃算 法優(yōu)化局部結(jié)構(gòu)，使總費(fèi)用更加趨近于最優(yōu)解。4.2.2 0-1 線性規(guī)劃4.2.2.1 分段情況及三層運(yùn)輸網(wǎng)絡(luò)介紹由前（ 3.2.4 ）分析可知，碼頭修建位置應(yīng)在（ 0,120）之間，我們不妨將整段公路 及碼頭的（0120）部分等分為40段，碼頭、進(jìn)料點(diǎn)的可能

17、位置均處于這些離散的分 界點(diǎn)上。由于當(dāng)碎石由公路的進(jìn)料點(diǎn)運(yùn)入后，還存在一個由進(jìn)料點(diǎn)分發(fā)至各具體施工 地點(diǎn)的過程，這部分運(yùn)輸費(fèi)用顯然也不能忽略，由積分的思想可知，我們不妨設(shè)公路 每段的中點(diǎn)為可能的卸料點(diǎn)，如此便構(gòu)成一個三層運(yùn)輸網(wǎng)絡(luò)，如下圖：422.2目標(biāo)函數(shù)設(shè)0-1變量Xjk,yij,tmi,含義如下:Xijk10,yj表示k號卸料點(diǎn)所需碎石經(jīng)i號碼頭，j號入料點(diǎn)運(yùn)進(jìn) 反之。i號碼頭與j號入料點(diǎn)之間可以通行（既有臨時通路）。 反之。i號位置建碼頭。反之。則目標(biāo)函數(shù)為：總費(fèi)用=公路建設(shè)所需碎石的總運(yùn)輸費(fèi)用（C1）+臨時道路的總建設(shè)費(fèi)用（C2）+碼 頭費(fèi)用（C3）+部分常量成本（C4）404040C

18、i =、 CjkXjki J j 丄 k44040c y /fijYji4 j 440C3 = x 105tmii=1C4 =281109.4（單位:元）4.223約束條件1）系數(shù)計(jì)算：設(shè)運(yùn)輸碎石從i-j-k的費(fèi)用為Cjk,修建i- j的臨時道路費(fèi)用為fj。則由三層運(yùn)輸網(wǎng)絡(luò)圖示可知，Cjk應(yīng)分三種情況考慮：至15號碼頭屬于逆流航行，至639號碼頭屬于順流航行，40號為S2應(yīng)單獨(dú)考慮。同理，fj也如此計(jì)算如下：3750010d206.76L5(j -k)(i=1,2,，5)Cjk =<375006di +206.763十 L +5(j k)(i=6,7,，39)7500006.763+ L

19、5(j -k)(i=40 )L40010dj +20(4.263 +)(i=1,2,5 )2Lf. -i4006di 20(4.263 L)i=6,7,392L8000(4.263 十寸)(i=40 )2）每一個卸料點(diǎn)都必然只有一條運(yùn)石路線到達(dá):4040C2 八、Xijk =1i 4 j 4k=1,2,03）ifj的道路存在與否對if jf k碎石運(yùn)輸路線的約束:40yj -Xijk -40y0kA4）i號碼頭存在與否對i fj碎石運(yùn)輸路線的約束：i=1,2,040乞、yi<40tmjd：4.224結(jié)果分析總費(fèi)用：16,5685,9000 （元）表2:出料點(diǎn)、進(jìn)料點(diǎn)、分界點(diǎn)位置表編號出料

20、點(diǎn)位置 （橫坐標(biāo)/km）編號進(jìn)料點(diǎn)位置 （橫坐標(biāo)/km）編號分界點(diǎn)位置 （橫坐標(biāo)/km）117 （碼頭）110110220 （碼頭）215220326 （碼頭）325330435 （碼頭）435440547 （碼頭）545:545650 （碼頭）650690774 （碼頭）790r 7105892 （碼頭）811081309180 （S2）9150P 9155101701018011190用lingo進(jìn)行計(jì)算，得出在40分段下的最優(yōu)整體結(jié)構(gòu)，具體方案為8碼頭，11條臨時道路，總費(fèi)用為16,5685,9000 （元）。前4.1中的三碼頭方案總費(fèi)用為17,2501,1687 （元），相比上述方案增

21、大了16,5685,9000= 4.11%，增加的絕對數(shù)值達(dá)到了6815,2687 （元），可見運(yùn)輸系統(tǒng)整體結(jié)構(gòu)對最優(yōu)解影響巨大，僅靠人工來尋求最優(yōu)整體結(jié)構(gòu)很難做到，這就凸 顯了用0-1規(guī)劃來從全局角度優(yōu)化整體結(jié)構(gòu)的重要性和必要性。但由于該方案畢竟是將連續(xù)問題離散化，實(shí)際中若要得到全局最優(yōu)解應(yīng)將問題離 散為無窮多段，但如果再將離散程度提高十倍，簡單估算將使時間復(fù)雜度至少提高為 原問題的103倍，所以我們無法再通過提高分段數(shù)來使得整體結(jié)構(gòu)更優(yōu)，因此我們認(rèn)為 整體結(jié)構(gòu)已達(dá)到目前條件下的最優(yōu)。至此我們已完成了對運(yùn)輸系統(tǒng)整體結(jié)構(gòu)的優(yōu)化， 接下我們進(jìn)行局部結(jié)構(gòu)的非線性規(guī)劃尋優(yōu)。非線性規(guī)劃尋優(yōu)在前述0-1

22、線性規(guī)劃給出整體結(jié)構(gòu)之后，我們只需以碼頭，進(jìn)料點(diǎn)，分界點(diǎn)位置為 變量，以總費(fèi)用為目標(biāo)函數(shù)，用 4.1中的非線性規(guī)劃算法使其各點(diǎn)位置局部擾動，趨近 最優(yōu)即可，具體計(jì)算過程不再詳述，結(jié)果如下：總費(fèi)用：16,5027,2857 （元）表3:從si，s2所取的碎石量表臨時道路建設(shè)所用碎石 （單位：m3）公路AB建設(shè)所用碎石 （單位：m3）所用碎石總量（單位：m3）si52878.63715990730.11451043608.752s271546.48796509269.8855580816.3735表4:出料點(diǎn)、進(jìn)料點(diǎn)、分界點(diǎn)位置表編號出料點(diǎn)位置 （橫坐標(biāo)/km）編號進(jìn)料點(diǎn)位置 （橫坐標(biāo)/km）編號

23、分界點(diǎn)位置 （橫坐標(biāo)/km）118.92600（碼頭）19.50724112.10011218.92600（碼頭）217.18754221.16109324.78833 （碼頭）324.97344328.89557:433.37084 （碼頭）432.77693436.20283541.72291 （碼頭）540.21071542.79226:650.00000 （碼頭）650.00067690.16619776.65349 （碼頭）:792.991787109.44589:895.70385 （碼頭）8113.617988132.097359180 （S2）9151.860709158.40

24、39210170.7696110179.2825111187.98254用lingo進(jìn)行計(jì)算，得出具體方案為7碼頭，10條臨時道路，總費(fèi)用為 16,5027,2857 （元）。從圖中可見碼頭1和碼頭2經(jīng)過非線性優(yōu)化后合并為一個碼頭，可節(jié)約10萬元。這一方面說明了離散方案不可避免的局限性，另一方面也說明了雙重規(guī)劃模型的穩(wěn)定 性。前422中用0-1規(guī)劃運(yùn)算后的總費(fèi)用為16,5685,9000 （元），相比上述方案增大了16,5685,9000-16,5027,28570.39%，增加的絕對數(shù)值達(dá)到了648,6143 （元），可見運(yùn)16,5027,2857輸系統(tǒng)局部結(jié)構(gòu)對最優(yōu)解影響也很大，這就凸顯了

25、用非線性規(guī)劃算法來進(jìn)一步優(yōu)化運(yùn)輸系統(tǒng)局部結(jié)構(gòu)的重要性和必要性。5、模型檢驗(yàn)由于我們所用的模型只能求出近似最優(yōu)解，而本問題中涉及到的總費(fèi)用達(dá)十幾 億，故應(yīng)持慎重的態(tài)度對模型做進(jìn)一步的檢驗(yàn)和調(diào)整，以充分節(jié)約資金。5.1增刪臨時道路對模型結(jié)果的影響為了檢查我們用0-1規(guī)劃得到的整體結(jié)構(gòu)的合理性，我們在通過0-1規(guī)劃得到的較優(yōu)方案中，新增或刪除1條臨時道路，再以之以為基礎(chǔ)運(yùn)用非線性算法求解之，得 到的總費(fèi)用均比不增刪時要大，這就充分證明了0-1規(guī)劃模型對于運(yùn)輸系統(tǒng)整體結(jié)構(gòu)優(yōu)化的有效性。具體過程如下：我們選擇了下圖中的第 4條臨時道路（黃色線路）進(jìn)行刪除檢 驗(yàn)，選擇在下圖中的第7條臨時道路與第8條臨時道

26、路之間加一條臨時道路以進(jìn)行增 加檢驗(yàn)。具體情況見下表:檢驗(yàn)方式總費(fèi)用（億元）刪除第4號線路16.6667第7、8條臨時道路之間增 加一條臨時道路16.7432與最優(yōu)值16,5685,9000元） 比較的相對增加量（萬元）0.59%與最優(yōu)值16,5685,9000元） 比較的絕對增加量（萬元）9801.05%17465.2增加岔路對模型結(jié)果的影響經(jīng)過觀察我們發(fā)現(xiàn)從S2出發(fā)的最左端的臨時道路斜率較小，故我們認(rèn)為在該路 線末端修岔路最有可能減少總費(fèi)用。設(shè)D為AB中點(diǎn)。在AS2取一點(diǎn)C使AC=BC，易知S2A=63.56776 （公里）， AC=BC=7.386871 （公里），AB=6.54 （公里

27、）。未分岔前 AB段碎石全部沿S2A運(yùn)達(dá)，分岔后，AD段沿ACS2運(yùn)輸碎石，DB段沿BCS2運(yùn)輸碎石，平均運(yùn)輸距離減少了AB4= 1.635 （公里），這樣減少運(yùn)費(fèi)=1.635X 20X 6.54X 7500=1603935 （元）。而修BC的費(fèi)用為3715556 （元）。故總費(fèi)用沒有減少，反而增加了 2111621 （元），這主 要是由于將修路用的碎石運(yùn)到分岔口處的距離太遠(yuǎn)，運(yùn)費(fèi)十分高，故模型中關(guān)于臨時 道路是直線且不分岔是合乎實(shí)際的6、模型的進(jìn)一步討論將位置及長度離散化的方法，還能用在很多類似于確定修路位置，橋梁位置等問題 中，離散化了之后，原來的非線性問題可轉(zhuǎn)化為線性問題，一些難以用連續(xù)

28、變量描述 的約束，可以很簡單地用 0-1 變量表示，避免做多次試探即能得到很好的初始方案，從 理論上說離散化時分段越多，分點(diǎn)越密，越接近連續(xù)的實(shí)際情形，但分得越多 0-1 變量 亦越多，直接用優(yōu)化軟件來解變得不可行，有必要針對此類問題設(shè)計(jì)高效率的近似算 法， 0-1規(guī)劃問題是 NPC 問題，但針對此類問題完全有可能設(shè)計(jì)出多項(xiàng)式時間算法求 出很好的近似最優(yōu)解，由于時間太倉促，我們暫時還未提出有效的算法。7. 模型的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：1、本模型較正確地處理了 道路改造項(xiàng)目中碎石運(yùn)輸 問題，模型較為符合實(shí) 際。2、二層規(guī)劃模型的使用貼近題意，能準(zhǔn)確、快速地計(jì)算最小總費(fèi)用，有很強(qiáng)的實(shí) 用價(jià)值；3、在計(jì)算模型

29、的解時，我們利用了專業(yè)的數(shù)學(xué)軟件matlab、lingo和excel,在推廣中探討了模型的實(shí)用性并分析其靈敏度。缺點(diǎn)：1考慮的因素比較全面，但算法較為單一。2部分假設(shè)還不太符合實(shí)際情況；8. 參考文獻(xiàn)1.湯代焱.運(yùn)籌學(xué)，中南大學(xué)出版社，2 0 0 2。2葉其孝，大學(xué)生數(shù)學(xué)建模競賽輔導(dǎo)材料，湖南教育出版社，長沙，19933姜啟源，數(shù)學(xué)模型，高等教育出版社，北京， 2003附錄一、 Matlab 主要程序function f = myobjfun10ok120jian1(ax)if ax<=200 & ax>=0for a=1:10 x(a)=ax(a);endfor a=11

30、:20 z(a-10)=ax(a);endfor a=21:29r(a-20)=ax(a);endx(9)=180;x(10)=180;x(8)=180;%r(1)=0;%r(5)=200;pt1=0;pt2=0;pt3=0;LL1=0;LL2=0;for i=2:7匸sqrt(x(i)-z(i)F2+(gety(x(i)-100F2);LL1=LL1+l;d=getcurvelong6(18.92600222,x(i);pt1=pt1+ 7500*(z(i)-r(i-1)*(6*d+20*(l+4.36731650690042+(z(i)-r(i-1)/2)+7500*(r(i)- z(i)

31、*(6*d+20*(l+4.36731650690042+(r(i)-z(i)/2);endfor i=8:9l=sqrt(x(i)-z(i)A2+(157-100)A2);LL2=LL2+l;pt1=pt1+ 7500*(z(i)-r(i-1)*20*(l+(z(i)-r(i-1)/2)+7500*(r(i)-z(i)*20*(l+(r(i)-z(i)/2);endi=1;匸sqrt(x(i)-z(i)F2+(gety(x(i)-100F2);LL1=LL1+l;d=getcurvelong6(18.92600222,x(i);pt1=pt1+ 7500*(z(i)-0)*(6*d+20*(

32、l+4.36731650690042+(z(i)-0)/2)+7500*(r(i)- z(i)*(6*d+20*(l+4.36731650690042+(r(i)-z(i)/2);i=10;l=sqrt(x(i)-z(i)A2+(157-100)A2);LL2=LL2+l;d=getcurvelong6(18.92600222,x(i);pt1=pt1+ 7500*(z(i)-r(i-1)*20*(l+(z(i)-r(i-1)/2)+7500*(200-z(i)*20*(l+(200-z(i)/2); % pt1=pt1+ 7500*(z(i)-r(i-1)*(6*d+20*(l+4.3673

33、1650690042+(z(i)-r(i- 1)/2)+7500*(200-z(i)*(6*d+20*(l+4.36731650690042+(200-z(i)/2);for i=1:7l=sqrt(x(i)-z(i)A2+(gety(x(i)-100)A2);d=getcurvelong6(18.92600222,x(i);pt2=pt2+400*l*(60+6*d+20*(4.36731650690042+l/2);endfor i=8:10l=sqrt(x(i)-z(i)A2+(157-100)A2);pt2=pt2+400*l*(60+20*l/2);endf = pt1+pt2+18

34、1109.4+90000000+(10A5)*9;elsesm=0;for a=1:29if ax(a)<0sm=sm- 10000000000000000000000000000*ax(a)+100000000000000000;endif ax(a)>200sm=sm- 10000000000000000000000000000*(200-ax(a)+100000000000000000;endendf=sm/100000000000000 +100000000000000000; endlingo 主要程序model :sets :cf10/w1.w40/:objectpoi

35、nt;cf9/w1.w39/:inputpoint;cf7/w1.w40/:outputpoint;cf6/w1.w39/:tm;cx(cf7,cf9,cf10):x,c;cy(cf7,cf9):y,f;endsetsdata :l=40;M=40;c=2.47400E+007 2.47400E+007 2.84900E+007 3.22400E+007 3.59900E+007 3.97400E+0074.34900E+007 4.72400E+007 5.09900E+007 5.47400E+007 5.84900E+007 6.22400E+007 6.59900E+0076.9740

36、0E+007 7.34900E+007 7.72400E+007 8.09900E+007 8.47400E+007 8.84900E+007 9.22400E+0079.59900E+007 9.97400E+007 1.03490E+008 1.07240E+008 1.10990E+008 1.14740E+008 1.18490E+0081.22240E+008 1.25990E+008 1.29740E+008 1.33490E+008 1.37240E+008 1.40990E+008 1.44740E+0081.48490E+008 1.52240E+008 1.55990E+008 1.59740E+008 1.63490E+008 1.67240E+0082.89758E+007 2.52258E+007 2.52258E+007 2.89758E+007 3.27258E+007 3.64758E+007 4.02258E+0074.39758E+007 4.77258E+007 5.14758E+007 5.5225