中南大學 數(shù)學建模 lingo matlab 優(yōu)化建模論文 貨運公司的運輸問題

貨運公司的運輸問題摘要本文根據(jù)貨物種類，各公司的貨物需求以及運輸路線，建立線性規(guī)劃數(shù)學模型，并運用圖上作業(yè)法優(yōu)化，提出了運輸費用最低的運輸方案。首先，用lingo11.0計算最少發(fā)車次數(shù)。減少發(fā)車次數(shù)，盡量保證每趟車滿載，能夠有效利用資源，減少運輸費用。然后，運用圖上作業(yè)法，尋找最優(yōu)運輸路線。分析觀察港口到各公司的距離，確定兩條最優(yōu)運輸路線：，。最后，根據(jù)“先卸小件”的題目要求，設計調(diào)運方案表，確定最終最優(yōu)運輸方案。如果“次數(shù)最少”和“路線最優(yōu)”的方案無法滿足“先卸小件”這一條件，則優(yōu)先考慮加運載次數(shù)來達到要求。通過建模求解，得到以下結(jié)果：1.若貨運公司派出運輸車6輛，每輛車從港口出發(fā)（不定方向）后運輸途中不允許掉頭，按照最優(yōu)路線滿載運輸28次，得最小運輸成本為4864元；2.每輛車在運輸途中可隨時掉頭，若要使得成本最小，貨運公司需要安排4輛車，并按照最優(yōu)路線，滿載運行約8小時，成本為4487.2元。3.如果有載重量為4噸、6噸、8噸三種運輸車，載重運費都是1.8元/噸公里，空載費用分別為0.2，0.4，0.7元/公里，其他費用一樣，需要安排3輛8噸貨車，運輸成本為4435.5元。本文運用線性規(guī)劃方法尋找最少發(fā)車次數(shù)，并運用圖上作業(yè)法尋找最優(yōu)行車路線，對問題進行了2次優(yōu)化，使得所建模型更加接近實際問題，所得的解具有很高的實際參考價值；不足之處在于本文費用計算較為繁瑣，公司數(shù)量如果過多，數(shù)據(jù)量會很大，處理起來不方便，不適合廣泛推廣一、問題重述某地區(qū)有8個公司（如圖一編號①至⑧），某天某貨運公司要派車將各公司所需的三種原材料A,B,C從某港口（編號⑨）分別運往各個公司。路線是唯一的雙向道路（如圖一）。貨運公司現(xiàn)有一種載重6噸的運輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次（車輛每出動一次為一車次）。每輛車平均需要用15分鐘的時間裝車，到每個公司卸車時間平均為10分鐘，運輸車平均速度為60公里／小時（不考慮塞車現(xiàn)象），每日工作不超過8小時。運輸車載重運費1.8元/噸公里，運輸車空載費用0.4元/公里。一個單位的原材料A,B,C分別毛重4噸、3噸、1噸，原材料不能拆分，為了安全，大小件同車時必須小件在上，大件在下。卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當天的需求量（見圖二）。問題：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)度的難度所在，給出你的解決問題的想法（可結(jié)合實際情況深入分析）。（圖一）唯一的運輸路線圖和里程數(shù)（圖二）各個公司對每種材料的需求量（單位/天）公司編號各種材料的需求量（單位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧531二、問題假設1.假設貨物運輸過程中不會發(fā)生拋錨、塞車等意外情況，保證工作時間僅僅花在貨物運輸及裝卸上；2.假設貨物的調(diào)配僅由港口調(diào)配，各公司對貨物的先后到達沒有特別要求；三、符號說明X1：A+2C（一單位A加兩單位C的運載方式，以下各項同理）；X2：2B；X3：6C；X4：B+3C；Y1：A；Y2：B+C；Y3：4C；Y4：A+2C；Y5：B+3C；Y6：2B；Y7：6C；Y8：2A；Y9：A+B+C；Y10：A+4C；Y11：2B+2C；Y12：8C；M：運輸成本；四、問題分析本題是一個貨物運輸問題。根據(jù)題意，我們需要在滿足各公司需求，保證工作時間不超過8小時的情況下，尋找最佳的運輸方案，盡可能降低運輸成本。首先，考慮減少運輸?shù)拇螖?shù)。減少運輸次數(shù)，能夠減少車行駛的路程，降低成本。因此，優(yōu)先考慮每輛車滿載在滿載的情況下運輸，運用lingo11.0，求解最少的運輸次數(shù)。接著，運用圖上作業(yè)法（見附錄1），判別最佳的運輸線路。從⑨順時針到④共29公里，從⑨逆時針到⑤共23公里，兩者路程都小于總路程的一半30公里且行車路線無對流為單向。由圖上作業(yè)法得，規(guī)定車不跨過④或者⑤進行負載運輸為最優(yōu)運輸方案。最后，根據(jù)題目中“先卸小件”的條件對方案進行調(diào)整。如果“次數(shù)最少”和“路線最優(yōu)”的方案無法滿足“先卸小件”這一條件，則優(yōu)先考慮加運載次數(shù)來達到模型要求（證明見附錄2）。對于“每輛車在運輸過程中可隨時掉頭”的情況，依舊遵循上述的分析步驟?！暗纛^”的意義在于減少空載行駛的路程以及減少車輛運輸?shù)臅r間。如果負載掉頭，會為貨物的運輸附加額外的路程，增加運輸費用，故空載“掉頭”才有意義。五、模型的建立與求解問題一：首先考慮計算最少的運輸次數(shù)。在滿載情況下，共有以下四種運輸方式：X1：A+2C（一單位A加兩單位C的運載方式，以下各項同理）；X2：2B；X3：6C；X4：B+3C；建立求解最少次數(shù)的數(shù)學模型：MINX1+X2+X3+X4STX1>=182X2+X4>=182X1+6X3+3X4>=26End用lingo11.0求解（見附錄3），解得，X1=18，X2=9，X3=X4=0，最小發(fā)車次數(shù)為27。然后，使用圖上作業(yè)法，畫出路線圖并設計合理的調(diào)運方案。結(jié)合題目“先卸小件”的實際條件，27次運輸無法滿足，故將一次X2：2B拆成運2次B材料，運輸次數(shù)修正為28次。優(yōu)化后的最終運輸方案如下表：順時針調(diào)運方案裝載方式卸貨方式A+2C①*2，②，③*2，④A+C①A①，④*22B①，②*3逆時針調(diào)運方案裝載方式卸貨方式A+2C⑤,⑦*2A+C⑧A⑧*42B④,⑥*2,⑦,⑧*2B+3C⑤*3,⑥*2,⑦根據(jù)調(diào)運方案，計算運輸費用（詳見附錄4）。結(jié)合發(fā)車次數(shù)、車輛數(shù)、出車費用，最終計算得到運輸成本M=4864元。此批貨物共需運輸28次，共有6把車。每次運輸至多停止卸貨2次。假設每趟車都停止卸貨2次，平均每輛車工作6.758小時，滿足題意。問題二：在貨車運輸過程中“允許調(diào)頭”的情況下，會出現(xiàn)以下幾種情況影響運輸成本：1.通過掉頭，選擇最短的返回路徑，節(jié)省了空載運費的支出；2.通過掉頭，選擇最短的返回路徑，節(jié)省了運輸時間；3.貨車載重調(diào)頭可以解決大小貨物的卸貨順序問題，減少出車總次數(shù)，但增加了貨物的運輸距離，導致載重費用的增加。針對情況3，使用圖上作業(yè)法進行最優(yōu)判別，發(fā)現(xiàn)貨車載重折返，相比增加出車次數(shù)會帶來更高的成本，不可取。由上述分析，得出問題二的解題思路與調(diào)運方案與問題一相同；“允許掉頭”只是能讓空載的車及時折返，節(jié)省了空載費以及運輸時間。使用問題一的調(diào)運方案。得到結(jié)果如下（附錄5）：空載費為167.2元完成所有運輸任務的總時間為26.47h則需要安排的車輛數(shù)應是4則完成運輸任務的總費用應為：4487.2元問題三：假設車輛允許掉頭：仿照問題一的解決思路，首先計算最少的發(fā)車次數(shù)。在滿載的條件下，共有以下12種運輸方式：4噸6噸8噸Y1AY4A+2CY82AY2B+CY5B+3CY9A+B+CY34CY62BY10A+4CY76CY112B+2CY128C建立求最少運輸次數(shù)的數(shù)學模型：MINY1+Y2+Y3+Y4+Y5+Y6+Y7+Y8+Y9+Y10+Y11STY1+Y4+2Y8+Y9+Y10>=18Y2+Y5+2Y6+Y9+2Y11>=18Y2+4Y3+2Y4+3Y5+6Y7+Y9+4Y10+2Y11+8Y12>=26END使用lingo11.0，求解（詳見附錄6）得到最少的發(fā)車次數(shù)為19次，其中Y8：2A需9次，Y11：2B+2C需9次，Y12：8C需要1次。使用圖上作業(yè)法，畫出路線圖并設計合理的調(diào)運方案。結(jié)合題目“先卸小件”的實際條件，將2個Y11改運為B+C和B+5C，Y12改為Y7。具體調(diào)運方案如下表：順時針調(diào)運方案裝載方式卸貨方式2A①*2，③，④，①+④2B+2C(①+②)*3B+5C②+③+④逆時針調(diào)運方案裝載方式卸貨方式2A⑧+⑤,⑦,⑧*22B+2C⑦,(⑦+⑥)*2,⑤B+C⑧6C⑦+⑤+④根據(jù)調(diào)運方案，用一輛8t的貨車完成所有任務所需時間約為20小時（小于24小時），故至少應派3輛車來完成此任務，于是這3輛車還有繼續(xù)工作4小時的能力。如按照原計劃，調(diào)用6t和4t的貨車，雖然節(jié)省了空載費用，但比繼續(xù)使用原來的3輛8t的貨車增加的用車費。經(jīng)過計算（見附錄7），繼續(xù)派用8t的貨車去完成運輸任務更優(yōu)。則將方案調(diào)整為全部使用8t的貨車。根據(jù)圖上作業(yè)法的最優(yōu)調(diào)度方案，計算運輸總費用為4435.5元六、參考文獻[1]陳汝棟，于延榮，數(shù)學模型與數(shù)學建模，國防工業(yè)出版社，2006[2]姜啟源，數(shù)學模型，高等教育出版社，2003附錄1.圖上作業(yè)法假設：調(diào)度時，不能安排貨物跨④運輸。證明：根據(jù)圖上作業(yè)法的最優(yōu)判別準則“2，圖中的每一圈中滿足s1＜1/2s且s0＜1/2s(記圈的總長為s，s0，s1分別表示順時針，逆時針的流量。)”.由此，結(jié)合本模型分析可得，調(diào)度時貨車不能跑④⑤之間的路線。但考慮到，當④所需貨物正好可由⑤順便帶過去的情況下，到底是跑④⑤之間的路線運輸還是重新安排發(fā)車的問題。下面給予證明：因為卸貨的先后順序決定了跨⑤運輸順帶給④的貨物，必定是A或B,由于A重于B，如果A能跨線運輸則B必能跨線運輸?，F(xiàn)探討A跨線運輸與重新安排發(fā)車的運費問題。A跨過⑤給④順帶貨物，導致④所需貨物增加了31－29=2m從而導致增加的載重費用為2*1.8=3.6元而重新安排發(fā)車，所增加的發(fā)車費為10元以及重新發(fā)車必定增加了空載路程，即另又增加了額外的空載費。故，重新安排發(fā)車不可取。綜上述，安排調(diào)度時，遵循圖上作業(yè)法德最優(yōu)判別準則，不跑④⑤之間的線路運輸，當且僅當不跨線運輸就必須要增加發(fā)車次數(shù)時，選擇跨線運輸。即假設成立。證畢。并在此結(jié)論的指導下完成圖上作業(yè)法的安排運輸計劃。并進行調(diào)整，優(yōu)化，最終得到最優(yōu)調(diào)度方案。2.假設：調(diào)度時，貨車載重返回會造成更高的成本。證明：倘若貨車載重返回，必定是載A或B，由于A重于B，如果能證明調(diào)度時，不能載B返回，則假設成立。分析實際調(diào)度情況，要載B返回，目的是到較遠站先卸下C.這個目的也能通過增加發(fā)車次數(shù)來達到，即發(fā)兩次車分別向兩個目的地運送貨物B,C。現(xiàn)在只要證明增加發(fā)車次數(shù)比載B返回來達到同樣的目的更省錢即可。令貨車載重返回所增加的載重距離為2m則載B返回增加的運費為1.8*3*2mm又增加一次發(fā)車所增加的的出港費為10m增加一次發(fā)車所增加的空載距離為m+n增加的空載費用為0.4*（m+n）本模型中，取m=4時，有l(wèi)10+0.4*（m+n）—1.8*3*2m=11.6+0.4n-43.2=0.4n-31.6l令0.4n-31.6》01則有n》79而n的取值不可能滿足n》79易知，當m的取值增大時，滿足不等式1的n值隨之增大。而本模型中的m值均大于4，則不等式1始終成立。即，增加一次發(fā)車所增加的費用必定比載重返回所增加的載重費要少。故，假設成立。證畢。3.問題一求解：MINX1+X2+X3+X4STX1>=182X2+X4>=182X1+6X3+3X4>=26EndGlobaloptimalsolutionfound.Objectivevalue:27.00000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostX118.000000.000000X29.0000000.000000X30.0000001.000000X40.0000000.5000000RowSlackorSurplusDualPrice127.00000-1.00000020.000000-1.00000030.000000-0.5000000410.000000.0000004.方案1計算：總的卸貨次數(shù)為33次，卸貨時間裝車次數(shù)為28，裝貨時間運行時間所需總時間平均每輛車的運行時間載重的總路程：S貨車卸空處的公司編號；：港口到號公司的調(diào)運距離；：貨車在公司處的卸空次數(shù)由不能調(diào)頭可知空載費用元：公司編號，取值1,2…8;:各公司所需A,B,C貨物的總重量；:港口到號公司的調(diào)運距離；載重費用元；出港口費用：元派車費用：元總費用：元5.問題二：方案2計算：總得卸貨時間：總得裝車時間：計算空載路程：考慮到黨貨車沒到達=4\*GB3④點的時候，按原路程返回路程會比跨過=4\*GB3④點返回要短，所以確定此種情況貨車按原路返回。當貨車到達=4\*GB3④點的時候，都使貨車按路線=4\*GB3④=3\*GB3③=2\*GB3②=1\*GB3①=9\*GB3⑨返回。所以參照方案1的計算可知又由于調(diào)運方案不變，所以載重路程不變，即貨車運行時間所需總時間假設派出的車輛都滿天工作（即每天工作8h），則需要派出的車輛n最少為，取，即只需要配出4輛車就能滿足調(diào)運工作要求。計算費用：=1\*GB2⑴空載費用：=2\*GB2⑵載重費用：=3\*GB2⑶出港口費用：=4\*GB2⑷派車費用：總費用：6.問題三求解：MINY1+Y2+Y3+Y4+Y5+Y6+Y7+Y8+Y9+Y10+Y11STY1+Y4+2Y8+Y9+Y10>=18Y2+Y5+2Y6+Y9+2Y11>=18Y2+4Y3+2Y4+3Y5+6Y7+Y9+4Y10+2Y11+8Y12>=26ENDGlobaloptimalsolutionfound.Objectivevalue:18.00000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostY10.0000000.5000000Y20.0000000.5000000Y30.0000001.000000Y40.0000000.5000000Y50.0000000.5000000Y60.0000000.000000Y70.0000001.000000Y89.0000000.0000