豬肉貨物配送問題

1、2014第五屆徐州工程學(xué)院校級(jí)數(shù)學(xué)建模聯(lián)賽承 諾 書我們仔細(xì)閱讀了徐州工程學(xué)院校級(jí)數(shù)學(xué)建模聯(lián)賽的競賽規(guī)則。我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與本隊(duì)以外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其它公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承擔(dān)由此引起的一切后果。我們授權(quán)五一數(shù)學(xué)建模聯(lián)賽賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開展

2、示（包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。我們參賽選擇的題號(hào)為（從A/B中選擇一項(xiàng)填寫）： A 我們的參賽報(bào)名號(hào)為： 第3組 參賽組別（研究生或本科或?qū)？疲?本科 所屬學(xué)校（請?zhí)顚懲暾娜?徐州工程學(xué)院 參賽隊(duì)員 (打印并簽名) ：1. 杜鵬 2. 張真齊 3. 吳韻楠 日期： 2014 年 4 月 19 日題目 貨物配送問題 摘要本文對于多種情形下貨物配送問題進(jìn)行分析，構(gòu)造算法、曲線擬合等模型，分析成本和距離、需求量等因素之間的關(guān)系。問題一要求設(shè)計(jì)生產(chǎn)和配送方案，使得運(yùn)輸成本最低。因?yàn)榕渌统杀靖\(yùn)輸?shù)呢浳镏亓坑嘘P(guān)，運(yùn)輸成本同時(shí)和運(yùn)輸距離相關(guān)，要使得運(yùn)輸成本達(dá)

3、到最小，就需要使從生產(chǎn)基地出發(fā)配送到銷售連鎖店的距離最短。題中給出了城鎮(zhèn)的位置以及城鎮(zhèn)間的道路，所以可以運(yùn)用算法，建立有向圖,求出任意兩個(gè)城鎮(zhèn)間的最短距離矩陣和最短距離的路徑選擇矩陣。經(jīng)對比兩個(gè)生產(chǎn)基地到銷售連鎖店的距離，對兩個(gè)矩陣中數(shù)據(jù)進(jìn)行篩選得出生產(chǎn)和配送方案。問題二要求分析近5年每個(gè)月154個(gè)城鎮(zhèn)的鮮豬肉需求量，預(yù)測何時(shí)全省的豬肉需求達(dá)到峰值和達(dá)到峰值時(shí)需求排名前五的城鎮(zhèn)和后五的城鎮(zhèn)。綜合考慮，選擇把時(shí)間量度定位月，對5年60個(gè)月的數(shù)據(jù)運(yùn)用做出散點(diǎn)圖，運(yùn)用擬合曲線，求出在2014年2月全省的豬肉需求量達(dá)到峰值。又因?yàn)槿〉呢i肉需求在達(dá)到峰值前都是增加的，可以判斷大部分城鎮(zhèn)的需求量都是增加

4、的，可能有的城鎮(zhèn)需求增長快慢不一，且數(shù)據(jù)量較大，處理起來稍有難度。所以假設(shè)該省每個(gè)小鎮(zhèn)需求量增長曲線同全省的增長曲線是同一類型，運(yùn)用求出達(dá)到峰值時(shí)，排名前五的小鎮(zhèn)為120、31、63、106、150，排名后五的小鎮(zhèn)為143、30、74、84、102。問題三要求選擇一些城鎮(zhèn)增加銷售連鎖店，擴(kuò)大全省的銷售量，盡可能少的增加銷售點(diǎn)。因?yàn)槊吭黾右粋€(gè)銷售連鎖店對本城鎮(zhèn)的銷售量提高，對周圍10公里的城鎮(zhèn)銷售量增加。得到增加一個(gè)銷售連鎖店的增加的銷售量為：同時(shí)引入一個(gè)，表示是否增加銷售連鎖店。在綜和考慮到銷售能力、實(shí)際銷售量的約束條件。又考慮總的銷售量只有小于等于所有城鎮(zhèn)的需求量才有意義，結(jié)合以上信息建立一

5、個(gè)流程圖，應(yīng)用編寫程序，得到在6、32、56、58、69、76、111、113、115、117、124、135、136、138、139、140、147、149小鎮(zhèn)增加銷售連鎖店，使得總的銷售量達(dá)到最大值。關(guān)鍵詞 算法 曲線擬合 流程圖 一、問題重述1.1問題背景隨著我國生產(chǎn)和流通企業(yè)的結(jié)構(gòu)調(diào)整，經(jīng)濟(jì)的快速發(fā)展和市場競爭的加劇，貨物配送業(yè)會(huì)受到越來越多的重視。配送方式是現(xiàn)代物流的一個(gè)核心內(nèi)容，可以說是現(xiàn)代市場經(jīng)濟(jì)體制、現(xiàn)代科學(xué)技術(shù)和系統(tǒng)物流思想的綜合產(chǎn)物。配送對于經(jīng)濟(jì)發(fā)展的意義，重要的是在于它是企業(yè)發(fā)展的一個(gè)戰(zhàn)略手段。基于此需要我們從理論與實(shí)踐相結(jié)合的角度，來加強(qiáng)對貨物配送問題的研究。貨物配送是

