數(shù)學(xué)建模 運(yùn)輸問題 送貨問題

1、數(shù)學(xué)建模論文題 目: 送貨問題 學(xué)院(直屬系): 數(shù)學(xué)與計(jì)算機(jī)學(xué)院 年級、 專業(yè): 2010級信息與計(jì)算科學(xué) 姓 名:楊尚安 :劉 洋 :譚 笑 指 導(dǎo) 教 師: 蒲 俊 完 成 時 間: 2012年 3 月 20 日 摘要本文討論的是貨運(yùn)公司的運(yùn)輸問題，根據(jù)各公司需求和運(yùn)輸路線圖，建立了線性規(guī)劃模型和0-1規(guī)劃模型，對貨運(yùn)公司的出車安排進(jìn)行了分析和優(yōu)化，得出運(yùn)費(fèi)最小的調(diào)度方案。對于問題一，由于車輛在途中不能掉頭，出車成本固定，要使得總成本最小，即要使在一定的車輛數(shù)下，既滿足各公司的需求，又要盡量減小出車次數(shù)。故以最小出車數(shù)為目標(biāo)函數(shù)，建立線性規(guī)劃模型，并通過lingo求解，得出最小出車數(shù)27

2、次。接著考慮車的方向問題，出車分為順時針和逆時針，建立0-1模型，并求解，得出滿足問題一的調(diào)度方案（見附錄表1）。對于問題二，車輛允許掉頭，加上車輛裝載貨物和空裝時運(yùn)輸費(fèi)不同，要使總成本最小，故可以通過修改原目標(biāo)函數(shù)，建立線性規(guī)劃模型和0-1規(guī)劃模型，求解，得出最佳派出車輛3輛并列出滿足問題二的調(diào)度方案。對于問題三第一小問，增加了運(yùn)輸車輛的類型。即裝載材料的方法很多，在上述分析的基礎(chǔ)上，通過增加約束條件，建立新的線性規(guī)劃模型，并求解，得出滿足問題三的調(diào)度方案。在第二小問中，由于給出部分公司有道路相通，可采用運(yùn)籌學(xué)中的最短路問題的解決方法加以解決。關(guān)鍵字：線性規(guī)劃模型 0-1規(guī)劃模型 調(diào)度一、問

3、題重述某地區(qū)有8個公司(如圖一編號至)，某天某貨運(yùn)公司要派車將各公司所需的三種原材料A,B,C從某港口(編號)分別運(yùn)往各個公司。路線是唯一的雙向道路(如圖)。貨運(yùn)公司現(xiàn)有一種載重 6噸的運(yùn)輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次(車輛每出動一次為一車次)。每輛車平均需要用15分鐘的時間裝車，到每個公司卸車時間平均為10分鐘，運(yùn)輸車平均速度為60公里小時(不考慮塞車現(xiàn)象)，每日工作不超過8小時。運(yùn)輸車載重運(yùn)費(fèi)1.8元/噸公里，運(yùn)輸車空載費(fèi)用0.4元/公里。一個單位的原材料A,B,C分別毛重4噸、3噸、1噸，原材料不能拆分，為了安全，大小件同車時必須小件在上，大件在下。卸

4、貨時必須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當(dāng)天的需求量(見表)。 問題：1、貨運(yùn)公司派出運(yùn)輸車6輛，每輛車從港口出發(fā)(不定方向)后運(yùn)輸途中不允許掉頭，應(yīng)如何調(diào)度(每輛車的運(yùn)載方案，運(yùn)輸成本)使得運(yùn)費(fèi)最小。2、每輛車在運(yùn)輸途中可隨時掉頭，若要使得成本最小，貨運(yùn)公司怎么安排車輛數(shù)？應(yīng)如何調(diào)度？3、(1)如果有載重量為4噸、6噸、8噸三種運(yùn)輸車，載重運(yùn)費(fèi)都是1.8元/噸公里，空載費(fèi)用分別為0.2，0.4，0.7元/公里，其他費(fèi)用一樣，又如何安排車輛數(shù)和調(diào)度方案？(2)當(dāng)各個公司間都有或者部分有道路直接相通時，分析運(yùn)輸調(diào)度的難度所在，給出你的解決問題的想法(可結(jié)合實(shí)際情況深

5、入分析)。圖唯一的運(yùn)輸路線圖和里程數(shù)公司材料A41231025B15012423C52424351二、符號說明 表示為一個車裝一單位A和兩單位C； 表示為一個車裝六單位C； 表示為一個車裝兩單位B； 表示為一個車裝一單位B和三單位C； 表示最小運(yùn)輸次數(shù)； 表示為一個車裝一單位A和一單位C； 表示為一個車裝一單位A； 表示第i次運(yùn)輸裝A的單位數(shù) ； 表示第i次運(yùn)輸裝B的單位數(shù)； 表示第i次運(yùn)輸裝C的單位數(shù)； 表示第i次運(yùn)輸A到達(dá)目的地所走的路程； 表示第i次運(yùn)輸B到達(dá)目的地所走的路程； 表示第i次運(yùn)輸C到達(dá)目的地所走的路程； 表示運(yùn)輸車的方向（等于0按照順時針即 ；等于1按照逆時針即 ）； 表示

