數(shù)學建模運輸問題送貨問題

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

2、并求解,得出滿足問題一的調(diào)度方案見附錄表1.對于問題二,車輛允許掉頭,加上車輛裝載貨物和空裝時運輸費不同,要使總本錢最小,故可以通過修改原目標函數(shù),建立線性規(guī)劃模型和0-1規(guī)劃模型,求解,得出最正確派出車輛3輛并列出滿足問題二的調(diào)度方案.對于問題三第一小問,增加了運輸車輛的類型.即裝載材料的方法很多,在上述分析的根底上,通過增加約束條件,建立新的線性規(guī)劃模型,并求解,得出滿足問題三的調(diào)度方案.在第二小問中,由于給出局部公司有道路相通,可采用運籌學中的最短路問題的解決方法加以解決.關鍵字：線性規(guī)劃模型0-1規(guī)劃模型調(diào)度一、問題重述某地區(qū)有8個公司如圖一編號至,某大某貨運公司要派車將各公司所需的三

3、種原材料A,B,C從某港口編號分別運往各個公司.路線是唯一的雙向道路如圖1.貨運公司現(xiàn)有一種載重6噸的運輸車,派車有固定本錢20元/輛,從港口出車有固定本錢為10元/車次車輛每出動一次為一車次.每輛車平均需要用15分鐘的時間裝車,到每個公司卸車時間平均為10分鐘,運輸車平均速度為60公里/小時不考慮塞車現(xiàn)象,每日工作不超過8小時.運輸車載重運費1.8元/噸公里,運輸車空載費用0.4元/公里.一個單位的原材料A,B,C分別毛重4噸、3噸、1噸,原材料不能拆分,為了平安,大小件同車時必須小件在上,大件在下.卸貨時必須先卸小件,而且不允許卸下來的材料再裝上車,另外必須要滿足各公司當天的需求量見表1.

4、問題：1、貨運公司派出運輸車6輛,每輛車從港口出發(fā)不定方向后運輸途中不允許掉頭,應如何調(diào)度每輛車的運載方案,運輸本錢使得運費最小.2、每輛車在運輸途中可隨時掉頭,假設要使得本錢最小,貨運公司怎么安排車輛數(shù)？應如何調(diào)度？3、1如果有載重量為4噸、6噸、8噸三種運輸車,載重運費都是1.8元/噸公里,空載費用分別為0.2,0.4,0.7元/公里,其他費用一樣,又如何安排車輛數(shù)和調(diào)度方案？2當各個公司間都有或者局部有道路直接相通時,分析運輸調(diào)度的難度所在,給出你的解決問題的想法可結合實際情況深入分析.圖1唯一的運輸路線圖和里程數(shù)司A41231025B1501r2423C52424351、符號說明x1表

5、示為一個車裝一單位A和兩單位C;x2表示為一個車裝六單位C;x3表示為一個車裝兩單位B;x4表示為一個車裝一單位B和三單位C;S表示最小運輸次數(shù)；x5表示為一個車裝一單位A和一單位C;x6表示為一個車裝一單位A;Xi1表示第i次運輸裝A的單位數(shù)；Xi2表示第i次運輸裝B的單位數(shù)；Xi3表示第i次運輸裝C的單位數(shù)；Y i1表示第i次運輸A到達目的地所走的路程；Y i2表示第i次運輸B到達目的地所走的路程；Y i3表示第i次運輸C到達目的地所走的路程；P表示運輸車的方向等于0根據(jù)順時針即092;等于1根據(jù)逆時針即09；M表示最小本錢；Zij表示第i次運輸j的所走單位路程的單位本錢；a表小8個公司對

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