6、現(xiàn)代流通業(yè)的重要組成部分。現(xiàn)代物流技術(shù)的研究開發(fā)取得一定進(jìn)展。一些貨物配送企業(yè)在研究開發(fā)物流信息技術(shù)和物流配送管理技術(shù)上取得了許多成果，這對于推動(dòng)我國現(xiàn)代物流發(fā)展發(fā)揮了積極作用。配送運(yùn)輸屬于運(yùn)輸中的末端運(yùn)輸、支線運(yùn)輸，和一般運(yùn)輸形態(tài)主要區(qū)別在于：配送運(yùn)輸是較短距離、較小規(guī)模、額度較高的運(yùn)輸形式，一般使用汽車做運(yùn)輸工具。與干線運(yùn)輸?shù)牧硪粋€(gè)區(qū)別是，配送運(yùn)輸?shù)穆肪€選擇問題是一般干線運(yùn)輸所沒有的，干線運(yùn)輸?shù)母删€是唯一的運(yùn)輸線，而配送運(yùn)輸由于配送用戶多，一般城市交通路線又較復(fù)雜，如何組合成最佳路線，如何使配裝和路線有效搭配等，是配送運(yùn)輸?shù)奶攸c(diǎn)，也是難度較大的工作。1.2問題重述某公司是一家肉類食品加工與

7、銷售公司，主營：鮮豬肉。該公司在全省縣級(jí)及以上城鎮(zhèn)設(shè)立銷售連鎖店。全省縣級(jí)及以上城鎮(zhèn)地理位置及道路連接見數(shù)據(jù)文件：全省交通網(wǎng)絡(luò)數(shù)據(jù).xlsx研究以下問題：1、目前該公司現(xiàn)有2個(gè)生產(chǎn)基地、23家銷售連鎖店，生產(chǎn)基地設(shè)在120號(hào)和63號(hào)城鎮(zhèn)，為23家連鎖店提供鮮豬肉，連鎖店的日銷售量見附錄1。若運(yùn)輸成本為0.45元/噸公里，請你為公司設(shè)計(jì)生產(chǎn)與配送方案，使運(yùn)輸成本最低。2、公司收集了近5年全省各城鎮(zhèn)的鮮豬肉月度需求數(shù)據(jù)（文件：各城鎮(zhèn)月度需求數(shù)據(jù).txt）請你分析各城鎮(zhèn)需求特征，并預(yù)測未來數(shù)年，何時(shí)全省鮮豬肉需求達(dá)到峰值，達(dá)到峰值時(shí)需求達(dá)到前5位和后5位的城鎮(zhèn)是那些？3、通過廣告宣傳等手段，未來幾年

8、公司在全省的市場占有率可增至3成左右（各城鎮(zhèn)對公司產(chǎn)品每日需求預(yù)測數(shù)據(jù)見文件：公司未來各城鎮(zhèn)每日需求預(yù)測數(shù)據(jù).txt），為增加市場競爭力，決定增設(shè)銷售連鎖店，其中每增設(shè)一家連鎖店，對于本城鎮(zhèn)的供貨能力可增加1.5成，對于十公里以內(nèi)的城鎮(zhèn)銷售能力可增加0.8成，但是每增設(shè)一家銷售店，增設(shè)的銷售連鎖店銷售能力控制在每日20噸至40噸內(nèi)，并且要求增設(shè)的銷售連鎖店的銷售量必須達(dá)到銷售能力的下限，如何在滿足上述條件的情況下，盡可能少的增設(shè)銷售點(diǎn)。請你為公司設(shè)計(jì)增設(shè)銷售連鎖店方案，使全省銷售量達(dá)到最大。二、問題分析2.1對于問題一的分析問題一要求設(shè)計(jì)生產(chǎn)和配送方案，使得運(yùn)輸成本最低。題目中已知有兩個(gè)生產(chǎn)基

