數(shù)學(xué)建模--運(yùn)輸問題

1、運(yùn)輸問題摘要本文主要研究的是貨物運(yùn)輸?shù)淖疃搪窂絾栴}，利用圖論中的Floyd算法、Kruskal算法，以及整數(shù)規(guī)劃的方法建立相關(guān)問題的模型，通過matlab，lingo編程求解出最終結(jié)果。關(guān)于問題一，是一個(gè)兩客戶間最短路程的問題，因此本文利用Floyd算法對(duì)其進(jìn)行分析?？紤]到計(jì)算的方便性，首先，我們將兩客戶之間的距離輸入到網(wǎng)絡(luò)權(quán)矩陣中；然后，逐步分析出兩客戶間的最短距離；最后，利用Matlab軟件對(duì)其進(jìn)行編程求解，運(yùn)行得到結(jié)果：23891

2、0總路程為85公里。關(guān)于問題二，運(yùn)輸公司分別要對(duì)10個(gè)客戶供貨，必須訪問每個(gè)客戶，實(shí)際上是一個(gè)旅行商問題。首先，不考慮送貨員返回提貨點(diǎn)的情形，本文利用最小生成樹問題中的Kruskal算法，結(jié)合題中所給的鄰接矩陣，很快可以得到回路的最短路線：15763489102；然后利用問題一的Floyd算法編程，能求得從客戶2到客戶1（提貨點(diǎn)）的最短路線是：21，路程為50公里。即最短路線為：157634891021。但考慮到最小生成樹法局限于頂點(diǎn)數(shù)

3、較少的情形，不宜進(jìn)一步推廣，因此本文建立以路程最短為目標(biāo)函數(shù)的整數(shù)規(guī)劃模型；最后，利用LINGO軟件對(duì)其進(jìn)行編程求解，求解出的回路與Kruskal算法求出的回路一致。關(guān)于問題三，是在每個(gè)客戶所需固定貨物量的情況下，使得行程之和最短。這樣只要找出兩條盡可能短的回路，并保證每條線路客戶總需求量在50個(gè)單位以內(nèi)即可。因此我們?cè)趩栴}二模型的基礎(chǔ)上進(jìn)行改進(jìn)，以貨車容量為限定條件，建立相應(yīng)的規(guī)劃模型并設(shè)計(jì)一個(gè)簡單的尋路算法，對(duì)于模型求解出來的結(jié)果，

4、本文利用Kruskal算法結(jié)合題中所給的鄰接矩陣進(jìn)行優(yōu)化。得到優(yōu)化結(jié)果為：第一輛車：15234891，第二輛車：1769101，總路程為280公里。關(guān)于問題四，在問題一的基礎(chǔ)上我們首先用Matlab軟件編程確定提貨點(diǎn)到每個(gè)客戶點(diǎn)間的最短路線，然后結(jié)合一些限定條件建立一個(gè)目標(biāo)模型，設(shè)計(jì)一個(gè)較好的解決方案進(jìn)行求解可得到一種很理想的運(yùn)輸方案。根據(jù)matlab運(yùn)行結(jié)果分析得出4條最優(yōu)路線分別為：152，1438，176，1910。最短總路線為2

5、45公里，最小總費(fèi)用為645。關(guān)鍵詞：Floyd算法Kruskal算法整數(shù)規(guī)劃旅行商問題關(guān)于問題一，是一個(gè)兩客戶間最短路程的問題，因此本文利用Floyd算法對(duì)其進(jìn)行分析。考慮到計(jì)算的方便性，首先，我們將兩客戶之間的距離輸入到網(wǎng)絡(luò)權(quán)矩陣中；然后，逐步分析出兩客戶間的最短距離；最后，利用Matlab軟件對(duì)其進(jìn)行編程求解。關(guān)于問題二，運(yùn)輸公司分別要對(duì)10個(gè)客戶供貨，必須訪問每個(gè)客戶，實(shí)際上是尋找一條最短的行車路線。首先，不考慮送貨員返回提貨點(diǎn)

6、的情形，本文利用最小生成樹問題中的Kruskal算法，結(jié)合題中所給的鄰接矩陣，很快可以得到回路的最短路線：；然21098436751vvvvvvvvvv?????????后利用問題一的Floyd算法和程序，能求得從客戶2到客戶1（提貨點(diǎn)）的最短路線是：，路程為50公里。但考慮到最小生成樹法局限于頂點(diǎn)數(shù)較12vv?少的情形，不宜進(jìn)一步推廣，因此本文又根據(jù)路程最短建立以路程最短為目標(biāo)函數(shù)的整數(shù)規(guī)劃模型；最后，利用LINGO軟件對(duì)其進(jìn)行編程求

7、解。關(guān)于問題三，是在每個(gè)客戶所需固定貨物量的情況下，使得行程之和最短。這樣只要找出兩條盡可能短的回路，并保證每條線路客戶總需求量在50個(gè)單位以內(nèi)即可。因此我們?cè)趩栴}二模型的基礎(chǔ)上進(jìn)行改進(jìn)，以貨車容量為限定條件，建立相應(yīng)的規(guī)劃模型并設(shè)計(jì)一個(gè)簡單的尋路算法，對(duì)于模型求解出來的結(jié)果，本文利用Kruskal算法結(jié)合題中所給的鄰接矩陣進(jìn)行優(yōu)化。關(guān)于問題四，我們首先用Matlab軟件編程確定提貨點(diǎn)到每個(gè)客戶點(diǎn)間的最短路線，然后結(jié)合一些限定條件建立一

8、個(gè)目標(biāo)模型，設(shè)計(jì)一個(gè)較好的解決方案進(jìn)行求解可得到一種很理想的運(yùn)輸方案。三、模型假設(shè)1.假設(shè)客戶級(jí)別平等；2.假設(shè)不考慮裝卸車費(fèi)用；3.假設(shè)貨車不發(fā)生意外事故；4.假設(shè)運(yùn)輸過程中貨物無損失；四、符號(hào)說明不同的客戶；:ijv102.1102.1????ji從客戶到客戶的距離；:ijlivjv????；個(gè)客戶無直接的路到達(dá)個(gè)客戶到第從第：；個(gè)客戶有直接的路到達(dá)個(gè)客戶到第從第：jijixij01；個(gè)客戶的距離個(gè)客戶到第從第jicij:；個(gè)客戶所