7、C的件數(shù)等問題.對于問題一,由于車不可以跳頭,我們通過考慮每輛車的容量、卸貨順序、滿足各公司需求按需分配,首先找到一個符合要求的解,然后將其優(yōu)化算出最終結果.如果假設一輛車在全程只裝一次,也只卸一次,即用時最短,會花上85分鐘,又由于一輛車工作時間不能超過8h,故一輛車最多跑5次,六輛車共30次o所以我們可以首先考慮在滿足各地所需貨物的前提下,設計出車的運貨方案,利用lingo軟件從方案選擇出出車次數(shù)最少的一種方案作為汽車的運送方案,經(jīng)計算車次最少需要27車次,其中9車次運2B,8車次運1A2c10車次運1A1G然后在利用這種方案向各地安排輸送貨物的方案.由于運送B的車是單獨的,所以我們可以首

8、先將運送B的車單獨考慮,然后在安排同時運送A和C的車次.這里可以使用0、1規(guī)劃模型,0表示順時針(即.)運送,1表示逆時針(即.)運貨.對于問題二,解決方法和第一問中的解決方法是一樣的,不過由于這時候運輸車可以掉頭,故可以減少由于運輸車在途中空載的路程,而這只會影響模型中目標函數(shù)的中的價值系數(shù)的改變,其他和第一問的求解方法是一致的.對于問題三,題中給出了三種不同的運輸車,每輛車有不同的裝載方式.所以根據(jù)每個公司對A,B,C的需求,建立線性模型,使彳#8個公司可以從這些不同的運輸方式中選擇最為適宜的運輸方式的組合以滿足要求,然后根據(jù)每輛車的工作時間,結合這些公司所選擇的不同的運輸方式,確定出在保

9、證完成任務的情形下,所需要不同類型運輸車的最少數(shù)目.然后對不同類型運輸車在運輸途中的方案的分析,安排出合理的車輛數(shù)和調(diào)度方案.五、模型建立與求解5.1 問題一5.1.1 數(shù)據(jù)分析題中已經(jīng)給出了固定的車輛數(shù),6輛.首先考慮滿足各公司需求的最少出車次數(shù),在此根底上安排調(diào)度車輛,使總本錢最少.一輛車在全程只裝一次,只卸貨一次的情況下所用時間最少,根據(jù)題中數(shù)據(jù),全程會用85分鐘,而一輛車的工作時間不能超過8小時,故一輛車最多只能跑5次,6輛車即最多只跑30次.接著對車輛的裝載情況進行分析.一輛車最多只能裝6噸貨物,而一個單位的原材料A,B,C分別毛重4噸、3噸、1噸,假設每輛車都能發(fā)揮最大裝載力,故有

10、裝載情況(1)一車裝一單位AJ口兩單位C,(2)一車裝六單位C,(3)一車裝兩單位B,(4)一車裝一單位出口三單位C.故可建立如下模型：其中X1表示為一個車裝一單位用口兩單位C,x2表示為一個車裝六單位C,x3表示為一個車裝兩單位B,x4表示為一個車裝一單位出口三單位C,S表示最小運輸次數(shù)min=x1+x2+x3+x4;Xl=18；J2*x3+x4=18;12*x1+6*x2+3*x4>=26;求解得出滿足各公司對于所口B的需求,卻會多運C.上面得出的模型顯然不是最優(yōu)模型,經(jīng)分析后優(yōu)化模型,考慮第五種情況：一個車裝一單位將口一單位C.和第六種情況：一個車裝一單位A.得出優(yōu)化后的模型：其中

11、4表示為一個車裝一單位用口一單位C,x表示為一個車裝一單位Amin=x1+x2+x3+x4+x5+x6;x1+x5+x6=18;J2*x3+x4=18;2*x1+3*x4+6*x2+x5=26;Lx1+x2+x3+x4+x5+x6<=30;解得最少出車次數(shù)為27次,其中9次裝兩單位B,8次裝一單位A和兩單位C,10次裝一單位A和一單位Co對于B,可單獨考慮,27次中有9次裝兩單位的B,可先順時針運兩次給公司2,順時針運1單位B合公司1,1單位B合公司2,以此類推.對于A,C,由于需要考慮卸貨時小件先卸,大件后卸,公司1可以運3次一單位府口一單位C,一次一單位用口一兩單位C以此類推.5.1

