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

答卷編號(hào)（競(jìng)賽組委會(huì)填寫(xiě)）：答卷編號(hào)（競(jìng)賽組委會(huì)填寫(xiě)）：論文題目：貨運(yùn)公司的運(yùn)輸問(wèn)題參賽隊(duì)員：1.郭海良電話(huà)：2.林歡電話(huà)：3.黎小龍電話(huà)卷編號(hào)（參賽報(bào)名號(hào)）：答卷編號(hào)（競(jìng)賽組委會(huì)填寫(xiě)）：評(píng)閱情況（評(píng)閱專(zhuān)家填寫(xiě)）：評(píng)閱1.評(píng)閱2.評(píng)閱3.貨運(yùn)公司的運(yùn)輸問(wèn)題摘要本文對(duì)有序卸貨的運(yùn)輸問(wèn)題，由于線(xiàn)路唯一，所以將費(fèi)用最小轉(zhuǎn)化為求車(chē)次最少為目標(biāo)，建立了線(xiàn)性規(guī)劃，再運(yùn)用其他算法匹配出具體的車(chē)輛調(diào)運(yùn)方案。對(duì)于問(wèn)題一，模型一：首先以各公司總體的需求為約束，以總車(chē)次最小為目標(biāo)的線(xiàn)性規(guī)劃，再以此為基礎(chǔ)，分別同過(guò)各公司的單獨(dú)需求為約束，所需車(chē)次為目標(biāo)的線(xiàn)性規(guī)劃，運(yùn)用LINGO,最后利用啟發(fā)式算法對(duì)每車(chē)次具體載重以及路線(xiàn)作具體調(diào)整得出車(chē)次的具體調(diào)度，得出總車(chē)次為27次，6輛車(chē)車(chē)工作時(shí)間分別為7.083小時(shí)、7.083小時(shí)、7.083小時(shí)、6小時(shí)、6小時(shí)、6小時(shí)，總費(fèi)用為5187.6元。模型二：通過(guò)建立線(xiàn)性規(guī)劃模型、0—1規(guī)劃模型得出的結(jié)果為：總車(chē)次27次，總費(fèi)5617.2元。對(duì)比可得模型一比模型二更優(yōu)對(duì)于問(wèn)題二，首先通過(guò)遍歷算法和目標(biāo)規(guī)劃模型確定了卸貨次數(shù)最少（即車(chē)次最少）的方案，再通過(guò)貪婪算法匹配出最小車(chē)次的調(diào)度方案，得出需要4輛車(chē)，工作時(shí)間分別為7.967小時(shí)、7.883小時(shí)、7.483小時(shí)、6.233小時(shí)。這里為了簡(jiǎn)化問(wèn)題求解，先考慮在每個(gè)公司卡車(chē)卸貨的次數(shù)和方案，再考慮路徑等問(wèn)題。對(duì)于路徑的選擇，首先考慮可一次性卸貨的車(chē)次路徑方案，再考慮公司間貨物匹配的車(chē)次路線(xiàn)方案，最后用貪婪算法得出具體調(diào)度方案見(jiàn)表5.2.4。對(duì)于公司間匹配運(yùn)貨得出如下：各種卸貨方案只有的方案可以匹配，而且匹配只會(huì)發(fā)生在不同公司之間。對(duì)于無(wú)法匹配的卸貨方案就只能耗費(fèi)一車(chē)次來(lái)單獨(dú)完成。對(duì)于問(wèn)題三，（第一問(wèn)）分了4，6，8噸載重的三種車(chē)，為了卸貨效率較高，要求每種車(chē)卸貨的重量為本車(chē)最大載重的一半以上，如問(wèn)題二中一樣通過(guò)遍歷算法和目標(biāo)規(guī)劃模型確定了卸貨次數(shù)最少（即車(chē)次最少）的方案，再通過(guò)貪婪算法匹配出最小車(chē)次的調(diào)度方案，得出需要：4噸位車(chē)1輛，2次；6噸位1輛，2次，8噸位2輛，18次，即共用4輛車(chē)，出車(chē)22次，詳細(xì)調(diào)用如表5.3.1。這里由于所有載重車(chē)輛的載重噸位都在最大載重量的一半以上，所有不存在需要匹配的卸貨方案。因此每次卸貨都要耗費(fèi)單獨(dú)一個(gè)車(chē)次來(lái)完成對(duì)于第二問(wèn)我們作為擴(kuò)展稍微做了探索，由于部分公司間有路相通，因此不但要考慮車(chē)次的問(wèn)題，還要考慮路徑問(wèn)題，即最短路問(wèn)題，而最短路問(wèn)題又是圖論里一個(gè)典型的問(wèn)題，可以采用迪克斯特拉（Dijkstra）算法來(lái)解決，另一個(gè)方法就是運(yùn)用遺傳算法。關(guān)鍵字：線(xiàn)性規(guī)劃，遍歷算法，貪婪算法一、問(wèn)題重述某地區(qū)有8個(gè)公司（如圖一編號(hào)①至⑧），某天某貨運(yùn)公司要派車(chē)將各公司所需的三種原材料A,B,C從某港口（編號(hào)⑨）分別運(yùn)往各個(gè)公司。路線(xiàn)是唯一的雙向道路（如圖一）。貨運(yùn)公司現(xiàn)有一種載重6噸的運(yùn)輸車(chē)，派車(chē)有固定成本20元/輛，從港口出車(chē)有固定成本為10元/車(chē)次（車(chē)輛每出動(dòng)一次為一車(chē)次）。每輛車(chē)平均需要用15分鐘的時(shí)間裝車(chē)，到每個(gè)公司卸車(chē)時(shí)間平均為10分鐘，運(yùn)輸車(chē)平均速度為60公里／小時(shí)（不考慮塞車(chē)現(xiàn)象），每日工作不超過(guò)8小時(shí)。運(yùn)輸車(chē)載重運(yùn)費(fèi)1.8元/噸公里，運(yùn)輸車(chē)空載費(fèi)用0.4元/公里。問(wèn)題：1.貨運(yùn)公司派出運(yùn)輸車(chē)6輛，每輛車(chē)從港口出發(fā)（不定方向）后運(yùn)輸途中不允許掉頭，應(yīng)如何調(diào)度（每輛車(chē)的運(yùn)載方案，運(yùn)輸成本）使得運(yùn)費(fèi)最小。2.每輛車(chē)在運(yùn)輸途中可隨時(shí)掉頭，若要使得成本最小，貨運(yùn)公司怎么安排車(chē)輛數(shù)？應(yīng)如何調(diào)度？3.選做（任選一問(wèn)）：（1）如果有載重量為4噸、6噸、8噸三種運(yùn)輸車(chē)，載重運(yùn)費(fèi)都是1.8元/噸公里，空載費(fèi)用分別為0.2，0.4，0.7元/公里，其他費(fèi)用一樣，又如何安排車(chē)輛數(shù)和調(diào)度方案？（2）當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，分析運(yùn)輸調(diào)度的難度所在，給出你的解決問(wèn)題的想法（可結(jié)合實(shí)際情況深入分析）。圖一圖二公司編號(hào)各種材料的需求量（單位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧531二、問(wèn)題的分析對(duì)于問(wèn)題一，因?yàn)檫\(yùn)輸?shù)木€(xiàn)路唯一，且中途不可調(diào)頭，相當(dāng)于圍繞線(xiàn)路開(kāi)一個(gè)圈再回到港口。所以為了減少費(fèi)用，應(yīng)盡可能的減少出車(chē)的車(chē)次，為此每一車(chē)次盡量實(shí)現(xiàn)滿(mǎn)載，而滿(mǎn)載的組合有1A+2C、2B、B+3C、6C四種情況，在滿(mǎn)足各各公司的每日需求的額條件下，建立線(xiàn)性規(guī)劃模型求出符合要求的最小車(chē)次。在此前基礎(chǔ)上再以各公司的需求為約束，分別用線(xiàn)性規(guī)劃求的所需車(chē)次，從而得到整體的最優(yōu)解。對(duì)于問(wèn)題二，因?yàn)檐?chē)輛中間可以調(diào)頭，在載重路線(xiàn)最短的情況下，載重線(xiàn)路也就是返程線(xiàn)路。為了簡(jiǎn)化問(wèn)題求解，先考慮在每個(gè)公司卡車(chē)卸貨的次數(shù)和方案。首先，假定所有的卡車(chē)只卸貨一次，卸完貨后立即返程。為了使運(yùn)送的路程、運(yùn)費(fèi)，車(chē)次盡可能少，因此，這是一個(gè)優(yōu)化問(wèn)題，目標(biāo)函數(shù)是卸貨總次數(shù)最少，而為了保證每次卸貨的效率，假設(shè)在每個(gè)站點(diǎn)卸貨的重量必須在其最大載重量的一半以上。由于可返回，這里把6噸車(chē)裝載的可能性都考慮進(jìn)去共12種，目標(biāo)就在這12種搭配中選擇對(duì)于問(wèn)題三，問(wèn)題3的建模思路和問(wèn)題2基本一致，遵循如下步驟：尋求最優(yōu)卸貨方案尋找最優(yōu)（成本最低，時(shí)間最省）運(yùn)送路線(xiàn)；尋求最優(yōu)車(chē)輛調(diào)度方案（出車(chē)最少，同時(shí)保證不超時(shí)）問(wèn)題3分了4，6，8噸載重的三種車(chē)，為了卸貨效率較高，要求每種車(chē)卸貨的重量為本車(chē)最大載重的一半以上；同時(shí)注意到，對(duì)于低于6噸的貨物，可以由6噸載重的卡車(chē)運(yùn)，沒(méi)有必要用8噸的（空載車(chē)費(fèi)隨最大載重量增加而變貴），而4噸以下的就沒(méi)必要用6噸的車(chē)來(lái)卸貨，這樣只會(huì)增加卸貨的次數(shù)，因此只考慮3，4，5，6，7，8噸卸貨的方案。三、模型假設(shè)1：每趟車(chē)運(yùn)完最后一次原料時(shí)，都按時(shí)返回港口；2:假設(shè)貨運(yùn)公司安排車(chē)輛時(shí)，盡力使每輛車(chē)都在工作，而不是優(yōu)先讓某一輛車(chē)工作四、符號(hào)說(shuō)明在J公司卸A種貨物的重量；在J公司卸B種貨物的重量；在J公司卸C種貨物的重量；i方案下卸載a貨物的單位數(shù)；i方案下卸載b貨物的單位數(shù)；i方案下卸載c貨物的單位數(shù)；貨車(chē)最大載重量五、模型的建立與求解5.1問(wèn)題一模型的建立與求解模型一：在問(wèn)題一的假設(shè)下，可知每次出車(chē)的行程都相同，所以存在貪婪因子，在卸貨約束和滿(mǎn)載的條件下，即可用貪婪算法求的局部每次出車(chē)的最小費(fèi)用，再得到全局最優(yōu)解。對(duì)于在路程相同的情況下使總費(fèi)用最小，則出車(chē)次數(shù)需最小，這里以各公司所需原材料為約束條件，以每種滿(mǎn)載組合的車(chē)次為決策變量，總車(chē)次最小為目標(biāo)函數(shù)，建立線(xiàn)性規(guī)劃模型。其中滿(mǎn)載組合有M1次:1A+2C、M2次:2B、M3次:1B+3C、M4次:6CM1、M2、M3、M4為整數(shù)用LINGO求的總車(chē)次為27，其中M1=18,M2=9,M3=0,M4=0。在總車(chē)次確定的情況下，依次為基礎(chǔ)，再對(duì)以每一個(gè)公司的需求為約束分別建立線(xiàn)性規(guī)劃模型，確定滿(mǎn)足各個(gè)公司需求的最小車(chē)次與運(yùn)載組合（這樣的好處是既可以確定各個(gè)車(chē)次也能結(jié)合總車(chē)次與載重對(duì)整體進(jìn)行調(diào)整）其中Ai、Bi、Ci分別為各公司對(duì)原料A、B、C的需求量，利用啟發(fā)式算法對(duì)每車(chē)次具體載重以及路線(xiàn)作具體調(diào)整得出車(chē)次具體調(diào)度為：一次性卸載有22次公司車(chē)次載重123456782*(A+2C）A+2C2*(A+2C)A+2CA+2C2*2B2*(A+2C)A+CA+C2*2B2B2B4*A2B其中多于一次卸載的有5次載重一個(gè)（A+2C）原料由港口經(jīng)7公司卸載一單位C，再經(jīng)6公司卸載一單位C,最后在4公司卸載A;載重一個(gè)(A+2C)經(jīng)6公司卸載2單位C,再經(jīng)1公司卸載一單位A；載重一個(gè)(A+2C)經(jīng)5公司卸載2C,再經(jīng)4公司卸載一單位A;載重2B經(jīng)1卸載1個(gè)單位B,再經(jīng)2公司卸載1單位B;載重2B經(jīng)公司8卸載1B,再經(jīng)4卸載1B.由上可得：公司1運(yùn)(A+2C)2次，(A+C)的1次，再由2個(gè)其他車(chē)次分別運(yùn)載1單位B和1單位A;公司2運(yùn)2單位B原料2次，（A+2C）1次，再分別由其他1車(chē)次提供1單位B；公司3運(yùn)（A+2C）2次；公司4運(yùn)(A+2C)1次，再分別由其他3車(chē)次各提供2單位A,1單位B；公司5運(yùn)(A+2C)1次，2B運(yùn)1次，再由其他車(chē)次提供2C;公司6運(yùn)2B原料2次，再由其他2車(chē)次各提供1單位C和2單位C;公司7運(yùn)(A+2C)2次，2B原料1次，再由其他車(chē)次提供1單位C；公司8運(yùn)(A+C)11次，A原料4次，2B料1次，再由其他車(chē)次提供1單位B?？傎M(fèi)用=其中m為每車(chē)次貨物重量，Si為載重所走的路程，（60-Si）為空載的路程。各車(chē)次所用具體費(fèi)用看附錄表5.1時(shí)間其中Ti1表示第i車(chē)次載重所用時(shí)間，Ti2表示第i車(chē)次空載所用時(shí)間，由于這里路程相同，車(chē)速相同，所以各車(chē)次運(yùn)載一次所用時(shí)間相同，不同的是卸貨次數(shù)的不同而增加的卸貨時(shí)間。一共是27車(chē)次，即27圈，60公里/圈，所用27小時(shí)，加上一次性卸貨的有22次，用去220分鐘，需兩次卸貨的4次，為80分鐘，3次卸貨的1次為30分鐘，裝載時(shí)間為405鐘，結(jié)論：通過(guò)線(xiàn)性規(guī)劃模型得出總車(chē)次為27次，用啟發(fā)式算法配車(chē)6兩車(chē)分別工作時(shí)間為7.083小時(shí)、7.083小時(shí)、7.083小時(shí)、6小時(shí)、6小時(shí)、6小時(shí)，總費(fèi)用為5187.6元模型二：如模型一一樣先用線(xiàn)性規(guī)劃M(mǎn)1次:1A+2C、M2次:2B、M3次:1B+3C、M4次:6CM1、M2、M3、M4為整數(shù)求的整體最少車(chē)次為27次。下面用0-1規(guī)劃模型求解最優(yōu)的調(diào)度方式。對(duì)這些運(yùn)輸方式，分別記順時(shí)針的調(diào)用車(chē)次序?yàn)閕0（i0=1~27），其中i=1~12為調(diào)用方式（A+2C），i=13~14為調(diào)用方式A+C，i=15~18為調(diào)用方式A，i=19~17為調(diào)用方式（2B）；逆時(shí)針的調(diào)用車(chē)次序?yàn)閕1（i1=1~27），其中i=1~4為調(diào)用方式A，i=5~6為調(diào)用方式A+C，i=7~18為調(diào)用方式（A+2C），i=19~27為調(diào)用方式（2B）。對(duì)于每個(gè)被調(diào)用以滿(mǎn)足不用公司要求的車(chē)次，由于不考慮掉頭，故可以得到其運(yùn)輸所需要的經(jīng)費(fèi)為Pij=∑（1.8w*Sij+0.4*sj0）（i=1~27，j=0或1），其中w為運(yùn)輸車(chē)的載重，Sij為所運(yùn)載的區(qū)間的路程，Sj0則表示空車(chē)回到港口的距離，總費(fèi)用為：P=∑Pij+S*10+20*K，其中K為所調(diào)用的車(chē)輛的個(gè)數(shù)；其中Pij的計(jì)算所得的結(jié)果參看表（1），表（2）中列出各個(gè)公司所需的材料是由哪些車(chē)次所負(fù)責(zé)運(yùn)輸?shù)?。根?jù)這兩個(gè)表中的數(shù)據(jù)設(shè)Xij（其中i=1~27，j=0或1）為第i輛列車(chē)的調(diào)度情況：其中Xi0=1表示第i輛車(chē)次采用順時(shí)針運(yùn)行，Xi0=0則表示不采用第i輛車(chē)次順時(shí)針運(yùn)輸，Xi1=1則表示第i輛車(chē)采用逆時(shí)針運(yùn)輸，Xi1=0表示第i輛車(chē)不采用順時(shí)針運(yùn)輸。由上可以對(duì)這個(gè)問(wèn)題建立一個(gè)0-1規(guī)劃模型：Min∑Pij*XijS.T∑Xij〉=27x10+x181=1;x20+x171=1;x130+x61=1;x150+x151=1;（對(duì)于公司（1）兩種不同運(yùn)輸方式中只能選擇一種）……….（其他公司的處理方法一樣，其中如：x141-x151=0，這是說(shuō)明如過(guò)采用141，則也采用151的車(chē)次，其他各處同理）Xij=0或1結(jié)論：對(duì)上0-1模型，代入數(shù)據(jù)，用Lingo求解可得∑Pij=5227.2，又由于S=27，K=6，所以總費(fèi)用為P=5617.2（元）[5]5.2問(wèn)題二模型的建立與求解為了簡(jiǎn)化問(wèn)題求解，先考慮在每個(gè)公司卡車(chē)卸貨的次數(shù)和方案。首先，假定所有的卡車(chē)只卸貨一次，卸完貨后立即返程。其余假設(shè)與最初假設(shè)一致。為了使運(yùn)送的路程，運(yùn)費(fèi)，車(chē)次盡可能少，因此，這是一個(gè)優(yōu)化問(wèn)題，目標(biāo)函數(shù)是卸貨總次數(shù)最少，而為了保證每次卸貨的效率，假設(shè)在每個(gè)站點(diǎn)卸貨的重量必須在其最大載重量的一半以上。則卸貨的方案滿(mǎn)足以下條件：利用遍歷算法可以很快確定各種貨物的卸載方案如下表：（表5.2.1）方案號(hào)abc組合C1102A+2CC20202BC30066CC4013B+3CC5101A+CC6100AC7010BC8011B+CC9012B+2CC100033CC110044CC120055C那么對(duì)于一個(gè)載重6噸的貨車(chē)總共有12種載重方案，使得其載重量在3---6噸之間。設(shè)Ci為公司第i種卸貨方案的使用次數(shù)；那么使用這些方案，要在j公司卸貨，使得卸貨總次數(shù)最小，相當(dāng)于下面這個(gè)規(guī)劃問(wèn)題：利用LINGO可以變成求出各個(gè)公司對(duì)應(yīng)各種方案的最小次數(shù)如下表：（表5.2.2）方案工廠(chǎng)1工廠(chǎng)2工廠(chǎng)3工廠(chǎng)4工廠(chǎng)5工廠(chǎng)6工廠(chǎng)7工廠(chǎng)8C1A+2C20201000C22B02000201C36C00000000C4B+3C00000010C5A+C01020010C6A20010015C7B00010000C8B+C11002011C9B+2C00000000C103C00000100C114C00000000C125C00000000由上表可得各公司最少卸貨方案為1公司：2C1+2C6+C8、2公司：2C1+2C6+C8、3公司：2C1、4公司：2C5+C6+C7、5公司:C1+2C8、6公司：2C2+C107公司：C4+C5+C6+C8、8公司：C2+5C6+C8現(xiàn)在每個(gè)公司的最少卸貨方案已定，在這個(gè)優(yōu)化的基礎(chǔ)上，我們考慮盡可能的降低成本，車(chē)次，和時(shí)間的問(wèn)題。盡管每個(gè)公司的卸貨方案已定，但是出動(dòng)多少車(chē)次的車(chē)，以及如何安排車(chē)上貨物，車(chē)子的運(yùn)行路線(xiàn)未定。這里首先考慮減少車(chē)次。例如：兩個(gè)不同公司，如果同時(shí)有兩個(gè)方案x,y它們的卸貨重量均為3噸，那么這兩個(gè)方案完全可以由一部車(chē)子一次來(lái)完成。那么在不同工廠(chǎng)之間就存在可以“匹配”的方案。根據(jù)我們之前的假設(shè)，為了提高卸貨運(yùn)輸效率，每種卸貨方案卸載重量最少，如果要匹配的方案，最少要在兩個(gè)公司之間匹配，匹配方案的載重；顯然，這樣一來(lái)，可以匹配的方案必然是3噸卸貨方案和3噸的卸貨方案匹配了。那么一個(gè)公司最多有幾個(gè)3噸的卸貨方案呢？答案是最多一個(gè)，如果存在2個(gè)以上，那么兩個(gè)3噸的貨物完全可以由一個(gè)6噸滿(mǎn)載卡車(chē)一次卸完，這顯然不是最優(yōu)方案，上面我們得出的正是最優(yōu)卸貨方案，所以沒(méi)有必要再考慮一個(gè)公司是否有多個(gè)3噸的卸貨方案了。綜上所述，各種卸貨方案只有的方案可以匹配，而且匹配只會(huì)發(fā)生在不同公司之間。對(duì)于無(wú)法匹配的卸貨方案就只能耗費(fèi)一車(chē)次來(lái)單獨(dú)完成了。路線(xiàn)選擇：（1）單車(chē)次卸貨方案的路線(xiàn)選擇本問(wèn)題中的車(chē)子可以倒車(chē)返程。由碼頭到某公司可以順時(shí)針走，也可以逆時(shí)針，如果某車(chē)次的車(chē)去j公司卸貨，卸貨完成后返程，那么可能的路程就是2L1,2L2。為節(jié)省路費(fèi)和時(shí)間，我們對(duì)每個(gè)車(chē)次卸貨方案選擇最短路線(xiàn)。即路程為。選擇路線(xiàn)為L(zhǎng)1,L2中最短的一條走。（2）可匹配方案車(chē)次的路線(xiàn)選擇如有兩個(gè)公司，它們之間可以匹配貨物，根據(jù)之前的推斷，在公司I,j都存在卸貨重量為，它們之間的距離為，到港口間的直接距離為。如何選擇路線(xiàn)才是最好呢？我們以成本為最優(yōu)先考慮，對(duì)于這個(gè)問(wèn)題，卡車(chē)有以下4種路線(xiàn)選擇：港口----I------J-----港口；運(yùn)費(fèi)成本：港口----I----J----J----港口；運(yùn)費(fèi)成本：港口----J----I----港口；運(yùn)費(fèi)成本：港口----J----I----J----港口；運(yùn)費(fèi)成本：方案選擇：從以上的等式，其中的P1表示載重運(yùn)費(fèi)，單位元/噸公里；P2表示空載路費(fèi)。其中P1=1.8;P2=0.4；所以?xún)?yōu)先考慮的是系數(shù)最大的，即：系數(shù)的項(xiàng)，L1或L2，取最小值的那條路線(xiàn)。然后在觀(guān)察，其項(xiàng)恒等于L0，對(duì)于給定的公司，L0為一個(gè)定值，沒(méi)有優(yōu)化的余地。再看剩下的項(xiàng)，它等于總路線(xiàn)，其選擇的回程路線(xiàn)應(yīng)該是回程最短的路線(xiàn)?？梢宰C明，這里最少運(yùn)費(fèi)的路線(xiàn)也是最省時(shí)間的路線(xiàn)。匹配方案的選擇：如果所有的公司里，總共n個(gè)公司可以匹配卸貨方案，那么匹配的總方法就有；我們可以把每個(gè)可以匹配的公司看做圖論里的頂點(diǎn)，他們之間連線(xiàn)形成一個(gè)完全圖，每條連線(xiàn)上賦上權(quán)值表示I,j公司之間在走最優(yōu)路線(xiàn)下的費(fèi)用（元）和時(shí)間（分）線(xiàn)性組合，其中選擇恰當(dāng)?shù)腁,B的值使得路費(fèi)成本P能夠更優(yōu)先考慮，一般使得AP>=Bt選擇最優(yōu)匹配組合的算法：先選擇權(quán)值最小的一條連線(xiàn)，把其上的兩個(gè)頂點(diǎn)（公司）鏈接起來(lái)；記錄已經(jīng)連線(xiàn)的頂點(diǎn)；再選取次小權(quán)值的連線(xiàn)，如果連線(xiàn)上的頂點(diǎn)不是記錄中已經(jīng)連線(xiàn)的頂點(diǎn)，則執(zhí)行（2）步；否則選取下一個(gè)次小權(quán)值的連線(xiàn)，重復(fù)（3）。直至記錄中的頂點(diǎn)數(shù)與總頂點(diǎn)書(shū)的差小于等于1。程序終止。以上實(shí)例中，只有4，6公司可以匹配，因此，這里只需要考慮4，6公司匹配的最優(yōu)路線(xiàn)問(wèn)題。選擇最小車(chē)次的調(diào)度方案：通過(guò)上面的方法，現(xiàn)在已經(jīng)確定了最小運(yùn)費(fèi)和最少時(shí)間的方案。還剩下：最少出車(chē)的調(diào)度方案：車(chē)的調(diào)度方案應(yīng)該確定一下變量：出車(chē)的數(shù)量num；每輛車(chē)分別在哪些公司（J）卸貨，在每個(gè)公司卸貨幾次。采用貪婪算法來(lái)解決匹配方案：（貪婪算法的程序見(jiàn)附錄3）初始化車(chē)輛數(shù)num=1；按照運(yùn)送時(shí)間。從大到小對(duì)各個(gè)公司進(jìn)行排序；并定義為公司j的卸貨次數(shù)；令使用時(shí)間q=0初始化；按照排序好的公司做一下工作：從排好序的公司，依次執(zhí)行其卸貨車(chē)次的運(yùn)輸，執(zhí)行完j公司的所有運(yùn)送后，執(zhí)行下一公司的運(yùn)送，每運(yùn)送一次，q=q+；并使直至q<=t_max（最大時(shí)間，這里是480分鐘）不成立，然后另j=j+1；指向下一公司，觀(guān)察q+tj<=t_max是否成立，成立則q=q+tj；否則j=j+1；循環(huán)執(zhí)行至j>n，這里n是公司數(shù)量；num=num+1；遍歷檢測(cè)mj，若所有mj==0，則退出程序；否則記錄下此時(shí)num對(duì)應(yīng)的q值，即為其運(yùn)送的時(shí)間。本問(wèn)題中，每個(gè)公司的運(yùn)送次數(shù)如下表：表5.2.3公司4353，6（匹配）62718時(shí)間837371605555474135卸貨次數(shù)423134457車(chē)輛需要4輛，具體車(chē)次如下表：表5.2.4車(chē)公司1公司2公司3公司4公司5公司6公司7公司83，6匹配12次4次23次3次1次1次31次4次4次44次6次結(jié)論：共用4輛車(chē)，所用時(shí)間分別為，1車(chē)7.967小時(shí)；2車(chē)7.883小時(shí)；3車(chē)7.483小時(shí)；4車(chē)6.233小時(shí)。5.3問(wèn)題三模型的建立與求解5.3.1第一問(wèn)問(wèn)題3分了4，6，8噸載重的三種車(chē)，為了卸貨效率較高，要求每種車(chē)卸貨的重量為本車(chē)最大載重的一半以上；同時(shí)注意到，對(duì)于低于6噸的貨物，可以由6噸載重的卡車(chē)運(yùn)，沒(méi)有必要用8噸的（空載車(chē)費(fèi)隨最大載重量增加而變貴），而4噸以下的就沒(méi)必要用6噸的車(chē)來(lái)卸貨，這樣只會(huì)增加卸貨的次數(shù)，因此只考慮3，4，5，6，7，8噸卸貨的方案。其中：4噸載重車(chē)可以卸貨：3噸，4噸；6噸載重車(chē)可以卸貨：5噸，6噸；8噸載重車(chē)可以卸貨：7噸，8噸；基于以上假設(shè)，卸貨方案有以下幾種則卸貨的方案滿(mǎn)足以下條件：利用遍歷算法可以很快確定各種貨物的卸載方案如下：4噸載重車(chē)卸貨方案C1AC2B+CC34CC4BC53C6噸載重車(chē)卸貨方案D1A+2CD2B+3CD32BD46CD5A+CD6B+2CD75C8噸載重車(chē)卸貨方案E12AE2A+B+CE3A+4CE42B+2CE5B+5CE68CE77CE8A+3CE9A+BE102B+CE11B+4C現(xiàn)在對(duì)每一個(gè)公司單獨(dú)求出其卸貨次數(shù)最低的優(yōu)化模型：利用LINGO可以求出最優(yōu)卸貨方案如下：4噸載重車(chē)的卸貨方案4噸方案公司1公司2公司3公司4公司5公司6公司7公司8C1A11C2B+CC34CC4BC53C6噸載重車(chē)的卸貨方案6噸公司1公司2公司3公司4公司5公司6公司7公司8D1A+2CD2B+3CD32BD46CD5A+CD6B+2C1D75C18噸載重車(chē)的卸貨方案8噸公司1公司2公司3公司4公司5公司6公司7公司8E12A111E2A+B+C11E3A+4C11E42B+2C1E5B+5CE68CE77CE8A+3CE9A+B1122E102B+C21E11B+4C1由于所有載重車(chē)輛的載重噸位都在最大載重量的一半以上，所有這里不存在需要匹配的卸貨方案。因此每次卸貨都要耗費(fèi)單獨(dú)一個(gè)車(chē)次來(lái)完成。根據(jù)以上數(shù)據(jù)，共需要22車(chē)次。為了最大程度減少出車(chē)次數(shù)和盡可能發(fā)揮每輛車(chē)的使用時(shí)間，仍然和問(wèn)題2一樣，采用貪婪算法，得出的結(jié)果如下：4噸位車(chē)1輛，2次；6噸位1輛，2次，8噸位2輛，18次即公用4輛車(chē)，出車(chē)22次，詳細(xì)調(diào)用如下表：表5.3.14噸車(chē)：1輛車(chē)公司1公司2公司3公司4公司5公司6公司7公司811次1次6噸車(chē)：1輛車(chē)公司1公司2公司3公司4公司5公司6公司7公司811次1次8噸車(chē)：2輛車(chē)公司1公司2公司3公司4公司5公司6公司7公司811次1次1次2次2次23次2次2次4次6模型的評(píng)價(jià)對(duì)于問(wèn)題一的模型一，在港口少，送貨地點(diǎn)少時(shí)能夠較輕松的實(shí)現(xiàn)最優(yōu)調(diào)度，且相對(duì)其他模型費(fèi)用更低，值得推廣。但當(dāng)港口增多，需求加大，公司增多時(shí)則比較難以做到最優(yōu)的匹配。7模型的擴(kuò)展對(duì)于問(wèn)題三的第二問(wèn)，由于各公司間有道路相通，因此不但要考慮車(chē)次問(wèn)題，還要考慮路徑的長(zhǎng)短。而最短路問(wèn)題可用迪克斯特拉（Dijkstra）算法該算法為：1給Vs以P標(biāo)號(hào)，P（Vs）=0,其余各點(diǎn)均給T標(biāo)號(hào)，T(vi)=+；2若vs點(diǎn)為剛得到P的點(diǎn)，考慮這樣的點(diǎn)vj；（vi，vj）屬于E，且vj為T(mén)標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下改進(jìn)：3比較所具有T標(biāo)號(hào)的點(diǎn)，把最小者均改為P的標(biāo)號(hào)，即：當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)，若全為P標(biāo)號(hào)則停止。否則用代vi轉(zhuǎn)回第2步。對(duì)于問(wèn)題三可把港口標(biāo)vs，vi即為各公司的點(diǎn)，算出最短距離再用如問(wèn)題二中的解決方法，即可求出最優(yōu)調(diào)度方案，另外還可用遺傳算法實(shí)現(xiàn)調(diào)度。參考文獻(xiàn)[1]周凱，宋軍全等編著，數(shù)學(xué)建模競(jìng)賽輔導(dǎo)教程，浙江大學(xué)出版社，20XX年8月[2]徐光輝等編著，運(yùn)籌學(xué)基礎(chǔ)手冊(cè)(第一版)，科學(xué)出版社，1999年3月[3]謝金星，薛毅，優(yōu)化模型與LINGO軟件，清華大學(xué)出版社，20XX年[4]陳杰,MATLAB寶典,電子工業(yè)出版社,20XX年[5]武漢理工大學(xué)，貨運(yùn)公司的運(yùn)輸問(wèn)題，/view/5f8f8d6e58fafab069dc0294.html20XX年8月4日[6]胡運(yùn)權(quán)，郭耀煌編著，運(yùn)籌學(xué)教程（第三版），清華大學(xué)出版社，20XX年4月附錄LINGO代碼：1問(wèn)題3解決代碼：MINC1+C2+C3+C4+C5+D1+D2+D3+D4+D5+D6