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

貨運公司的運輸問題108隊：劉漢云、秦思謀、周彪摘要本文根據(jù)貨運公司確定的運輸路線圖和需要完成的運輸量，建立了線性規(guī)劃模型，采用枚舉方法，解決了在運費最小的前提下貨運公司的車輛調(diào)度問題。首先建立線性規(guī)劃模型。貨運公司運費來自兩方面的費用：派車與出車的固定成本、載重與空載行程產(chǎn)生的運費。由于派車成本固定，載重行程和空載行程相互聯(lián)系，故獨立的變量為出車次數(shù)和載重行程。以最小化運費為目標(biāo)函數(shù)，以第j輛車第k次出車到i公司運載A材料的數(shù)量為決策變量，以各公司的材料需求、大小材料的卸貨順序、車輛使用時間等為約束條件，建立線性規(guī)劃模型。為方便計算，建立運輸車與各公司之間的關(guān)系矩陣(PN)，行對應(yīng)公司編號，列分別表示A、B、C各公司對相應(yīng)各種材料的需求量，港口到各公司順時針行駛路程數(shù)，港口到各公司逆時針行駛路程數(shù)。采用枚舉法求解，求得共出車28次，總運費為5264.8元。對于問題二，在問題一的基礎(chǔ)上考慮每輛車在運輸途中可隨時掉頭的情況，修改空載行程變量和車輛使用時間變量，。問題三中增加了運輸車的種類，并區(qū)分了運輸車空載時的運費，由于運輸車裝載材料的方式有很多種，在上面分析的基礎(chǔ)上，增加約束條件，得出一種新的線性規(guī)劃模型，通過Lingo7.0解得三種車型的調(diào)配數(shù)量，以及將材料運到每個公司所需的車次安排范圍，最后再根據(jù)每輛車的工作時間的約束條件，利用窮舉法，從安排車次數(shù)量最小的情況開始窮舉，逐漸找到了滿足約束條件，且所需安排的車次數(shù)最優(yōu)的情況，即得到了問題三的最優(yōu)結(jié)果。最后對模型進(jìn)行了評價和推廣，本文對建立的線性規(guī)劃模型采用枚舉算法進(jìn)行求解，沒有進(jìn)行編程求解，在一定程度上具有誤差。可通過放松約束條件，編寫程序進(jìn)行求解，逐步加緊約束，進(jìn)行優(yōu)化，逐步接近實際情況。關(guān)鍵詞：線性規(guī)劃貨運公司枚舉法

一、問題的重述與分析1、問題的重述某地區(qū)有8個公司（如圖一編號①至⑧），某天某貨運公司要派車將各公司所需的三種原材料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噸，原材料不能拆分，為了安全，大小件同車時必須小件在上，大件在下。卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當(dāng)天的需求量（見表1）。2、待解決的問題問題一：貨運公司派出運輸車6輛，每輛車從港口出發(fā)（不定方向）后運輸途中不允許掉頭，應(yīng)如何調(diào)度（每輛車的運載方案，運輸成本）使得運費最小。問題二：每輛車在運輸途中可隨時掉頭，若要使得成本最小，貨運公司怎么安排車輛數(shù)？應(yīng)如何調(diào)度？問題三：如果有載重量為4噸、6噸、8噸三種運輸車，載重運費都是1.8元/噸公里，空載費用分別為0.2，0.4，0.7元/公里，其他費用一樣，又如何安排車輛數(shù)和調(diào)度方案？3、問題分析問題一中的運費來自兩方面的費用：派車與出車的固定成本、載重運費與空載運費。派車數(shù)由是確定的，由公司派出6輛進(jìn)行運輸；減少出車次數(shù)能減少運費。運輸途中不能掉頭，每輛車每次必須行車60公里，由載重運費與空載運費知減少載重行車距離能有效減少運費。所以最小化運費可從三個方面進(jìn)行：減少出車次數(shù)，減少載重行車距離，增加空載距離。其中獨立變量為出車次數(shù)和載重行車距離。以最小化運費為目標(biāo)函數(shù)，以第j輛車第k次出車到i公司運載A材料的數(shù)量為決策變量，以各公司的材料需求、大小材料的卸貨順序、車輛使用時間等為約束條件，建立線性規(guī)劃模型?？紤]數(shù)據(jù)簡單，計算過程簡單，而材料配載過程復(fù)雜，故采用枚舉法。問題二中在問題一的基礎(chǔ)上增加了運輸途中可以掉頭的條件。仍采用枚舉的方法對問題進(jìn)行解答。問題三中在問題一、二的基礎(chǔ)上增加了運輸車種類：載重量分別為4噸、6噸、8噸；載重運費都是1.8元/噸公里，空載費用分別為0.2，0.4，0.7元/公里，其他費用一樣。根據(jù)問題一、二的解答方式，以盡可能裝滿車，每輛車盡可能一次性卸載完為原則，對4，6，8噸三種車型的數(shù)量和調(diào)配方式進(jìn)行安排，并以派出車輛的次數(shù)最少為最優(yōu)目標(biāo)解，列出目標(biāo)函數(shù)和約束函數(shù)。