6、最小成本； 表示第i次運(yùn)輸j的所走單位路程的單位成本； 表示8個公司對A的總需求量； 表示8個公司對B的總需求量； 表示8個公司對C的總需求量；三、模型假設(shè)1假設(shè)每輛車裝載時發(fā)揮其最大的裝載能力；2假設(shè)貨運(yùn)公司都是先考慮節(jié)省人力和出車次數(shù)最少的情況下再考慮如何安排運(yùn)輸方式以減少經(jīng)費(fèi)支出；3假設(shè)運(yùn)輸車行駛過程中不考慮塞車等各種拋錨現(xiàn)象，以保證每輛車每天可以達(dá)到最大的作業(yè)時間四、問題分析本題考慮從一個貨源地往其余八個地運(yùn)送貨物，要求運(yùn)輸成本最少的運(yùn)送方案。由于運(yùn)輸問題中涉及到車量的限載重量（6噸）、車速的最大值（60km/h）、汽車每天最多的工作時間(8小時)、汽車每次上貨時間（15min）、每次

7、下貨的時間（10min）以及ABC三種原材料每件的毛重和八個需貨地分別所需ABC的件數(shù)等問題。對于問題一，由于車不可以跳頭，我們通過考慮每輛車的容量、卸貨順序、滿足各公司需求按需分配，首先找到一個符合要求的解，然后將其優(yōu)化算出最終結(jié)果。如果假設(shè)一輛車在全程只裝一次，也只卸一次，即用時最短，會花上85分鐘，又因?yàn)橐惠v車工作時間不能超過8h，故一輛車最多跑5次，六輛車共30次。所以我們可以首先考慮在滿足各地所需貨物的前提下，設(shè)計(jì)出車的運(yùn)貨方案，利用lingo軟件從方案選擇出出車次數(shù)最少的一種方案作為汽車的運(yùn)送方案，經(jīng)計(jì)算車次最少需要27車次，其中9車次運(yùn)2B，8車次運(yùn)1A2C，10車次運(yùn)1A1C。

8、然后在利用這種方案向各地安排輸送貨物的方案。由于運(yùn)送B的車是單獨(dú)的，所以我們可以首先將運(yùn)送B的車單獨(dú)考慮，然后在安排同時運(yùn)送A和C的車次。這里可以使用0、1規(guī)劃模型，0表示順時針（即.）運(yùn)送，1表示逆時針（即.）運(yùn)貨。對于問題二，解決方法和第一問中的解決方法是一樣的，不過由于這時候運(yùn)輸車可以掉頭，故可以減少由于運(yùn)輸車在途中空載的路程，而這只會影響模型中目標(biāo)函數(shù)的中的價值系數(shù)的改變，其他和第一問的求解方法是一致的。對于問題三，題中給出了三種不同的運(yùn)輸車，每輛車有不同的裝載方式。所以根據(jù)每個公司對A,B,C的需求，建立線性模型，使得8個公司可以從這些不同的運(yùn)輸方式中選擇最為合適的運(yùn)輸方式的組合以滿

9、足要求，然后根據(jù)每輛車的工作時間，結(jié)合這些公司所選擇的不同的運(yùn)輸方式，確定出在保證完成任務(wù)的情形下，所需要不同類型運(yùn)輸車的最少數(shù)目。然后對不同類型運(yùn)輸車在運(yùn)輸途中的方案的分析，安排出合理的車輛數(shù)和調(diào)度方案。五、模型建立與求解5.1 問題一5.1.1 數(shù)據(jù)分析題中已經(jīng)給出了固定的車輛數(shù)，6輛。首先考慮滿足各公司需求的最少出車次數(shù)，在此基礎(chǔ)上安排調(diào)度車輛，使總成本最少。一輛車在全程只裝一次，只卸貨一次的情況下所用時間最少，根據(jù)題中數(shù)據(jù)，全程會用85分鐘，而一輛車的工作時間不能超過8小時，故一輛車最多只能跑5次，6輛車即最多只跑30次。接著對車輛的裝載情況進(jìn)行分析。一輛車最多只能裝6噸貨物，而一個單