9、地，需要把貨物配送到23個(gè)分布在全省的銷售連鎖店中，為了不造成浪費(fèi)，每一個(gè)生產(chǎn)基地的最小生產(chǎn)量必須等于該生產(chǎn)基地配送的銷售連鎖店的需求量總和。因此，現(xiàn)需要確定配送方案才能確定兩個(gè)生產(chǎn)基地的生產(chǎn)量。配送方案的選擇與運(yùn)輸成本直接掛鉤，運(yùn)輸成本與運(yùn)輸距離和運(yùn)輸重量成正比的，因此我們需要綜合考慮運(yùn)輸距離和運(yùn)輸成本。綜合以上這些提出兩種運(yùn)輸方案，第一種是每一個(gè)銷售連鎖店配送都是分立的，即送完該城鎮(zhèn)后配送任務(wù)結(jié)束。第二種是一次運(yùn)輸幾個(gè)城鎮(zhèn)的貨物，在配送完幾個(gè)小鎮(zhèn)后配送任務(wù)完成。無論哪種配送方案都需要考慮城鎮(zhèn)與城鎮(zhèn)間最短道路的問題，題中給出了城鎮(zhèn)間道路數(shù)據(jù)，但是大部分城市之間沒有直接相連的公路，而具體的配送

10、道路的選擇需要這些數(shù)據(jù)，因此我們需要求出任意兩城鎮(zhèn)間的最短道路。可以運(yùn)用算法和編程求解出任意兩個(gè)城鎮(zhèn)間的最短道路，選擇需要的數(shù)據(jù)來實(shí)現(xiàn)最小成本和具體的運(yùn)輸配送方案。2.2對于問題二的分析問題二給出近5年每個(gè)月154個(gè)城鎮(zhèn)的鮮豬肉需求量，要求我們分析這些數(shù)據(jù)，預(yù)測何時(shí)全省的豬肉需求達(dá)到峰值和達(dá)到峰值時(shí)需求排名前五的城鎮(zhèn)和后五的城鎮(zhèn)。該問題有兩小問，第一個(gè)小問的對象是全省的豬肉需求量，可先求出5年每個(gè)月全省的豬肉需求量，因?yàn)閱栴}要求預(yù)測未來數(shù)年何時(shí)全省豬肉需求量達(dá)到峰值，并沒有明確給出時(shí)間量度是年還是月。倘若時(shí)間量度是年，面臨數(shù)據(jù)稀少，可能導(dǎo)致預(yù)測出的結(jié)果與實(shí)際情況誤差較大。因此本文選擇把時(shí)間量度

11、定位月，對5年60個(gè)月的數(shù)據(jù)運(yùn)用做出散點(diǎn)圖，根據(jù)散點(diǎn)圖判斷選擇擬合曲線，求出何時(shí)到達(dá)峰值。第二小問要求求出達(dá)到峰值的年份排名前五和后五的城鎮(zhèn)。考慮到全省的豬肉需求在達(dá)到峰值前都是增加的，可以判斷大部分城鎮(zhèn)的需求量都是增加的，可能出現(xiàn)有的城鎮(zhèn)需求增長較快，有的增長較慢，加上數(shù)據(jù)量較大，處理起來稍有難度。本文假設(shè)該省每個(gè)小鎮(zhèn)需求量增長曲線同全省的增長曲線是同一類型，運(yùn)用求出達(dá)到峰值時(shí)，排名前五和后五的小鎮(zhèn)。2.3對于問題三的分析問題三給出了未來各城鎮(zhèn)的每日需求量，而且問題一中的銷售連鎖店的銷售量總和達(dá)不到城鎮(zhèn)每日的需求量，同時(shí)為了增強(qiáng)市場競爭力，要求選擇一些城鎮(zhèn)增加銷售連鎖店，擴(kuò)大全省的銷售量，盡

12、可能少的增加銷售點(diǎn)。并且給出了一些限制條件，可以看出，此問可以建立規(guī)劃模型，來求滿足所給的條件下，使得全省的銷售量達(dá)到最大的銷售連鎖店的量。三、模型假設(shè)結(jié)合本題的實(shí)際，為了確保模型求解的準(zhǔn)確性和合理性，我們排除了一些位置因素的干擾，提出以下幾點(diǎn)假設(shè)：1、假設(shè)題目所給數(shù)據(jù)準(zhǔn)確無誤；2、配送過程中不考慮回程的費(fèi)用；3、本城鎮(zhèn)內(nèi)部配送的路徑為0；4、增加的銷售量能夠達(dá)到供給能力的上限。四、符號(hào)說明為了便于問題的求解，給出以下符號(hào)說明：無向圖的鄰接矩陣無向圖殘差平方和擬合程度指標(biāo)判斷矩陣城鎮(zhèn)未來某日的需求量小鎮(zhèn)供貨能力矩陣某一個(gè)小鎮(zhèn)增加銷售連鎖店后增加的銷售量增加銷售連鎖店后增加的銷售量總和原來23個(gè)