表1各個公司對每種材料的需求量（單位/天）公司編號各種材料的需求量（單位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧531圖1運輸路線圖和里程數(shù)

二、基本假設(shè)1、各個公司對在材料的需求量在一天中均衡，即材料只要能在當(dāng)天運到即可；2、假設(shè)貨運公司都是先考慮節(jié)省人力和出車次數(shù)最少的情況下再考慮如何安排運輸方式以減少經(jīng)費支出；3、假設(shè)運輸車行駛過程中不考慮塞車等現(xiàn)象，以保證每輛車每天可以達(dá)到最大的作業(yè)時間。4、材料的運輸途中不會損壞；5、每日的工作時間只包括裝卸時和在公路行走時間；6、港口的材料能保證充足，并裝材料及時。三、符號說明符號含義總路程第j輛車第k次出車到i公司運載A材料的數(shù)量出車的方向，0表示順時針，1表示逆時針為0，到達(dá)i公司的距離；為0，到達(dá)i公司的距離；,,,,材料的重量，，i公司對,,材料的需求量；第j輛車在第k次是否出車，=1表示出車，=0表示不出車；第j輛車在第k次出車途中卸材料的次數(shù)第j輛車在第k次出車卸完材料的公司編號其他符號在文中均有說明。四、問題一模型的建立與求解4.1模型分析貨運公司運費來自兩方面的費用：派車與出車的固定成本、載重與空載行程產(chǎn)生的運費。由于派車成本固定，載重行程和空載行程相互聯(lián)系，故獨立的變量為出車次數(shù)和載重行程。以最小化運費為目標(biāo)函數(shù)，以第j輛車第k次出車到i公司運載A材料的數(shù)量為決策變量，以各公司的材料需求、大小材料的卸貨順序、車輛使用時間等為約束條件，建立線性規(guī)劃模型。4.2模型的建立首先由于從港口出發(fā)有兩個不同的方向，所以我們要考慮每車次出發(fā)的方向。另外，每天的運輸方案必須滿足一定的約束條件。根據(jù)這些我們建立一般的規(guī)劃模型：目標(biāo)函數(shù)：約束條件：（1）保證各個公司每天所需的每種材料得到滿足，即所有運到該公司的材料在當(dāng)天運抵；，，；（2）每輛車每天的工作時間不超過8小時；；（3）保證每次大小件同車時小件在上，大件在下，卸貨時先卸小件再卸大件。當(dāng)=0，時，，，時，，當(dāng)，時，，，時，，。4.3模型的求解由于每輛最大的載重為6噸，運輸時A材料只能和C材料進(jìn)行組合。我們首先安排A材料的運輸，并盡量和C材料。同時某個公司如果需要的B材料數(shù)量為偶數(shù)，也優(yōu)先安排，剩下的材料在進(jìn)行優(yōu)化。這樣可以大大地減少工作量。由于經(jīng)過以下處理以后所剩情況不多，我們采用枚舉的方法求解即可。4.3.1附加符號說明構(gòu)造一個8行5列的矩陣如圖2。其中行號對應(yīng)公司編號；列號用A、B、C、D、E表示，其中A、B、C表示各公司對相應(yīng)各種材料的需求量；D表示從港口到各公司順時針行駛相應(yīng)的路程數(shù)；E表示從港口到各公司逆時針行駛相應(yīng)的路程數(shù)。矩陣左側(cè)的數(shù)字表示出車次數(shù)，“順”“逆”表示相應(yīng)的出車方向。4.3.2求解方法由于A、B、C三種材料毛重和運輸車載重噸位的特殊性，因而材料的搭配種類是可以枚舉的，其中A與B材料明顯不能同時裝車，而C可以任意搭配，比較靈活。故A、B材料的多少是決定出車次數(shù)的關(guān)鍵，而C可以不予考慮。而要求費用最少，則盡量使每次出車時運輸車都滿載，此種情況優(yōu)先考慮，滿載搭配方案只有A+C+C、B+C+C+C、B+B三種，在上面的矩陣中優(yōu)先對這三種滿載情況進(jìn)行相應(yīng)的變換，然后在根據(jù)所得矩陣再進(jìn)行相應(yīng)的靈活調(diào)度。由上述各圖統(tǒng)計可得相應(yīng)的總出車次數(shù)為28，由于途中的卸貨次數(shù)最多為4次。當(dāng)運輸途中一次卸貨時，若出車時間相同，則各運輸車幾乎同時抵達(dá)港口，因而6輛運輸車同時出車，則每輛車最多出車5車次。圖3至圖9為運輸車運載方式和各公司所需材料數(shù)量變化圖。圖2圖3圖4圖5圖6圖7圖8圖9具體的車輛調(diào)度，時間安排，運輸費用見表2。表2運輸車調(diào)度信息運輸方式卸貨順序載重距離（km）空載距離（km）所用時間（min）費用（元）1A+C+C(順)185285107.22A+C+C(順)185285107.23A+C+C(順)21545851804A+C+C(順)3243685273.65A+C+C(順)3243685273.66A+C+C(順)4293185325.67A+C+C(逆)5233785263.28A+C+C(逆)7114985138.49A+C+C(逆)7114985138.410B+C+C+C（逆）615458518011B+B（順）215458518012B+B（順）215458518013B+B（逆）5233785263.214B+B（逆）615458518015B+B（逆）7114985138.416B+B（逆）8555857617B+C+C+C（順）1à5à64515105396.618A+C+C(逆)8à7à43127105263.619B+B（順）1à2154595142.220B+B（逆）8à431299520621A（順）3243685187.222A（順）3243685187.223A（順）3243685187.224A（逆）8555855825A（逆）8555855826A（逆）8555855827A（逆）8555855828A（逆）85558558總計24404864.8注：表中費用不包括派車固定成本和出車固定成本。總運輸費用為派車費用、出車費用、載重費用、空載費用總和，求得計算得運輸總費用為元。五、問題二模型的建立與求解5.1模型的分析在問題一的基礎(chǔ)上增加了運輸途中可掉頭的條件，故問題一建立的模型不再適用，需要進(jìn)行改進(jìn)。在運輸途中可掉頭，對問題一建立的目標(biāo)函數(shù)和約束條件的影響為空載行程變量和車輛使用時間變量。對這兩個變量進(jìn)行修改即可適用于問題二。5.2模型的建立當(dāng)矩陣中D列數(shù)值大于E列數(shù)值時，=0，=1；反之，=1，=0。目標(biāo)函數(shù)：約束條件（2）：5.3模型的求解5.3.1符號說明建立問題二中運輸車與各公司之間的關(guān)系矩陣。符號新增“”“”標(biāo)記?！啊北硎驹撥囆敦浐蟮纛^回跑；“”表示該車卸貨后不調(diào)頭，繼續(xù)直走。圖10圖11圖12圖13圖14圖15圖16圖17由于A、B、C三種材料毛重和運輸車載重噸位的特殊性，因而材料的搭配種類是可以枚舉的，其中A與B材料明顯不能同時裝車，而C可以任意搭配，比較靈活。故A、B材料的多少是決定出車次數(shù)的關(guān)鍵，而C可以不予考慮。而要求費用最少，則盡量使每次出車時運輸車都滿載，此種情況優(yōu)先考慮，滿載搭配方案只有A+C+C、B+C+C+C、B+B三種（不考慮C單獨滿載的情況），在上面的矩陣中我們優(yōu)先對這三種滿載情況進(jìn)行相應(yīng)的變換，在同意公司卸貨時不需要考慮大小件的卸貨順序；不同公司搭配送貨時在圖中卸貨順序用箭頭標(biāo)記。然后在根據(jù)所得矩陣再進(jìn)行相應(yīng)的靈活調(diào)度。運輸車順時針還是逆時針運行由相應(yīng)公司的D、E的大小決定。由上述各圖統(tǒng)計可得相應(yīng)的總出車次數(shù)為28，由于途中的卸貨次數(shù)最多為4次，當(dāng)開始出車時間相同時，我們可認(rèn)為各運輸車幾乎同時抵達(dá)港口，因而6輛運輸車同時出車，則每輛車最多出車5車次。具體的車輛調(diào)度，時間安排，運輸費用見表3。表3運輸車調(diào)度信息運輸方式卸貨順序載重距離（km）空載距離（km）所用時間（min）車次費用（元）1A+C+C(順)188411（1）89.62A+C+C(順)188412（1）89.63A+C+C(順)21515553（1）1684A+C+C(順)32424734（1）268.85A+C+C(順)32424735（1）268.86A+C+C(順)42929836（1）324.87A+C+C(逆)52323711（2）257.68A+C+C(逆)71111472（2）123.29A+C+C(逆)71111473（2）123.210B+C+C+C（逆）61515554（2）168.11B+B（順）21515555（2）168.12B+B（順）21515556（2）16813B+B（逆）52323711（3）257.214B+B（逆）61515552（3）168.15B+B（逆）71111473（3）123.216B+B（逆）855354（3）56.17B+C+C+C（順3）396.618A+C+C(逆)878115676（3）153.219B+B（順）121515652（4）130.220B+B（逆）843129953（4）206.21A（順）32424734（4）139.222A（順）32424731（4）139.223A（順）32424736（4）139.224A（逆）855355（4）29.25A（逆）855352（5）2926A（逆）855354（5）29.27A（逆）855353（5）29.28A（逆）855351（5）2945141316304270.6注：表中費用不包括派車固定成本和出車固定成本。計算總費用：元。六、問題三模型的建立與求解3.1模型分析在問題一、二的基礎(chǔ)上增加了運輸車種類：載重量分別為4噸、6噸、8噸；載重運費都是1.8元/噸公里，空載費用分別為0.2，0.4，0.7元/公里，其他費用一樣。根據(jù)問題一、二的解答方式，以盡可能裝滿車，每輛車盡可能一次性卸載完為原則，對4，6，8噸三種車型的數(shù)量和調(diào)配方式進(jìn)行安排，并以派出車輛的次數(shù)最少為最優(yōu)目標(biāo)解，列出目標(biāo)函數(shù)和約束函數(shù)。3.2模型的建立三種運輸車的所有裝載方式如下表所示：表4三種運輸車的裝載方式載重4噸載重6噸載重8噸根據(jù)對于每個公司的需求我們都是考慮盡可能用上面給出的不同的裝載方式來滿足，可建立模型如下：S.T.是正整數(shù)其中表示第n個公司分別對A，B，C產(chǎn)品的需求量。代入用LinGo7.0求解可以得出下表：表5問題三運輸車調(diào)度信息表公司編號各種材料的需求量（單位/天）所需車次所需車型ABC①4158噸②1526噸、8噸③2046噸④3124噸、6噸、8噸⑤1246噸、8噸⑥0436噸⑦2256噸、8噸⑧5318噸現(xiàn)對上表分析，考慮到增加車輛有20元的增加費用，車輛越少越好。但必須在規(guī)定時間內(nèi)（8小時），完成一定車次的任務(wù)。所需的車輛數(shù)至少為：4噸、6噸、8噸各一輛。每輛車的工作時間的約束條件為：接下來采用窮舉法，根據(jù)上表所得情況，以盡可能保留6噸車型，優(yōu)先加開8噸車型為原則，以下表所列的情況按順序依次進(jìn)行計算：表6三種運輸車窮舉順序窮舉順序載重4噸載重6噸載重8噸①1輛1輛1輛②1輛2輛1輛③1輛2輛2輛④1輛3輛2輛⑤1輛3輛3輛⑥1輛4輛3輛⑦1輛4輛4輛依次窮舉后，得到第三種情況，即所需車數(shù)為：1+2+2=5（輛）的情況是最優(yōu)的。按運費計算公式，求出完成一天任務(wù)的總運費為：4588.7元?？紤]到，4噸車只用了一次，可加開一次6噸車代替，以減少費用。事實證明6噸車加開一次時間是完全允許的，可節(jié)約費用：那么車輛數(shù)變?yōu)椋?輛；費用：4573.5元。七、模型的評價與改進(jìn)本文對建立的線性規(guī)劃模型采用枚舉算法進(jìn)行求解，簡化了計算過程，但沒有進(jìn)行編程求解，在一定程度上具有誤差?？赏ㄟ^放松約束條件，編寫程序進(jìn)行求解，逐步加緊約束，進(jìn)行優(yōu)化，逐步接近實際情況。八、模型的推廣可把問題抽象為網(wǎng)絡(luò)圖，利用圖論理論這一數(shù)學(xué)工具把實際問題抽象為網(wǎng)絡(luò)圖問題，進(jìn)而建立數(shù)學(xué)模型。再用圖論的相關(guān)算法求解?！緟⒖嘉墨I(xiàn)】陳東彥，李冬梅，王樹忠．?dāng)?shù)學(xué)建模．北京．科學(xué)出版社，2007附錄：LINGO代碼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-x