10、位的原材料A,B,C分別毛重4噸、3噸、1噸，假設(shè)每輛車都能發(fā)揮最大裝載力，故有裝載情況（1）一車裝一單位A和兩單位C，（2）一車裝六單位C，（3）一車裝兩單位B，（4）一車裝一單位B和三單位C。故可建立如下模型：其中 表示為一個車裝一單位A和兩單位C， 表示為一個車裝六單位C， 表示為一個車裝兩單位B， 表示為一個車裝一單位B和三單位C， 表示最小運(yùn)輸次數(shù)min =x1+x2+x3+x4;x1=18;2*x3+x4=18;2*x1+6*x2+3*x4=26; 求解得出滿足各公司對于A和B的需求，卻會多運(yùn)C。上面得出的模型顯然不是最優(yōu)模型，經(jīng)分析后優(yōu)化模型，考慮第五種情況：一個車裝一單位A和一

11、單位C。和第六種情況：一個車裝一單位A。得出優(yōu)化后的模型：其中 表示為一個車裝一單位A和一單位C， 表示為一個車裝一單位Amin=x1+x2+x3+x4+x5+x6;x1+x5+x 6=18;2*x3+x4=18;2*x1+3*x4+6*x2+x5=26;x1+x2+x3+x4+x5+x6=30;解得最少出車次數(shù)為27次，其中9次裝兩單位B，8次裝一單位A和兩單位C，10次裝一單位A和一單位C。對于B，可單獨(dú)考慮，27次中有9次裝兩單位的B，可先順時針運(yùn)兩次給公司2，順時針運(yùn)1單位B給公司1,1單位B給公司2，以此類推。對于A,C，由于需要考慮卸貨時小件先卸，大件后卸，公司1可以運(yùn)3次一單位A

12、和一單位C，一次一單位A和一兩單位C。 以此類推。5.1.2 模型建立最少出車次數(shù)為27次，通過分析題中數(shù)據(jù)和線路圖可得到如下求解最小運(yùn)費(fèi)的模型：其中 表示第i次運(yùn)輸裝A的單位數(shù) ， 表示第i次運(yùn)輸裝B的單位數(shù)， 表示第i次運(yùn)輸裝C的單位數(shù)， 表示第i次運(yùn)輸A到達(dá)目的地所走的路程， 表示第i次運(yùn)輸B到達(dá)目的地所走的路程， 表示第i次運(yùn)輸C到達(dá)目的地所走的路程， 表示運(yùn)輸車的方向（等于0按照順時針即 ；等于1按照逆時針即 ）， 表示最小成本， 表示第i次運(yùn)輸j的所走單位路程的單位成本，表示8個公司對A的總需求量，表示8個公司對B的總需求量，表示8個公司對C的總需求量每輛車的容量：卸貨順序：在時，

13、在時，滿足各公司需求：其中：5.1.3 模型求解由于B的運(yùn)輸車次時單獨(dú)的，故單獨(dú)考慮B的運(yùn)輸。我們考慮到車只能順時針或逆時針運(yùn)送以及載重運(yùn)費(fèi)大于空載運(yùn)費(fèi)，所以就近下貨會節(jié)省運(yùn)費(fèi)。又由于運(yùn)B的車每次都是運(yùn)2個單位的B，因此在就近下貨的前提下在考慮八個需要地所需B件數(shù)的奇、偶問題求出運(yùn)送B的最優(yōu)方案。設(shè)計(jì)出 1-8地所需原材料數(shù)量簡表，例如（4 1 5）表示需要4單位A，1單位B，5單位C。 1 2 3 4 5 6 7 8（4 1 5）（1 5 2）（2 0 4）（3 1 2）（1 2 4）（0 4 3）（2 2 5）（5 3 1）利用首先滿足需要偶數(shù)單位原材料的原則分配可得:順時針往2送2*2B