13、銷售連鎖店的銷售量總和其他未出現(xiàn)的符號(hào)，在文章首次出現(xiàn)時(shí)會(huì)有說明。五、模型的建立與求解經(jīng)過以上的分析和準(zhǔn)備，我們將逐步建立以下數(shù)學(xué)模型，進(jìn)一步闡述模型的實(shí)際建立過程。5.1模型的建立1、 算法：求最短路徑問題的算法，可以算出任意兩個(gè)節(jié)點(diǎn)之間最短距離的算法； 2、曲線擬合：用連續(xù)曲線近似地刻畫或比擬平面上離散點(diǎn)組所表示的坐標(biāo)之間的函數(shù)關(guān)系；3、賦權(quán)圖：每條邊都有一個(gè)非負(fù)實(shí)數(shù)對應(yīng)的圖。這個(gè)實(shí)數(shù)稱為這條邊的權(quán)。5.2問題一模型的建立與求解題目中給出了共154個(gè)城鎮(zhèn)，23家銷售連鎖店，以及2個(gè)生產(chǎn)基地，現(xiàn)要求從2個(gè)生產(chǎn)基地每天配送鮮豬肉給23家銷售連鎖店，生產(chǎn)基地設(shè)在120號(hào)和63號(hào)城鎮(zhèn)，23家銷售連

14、鎖店的分布圖如圖1：圖1 銷售連鎖店分布圖圖一中方框里的信息依次是銷售連鎖店代號(hào)、所在城鎮(zhèn)代號(hào)、該銷售連鎖店每天需求量（單位：噸），藍(lán)線表示銷售連鎖店之間的直達(dá)公路，藍(lán)線上的數(shù)字表示銷售連鎖店之間的距離（單位：公里）。觀察該圖，可以看出銷售連鎖店1和銷售連鎖店10所在的城鎮(zhèn)為鮮豬肉的一個(gè)生產(chǎn)基地，銷售連鎖店3和銷售連鎖店18所在的城鎮(zhèn)為鮮豬肉的另一個(gè)生產(chǎn)基地。因此，這四個(gè)銷售連鎖店的運(yùn)輸都是城鎮(zhèn)內(nèi)部的運(yùn)輸，本題不去考慮。剩余的銷售連鎖店需要由這兩個(gè)生產(chǎn)基地中的任意一個(gè)配送鮮豬肉。從生產(chǎn)基地出發(fā)，考慮兩種配給方式。方式一，從生產(chǎn)基地出發(fā)途經(jīng)多個(gè)銷售連鎖店，出發(fā)時(shí)運(yùn)載多個(gè)銷售連鎖店所需的貨物。方式

15、二，生產(chǎn)基地向銷售連鎖店單獨(dú)運(yùn)輸。根據(jù)這個(gè)銷售連鎖店對鮮豬肉的需求量配送貨物。現(xiàn)根據(jù)一個(gè)簡單的例子證明兩種配送方案哪一種成本更低。選取圖一中生產(chǎn)基地中的1號(hào)，加上9號(hào)銷售連鎖店和5號(hào)銷售連鎖店，它們兩兩間的距離分別為，銷售連鎖店的需求量分別為，方式一的配送成本為，方式二的配送成本為，所以方式一減去方式二的成本為： 在三條線段共線的情況下，方式一減去方式二的成本為0，即方式一和方式二的配送成本相等；根據(jù)三角形法則，恒成立，所以方式一減去方式二的成本大于0，即方式二的成本小于方式一的成本。從圖1中可以看出，大部分銷售連鎖店所在的城鎮(zhèn)與生產(chǎn)基地沒有直接相連的公路，圖1并沒有標(biāo)出所有的城鎮(zhèn)，因此每個(gè)銷

16、售連鎖店實(shí)際都是可以到達(dá)的，只是相連的公路交錯(cuò)縱橫，擁有很多種選擇。問題一要求我們設(shè)計(jì)配送方案，使得運(yùn)輸成本最低。要使得運(yùn)輸成本最低，就要使得運(yùn)輸路徑最短，可以運(yùn)用算法，算出任意兩個(gè)節(jié)點(diǎn)之間最短距離。這里給出全省城鎮(zhèn)及道路分布圖2：圖2 全省城鎮(zhèn)及道路分布圖算法是計(jì)算賦權(quán)圖中各對頂點(diǎn)之間最短路徑，用算法每次以不同的頂點(diǎn)作為起點(diǎn)，計(jì)算從該點(diǎn)出發(fā)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行次這樣的操作，就可以得到從每一個(gè)頂點(diǎn)到其他路徑的最短路徑。 先建立無向圖，以各城鎮(zhèn)為圖的頂點(diǎn)，兩個(gè)城鎮(zhèn)間的直通公路為圖相應(yīng)兩頂點(diǎn)間的邊，得圖。對的每一邊，賦以一個(gè)實(shí)數(shù)，表示直通公路的長度，稱為的權(quán)，得到賦權(quán)圖。賦權(quán)圖中指定的兩

