供應(yīng)鏈網(wǎng)絡(luò)建立及破壞數(shù)學(xué)建模

目錄一、問(wèn)題重述2二、問(wèn)題提出2三、問(wèn)題分析3四、模型假設(shè)3五、主要符號(hào)說(shuō)明4六、模型的建立與求解56.1問(wèn)題一56.1.1蟻群算法的根本理論6模型求解96.2問(wèn)題二11迪杰斯特拉算法11模型求解126.3問(wèn)題三14獨(dú)立事件模型建立14模型求解15七、模型的優(yōu)缺點(diǎn)157.1動(dòng)態(tài)規(guī)劃15優(yōu)點(diǎn)15缺點(diǎn)157.2蟻群算法16優(yōu)點(diǎn)16缺點(diǎn)16八、參考文獻(xiàn)17九、附錄18一、問(wèn)題重述全球化競(jìng)爭(zhēng)的加劇促使越來(lái)越多的企業(yè)開(kāi)場(chǎng)采用供給鏈管理策略，以實(shí)現(xiàn)企業(yè)的一體化管理。供給鏈?zhǔn)且粋€(gè)復(fù)雜的網(wǎng)狀構(gòu)造系統(tǒng)，每一局部都面臨著各種潛在的風(fēng)險(xiǎn)，任何一局部出現(xiàn)問(wèn)題都可能給整個(gè)供給鏈帶來(lái)嚴(yán)重的影響，因此如何分析、評(píng)價(jià)和提高供給鏈系統(tǒng)的可靠性變得日益迫切。設(shè)施系統(tǒng)是供給鏈的核心，在供給鏈研究中有著極其重要的地位。在一個(gè)設(shè)施系統(tǒng)中，*些個(gè)設(shè)施由于自然災(zāi)害或者其他因素的影響可能失效，例如911恐懼襲擊事件、2004年的印度洋海嘯、2008年的汶川地震等都對(duì)諸多行業(yè)的設(shè)施系統(tǒng)造成了嚴(yán)重的破壞。現(xiàn)有*物流公司要在全國(guó)各城市之間建立供給鏈網(wǎng)絡(luò)。需要選定局部城市作為供給點(diǎn)，將貨物運(yùn)輸?shù)礁鞒鞘小ＭǔＣ總€(gè)供給點(diǎn)的貨物是充足的，可以充分滿(mǎn)足相應(yīng)城市的需求。假設(shè)該公司共考慮49個(gè)城市的網(wǎng)絡(luò)并假定作為供給點(diǎn)的城市其供給量可以滿(mǎn)足有需要的城市的需求?，F(xiàn)將要建立一個(gè)供給網(wǎng)絡(luò)，為各城市提供貨物供給。貨物運(yùn)輸利用汽車(chē)進(jìn)展公路運(yùn)輸。二、問(wèn)題提出〔1〕現(xiàn)在要從49個(gè)城市中選取局部城市做為供給點(diǎn)供給本城市及其它城市。建立供給點(diǎn)會(huì)花費(fèi)固定費(fèi)用，從供給點(diǎn)運(yùn)輸?shù)叫枨簏c(diǎn)會(huì)產(chǎn)生運(yùn)輸費(fèi)用，要使總費(fèi)用最小，問(wèn)建立多少個(gè)供給點(diǎn)最好。給出選中作為供給點(diǎn)的城市，并給出每個(gè)供給點(diǎn)供給的城市。同時(shí)根據(jù)坐標(biāo)作出每一個(gè)供給點(diǎn)到需求點(diǎn)的連接圖?！?〕假定有*組織對(duì)該供給網(wǎng)絡(luò)的道路進(jìn)展破壞。并非所有的道路都可以被破壞。當(dāng)*條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過(guò)該道路的只有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是使對(duì)方總費(fèi)用增加25%，而每破壞一條道路都需要本錢(qián)和代價(jià)，因此需要破壞最少的道路。問(wèn)破壞方選取哪幾條線(xiàn)路進(jìn)展破壞。給出具體的破壞道路和總費(fèi)用?！?〕假定各道路能否被破壞具有隨機(jī)性，當(dāng)*條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過(guò)該道路的只有改道，但總是沿最短路運(yùn)輸。由于破壞方選取一些邊進(jìn)展破壞時(shí)，這些邊不一定被破壞，而是服從一定的概率分布。運(yùn)輸時(shí)產(chǎn)生的費(fèi)用可按照各種情況下的平均費(fèi)用來(lái)考慮。如果破壞方選取的策略是使對(duì)方平均總費(fèi)用增加最大。給出具體的破壞道路和平均總費(fèi)用。三、問(wèn)題分析問(wèn)題一：對(duì)問(wèn)題一中的運(yùn)輸調(diào)度問(wèn)題進(jìn)展分析，根據(jù)動(dòng)態(tài)規(guī)劃算法進(jìn)展處理，利用lingo對(duì)其數(shù)學(xué)模型進(jìn)展求解，但該方式給出的算法所搜索的空間容量很大，利用目前的計(jì)算機(jī)求此問(wèn)題的準(zhǔn)確解已很難實(shí)現(xiàn)，并且需要相當(dāng)長(zhǎng)的時(shí)間才有可能得到準(zhǔn)確解，且其規(guī)模較小實(shí)際應(yīng)用的意義不大。為此，我們結(jié)合蟻群算法在求解運(yùn)輸調(diào)度問(wèn)題上的優(yōu)勢(shì)，在此根底上，將蟻群算法結(jié)合運(yùn)輸調(diào)度模型進(jìn)展仿真實(shí)現(xiàn)。問(wèn)題二：我們建立了基于迪杰斯特拉算法的模型。根據(jù)題目所給的的信息，對(duì)可破壞的道路進(jìn)展逐一破壞分析，得到最短傳輸路徑和相應(yīng)多消耗的費(fèi)用。再根據(jù)破壞方使對(duì)方總費(fèi)用增加25%這一策略得到具體破壞的道路和總費(fèi)用。問(wèn)題三：該問(wèn)題是在問(wèn)題二的根底上的優(yōu)化，由于破壞方選取一些邊進(jìn)展破壞時(shí)，這些邊不一定被破壞，而是服從一定的概率分布。在考慮此問(wèn)題時(shí)，要涉及到各邊所破壞的概率，再根據(jù)破壞方選取的策略得到具體的破壞道路和平均總費(fèi)用。四、模型假設(shè)〔1〕假設(shè)每個(gè)供給點(diǎn)的貨物是充足的，可以充分滿(mǎn)足相應(yīng)城市的需求；〔2〕假設(shè)每輛車(chē)所效勞的客戶(hù)總的需求量不得大于車(chē)輛的最大載質(zhì)量；〔3〕假設(shè)一個(gè)城市由只能有一個(gè)供給點(diǎn)供給；〔4〕忽略供給鏈網(wǎng)絡(luò)中運(yùn)輸貨物的不同對(duì)供給點(diǎn)設(shè)立的影響；〔5〕忽略貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車(chē)輛容量限制、行駛里程限制及時(shí)間限制的影響；〔6〕假設(shè)兩城市之間除了公路運(yùn)輸沒(méi)有其他運(yùn)輸方式；

