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

貨運公司的運輸問題隊伍名稱Aurora隊員馮潔黎寧褚燕摘要本文根據(jù)貨運公司需要完成的運輸量和確定的運輸路線圖，分別建立了線性規(guī)劃模型和0-1規(guī)劃模型，解決了車輛安排問題和調(diào)度問題，得出了運費最小的最優(yōu)方案。問題一，由于派車費用固定，每次出車的出車成本費用也是固定的，為了減小運輸成本，就要減少出車次數(shù)，但同時又要滿足各公司對材料的需求，以公司需求為約束條件，以最小出車數(shù)為目標函數(shù)，建立一個線性規(guī)劃模型，并用Lingo求解，得出了最少出車次數(shù)為27輛。然后，進一步考慮運輸車調(diào)度問題，由于出車方向分為逆時針和順時針兩種情況，而且這兩種情況是非此即彼的對立關系，故建立了一個0-1規(guī)劃模型，0表示順時針行駛，1表示逆時針行駛，采用Lingo求解，得出了運輸車在運輸途中不允許掉頭的調(diào)度方案（見表一）。問題二中允許運輸車掉頭只會影響運輸車卸貨后空載的行駛路程，也即運輸車的空載費用，故通過修改目標函數(shù)中的相關系數(shù)，仍然建立線性規(guī)劃模型和0-1規(guī)劃模型，采用Lingo求解，得出需要安排的運輸車為3輛，運輸途中允許掉頭的調(diào)度方案見表二。問題三中增加了運輸車的種類，并區(qū)分了運輸車空載時的運費，由于運輸車裝載材料的方式有很多種，在上面分析的基礎上，增加約束條件，得出一種新的線性規(guī)劃模型，通過Lingo解得需要安排的車輛數(shù)為5輛，調(diào)度方案見表三。關鍵字：線性規(guī)劃模型，0-1規(guī)劃模型2問題重述某地區(qū)有8個公司（如圖一編號①至⑧），某天某貨運公司要派車將各公司所需的三種原材料A,B,C從某港口（編號⑨）分別運往各個公司。路線是唯一的雙向道路（如圖一）。貨運公司現(xiàn)有一種載重6噸的運輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次（車輛每出動一次為一車次）。每輛車平均需要用15分鐘的時間裝車，到每個公司卸車時間平均為10分鐘，運輸車平均速度為60公里／小時（不考慮塞車現(xiàn)象），每日工作不超過8小時。運輸車載重運費1.8元/噸公里，運輸車空載費用0.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)度的難度所在，給出你的解決問題的想法（可結合實際情況深入分析）。（圖一）唯一的運輸路線圖和里程數(shù)（圖二）各個公司對每種材料的需求量（單位/天）公司編號各種材料的需求量（單位/天）ABC4151522043121240432255313模型假設1．假設每輛車裝載時發(fā)揮其最大的裝載能力；2．假設貨運公司都是先考慮節(jié)省人力和出車次數(shù)最少的情況下再考慮如何安排運輸方式以減少經(jīng)費支出；3．假設運輸車行駛過程中不考慮塞車拋錨現(xiàn)象，以保證每輛車每天可以達到最大的作業(yè)時間。4符號說明C1一單位A材料和二單位C材料的裝載方式；C2二單位B材料的裝載方式；C3六單位C材料的裝載方式；C4一單位B材料和三單位C材料的裝載方式；Pij被調(diào)用車的運輸經(jīng)費；Sij所運載的區(qū)間的路程；Sji表示空載路程；Xij第i輛列車的調(diào)度情況；Xi0=1表示第i輛車采用順時針運輸；Xi0=0表示第i輛車不采用順時針運輸；Xi1=1表示第i輛車采用逆時針運輸；Xi1=0表示第i輛車不采用順時針運輸；t0裝載時間；t1路途行程時間；t2卸載時間；Gni（n=1—8，i=1，2，3）表示第n個公司分別對A，B，C產(chǎn)品的需求量；5問題分析對于這個貨運公司的運輸問題，問題一中給出了6輛可以使用的運輸車，根據(jù)各公司對材料的需求，這6輛車必然會被反復的調(diào)用。要減少運輸經(jīng)費，首先要減少出車的次數(shù)，但是究竟要出車幾次才可以滿足公司對材料的需求呢？由于每輛車只能裝載6噸的貨物，我們考慮每次盡可能讓車輛裝滿6噸貨物，且可以在一個公司一次性卸下，6噸車全部裝滿原材料的方案有：6個C，2個B，1個A2個C，1個B3個C四種，這樣再根據(jù)八個公司對A，B，C三種材料總的需求量就可以建立一個線性規(guī)劃模型求出出車的最少次數(shù)S。在滿足最少出車次數(shù)S的前提下，還要考慮運輸車的調(diào)度問題，出車方向不定，分為逆時針和順時針兩種情況，而且這兩種情況是非此即彼的對立關系，這屬于0-1規(guī)劃問題，解決的方法是令Xi0等于1表示采用第i輛車次按順時針來運行，Xi0等于0表示不采用第i輛車次順時針運行。Xi1等于1表示采用第i輛車次逆時針運行，等于0表示不采用這輛車次逆時針運行，再結合題目中的其他相關數(shù)據(jù)便可以建立一個0-1規(guī)劃模型求解。問題二中的解決方法和第一問中的解決方法是一樣的，不過由于這時候運輸車可以掉頭，故可以減少由于運輸車在途中空載的路程，而這只會影響模型中目標函數(shù)的中的價值系數(shù)的改變，其他和第一問的求解方法是一致的。在第三問中給出了三種有不同裝載力的運輸車。我們可顛覆問題一中的思路，直接判定出港口至某公司的最短路徑。然后將該公司所需所有材料裝在一批車上，沿最短路徑運抵該公司。卸下所有材料，然后原路返回。一對于這三種不同的運輸車可以得出很多不同的裝載方式，比如對于裝載量為8噸的運輸車，可以為每次裝載2個A或者1個A和B等。根據(jù)每個公司對A，B，C不同材料的要求，我們再建立一個線性模型，使得這八個公司可以從這些不同的運輸方式中選擇最為合適的運輸方式的組合以滿足要求，然后對這些公司所選擇的不同的運輸方式再根據(jù)題目中每輛車每天最大的作業(yè)時間，可以確定出在保證完成任務的情形下，所需要不同類型運輸車的最少數(shù)目這樣就可以減少指派運輸車的支出。再結合前面的不同運輸方式的組合，就可以安排出車輛數(shù)和調(diào)度方案了。6模型的建立與求解6.1問題一的求解`首先求解出滿足每個公司的需求的最少出車次數(shù)，再在此情形下考慮如何調(diào)度這些車次，使得整個運輸作業(yè)所需的經(jīng)費最少。模型的建立與求解根據(jù)題目中給定的各個公司對A，B，C三種不同的材料的需求，可以計算出這些公司每天所需A，B，C三種材料的總數(shù)分別為18單位，18單位，26單位，由于每輛車的載重都是6噸，在假設一的前提下我們可以得出每輛車的裝載方式有如下四種方式：（a）1A+2C，（b）2B，（c）6C，（d）B+3C。我們分別設這四種方式需要調(diào)度的次數(shù)為C1，C2，C3，C4這樣我們就可以建立如下數(shù)學模型：MINS=C1+C2+C3+C4C1〉=182C2+C4〉=182C1+6C3+3C4〉=26C1~~C4為正整數(shù)；用LINGO進行求解可以得到S=27，C1=18，C2=9，C3=0，C4=0；對于這個結果可以進一步分析可知，公司并不需要那么多C材料（這也正是（c）,(d)運輸方式被排除在外的原因）。故只需要（a）的運輸方式為13個再加上單獨運輸A材料的5車次和9車次（b）運輸方式即可滿足條件，但是這未必是最好的安排，因為通過觀察知在運輸方式（a）與單獨運輸A的方式之間，還可能存在運輸A+C這種方式。故將次方案考慮在內(nèi)。圖三如圖三，按順時針方式對每個公司進行綜合的考慮可以得到A+2C方式12種，A+C方式2種，單獨運輸A方式4種，2B方式9種，可以較好的滿足題設條件。各種運輸方式表示調(diào)用順序表示符號A+2C方式A+C方式A方式2B方式順時針調(diào)用Xi0（i=1~27）i=1~12i=13~14i=15~18i=19~27逆時針調(diào)用Xi1（i=1~27）i=7~18i=5~6i=1~4i=19~27，由于不考慮掉頭，故可以得到其運輸所需要的經(jīng)費為Pij=∑（1.8w*Sij+0.4*sji）（i=1~27，j=0或1），其中w為運輸車的載重，Sij為所運載的區(qū)間的路程，Sji則表示空車回到港口的距離，總費用為：P=∑Pij+S*10+20*K，其中K為所調(diào)用的車輛的個數(shù)；其中Pij的計算所得的結果參看表（1），設Xij（其中i=1~27，j=0或1）為第i輛列車的調(diào)度情況：其中Xi0=1表示第i輛車次采用順時針運行，Xi0=0則表示不采用第i輛車次順時針運輸，Xi1=1則表示第i輛車采用逆時針運輸，Xi1=0表示第i輛車不采用順時針運輸。由上可以對這個問題建立一個0-1規(guī)劃模型：Min∑Pij*XijS.T∑Xij〉=27現(xiàn)考慮約束條件列出各公司材料所有可能的運輸車次，得下表：公司A的滿足B的滿足C的滿足順時針逆時針順時針逆時針順時針逆時針11020130150161171181611902711020130171181612301511902002102512612713016134050131141405014115146016017010111112122024160131570912202302312417080111121623024025021122123190110911017809071812502602012111001101207181918100110120140180112131415126027019120114051以公司一為例，可得如下約束條件（即正向運輸與逆向行駛?cè)赃x其一）。x10+x181=1;x20+x171=1;x130+x61=1;x150+x151=1; 以公司二為例，可得如下約束條件（即若有多次相同運載方案，則盡可能同向）x30+x161=1;x141-x151=0;x40+x141=1;x50-x40=0;……….（其他公司的處理方法一樣）Xij=0或1結論：對上0-1模型，代入附表中的數(shù)據(jù)，用Lingo求解可得∑Pij=5227.2，又由于S=27，K=6，所以總費用為P=5617.2（元），其中所調(diào)用的車次以及每個車次的所花的經(jīng)費參見表（3），對于所得的結果，由于車的速度為60公里/時，那么每輛車運行一周回到港口剛好需要1小時，而現(xiàn)在需要共需要轉(zhuǎn)27圈，又每輛車的每天的工作時間是8小時，所以這6輛車一天的能力是運轉(zhuǎn)48圈，所以即使再考慮裝載時間和卸貨時間所得結果也是合理的。本題求解時，通過線性規(guī)劃，求出最少出車次數(shù)。但其實為了減少費用，可以單獨枚舉，即根據(jù)每個公司的需求，先將裝滿6噸貨物且一次性卸載的情況排除后，針對每個公司剩余需求量進行組合，但是我們沒有進行該項復雜的工作。6.2問題二的求解問題二中的車輛可以掉頭，但是這只會影響每輛車在運行過程中空車運行回港口的路費，所以求解的模型和第一問中的模型是一樣的，只不過這時候的Pij已經(jīng)有所變化，這時候的Pij的求解是這樣計算的：如果Sji>Sij，則掉頭，否則繼續(xù)前進，其他的計算方式則和第一問中的一樣，具體的計算結果參見表（4）；結論：仍然使用Lingo進行求解，可以得到這時候的∑Pij=4615.2，這時候S仍為27，而K的確定是這樣的：把所有車次的時間按時間公式∑（t0+t1+t2），求出總的時間為：1711分鐘。每一輛車的最大工作時間為：60*8=480分鐘，粗略計算，需車數(shù)：1711/480≈4輛，綜合考慮裝載和卸貨時間用的時間，這個值也是合理的。那么這時的總費用P=4965.2（元）該道題跟第一問不同之處在于，當某一輛車上的原材料全部卸下之后，將它的已經(jīng)走過的路程與剩余路程進行比較，如果是已走的較短，則返程，否則走一圈回到港口。6．3問題三的求解以盡可能裝滿車為原則，4，6，8噸三種車型有以下裝法，并編好序。每輛車盡可能一次性卸完分析出每個公司所需車次。4噸（車型）6噸8噸Y1=B+CY4=2BY8=2AY2=AY5=A+2CY9=A+4CY3=4CX6=6CX10=A+B+CY7=B+3CY11=8CY15=B+CY12=2B+2CY16=B+2CY13=B+5CY14=B+AY17=B+4C對于每個公司的需求我們都是考慮盡可能用上面給出的不同的裝載方式來滿足，可建立模型如下：Min∑YiSTY2+Y5+2Y8+Y9+Y14=Gn1Y1+2Y4+Y7+Y15+Y16+Y11+2Y12+Y13+Y14+Y17=Gn24Y3+2Y5+3Y7+Y15+2Y16+4Y9+8Y11+2Y12+5Y13+4Y17=Gn3Yi是正整數(shù)其中Gni（n=1—8，i=1，2，3）表示第n個公司分別對A，B，C產(chǎn)品的需求量。代入用Lingo求解可以得出下表公司（需求）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）車次2Y8+X13Y4+Y14+Y122Y5Y2+Y5+Y14Y4+Y9Y4+Y15+Y16Y9+Y14+Y15Y8+Y10+2Y14現(xiàn)對上表分析，車輛數(shù)：考慮到增加車輛有20元的增加費用，車輛越少越好。但必須在規(guī)定時間內(nèi)（8小時），完成一定車次的任務。按時間計算公式:Σ（t0+t1+t2）(t0—裝載時間，t1—路途行程時間，t2—卸載時間)求出三種車所用時間分別為：4噸：83分鐘6噸：567分鐘8噸：621分鐘一輛車的最大工作時間為：8*60=480（分鐘）。易知所需車數(shù)為：1+2+2=5（輛）按運費計算公式:求出完成一天任務的總運費為：4694.6元?？紤]到，4噸車只用了一次，可加開一次6噸車代替，以減少費用。事實證明6噸車加開一次時間是完全允許的，可節(jié)約費用：20-（0．4-0.2）*24=15.2（元）。那么車輛數(shù)變?yōu)椋?輛;費用：4679.4元。這里我們的想法是，因為8噸的車空載費用比4噸和6噸之和要多，且4噸和6噸之和載重大于8噸，因此，如果減少八噸的車的使用輛數(shù)，可能節(jié)省的載重費用會少于增加派車輛數(shù)的派車費用。但是，這個單獨實現(xiàn)起來比較麻煩，需要用到編程軟件，因為對編程軟件的使用了解不多，沒有編程成功。7．參考文獻[1]徐玖平，胡知能，王委，運籌學，科學出版社，2004[2]姜啟源，數(shù)學模型，高等教育出版社，2003[3]謝金星，薛毅，優(yōu)化建模與LINDO/LINGO軟件，2005[4]貨運公司的運輸問題朱遠鵬賈利攀李雯附錄附表一經(jīng)費車次iPij011107.2582107.2583180584273.6585273.6676325.6471.27408.8138.48490.4138.49519.2227.210567.2288.811574.4317.612574.4317.61392.8380.414596398.41578.4459.616221.2539.617221.2564.818398564.819142．2762010618021138．418022180365．623220448．824303．24922549251226492563．627271596附表二經(jīng)費車次iPij011107.2582107.2583180584585676471.27138.48138.49227.210288.811317.612317.61392．8380.414398.415459.616539.61718197620106180211802223448．824252627附表四經(jīng)費車次iPij01189．638289．6383168384268．8385268．8476324．8471.27408．8123．28476123．29519．2221.610567．2288.811574.4317.612574.4317.61375．2380.414596398.41560．8459.616220.4539.617220．4564.818398564.81948．6562016890．821168146．422365．616823448．8214．424492303．22551249226563．649227596527附表五經(jīng)費車次iPij01189．638289．6383168384385476471.27123．28123．29221.610288.811317.612317.61375．2380.414398.415459.616539.617181948．6562016890．821168146．42216823214．424303．2252627LINGO代碼一Model:min=107.2*x10+107.2*x20+180*x30+273.6*x40+273.6*x50+325.6*x60+408.8*x70+490.4*x80+519.2*x90+567.2*x100+574.4*x110+574.4*x120+92.8*x130+596*x140+78.4*x150+221.2*x160+221.2*x170+398*x180+58*x11+58*x21+58*x31+58*x41+67*x51+471.2*x61+138.4*x71+138.4*x81+227.2*x91+288.8*x101+317.6*x111+317.6*x121+380.4*x131+398.4*x141+459.6*x151+539.6*x161+564.8*x171+564.8*x181+76*x190+142.2*x191+106*x200+180*x201+158.4*x210+180*x211+180*x220+365.6*x221+220*x230+448.8*x231+303.2*x240+492*x241+492*x250+512*x251+492*x260+563.6*x261+527*x270+596*x271;x10+x20+x30+x40+x50+x60+x70+x80+x90+x100+x110+x120+x130+x140+x150+x160+x170+x180+x11+x21+x31+x41+x51+x61+x71+x81+x91+x101+x111+x121+x131+x141+x151+x161+x171+x181+x190+x191+x200+x201+x210+x211+x220+x221+x231+x231+x240+x241+x250+x251+x260+x261+x270+x271>=27;x10+x181=1;x20+x171=1;x130+x61=1;x150+x151=1;x30+x161=1;x141-x151=0;x40+x141=1;x50-x40=0;x131-x141=0;x101-x131=0;x111-x131=0;x121-x131=0;x60+x131=1;x101-x131=0;x111-x131=0;x121-x131=0;x60-x160=0;x60-x170=0;x70+x91=1;x70-x80=0;x91-x111=0;x91-x121=0;x101-x91=0;x90+x81=1;x90-x110=0;x100-x110=0;x120-x110=0;x71-x91=0;x81-x91=0;x80-x90=0;x140+x11=1;x100-x140=0;x110-x140=0;x120-x140=0;x180-x140=0;x11-x51=0;x21-x51=0;x31-x51=0;x140+x51=1;x41-x51=0;x21-x51=0;x31-x51=0;x41-x51=0;x190+x271=1;x200+x261=1;x210+x251=1;x220+x241=1;x230+x231=1;x240+x221=1;x250+x211=1;x260+x201=1;x270+x191=1;@BIN(x10);@BIN(X11);@BIN(X20);@BIN(X21);@BIN(X30);@BIN(X31);@BIN(X40);@BIN(X41);@BIN(X50);@BIN(X51);@BIN(X60);@BIN(X61);@BIN(X70);@BIN(X71);@BIN(X80);@BIN(X81);@BIN(X90);@BIN(X91);@BIN(x100);@BIN(X101);@BIN(X110);@BIN(X111);@BIN(X120);@BIN(X121);@BIN(X130);@BIN(X131);@BIN(X140);@BIN(X141);@BIN(X150);@BIN(X151);@BIN(X160);@BIN(X161);@BIN(X170);@BIN(X171);@BIN(X180);@BIN(X181);@BIN(x190);@BIN(X191);@BIN(X200);@BIN(X201);@BIN(X210);@BIN(X211);@BIN(X220);@BIN(X221);@BIN(X230);@BIN(X231);@BIN(X240);@BIN(X241);@BIN(X250);@BIN(X251);@BIN(X260);@BIN(X261);@BIN(X270);@BIN(X271);endLINGO代碼二Model:min=89.6*x10+89.6*x20+168*x30+268.8*x40+268.8*x50+324.8*x60+408.8*x70+476*x80+519.2*x90+567.2*x100+574.4*x110+574.4*x120+75.2*x130+596*x140+60.8*x150+220.4*x160+220.4*x170+398*x180+38*x11+38*x21+38*x31+38*x41+47*x51+471.2*x61+123.2*x71+123.2*x81+221.6*x91+288.8*x101+317.6*x111+317.6*x121+380.4*x131+398.4*x141+459.6*x151+539.6*x161+564.8*x171+564.8*x181+48.6*x190+56*x191+168*x200+90.8*x201+168*x210+146.4*x211+365.6*x220+168*x221+448.8*x230+214.4*x231+492*x240+303.2*x241+512*x250+492*x251+563.6*x260+492*x261+596*x270+527*x271;x10+x20+x30+x40+x50+x60+x70+x80+x90+x100+x110+x120+x130+x140+x150+x160+x170+x180+x11+x21+x31+x41+x51+x61+x71+x81+x91+x101+x111+x121+x131+x141+x151+x161+x171+x181+x190+x191+x200+x201+x210+x211+x220+x221+x231+x231+x240+x241+x250+x251+x260+x261+x270+x271>=27;x10+x181=1;x20+x171=1;x130+x61=1;x150+x151=1