14、，逆時針往8送1*2B，7送1*2B，6送2*2B，5送1*2B后得到： 1 2 3 4 5 6 7 8（4 1 5）（1 1 2）（2 0 4）（3 1 2）（1 0 4）（0 0 3）（2 0 5）（5 1 1）接著順時針往1,2各送1*1B，逆時針往8,4各送1*1B。這樣正好9次將B的運(yùn)送完成。具體列表見附錄表1：故運(yùn)送B所需的載重總費(fèi)用為：162+162+124.2+189.9+54+118.8+162+162+248.4=1383.3元 空車所需的總費(fèi)用為：（45+45+45+29+55+49+45+45+37）*0.4=158元運(yùn)送B所需的總費(fèi)用為：1383.3+158=1541

15、.3元依次可得出運(yùn)A,C的情況，見附錄表2 即運(yùn)送A和C總費(fèi)用為: 4358.2元。綜上所述，六輛車的固定出車成本是120元，從港口固定出車的成本為270元。完成任務(wù)所需全部總費(fèi)用為：1541.3+4358.2+120+270=6289.5元。5.2問題二模型建立與求解0-1表示順時針出發(fā)，卸完貨后掉頭回去；1-0表示逆時針出發(fā)，卸完貨后掉頭回去。方向方案公司車次15012423總運(yùn)費(fèi)（元）最短時 間（min）0-12B2168550-12B2168550-12B11130.26512B11206951-02B256351-02B2123.2471-02B2179.2551-02B2179.2

16、551-02B2257.671總計(jì)150124231467.4533故運(yùn)送向各地運(yùn)送B貨物所需的總費(fèi)用為：168+168+130.2+206+56+123.2+179.2+179.2+257.6=1467.4元方向方案公司車次4,51,22,43,21,40,32,55,1總運(yùn)費(fèi)（元）最短時間（min）0-11A1C1,175.2410-11A1C1,175.2410-11A1C1,175.2410-11A1C1,1272.6830-11A1C1,1272.6831-01A1C0,11,0209551-01A1C0,11,0209551-01A1C0,11,0209551-01A1C0,11,

17、0338.68111A1C1,00,1276.2950-11A2C1,289.6410-11A2C1,2168550-11A2C1,2268.8730-11A2C1,2268.8731-01A2C1,2123.2471-01A2C1,2123.2471-01A2C0,11,1153.2571-01A2C1,2257.671總計(jì)4,51,22，43，21，40，32，55，136451094即運(yùn)送A和C總費(fèi)用為: 3645元。綜上所述，四輛車的固定出車成本是80元，從港口固定出車的成本為270元。完成任務(wù)所需全部總費(fèi)用為：1467.4+3645+80+270=5462.4元。5.3 問題三5.3

18、.1 數(shù)據(jù)分析以盡可能裝滿車為原則，題中所給出的三種不同的運(yùn)輸車4，6，8噸三種車型有以下裝法由于卸貨也需要時間，故可根據(jù)裝載的方式，使每輛車盡可能一次性卸完貨物分析出每個公司所需車次。 4噸（車型）6噸8噸Y1=B+CY4=2BY9=2AY2=AY5=A+2CY10=A+4CY3=4CX6=6CX10=A+B+CY6=B+3CY11=8CY7=B+CY12=2B+2CY8=B+2CY13=B+5CY14=B+AY15=B+4C5.3.2 模型建立min=sum(yi)y2+y5+2*y9+y10+y14=18;y1+2*y4+y6+y7+y8+2*y12+y13+y14+y15=18;y1+

19、4*y3+2*y5+3*y6+y7+2*y8+4*y10+8*y11+2*y12+5*y13+4*y15=26;求解可以得出下表:公司（需求）1（4，1，5）2（1，5，2）3（2，0，4）4（3，1，2）5（1，2，4）6（0，4，3）7（2，2，5）8（5，3，1）車次2Y9+Y13Y4+Y14+Y122Y5Y2+Y5+Y14Y4+Y10Y4+Y7+Y8Y10+Y14+Y7Y9+Y7+2Y14在考慮每輛車在規(guī)定的工作時間的前提下保證車輛盡量少。由表求出：4噸：83分鐘 6噸：567分鐘 8噸：621分鐘而每輛車最多工作480分鐘，故需要派出1+2+2=5輛車。求出總費(fèi)用沒4694.6元。六、模型評價與修正本題采用建立線性約束條件的方法得到用車量數(shù)最少的數(shù)學(xué)模型，然后根據(jù)此模型按需分配車輛的運(yùn)送方案，得到了比較滿意的結(jié)果，能較為準(zhǔn)確的計(jì)算及安排好出實(shí)際生活中遇到