17、個(gè)頂點(diǎn) 間一定存在最小的軌，它的權(quán)叫做間的距離，記作 賦權(quán)圖權(quán)的鄰接矩陣： 來存放。表示到?jīng)]有直接的邊相連。表示到的邊的長度。算法的思想是先把圖中點(diǎn)集分為成兩組：第一組為以求出最短路勁的頂點(diǎn)集合；第二組為其余未確定最短路徑的點(diǎn)的集合，按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入中。在加入的過程中，總保持從原點(diǎn)到中各頂點(diǎn)的最短路徑長度不大于從原點(diǎn)到中的任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離，中的頂點(diǎn)的距離就是從到頂點(diǎn)的最短路徑長度，中的頂點(diǎn)的距離，是從到頂點(diǎn)值包括中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。具體步驟1、初始時(shí),只包含源點(diǎn),的距離為0，包含除外的其他頂點(diǎn)，中頂點(diǎn)距離為邊上的

18、權(quán)；2、從中選取一個(gè)距離最小的頂點(diǎn),把加入中（該選定的距離就是到的最短路徑長度）；3、以為重新考慮的中間點(diǎn)，修改中各頂點(diǎn)的距離；若從源點(diǎn)到頂點(diǎn)的距離（經(jīng)過頂點(diǎn)）比原來距離（不經(jīng)過頂點(diǎn)）短，則修改頂點(diǎn)的距離值，修改后的距離值的頂點(diǎn)的距離加上邊上的權(quán)；4、重復(fù)步驟第二步和第三步知道所有頂點(diǎn)都包含在中。運(yùn)用編程算出每一個(gè)城鎮(zhèn)到所有城鎮(zhèn)的最短距離矩陣 和最短路線矩陣。在第一問中，兩個(gè)生產(chǎn)基地分別在120號(hào)鎮(zhèn)和63號(hào)鎮(zhèn)。兩個(gè)生產(chǎn)基地運(yùn)送到各個(gè)銷售連鎖店的成本各部相同，顯然選擇成本最小的。因?yàn)樽疃叹嚯x矩陣包括了154個(gè)城鎮(zhèn)到其他所有城鎮(zhèn)的最短距離，因此，從矩陣中提取23個(gè)銷售連鎖店到兩個(gè)生產(chǎn)基地的最短距離

19、，擇優(yōu)選擇配送的基地。并得到具體的配送方案如下表：表1 路徑選擇表連鎖店編號(hào)路徑選擇112012021201251311301063636321120125124133132141151421431622120123236364根據(jù)配送方案，從最短路線矩陣中提取出具體的路線安排和此方案的最小成本。結(jié)果如下表：表2 運(yùn)輸成本表連鎖店編號(hào)銷售量（公斤）最短距離(公里)運(yùn)輸成本(元)1287330023822363.71095.662295321733002114783103.64689.44955422180815.1141.57725952318407.316.05268根據(jù)配送方案，從最短路線