〔7〕假設(shè)運(yùn)輸單價(jià)不受天氣和油價(jià)等因素影響；〔8〕假設(shè)各城市的需求量在一段時(shí)間固定不變。五、主要符號(hào)說(shuō)明元素i在t時(shí)刻存在的螞蟻數(shù)量路徑(i，j)上t時(shí)刻的信息素濃度數(shù)值n城市數(shù)目m蟻群算法的規(guī)模即蟻群中的螞蟻總數(shù)t時(shí)刻所有城市間路徑上的信息素殘留量的集合螞蟻k下一步允許選擇的城市信息素強(qiáng)度影響因子啟發(fā)函數(shù)dist[n]存放從源點(diǎn)到每個(gè)終點(diǎn)當(dāng)前最短路徑的長(zhǎng)度path[n]存放相應(yīng)路徑S已求得最短路徑的終點(diǎn)的集合cos(i)表示以第i個(gè)城市建立供給點(diǎn)所需的固定費(fèi)用w(i)表示第i個(gè)城市所需的貨物重量d(i)路線(xiàn)序號(hào)i的距離乘以每公里費(fèi)用0.5元之后的值Total[i]以i為供給中心和周?chē)鞘袠?gòu)成網(wǎng)絡(luò)所需的總費(fèi)用ans[i]表示破壞道路要多序號(hào)i后要多花費(fèi)的費(fèi)用六、模型的建立與求解供給鏈網(wǎng)絡(luò)中一個(gè)重要的網(wǎng)絡(luò)節(jié)點(diǎn)是供給點(diǎn)設(shè)立。一般來(lái)講，如果用戶(hù)較為固定，按照配送費(fèi)用最小或者到各個(gè)消費(fèi)地的距離之和最小的原則，即供給點(diǎn)處于使物流網(wǎng)路運(yùn)營(yíng)費(fèi)用最小的位置或者供給點(diǎn)所處位置與各城市位置的通行距離之和應(yīng)為各待選位置中的最低者。此時(shí)，供給鏈網(wǎng)絡(luò)應(yīng)設(shè)為輻射型網(wǎng)絡(luò)布局。輻射型網(wǎng)絡(luò)布局如下列圖所示，供給點(diǎn)位于需求點(diǎn)的幾何中心位置，構(gòu)成需求地環(huán)繞供給點(diǎn)的布局格式。物料從此供給點(diǎn)向周?chē)鞣较蛳M(fèi)者配送，形成輻射型。需求地需求地需求地需求地供給點(diǎn)圖1：輻射型格局設(shè)立輻射型的格局應(yīng)滿(mǎn)足兩個(gè)方面的條件。一是需求地在供給點(diǎn)周?chē)鷰缀跏蔷鶆蚍植?，并且供給點(diǎn)周?chē)怯脩?hù)相對(duì)集中的經(jīng)濟(jì)區(qū)域；二是供給點(diǎn)是連接主干輸送線(xiàn)路和配送線(xiàn)路的一個(gè)轉(zhuǎn)運(yùn)站，把貨物送到指定地點(diǎn)。6.1問(wèn)題一根據(jù)題中所給出的各城市坐標(biāo)和各公路段及里程表，得到49個(gè)城市的分布圖如下。圖2：城市的分布圖對(duì)問(wèn)題一中的運(yùn)輸調(diào)度問(wèn)題進(jìn)展分析，根據(jù)動(dòng)態(tài)規(guī)劃算法進(jìn)展處理，利用lingo對(duì)其數(shù)學(xué)模型進(jìn)展編程并求解，但該方式給出的算法所搜索的空間容量很大，利用目前的計(jì)算機(jī)求此問(wèn)題的準(zhǔn)確解已很難實(shí)現(xiàn)，并且需要相當(dāng)長(zhǎng)的時(shí)間才有可能得到準(zhǔn)確解，且其規(guī)模較小實(shí)際應(yīng)用的意義不大。在實(shí)際應(yīng)用中的時(shí)候不是非要得到一個(gè)準(zhǔn)確的解，在大多數(shù)時(shí)候近似的解就已經(jīng)滿(mǎn)足了實(shí)際的需求，為此我們結(jié)合蟻群算法在求解運(yùn)輸調(diào)度問(wèn)題上的優(yōu)勢(shì)，在此根底上，將蟻群算法結(jié)合運(yùn)輸調(diào)度模型進(jìn)展仿真實(shí)現(xiàn)。6.1.1蟻群算法的根本理論螞蟻覓食時(shí)，會(huì)在所經(jīng)過(guò)路線(xiàn)上留下一種稱(chēng)為信息素的物質(zhì)，以此來(lái)標(biāo)識(shí)路線(xiàn)，其它螞蟻可以并且習(xí)慣追蹤此信息素爬行。在確定位置的食物和蟻穴之間，較近的路線(xiàn)，螞蟻重復(fù)爬行的次數(shù)就更高些，由于每只螞蟻每經(jīng)過(guò)一次都要釋放信息素，這樣重復(fù)次數(shù)多的路線(xiàn)由于其信息素濃度較大就更容易被其它螞蟻選中，這樣整個(gè)蟻群就由開(kāi)場(chǎng)的多路線(xiàn)爬行逐漸集中到最短的路線(xiàn)上爬行，使路線(xiàn)得到優(yōu)化選擇。蟻群算法是一種模擬自然界螞蟻覓食行為的啟發(fā)式搜索算法，由意大利學(xué)者M(jìn).Dorigo模擬此過(guò)程提出。其主要特點(diǎn)正反應(yīng)、并行式搜索。它尤其適用于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線(xiàn)性問(wèn)題，可廣泛用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域，是21世紀(jì)有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)之一。首先我們要對(duì)螞蟻的搜索環(huán)境進(jìn)展一些假設(shè)并設(shè)定一些具體參數(shù)，設(shè)：①為元素i在t時(shí)刻存在的螞蟻數(shù)量；②為路徑(i，j)上t時(shí)刻的信息素濃度數(shù)值；③n表示城市數(shù)目；④m表示蟻群算法的規(guī)模即蟻群中的螞蟻總數(shù)，；⑤是t時(shí)刻所有城市間路徑上的信息素殘留量的集合。蟻群算法的初始時(shí)刻各個(gè)路徑上的信息素通常設(shè)定為一個(gè)常數(shù)。螞蟻k(k=1,2,…，m)在路徑的搜索過(guò)程中，根據(jù)不同路徑上的信息素濃度來(lái)決定其下一步的搜索路徑。表示在t時(shí)刻螞蟻k由元素(城市)i轉(zhuǎn)移到元素(城市)j的選擇概率。式中，表示螞蟻k下一步允許選擇的城市，為信息素強(qiáng)度影響因子，表示螞蟻對(duì)于信息素濃度的敏感程度也說(shuō)明此路徑的相對(duì)重要性。其值越大，此時(shí)螞蟻在選擇下一搜索路徑時(shí)，容易受到信息素濃度的影響，螞蟻更趨向于信息素濃度較高的路徑，也就是有更多螞蟻?zhàn)哌^(guò)的路徑同時(shí)也是增強(qiáng)了螞蟻間的交流信息使彼此間的協(xié)調(diào)機(jī)制更明顯。為能見(jiàn)度因子又稱(chēng)期望因子，表示螞蟻本身的能見(jiàn)度對(duì)在路徑選擇中的重要性。其值越大則螞蟻選擇路徑時(shí)越是依賴(lài)于能見(jiàn)度信息。當(dāng)取值很高時(shí)螞蟻則是以一種幾乎貪婪的規(guī)則選擇下一步的搜索路徑，而忽略信息素影響。為啟發(fā)函數(shù)，其表達(dá)式如下:式中，表示兩個(gè)相鄰元素間的距離。的數(shù)值越小，說(shuō)明兩城市相距越近同時(shí)越大，也就越大，螞蟻下一步選擇這一個(gè)城市的概率也就越高，這也就說(shuō)該函數(shù)表征了螞蟻從一個(gè)城市到另一個(gè)城市的期望度數(shù)值。隨著螞蟻的不斷搜索，很多路徑上都會(huì)留下信息素，為了防止各個(gè)路徑上的大量殘留信息素不斷積累從而導(dǎo)致螞蟻忽略能見(jiàn)度信息，當(dāng)每只螞蟻每完成一步搜索或者螞蟻完成對(duì)n個(gè)城市的搜索(也就是算法完成一次迭代)后，需要對(duì)每條路徑上殘留的信息素量進(jìn)展更新。這樣在t+n時(shí)刻路徑(i，j)上的信息素濃度可以按照下面的公式調(diào)整。式中表示信息素?fù)]發(fā)因子，則表示信息素殘留因子。為了更加貼近自然界中的螞蟻群體，并防止信息素的過(guò)度累積，通常的取值圍為:；在完成一次迭代后用表示路徑(i，j)上的信息素增量，初始時(shí)刻，則表示螞蟻k在本次搜索過(guò)程中于路徑(i，j)上留下的信息素量。在蟻群算法中，信息素的更新策略直接關(guān)系著算法的效率和成功與否，而信息素更新的策略也會(huì)根據(jù)待解決的問(wèn)題特點(diǎn)來(lái)選擇。DorigoM曾經(jīng)提出了三種不同的根本蟻群算法模型。這三種模型分別是:Ant-Cycle模型、Ant-Quantity模型和Ant一Density模型。其中三種模型的差異在于信息素增量的求法的不同。在Ant-Cycle模型中式中，Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度;表示k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度。在Ant-Quanity模型中在Ant-Density模型中其中Ant-Quanity模型和Ant-Density模型采用的是局部信息素更新策略，也就是說(shuō)螞蟻在每走完一步到達(dá)下一城市就對(duì)剛剛走過(guò)的路徑信息素進(jìn)展更新；而Ant-Cycle模型中則是采用全局的信息素更新策略，當(dāng)一只螞蟻訪(fǎng)問(wèn)過(guò)所有城市以后才會(huì)對(duì)所走過(guò)的路徑進(jìn)展信息素更新。6.1.2模型求解用蟻群算法對(duì)問(wèn)題一進(jìn)展分析，得到最優(yōu)結(jié)果為：選擇出、、、、、、、這八個(gè)城市為供給點(diǎn)，總費(fèi)用為9304885元。每個(gè)供給點(diǎn)供給的城市及每一個(gè)供給點(diǎn)到需求點(diǎn)的連接圖如下：圖3：供給點(diǎn)供給圍圖每個(gè)供給點(diǎn)供給的城市及費(fèi)用情況如下表：表1：供給點(diǎn)供給城市及費(fèi)用情況表1無(wú)310082—，，—海拉爾，11401063烏市，，，—8714524呼市—，—，—**，—，14004005，，825780612382987，，，—，——澳門(mén)，—臺(tái)北16906378，，—，—臺(tái)北，，—，—，—2107604總費(fèi)用共計(jì)：9304885其中費(fèi)用的計(jì)算過(guò)程如下：Total[2]=cos(7)+w(40)*d(23)+w(41)*d(24)+w(8)*d(22)+w(6)*d(19)+w(39)*(d(20)+d(19))+w(42)*(d(100)+d(24))=1140106Total[3]=cos(28)+w(31)*d(93)+w(29)*d(91)+w(30)*d(92)+w(27)*d(87)+w(46)*(d(90)+d(87))=871452Total[4]=cos(4)+w(16)*d(13)+w(5)*d(12)+w(47)*(d(18)+d(12))+w(3)*d(9)+w(1)*(d(2)+d(9))+w(2)*(d(7)+d(9))+w(15)*(d(10)+d(9))=1400400Total[5]=cos(45)+w(44)*d(101)+w(17)*d(59)+w(18)*d(62)=825780Total[6]=cos(23)+w(22)*d(74)=1238298Total[7]=cos(20)+w(25)*d(71)+w(24)*d(70)+w(48)*d(72)+w(21)*d(69)+w(19)*d(64)+w(49)*(d(69)+d(73))+w(34)*(d(66)+d(64))+w(35)*(d(67)+d(64))+w(33)*(d(67)+d(64)+d(95))=1690637Total[8]=cos(11)+w(10)*d(29)+w(9)*d(27)+w(37)*d(37)+w(13)*d(35)+w(14)*d(36)+w(12)*(d(30)+d(29))+w(43)*(d(34)+d(29))+w(38)*(d(33)+d(29))+w(36)*(d(45)+d(35))+w(32)*(d(44)+d(35))=21076046.2問(wèn)題二假定有*組織對(duì)該供給網(wǎng)絡(luò)的道路進(jìn)展破壞。并非所有的道路都可以被破壞。當(dāng)*條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過(guò)該道路的只有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是使對(duì)方總費(fèi)用增加25%，而每破壞一條道路都需要本錢(qián)和代價(jià)，因此需要破壞最少的道路。對(duì)于此問(wèn)題，我們采用迪杰斯特拉算法進(jìn)展求解。6.2.1迪杰斯特拉算法迪杰斯特拉算法是典型最短路徑算法，用于計(jì)算圖或網(wǎng)中*個(gè)特定頂點(diǎn)到其他所有頂點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外，層層擴(kuò)展，直到擴(kuò)展覆蓋所有頂點(diǎn)。迪杰斯特拉算法思想設(shè)G=(V,E)為一個(gè)帶全有向圖，把圖中頂點(diǎn)集合V分成兩組。第一組為已求出最短路徑的頂點(diǎn)集合〔用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑，就將所到達(dá)最短路徑的頂點(diǎn)參加到集合S中，直到全部頂點(diǎn)都參加到S中〕。第二組為其余未確定最短路徑的頂點(diǎn)集合〔用U表示，U=V-S，U中的頂點(diǎn)不斷的參加到S中，直到U為空，S=V〕。在U參加S的過(guò)程中，始終保持源點(diǎn)到S中各頂點(diǎn)的最短路徑長(zhǎng)度小于或等于源點(diǎn)到U中任意頂點(diǎn)的最短路徑長(zhǎng)度。迪杰斯特拉算法執(zhí)行步驟設(shè)n為圖G=(V,E)中的頂點(diǎn)數(shù)，dist[n]存放從源點(diǎn)到每個(gè)終點(diǎn)當(dāng)前最短路徑的長(zhǎng)度，path[n]存放相應(yīng)路徑，S為已求得最短路徑的終點(diǎn)的集合，U為V-S，初始為不含有源點(diǎn)的所有頂點(diǎn)?！?〕初始化已求的最短路徑的集合S為只含有元素源點(diǎn)a，S=｛a｝?！?〕從U中選取一個(gè)距離源點(diǎn)v最小的頂點(diǎn)k，把k參加S中〔該選定的距離就是v到k的最短路徑長(zhǎng)度〕?！?〕以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；假設(shè)從源點(diǎn)v到頂點(diǎn)u〔uU〕的距離〔經(jīng)過(guò)頂點(diǎn)k〕比原來(lái)距離〔不經(jīng)過(guò)頂點(diǎn)k〕短，則修改頂點(diǎn)u的距離值，修改后的距離值為頂點(diǎn)k的距離加上頂點(diǎn)k到u邊上的權(quán)。〔4〕重復(fù)步驟〔2〕和〔3〕直到所有頂點(diǎn)都包含在S中。6.2.2模型求解假定有*組織對(duì)該供給網(wǎng)絡(luò)的道路進(jìn)展破壞。并非所有的道路都可以被破壞，可破壞的道路見(jiàn)下表。表2：破壞道路表1452343740410115192062425717458214992021根據(jù)第一題得到的供給圍的分布圖并結(jié)合上表，我們運(yùn)用迪杰斯特拉算法對(duì)破壞后道路進(jìn)展分析，求得了改道后的最短路運(yùn)輸路徑和破壞道路后所多消耗的費(fèi)用。表3：破壞道路后路線(xiàn)更改及多消消耗用表14-55-45-1-3-410780047-5-447-5-1-3-423-43-43-16-410811201-3-41-5-42-3-42-1-5-415-3-415-16-433-4和4-55-45-30-28130039047-5-447-5-30-283-43-16-41-3-41-3-16-42-3-42-3-16-415-3-415-16-447-4040-740-41-738357510-1110-1110-9-1123951412-10-1112-10-9-1113-10-1113-10-9-1138-10-1138-10-9-11619-2019-2019-21-2038162534-19-2034-19-21-2035-19-2035-19-21-2033-35-19-2033-35-19-21-20724-25無(wú)影響無(wú)影響不產(chǎn)生817-4517-4517-44-45212670921-49無(wú)影響無(wú)影響不產(chǎn)生1020-2120-2121-19-207701549-21-2049-21-19-201119-20和20-2119-2019-18-4565096934-19-2034-19-18-4535-19-2035-19-18-4533-35-19-2033-35-19-18-4521-2021-19-18-4549-21-2049-21-19-18-45其中，破壞道路后多消耗的費(fèi)用計(jì)算過(guò)程如下：ans[1]=w(5)*(d(3)+d(2)+d(9)-d(12))+w(47)*(d(3)+d(2)+d(9)-d(12))=107800ans[2]=w(3)*(d(11)+d(13)-d(9))+w(1)*(-d(2)-d(9)+d(3)+d(12))+w(2)*(d(1)+d(3)+d(12)-d(7)-d(9))+w(15)*(d(50)+d(13)-d(9)-d(10))=1081120ans[3]=w(5)*(d(16)+d(92)-d(12))+w(47)*(d(16)+d(92)-d(12))+w(3)*(d(11)+d(13)-d(9))+w(1)*(d(11)+d(13)-d(9))+w(2)*(d(11)+d(13)-d(9))+w(15)*(d(50)+d(13)-d(9)-d(10))=1300390ans[4]=w(40)*(d(24)+d(98)-d(23))=38357ans[5]=w(10)*(d(26)+d(27)-d(29))+w(12)*(d(27)+d(26)-d(29))+w(13)*(d(27)+d(26)-d(29))+w(38)*(d(27)+d(26)-d(29))=239514ans[6]=w(19)*(d(65)+d(69)-d(64))+w(34)*(d(65)+d(69)-d(64))+w(35)*(d(65)+d(69)-d(64))+w(33)*(d(65)+d(69)-d(64))=381625ans[8]=w(17)*(d(58)+d(101)-d(59))=212670ans[10]=w(21)*(d(65)+d(64)-d(69))+w(49)*(d(64)+d(65)-d(69))=77015ans[11]=w(19)*(d(60)+d(62)-d(64))+w(34)*(d(60)+d(62)-d(64))+w(35)*(d(60)+d(62)-d(64))+w(33)*(d(60)+d(62)-d(64))+w(21)*(d60)+d(62)+d(65)-d(69))+w(49)*(d(60)+d(62)+d(65)-d(69))=650969第一問(wèn)得到的總費(fèi)用為9304885元，如果破壞方選取的策略是使對(duì)方總費(fèi)用增加25%，而每破壞一條道路都需要本錢(qián)和代價(jià)，因此需要破壞最少的道路。根據(jù)上表我們發(fā)現(xiàn)，破壞3-4和4-5，10-11，17-45，19-20和20-21這六條道路，得到的總費(fèi)用情況最接近使對(duì)方總費(fèi)用增加25%這一策略。破壞后六條道路后的供給分布圖如下：圖4：破壞道路后的供給分布圖破壞3-4和4-5，10-11，17-45，19-20和20-21這六條道路多消耗的費(fèi)用為2403543元(接近9304885*25%=2326221.25元)。6.3問(wèn)題三6.3.1獨(dú)立事件模型建立道路破壞是獨(dú)立事件，相互之間不影響。根據(jù)問(wèn)題一中的供給分布圖可以看到破壞6,8對(duì)費(fèi)用無(wú)影響，固破壞道路序號(hào)為1、2、3、4、5、7、9，此時(shí)，增加的最大平均費(fèi)用為：其中：r[i]為破壞道路序號(hào)；i增加的費(fèi)用；p[i]為破壞道路i的概率；ma*_crease為破壞道路增加費(fèi)用的最大平均值。6.3.2模型求解r=[107800,1081120,38357,239514,381625,0,212670,0,77015]p=[0.6,0.7,0.45,0.5,0.55,0.4,0.5,0.6,0.6]ma*_crease=r(3)*p(3)+r(4)*p(4)+r(7)*p(7)+r(1)*p(1)*(1-p(2))+r(2)*p(2)*(1-p(1))+1300390*p(1)*p(2)+r(5)*p(5)*(1-p(9))+r(9)*p(9)*(1-p(5))+650969*p(5)*p(9)得到：ma*_crease=1431200根據(jù)以上分析可以得到：破壞道路的序號(hào)為1、2、3、4、5、7、9，平均總費(fèi)用為1431200元七、模型的優(yōu)缺點(diǎn)7.1動(dòng)態(tài)規(guī)劃7.1.1優(yōu)點(diǎn)〔1〕可以解決線(xiàn)性,非線(xiàn)性,整數(shù)規(guī)劃無(wú)法有效求解的復(fù)雜問(wèn)題；〔2〕容易找到全局最優(yōu)解；〔3〕可以得到一組解。7.1.2缺點(diǎn)〔1〕沒(méi)有標(biāo)準(zhǔn)的模型可供給用,構(gòu)模依賴(lài)于個(gè)人的經(jīng)歷和技巧；〔2〕狀態(tài)變量需滿(mǎn)足無(wú)后效性,有較大的局限性；〔3〕動(dòng)態(tài)規(guī)劃的維數(shù)災(zāi)難限制了對(duì)規(guī)模較大問(wèn)題的求解效率。7.2蟻群算法7.2.1優(yōu)點(diǎn)〔1〕不依賴(lài)于所求問(wèn)題的具體數(shù)學(xué)表達(dá)式描述，具有很強(qiáng)的找到全局最優(yōu)解的優(yōu)化能力；〔2〕該算法具有正反應(yīng)、較強(qiáng)的魯棒性、全局性、普遍性、優(yōu)良的分布式并行計(jì)算機(jī)制、易于與其他方法相結(jié)合等諸多優(yōu)點(diǎn)。7.2.2缺點(diǎn)〔1〕蟻群算法的成功主要在實(shí)驗(yàn)層次上，很少有理論來(lái)解釋利用蟻群算法為什么能夠成功地解決這些問(wèn)題，它沒(méi)有堅(jiān)實(shí)的數(shù)學(xué)根底；〔2〕蟻群算法的模型普適性不強(qiáng)，其模型不能直接應(yīng)用于實(shí)際優(yōu)化問(wèn)題；〔3〕蟻群算法的局部搜索能力較弱，易于出現(xiàn)停滯和局部收斂、收斂速度慢等問(wèn)題，因而往往需要嵌入一些專(zhuān)門(mén)的輔助技巧；〔4〕長(zhǎng)時(shí)間花費(fèi)在解的構(gòu)造上，從而導(dǎo)致搜索時(shí)間過(guò)長(zhǎng)；〔5〕算法最先基于離散問(wèn)題，不能直接解決連續(xù)優(yōu)化問(wèn)題。八、參考文獻(xiàn)［1］CHRISTOPHERM．通過(guò)降低本錢(qián)和增加效勞的物流及供給鏈管理策略(第二版)［M］．:電子工業(yè)，2003．［2］啟蘭，王稼瓊，宏志．物流規(guī)劃中的需求與潛在需求分析［J］．中國(guó)軟科學(xué)，2004(2):92—95．［3］肖月，倪梅，伊松．物流需求分析指標(biāo)研究［J］．鐵道物資科學(xué)管理，2003(2):33—34．［4］波，林巖．從供給鏈到需求流動(dòng)網(wǎng)［J］．工業(yè)工程，2007，10(2):1—6．［5］劍，蔡連僑．供給鏈建模與優(yōu)化［J］．系統(tǒng)工程理論與實(shí)踐，2001(6):26—33．［6］任鳴鳴．供給鏈系統(tǒng)節(jié)點(diǎn)設(shè)施選址研究［D］．:華中科技大學(xué)，2008．[7]嘉.一類(lèi)特殊車(chē)輛路徑問(wèn)題[J].東北大學(xué)學(xué)報(bào)〔自然科學(xué)版〕，2001,22〔3〕[8]濤，明杰，王夢(mèng)光.不確定車(chē)輛數(shù)的車(chē)輛路徑問(wèn)題模型和混合算法[J].系統(tǒng)工程理論方法應(yīng)用，2003〔2〕[9]王正彬，杜文.考慮線(xiàn)路安排的物流配送方案模型及其算法研究[J].技術(shù)交流，2003〔12〕[10]曉峰，杜艷萍.車(chē)輛路徑問(wèn)題的蟻群算法研究[J].科技大學(xué)學(xué)報(bào)，2005,26〔4〕九、附錄%畫(huà)49個(gè)城市散點(diǎn)圖的代碼*=[3639,3712,3488,3326,3238,4196,4312,4386,4177,3918,4061,3780,4029,3676,3715,3429,3507,3394,3439,2935,3140,2769,2545,2778,2370,1304,3007,2562,2381,2788,1332,4263,3538,3470,3526,3928,4201,4016,4089,4296,4095,4512,3751,3334,3229,3054,3089,3044,3053]y=[2685,2601,2465,2444,2771,2956,3210,3430,1756,1821,1630,1788,1162,1422,2322,2092,1624,1357,799,760,450,1508,1643,1174,1025,1688,2030,2244,2324,2509,3305,1069,702,696,737,971,1603,2285,2613,2920,3374,2710,2055,1893,1633,2290,2749,919,261]a=[1,3,4,5,7,10,11,12,13,14,15,16,17,18,19,20,22,23,24,25,26,27,28,30,40,43,44,45]fori=1:49ifismember(i,a)==1plot(*(i),y(i),'.red','MarkerSize',10);elseplot(*(i),y(i),'.black','MarkerSize',10);endholdonte*t(*(i),y(i),num2str(i));end%求鄰接矩陣的代碼s=[11111122333444455566677789991010101010101111111212121213131313131414141515151616161617171718181818191919191920202020212222222222232323242425262627272727282828303335384040414446]d=[235615403154151651627303040477394084041421011151112141538431314371416174314193236371718191638431727434418444519244548202134353621242548492324252745