12、.2模型建立最少出車次數(shù)為27次,通過分析題中數(shù)據(jù)和線路圖可得到如下求解最小運費的模型：其中Xn表示第i次運輸裝A的單位數(shù),Xi2表示第i次運輸裝B的單位數(shù),Xi3表示第i次運輸裝C的單位數(shù),表示第i次運輸A到達目的地所走的路程,丫2表示第i次運輸B到達目的地所走的路程,Yi3表示第i次運輸C到達目的地所走的路程,P表示運輸車的方向等于0根據(jù)順時針即09；等于1根據(jù)逆時針即3,M表示最小本錢,Zij表示第i次運輸j的所走單位路程的單位本錢,a表示8個公司對A的總需求量,b表示8個公司對B的總需求量,c表示8個公司對C的總需求量每輛車的容量：Xi1Xi2Xi36卸貨順序：在P0時,YiY2Y2Y

13、3在P1時,Yi1丫2丫2丫3mXi1ai1m滿足各公司需求：Xi2bi1mXi3ci1其中：i1,2,.,m,j1,2,.,n5.1.3模型求解由于B的運輸車次時單獨的,故單獨考慮B的運輸.我們考慮到車只能順時針或逆時針運送以及載重運費大于空載運費,所以就近下貨會節(jié)省運費.又由于運B的車每次都是運2個單位的B,因此在就近下貨的前提下在考慮八個需要地所需B件數(shù)的奇、偶問題求出運送B的最優(yōu)方案.設計出1-8地所需原材料數(shù)量簡表,例如(415)表示需要4單位A,1單位B,5單位C.12345678(415)(152)(204)(312)(124)(043)(225)(531)利用首先滿足需要偶數(shù)單

14、位原材料的原那么分配可得：順時針往2送2*2B,逆時針往8送1*2B,7送1*2B,6送2*2B,5送1*2B后得到：12345678(415)(112)(204)(312)(104)(003)(205)(511)接著順時針往1,2各送1*1B,逆時針往8,4各送1*1B.這樣正好9次將B的運送完成.具體列表見附錄表1:故運送B所需的載重總費用為：162+162+124.2+189.9+54+118.8+162+162+248.4=1383.3元空車所需的總費用為：(45+45+45+29+55+49+45+45+37*0.4=158元運送B所需的總費用為：1383.3+158=1541.3元

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

16、2257.671總計150124231467.4533故運送向各地運送限物所需的總費用為：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總運費(元)最短時間(min)0-111A1C1.175.2410-11A1C1,175.2410-11A1C1,175.21410-111A1C1,1272.6830-11A1C1,1272.6831-011A1C：0,11,0209r5511-01A1CI0,11,0209551-01A1C0,11,0209551-011A1C0,11,

17、0338.6r81111A1C1,00,1276.2950-11A2C1,289.6410-111A2C1,2168r550-11A2C1,2268.8730-11A2C1,2268.8731-011A2C1,2123.2471-01A2C1,2123.2471-01A2C0,11,1153.2571-01A2C1,2257.671總計4,51,22,43,21,40,32,55,136451094即運送府DC總費用為：3645元.綜上所述,四輛車的固定出車本錢是80元,從港口固定出車的本錢為270元完成任務所需全部總費用為：1467.4+3645+80+270=5462.4元.5.3 問題三

18、5.3.1 數(shù)據(jù)分析以盡可能裝滿車為原那么,題中所給出的三種不同的運輸車4,6,8噸三種車型有以下裝法由于卸貨也需要時間,故可根據(jù)裝載的方式,使每輛車盡可能一次性卸完貨物分析出每個公司所需車次.4噸車型6噸8噸Y1=B+CY4=2BY9=2AY2=AY5=A+2CY10=A+4CY3=4CY6=B+3Cy11=8CY7=B+CY12=2B+2CY8=B+2CY13=B+5C1Y14=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+4*y3+2*y5+3*y

19、6+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輛車.求出總費用沒4694.6元.六、模型評價與修正此題采用建立線性約束條件的方法得到用車量數(shù)最少的數(shù)學模型,然后根據(jù)此模型按需分配車輛的運送方案,得到了比擬滿意的結果,能較為準確的計