20、矩陣中提取出具體的路線安排和此方案的最小成本。結(jié)果如下表：表3 生產(chǎn)方案表生產(chǎn)基地生產(chǎn)量(噸3問題二模型的建立與求解首先，運(yùn)用畫出全省5年每個(gè)月的豬肉需求量散點(diǎn)圖。根據(jù)點(diǎn)分布的特征決定采用哪種擬合方式。擬合常用的方法是線性最小二乘法，本文也采用線性最小二乘法進(jìn)行下面為線性最小二乘法的步驟：令其中是選定的一組線性無關(guān)函數(shù)，是待定系數(shù)。擬合的準(zhǔn)則是使與的距離的平方和最小，稱為最小二乘準(zhǔn)則。記為求使達(dá)到最小，可利用極值的必要條件得到關(guān)于的線性方程組記線性方程組可表示為當(dāng)線性無關(guān)時(shí)，列滿秩，可逆，線性方程組有唯一的解在根據(jù)散點(diǎn)圖確定函數(shù)。運(yùn)用編程求出擬合的曲線。

21、下面對所擬合出的曲線求它的趨線擬合程度指標(biāo)先求出殘差平方和 ，其中稱為回歸平方和，稱為總平方和第二小問要求預(yù)測全省豬肉需求量達(dá)到峰值時(shí)的排名前五和排名后五的小鎮(zhèn)，本題中共有154個(gè)小鎮(zhèn)，數(shù)據(jù)量非常大處理起來較為繁瑣，但是考慮到全省的豬肉需求量總體上市增加的，并且增加的曲線符合二次函數(shù)圖形。為了方便處理數(shù)據(jù)，本文認(rèn)為每一個(gè)小鎮(zhèn)每月增長曲線也符合二次函數(shù)的，運(yùn)用擬合所有數(shù)據(jù)，求出全省豬肉需求量達(dá)到峰值時(shí)每一個(gè)小鎮(zhèn)的豬肉需求量，進(jìn)行排名刷選出排名前五和后五的城鎮(zhèn)。畫出全省5年每個(gè)月的豬肉需求量散點(diǎn)圖如下圖3：圖3 全省5年每月豬肉需求量散點(diǎn)圖 圖4 二次擬合圖可以看出大致符合二次函數(shù)圖象，因此擬合方

22、式選擇為二次擬合。運(yùn)用對散點(diǎn)圖進(jìn)行擬合，得到的擬合圖如圖4：求出的擬合曲線函數(shù)關(guān)系式為：由擬合圖形可以看出5年來每月的豬肉需求量都是遞增的，并且有函數(shù)關(guān)系式得出在2014年2月全省的豬肉需求量達(dá)到峰值。進(jìn)行趨線擬合程度指標(biāo)檢驗(yàn)根據(jù)求出運(yùn)用擬合全省154個(gè)城鎮(zhèn)每個(gè)月的豬肉需求量數(shù)據(jù)，求出2014年每一個(gè)小鎮(zhèn)的豬肉需求量，進(jìn)行排名刷選出排名前五和后五的城鎮(zhèn)。如下表4表4 前五后五城鎮(zhèn)表前5城鎮(zhèn)需求量（噸）后5城鎮(zhèn)需求量（噸）1208660.7143118.5314645.330112.663382474106.91063569.48498150228410291.5從表中可以看出排名前五的小鎮(zhèn)為1

23、20、31、63、106、150，排名后五的小鎮(zhèn)為143、30、74、84、102。5.4問題三模型的建立與求解首先，根據(jù)第一問得到的最短距離矩陣，得到一個(gè)新的判斷矩陣 其中， ，分別表示從城鎮(zhèn)到城鎮(zhèn)的最短距離小于等于10公里，表示從城鎮(zhèn)到城鎮(zhèn)的最短距離大于等于10公里。其中。考慮到全省154個(gè)城鎮(zhèn)原來就有23個(gè)銷售連鎖店。擁有銷售連鎖店的小鎮(zhèn)的原來供貨能力就為小鎮(zhèn)中所有銷售連鎖店日銷售量的總和，大部分小鎮(zhèn)原來并沒有銷售連鎖店，這一部分小鎮(zhèn)的原來供貨能力就為，則可以生成一個(gè)小鎮(zhèn)供貨能力矩陣還需生成一個(gè)矩陣表示城鎮(zhèn)原來沒有銷售連鎖店，表示城鎮(zhèn)原來所有銷售連鎖店的日銷售量總和。 表示城鎮(zhèn) 每日的豬

24、肉需求量；令 ， 表示在該城鎮(zhèn)增加一個(gè)銷售連鎖店， 表示該城鎮(zhèn)不增加銷售連鎖店。原來23個(gè)銷售連鎖店的銷售量總和為 ,增加銷售連鎖店后增加的銷售量總和為 。全省的需求量總和為為。在某一城鎮(zhèn)增加一個(gè)銷售連鎖店，本城鎮(zhèn)的需求量可能也會(huì)因此增加，但增加銷售連鎖店對本城鎮(zhèn)的供貨能力可提高1.5成，即本城鎮(zhèn)的銷售量在原來基礎(chǔ)上最大增加 ；同時(shí)也對周圍10公里以內(nèi)的城鎮(zhèn)銷售能力增加。令某一個(gè)小鎮(zhèn)增加銷售連鎖店后增加的銷售量為本問中原來就有23個(gè)銷售連鎖店，根據(jù)第一問中所給的日銷售量，本文認(rèn)為第一問中所給出的日銷售量就是未來數(shù)年內(nèi)該銷售連鎖店的日銷售量。對比原來所有的銷售連鎖店日銷售量總和，和未來數(shù)年各城鎮(zhèn)

25、的日銷售量總和，發(fā)現(xiàn)原有的銷售量無法滿足現(xiàn)有的需求量。本文要使得全省的銷售量達(dá)到最大，即要求增加的連鎖店的銷售量加上原有銷售連鎖店的銷售量達(dá)到全省各城鎮(zhèn)日需求量的總和。為了便于建立模型，本文中，某一城鎮(zhèn)原有的銷售量等于其需求量。新增加的連鎖店等級(jí)高于原有的連鎖店。即周圍十公里內(nèi)的優(yōu)先購買新增設(shè)的銷售連鎖店的產(chǎn)品。則目標(biāo)函數(shù)為：限制條件1、增設(shè)的銷售連鎖店的銷售能力控制在20噸到40噸內(nèi)，得2、銷售量大于銷售能力的下限，得 可以看出，此問有兩個(gè)目標(biāo)函數(shù)，一個(gè)是要求全省的銷售量達(dá)到最大。因此第二個(gè)是要求增設(shè)的銷售連鎖店最小。這兩個(gè)約束變量看似相互矛盾，但其實(shí)目標(biāo)函數(shù)是在滿足約束條件的小鎮(zhèn)的數(shù)量較多

26、，使得如果全部都增設(shè)會(huì)使得實(shí)際的理論銷售量大于全省的需求量情況下為了避免不必要的費(fèi)用，增設(shè)最少的銷售連鎖店達(dá)到要求。但若滿足約束條件的小鎮(zhèn)的數(shù)量少，全部增設(shè)銷售連鎖店都無法滿足全省的需求量的時(shí)候，目標(biāo)函數(shù)就舍棄，所有滿足的小鎮(zhèn)都增設(shè)，使得全省的豬肉銷售量盡可能的大。綜上，可得出下面的流程圖：根據(jù)流程圖，運(yùn)用編寫程序，實(shí)現(xiàn)程序圖。得出最終的結(jié)果為如下表5：表5 增設(shè)銷售連鎖店的城鎮(zhèn)城鎮(zhèn)632565876111增加銷售量3450.333619.873897.812269.023872.283003.28城鎮(zhèn)113115117124135136增加銷售量2784.992024.492558.7423

27、39.3332242298.03城鎮(zhèn)138139140147148149增加銷售量2420.733680.632747.123533.383582.482717.46增加的銷售量為。六、模型評(píng)價(jià)與改進(jìn)6.1模型優(yōu)缺點(diǎn)分析6.1.1模型的優(yōu)點(diǎn)1、Floyd算法容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫簡單；2、曲線擬合可以使函數(shù)在某種準(zhǔn)則下與所有數(shù)據(jù)點(diǎn)最為接近；3、易于處理大量數(shù)據(jù)。6.1.2模型的缺點(diǎn)1、Floyd算法時(shí)間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)；2、問題二中，再對154個(gè)城鎮(zhèn)每月需求擬合時(shí)沒有考慮擬合的方式是否恰當(dāng)。6.2模型改進(jìn)問題一中可以應(yīng)用算法，求出需要的數(shù)據(jù)，不必

28、把所有的城鎮(zhèn)與城鎮(zhèn)間最短路徑求出來，提高運(yùn)算效率。七、模型推廣針對最短路徑選擇問題，可以應(yīng)用算法，該模型可以應(yīng)用到導(dǎo)航儀中，根據(jù)給出的起點(diǎn)和終點(diǎn)，結(jié)合周圍的道路分布情況，計(jì)算出最短的路徑，以圖形的形式反饋給客戶。也可廣泛應(yīng)用到物流行業(yè)中。八、參考文獻(xiàn)1物流配送 2014年4月14日2Floyd算法 2014年4月16日3曲線擬合 2014年4月19日4百度文庫，算法實(shí)現(xiàn)，7L8l22ov-BJcsylEQlumfjQ_0vYibQwskgy-omHMpCHL67SOIY18-HpbM-qY9hJqFmskiqSy，2014年4月16日附錄表1 路徑選擇表連鎖店編號(hào)路徑選擇11201202120

29、125131130106363634636515010315120125124133132141663651501076364658636667991201251241331321411514214316110120120111201191345404142353612636515010292827131201191345444334141201191345404142151201251311301069190284939416636666768693212311176366667686932418636319120123134149146145206366667686932122211201

30、25124133132141151421431622120123236364表2 運(yùn)輸成本表連鎖店編號(hào)銷售量（公斤）最短距離(公里)運(yùn)輸成本(元)1287330023822363.71095.66229532173300423947114.661235.5933595925861.72257.13169268481108.36413.55052271557019.09133.75408583875928.17491.3284635914744134.31891.1199881032517001111503151.19782.6123565129265135.1563.2656751345111

31、9.5424.260643149489110.58472.1821291512773170.17978.1116345166103108.36297.594486173251128.94188.632773182829500193965372.851299.924473206375168.95484.67531252114783103.64689.44955422180815.1141.57725952318407.316.05268表3 生產(chǎn)方案表生產(chǎn)基地生產(chǎn)量(噸)63163619120230208附錄2.1.1 用作城鎮(zhèn)散點(diǎn)圖及城鎮(zhèn)間道路連接圖：clcclear allclose all

32、x,y=textread('E:22.txt');plot(x,y,'.') %作散點(diǎn)圖hold onfor i=1:154c=num2str(i);c=' ',c;text(x(i),y(i),c)end %在點(diǎn)上標(biāo)城鎮(zhèn)序號(hào)m=textread('E:m.txt');n=textread('E:n.txt');for j=1:248p=m(j);q=n(j); line(x(p),x(q),y(p),y(q)end %連接有公路的兩點(diǎn)d=1,10,11,16,22,24,27,31,34,36,42,62,63,

33、64,79,94,106,120,123,141,145;for i=1:21 plot(x(i),y(i),'r+')end %給21個(gè)零售點(diǎn)加紅色標(biāo)記2.1.2 19個(gè)連鎖店生產(chǎn)基地的選擇矩陣：clcclear allclose alln=154;A = zeros(n);x=textread('E:m.txt');y=textread('E:n.txt');z=textread('E:路程.txt');ind=(y-1).*n+x;A(ind)=z;%把矩陣中Ax,y替換為zB=A'+A;idx=find(B=0);

34、 % 找出矩陣中等于0的數(shù)B(idx)=inf; % 把等于0的數(shù)替換為infB(logical(eye(size(B)=0;%給對角線上數(shù)賦為0a=B;%a是鄰接矩陣%start是起始點(diǎn)%terminal是終止點(diǎn)%D是最小權(quán)值表%path是最短路線表。D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(

35、i,j)=path(i,k); end end endendxlswrite('E:最小權(quán)值表.xls',D)m=D(1,10,11,16,22,24,27,31,34,36,42,65,64,79,94,106,123,141,145,120);n=D(1,10,11,16,22,24,27,31,34,36,42,65,64,79,94,106,123,141,145,63);c=m-nfor i=1:19 if c(i)>0 disp('選63'); else disp('選120'); endend %輸出19個(gè)零售店從63還是12

36、0運(yùn)輸?shù)倪x擇矩陣2.1.3 求解路徑選擇結(jié)果及最短距離大?。篶lcclear allclose alln=154;A = zeros(n);x=textread('E:m.txt');y=textread('E:n.txt');z=textread('E:路程.txt');ind=(y-1).*n+x;A(ind)=z;%把矩陣中Ax,y替換為zB=A'+A;idx=find(B=0); % 找出矩陣中等于0的數(shù)B(idx)=inf; % 把等于0的數(shù)替換為infB(logical(eye(size(B)=0;%給對角線上數(shù)賦為0a=B;

37、%a是鄰接矩陣%start是起始點(diǎn)%terminal是終止點(diǎn)%D是最小權(quán)值表%path是最短路線表。D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end endendxlswrite('E:最小權(quán)值表.xls',D)m=D(1,10,11,16

38、,22,24,27,31,34,36,42,65,64,79,94,106,123,141,145,120);n=D(1,10,11,16,22,24,27,31,34,36,42,65,64,79,94,106,123,141,145,63);c=m-nfor i=1:19 if c(i)>0 disp('選63'); else disp('選120'); endend %輸出19個(gè)零售店從63還是120運(yùn)輸?shù)倪x擇矩陣2.2.1 第二問對需求總和作散點(diǎn)圖，二次擬合并求出最大值：clcclear allclose allx=1:60;y=textread(

39、'E:擬合數(shù)據(jù).txt');p=polyfit(x,y,2)%對數(shù)據(jù)二次擬合xi=0:100;yi=polyval(p,xi);%求多項(xiàng)式值plot(xi,yi,x,y,'r*')%作散點(diǎn)圖及擬合圖，可看出100月之內(nèi)取到峰值max(yi)%求峰值m=find(yi=max(yi)%求峰值對應(yīng)的月份,由月份推出其所在年份2.2.2對各個(gè)城鎮(zhèn)達(dá)到峰值月份時(shí)需求量的預(yù)測：clcclear allclose allm=textread('E:城鎮(zhèn)需求數(shù)據(jù).txt');for i=1:154 x=1:60; y=m(i,:); p=polyfit(x,y

40、,2);%對數(shù)據(jù)二次擬合 xj=74; yj=polyval(p,xj);%求多項(xiàng)式值 disp(yj);end %得出第74月各個(gè)城鎮(zhèn)預(yù)測銷售量2.2.3對預(yù)測需求量排序，求其前5和后5需求量及其所屬城鎮(zhèn)：clcclear allclose alla=textread('E:1.txt');b,index=sort(a(:),'descend')%將矩陣a數(shù)據(jù)從大到小排列，并列出其位置可找出前5和后52.3.1 導(dǎo)出0-1判斷矩陣A：clcclear allclose alln=154;A = zeros(n);x=textread('E:m.txt');y=textread('E:n.txt');z=textread('E:路程.txt');ind=(y-1).*n+x;A(ind)=z;%把矩陣中Ax,y替換為zB=A'+A;idx=find(B=0); % 找出矩陣中等于0的數(shù)B(idx)=inf; % 把等于0的數(shù)替換為infB(logical(eye(size(B)=0;%給對角線上數(shù)賦為0a=B;%a是鄰接矩陣%start是起始點(diǎn)%terminal是終止點(diǎn)%D是最小權(quán)值表%path是最短路線表。D=a;n=size(D,1);path=ze