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

1、目錄一、問(wèn)題重述 2二、問(wèn)題提出 2三、問(wèn)題分析 3四、模型假設(shè) 3五、主要符號(hào)說(shuō)明 4六、模型的建立與求解 56.1 問(wèn)題一 56.1.1 蟻群算法的基本理論 66.1.2 模型求解 96.2 問(wèn)題二 116.2.1 迪杰斯特拉算法 116.2.2 模型求解 126.3 問(wèn)題三 146.3.1 獨(dú)立事件模型建立 146.3.2 模型求解 15七、模型的優(yōu)缺點(diǎn) 157.1 動(dòng)態(tài)規(guī)劃 157.1.1 優(yōu)點(diǎn) 157.1.2 缺點(diǎn) 157.2 蟻群算法 167.2.1 優(yōu)點(diǎn) 167.2.2 缺點(diǎn) 16八、參考文獻(xiàn) 17九、附錄 18一、問(wèn)題重述全球化競(jìng)爭(zhēng)的加劇促使越來(lái)越多的企業(yè)開(kāi)始采用供應(yīng)鏈管理策略

2、， 以實(shí)現(xiàn)企 業(yè)的一體化管理。供應(yīng)鏈?zhǔn)且粋€(gè)復(fù)雜的網(wǎng)狀結(jié)構(gòu)系統(tǒng)，每一部分都面臨著各種潛 在的風(fēng)險(xiǎn)，任何一部分出現(xiàn)問(wèn)題都可能給整個(gè)供應(yīng)鏈帶來(lái)嚴(yán)重的影響， 因此如何 分析、評(píng)價(jià)和提高供應(yīng)鏈系統(tǒng)的可靠性變得日益迫切。設(shè)施系統(tǒng)是供應(yīng)鏈的核心，在供應(yīng)鏈研究中有著極其重要的地位。在一個(gè)設(shè) 施系統(tǒng)中，某些個(gè)設(shè)施由于自然災(zāi)害或者其他因素的影響可能失效，例如 911 恐怖襲擊事件、2004年的印度洋海嘯、2008年的汶川地震等都對(duì)諸多行業(yè)的設(shè) 施系統(tǒng)造成了嚴(yán)重的破壞。現(xiàn)有某物流公司要在全國(guó)各城市之間建立供應(yīng)鏈網(wǎng)絡(luò)。 需要選定部分城市作 為供應(yīng)點(diǎn)，將貨物運(yùn)輸?shù)礁鞒鞘?。通常每個(gè)供應(yīng)點(diǎn)的貨物是充足的， 可以充分滿 足相

3、應(yīng)城市的需求。假設(shè)該公司共考慮49個(gè)城市的網(wǎng)絡(luò)并假定作為供應(yīng)點(diǎn)的城市其供應(yīng)量可以 滿足有需要的城市的需求?，F(xiàn)將要建立一個(gè)供應(yīng)網(wǎng)絡(luò)，為各城市提供貨物供應(yīng)。 貨物運(yùn)輸利用汽車進(jìn)行公路運(yùn)輸。二、問(wèn)題提出(1)現(xiàn)在要從49個(gè)城市中選取部分城市做為供給點(diǎn)供應(yīng)本城市及其它城 市。建立供給點(diǎn)會(huì)花費(fèi)固定費(fèi)用，從供應(yīng)點(diǎn)運(yùn)輸?shù)叫枨簏c(diǎn)會(huì)產(chǎn)生運(yùn)輸費(fèi)用， 要使 總費(fèi)用最小，問(wèn)建立多少個(gè)供應(yīng)點(diǎn)最好。給出選中作為供應(yīng)點(diǎn)的城市，并給出每 個(gè)供應(yīng)點(diǎn)供應(yīng)的城市。同時(shí)根據(jù)坐標(biāo)作出每一個(gè)供應(yīng)點(diǎn)到需求點(diǎn)的連接圖。(2)假定有某組織對(duì)該供應(yīng)網(wǎng)絡(luò)的道路進(jìn)行破壞。并非所有的道路都可以 被破壞。當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前

4、運(yùn)輸經(jīng)過(guò)該道路 的只有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是使對(duì)方總費(fèi)用增加 25%而每破壞一條道路都需要成本和代價(jià)，因此需要破壞最少的道路。問(wèn)破壞 方選取哪幾條線路進(jìn)行破壞。給出具體的破壞道路和總費(fèi)用。(3)假定各道路能否被破壞具有隨機(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)

5、度問(wèn)題進(jìn)行分析，根據(jù)動(dòng)態(tài)規(guī)劃算法進(jìn)行處理， 利用lingo對(duì)其數(shù)學(xué)模型進(jìn)行求解，但該方式給出的算法所搜索的空間容量很 大，利用目前的計(jì)算機(jī)求此問(wèn)題的精確解已很難實(shí)現(xiàn)，并且需要相當(dāng)長(zhǎng)的時(shí)間才有可能得到精確解，且其規(guī)模較小實(shí)際應(yīng)用的意義不大。為此，我們結(jié)合蟻群算 法在求解運(yùn)輸調(diào)度問(wèn)題上的優(yōu)勢(shì)，在此基礎(chǔ)上，將蟻群算法結(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)題二的基礎(chǔ)上的 優(yōu)化，由

6、于破壞方選取一些邊進(jìn)行破 壞時(shí)，這些邊不一定被破壞，而是服從一定的概率分布。在考慮此問(wèn)題時(shí)，要涉 及到各邊所破壞的概率，再根據(jù)破壞方選取的策略得到具體的破壞道路和平均總 費(fèi)用。四、模型假設(shè)(1)假設(shè)每個(gè)供應(yīng)點(diǎn)的貨物是充足的，可以充分滿足相應(yīng)城市的需求；(2)假設(shè)每輛車所服務(wù)的客戶總的需求量不得大于車輛的最大載質(zhì)量；(3)假設(shè)一個(gè)城市由只能有一個(gè)供應(yīng)點(diǎn)供應(yīng)；(4)忽略供應(yīng)鏈網(wǎng)絡(luò)中運(yùn)輸貨物的不同對(duì)供應(yīng)點(diǎn)設(shè)立的影響；(5)忽略貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限 制及時(shí)間限制的影響；(6)假設(shè)兩城市之間除了公路運(yùn)輸沒(méi)有其他運(yùn)輸方式；(7)假設(shè)運(yùn)輸單價(jià)不受天氣和油價(jià)等因素影響；(8

7、)假設(shè)各城市的需求量在一段時(shí)間內(nèi)固定不變五、主要符號(hào)說(shuō)明數(shù)學(xué)符號(hào)符號(hào)說(shuō)明b (t)元素i在t時(shí)刻存在的螞蟻數(shù)量% (t)路徑(i , j)上t時(shí)刻的信息素濃度數(shù)值n城市數(shù)目m蟻群算法的規(guī)模即蟻群中的螞蟻總數(shù)L =% (t )c，i G 仁 C t時(shí)刻所有城市間路徑上的信息素殘留量的集合allowed k螞蟻k下一步允許選擇的城市a信息素強(qiáng)度影響因子nij(t)啟發(fā)函數(shù)distn存放從源點(diǎn)到每個(gè)終點(diǎn)當(dāng)前最短路徑的長(zhǎng)度pathn存放相應(yīng)路徑S已求得最短路徑的終點(diǎn)的集合cos(i)表示以第i個(gè)城市建立供應(yīng)點(diǎn)所需的固定費(fèi)用w(i)表示第i個(gè)城市所需的貨物重量d(i)路線序號(hào)i的距離乘以每公里費(fèi)用0.5

8、元之后的值Totali以i為供應(yīng)中心和周圍城市構(gòu)成網(wǎng)絡(luò)所需的總費(fèi)用ansi表示破壞道路要多序號(hào)i后要多花費(fèi)的費(fèi)用六、模型的建立與求解供應(yīng)鏈網(wǎng)絡(luò)中一個(gè)重要的網(wǎng)絡(luò)節(jié)點(diǎn)是供應(yīng)點(diǎn)設(shè)立。 一般來(lái)講，如果用戶較為 固定，按照配送費(fèi)用最小或者到各個(gè)消費(fèi)地的距離之和最小的原則，即供應(yīng)點(diǎn)處于使物流網(wǎng)路運(yùn)營(yíng)費(fèi)用最小的位置或者供應(yīng)點(diǎn)所處位置與各城市位置的通行距 離之和應(yīng)為各待選位置中的最低者。此時(shí)，供應(yīng)鏈網(wǎng)絡(luò)應(yīng)設(shè)為輻射型網(wǎng)絡(luò)布局。輻射型網(wǎng)絡(luò)布局如下圖所示，供應(yīng)點(diǎn)位于需求點(diǎn)的幾何中心位置，構(gòu)成需求 地環(huán)繞供應(yīng)點(diǎn)的布局格式。物料從此供應(yīng)點(diǎn)向周圍各方向消費(fèi)者配送， 形成輻射 型。圖1:輻射型格局設(shè)立輻射型的格局應(yīng)滿足兩個(gè)

9、方面的條件。 一是需求地在供應(yīng)點(diǎn)周圍幾乎是 均勻分布，并且供應(yīng)點(diǎn)周圍是用戶相對(duì)集中的經(jīng)濟(jì)區(qū)域； 二是供應(yīng)點(diǎ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)題的精確解已很難實(shí)現(xiàn)，并且需要相當(dāng)長(zhǎng)的時(shí)間才有可能得到精確解，且其規(guī)模較小實(shí)際應(yīng)用的意義不大。 在實(shí)際應(yīng)用中的時(shí)候不 是非要得到一個(gè)精確的解，在大多數(shù)時(shí)候近

10、似的解就已經(jīng)滿足了實(shí)際的需求，為 此我們結(jié)合蟻群算法在求解運(yùn)輸調(diào)度問(wèn)題上的優(yōu)勢(shì)，在此基礎(chǔ)上，將蟻群算法結(jié) 合運(yùn)輸調(diào)度模型進(jìn)行仿真實(shí)現(xiàn)。6.1.1 蟻群算法的基本理論螞蟻覓食時(shí)，會(huì)在所經(jīng)過(guò)路線上留下一種稱為信息素的物質(zhì)，以此來(lái)標(biāo)識(shí)路線，其它螞蟻可以并且習(xí)慣追蹤此信息素爬行。在確定位置的食物和蟻穴之間， 較近的路線，螞蟻重復(fù)爬行的次數(shù)就更高些，由于每只螞蟻每經(jīng)過(guò)一次都要釋放 信息素，這樣重復(fù)次數(shù)多的路線由于其信息素濃度較大就更容易被其它螞蟻選 中，這樣整個(gè)蟻群就由開(kāi)始的多路線爬行逐漸集中到最短的路線上爬行，使路線得到優(yōu)化選擇。蟻群算法是一種模擬自然界螞蟻覓食行為的啟發(fā)式搜索算法，由意大利學(xué)者M(jìn).

11、Dorigo模擬此過(guò)程提出。其主要特點(diǎn)正反饋、并行式搜索。它尤其適用于處 理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問(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è)：b(t)為元素i在t時(shí)刻存在的螞蟻數(shù)量；Gj (t)為路徑(i , j)上t時(shí)刻的信息素濃度數(shù)值；n表示城市數(shù)目；nm表示蟻群算法的規(guī)模即蟻群中的螞蟻總數(shù)，m=£ bi(t);i=1L =% (t g g u C是t時(shí)刻所有城市間路徑上的信息素殘留量的集合。蟻群算法的初始時(shí)刻各個(gè)路徑上的信息素通常設(shè)定為

12、一個(gè)常數(shù),(t尸c。螞蟻k(k=1,2,mE路徑的搜索過(guò)程中，根據(jù)不同路徑上的信息素濃度來(lái)決定 其下一步的搜索路徑。Pjk(t )表示在t時(shí)刻螞蟻k由元素(城市)i轉(zhuǎn)移到元素(城 市)j的選擇概率。M(t)f “jt/KB,右j 仁 allowed k*t曰 E Fij(t)fpij(t) sfallowed k9否則式中，allowed k表示螞蟻k下一步允許選擇的城市，a為信息素強(qiáng)度影響因 子，表示螞蟻對(duì)于信息素濃度的敏感程度也表明此路徑的相對(duì)重要性。具值越大，此時(shí)螞蟻在選擇下一搜索路徑時(shí)，容易受到信息素濃度的影響，螞蟻更趨向于信 息素濃度較高的路徑，也就是有更多螞蟻?zhàn)哌^(guò)的路徑同時(shí)也是增強(qiáng)

13、了螞蟻間的交 流信息使彼此間的協(xié)調(diào)機(jī)制更明顯。P為能見(jiàn)度因子又稱期望因子，表示螞蟻本 身的能見(jiàn)度對(duì)在路徑選擇中的重要性。其值越大則螞蟻選擇路徑時(shí)越是依賴于能 見(jiàn)度信息。當(dāng)取值很高時(shí)螞蟻則是以一種幾乎貪婪的規(guī)則選擇下一步的搜索路 徑，而忽略信息素影響。(t)為啟發(fā)函數(shù)，其表達(dá)式如下：1d ij式中，dj表示兩個(gè)相鄰元素間的距離。dj的數(shù)值越小，說(shuō)明兩城市相距越 近同時(shí)（t）越大，Ka）也就越大，螞蟻下一步選擇這一個(gè)城市的概率也就越 高，這也就說(shuō)該函數(shù)表征了螞蟻從一個(gè)城市到另一個(gè)城市的期望度數(shù)值。隨著螞蟻的不斷搜索，很多路徑上都會(huì)留下信息素，為了防止各個(gè)路徑上的 大量殘留信息素不斷積累從而導(dǎo)致螞蟻

14、忽略能見(jiàn)度信息，當(dāng)每只螞蟻每完成一步 搜索或者螞蟻完成對(duì)n個(gè)城市的搜索（也就是算法完成一次迭代）后，需要對(duì)每條 路徑上殘留的信息素量進(jìn)行更新。 這樣在t+n時(shí)刻路徑（i , J）上的信息素濃度可 以按照下面的公式調(diào)整。j t+n = 1 - - * j t - j t式中P表示信息素?fù)]發(fā)因子，1-P則表示信息素殘留因子。為了更加貼近自然界中的螞蟻群體，并防止信息素的過(guò)度累積，P通常的取值范圍 為：PC 10,1）;在完成一次迭代后用%«）表示路徑。，j）上的信息素增量，初 始時(shí)刻 jt）=0, 寸（t）則表示螞蟻k在本次搜索過(guò)程中于路徑（i , j）上留下 的信息素量。在蟻群算法中，

15、信息素的更新策略直接關(guān)系著算法的效率和成功與 否，而信息素更新的策略也會(huì)根據(jù)待解決的問(wèn)題特點(diǎn)來(lái)選擇。DorigoM曾經(jīng)提出了三種不同的基本蟻群算法模型。這三種模型分別 是:Ant-Cycle 模型、Ant-Quantity 模型和Ant - Density模型。其中三種模型 的差別在于信息素增量丁 （t）的求法的不同。在Ant-Cycle模型中.LQ,若k在本次循環(huán)中經(jīng)過(guò)（i,j）小t尸Lka否則式中，Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度；Lk表示k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度在Ant-Quanity模型中&,若k只螞蟻在t和t+1之間經(jīng)過(guò)（i,j ）"：

16、。=20,否則在Ant-Density 模型中kQ,若k只螞蟻在t和t+1之間經(jīng)過(guò)（i, j ）"j t j ' &,否則其中Ant-Quanity模型和Ant-Density模型采用的是局部信息素更新策略， 也就是說(shuō)螞蟻在每走完一步到達(dá)下一城市就對(duì)剛剛走過(guò)的路徑信息素進(jìn)行更新； 而Ant-Cycle模型中則是采用全局的信息素更新策略，當(dāng)一只螞蟻訪問(wèn)過(guò)所有城 市以后才會(huì)對(duì)所走過(guò)的路徑進(jìn)行信息素更新。6.1.2模型求解用蟻群算法對(duì)問(wèn)題一進(jìn)行分析，得到最優(yōu)結(jié)果為：選擇出拉薩、長(zhǎng)春、蘭州、 太原、宜昌、成都、南寧、杭州這八個(gè)城市為供應(yīng)點(diǎn)，總費(fèi)用為9304885元。每個(gè)供應(yīng)點(diǎn)

17、供應(yīng)的城市及每一個(gè)供應(yīng)點(diǎn)到需求點(diǎn)的連接圖如下：圖3:供應(yīng)點(diǎn)供應(yīng)范圍圖崢八K市的點(diǎn)困現(xiàn)J如_ _ _ _ 拉 皿 敝 m(刮中sr脂科_一_每個(gè)供應(yīng)點(diǎn)供應(yīng)的城市及費(fèi)用情況如下表:表1:供應(yīng)點(diǎn)供應(yīng)城市及費(fèi)用情況表編號(hào)供應(yīng)點(diǎn) 供應(yīng)范圍費(fèi)用（元）1拉薩無(wú)310082K春沈陽(yáng)一大連，通遼，白城一海拉爾，哈爾濱11401063蘭州烏市，西寧，銀川，西安 延安871452 14太原呼市一包頭，石家莊一北京，石家莊天津，石 家莊一濟(jì)南，鄭州14004005:宜昌武漢，長(zhǎng)沙，南陽(yáng)825780 16成都重慶12382987貴陽(yáng)，昆明，柳州，?？谝欢I(yè)，廣州一深圳一 澳門，廣州一臺(tái)北16906378杭州上海，寧波，

18、福州一廈門，福州一臺(tái)北，南昌， 南京一青島，南京一徐州，南京一合肥2107604總費(fèi)用共計(jì)：9304885其中費(fèi)用的計(jì)算過(guò)程如下:Total2 =cos+w(40)*d(23)+w(41)*d(24)+w(8)*d(22)+w(6)*d(19)+w(3 9)*(d(20)+d(19)+w(42)*(d(100)+d(24)= 1140106Total3 =cos(28)+w(31)*d(93)+w(29)*d(91)+w(30)*d(92)+w(27)*d(87)+ w(46)*(d(90)+d(87)= 871452Total4 =cos(4)+w(16)*d(13)+w(5)*d(12)+

19、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) =1400400Total5 =cos(45)+w(44)*d(101)+w(17)*d(59)+w(18)*d(62)=825780Total6 =cos(23)+w(22)*d(74)= 1238298Total7 =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)

20、+w(3 5)*(d(67)+d(64)+ w(33)*(d(67)+d(64) +d(95)= 1690637Total8 =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)= 2107604Word格式6.2.2模型求解假定有某組織對(duì)該供應(yīng)網(wǎng)絡(luò)的道路進(jìn)行破壞。并非所有的道路都可以被破 壞。當(dāng)某條道路被破壞后，該條道路

21、就不能再被使用，以前運(yùn)輸經(jīng)過(guò)該道路的只 有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是使對(duì)方總費(fèi)用增加 25% 而每破壞一條道路都需要成本和代價(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)加

22、入到集合 S中，直到全部頂點(diǎn)都加入到 S中)。第二組為其余未確定最短路徑的頂點(diǎn)集合(用 U表示，U=V-G 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ù)，distn存放從源點(diǎn)到每個(gè)終點(diǎn)當(dāng)前最短路徑的長(zhǎng)度，pathn存放相應(yīng)路徑，S為已求得最短路徑的終點(diǎn)的集合，U為V-S,初始為不含有源點(diǎn)的所有頂點(diǎn)。(1)初始化已求的最短路徑的集合 S為只含有元素源點(diǎn)a, S= a。(2)從U中選取一個(gè)距離源點(diǎn)v最小的頂點(diǎn)k,把k加入S中(該選定的

23、距離就是v到k的最短路徑長(zhǎng)度)。(3)以k為新考慮的中間點(diǎn)，修改 U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn) u (u U)的距離(經(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中。假定有某組織對(duì)該供應(yīng)網(wǎng)絡(luò)的道路進(jìn)行破壞。并非所有的道路都可以被破 壞，可破壞的道路見(jiàn)下表。表2 :破壞道路表道路序號(hào)城巾1城巾21452343740410115192062425717458214992021根據(jù)第一題得到的供應(yīng)范圍的分布圖并結(jié)合上表， 我們運(yùn)用迪杰斯特拉算法 對(duì)破壞后道路進(jìn)行分析

24、，求得了改道后的最短路運(yùn)輸路徑和破壞道路后所多消耗 的費(fèi)用。表3:破壞道路后路線更改及多消耗費(fèi)用表序號(hào)破壞的道路原路線更改后路線多消耗的費(fèi)用（元）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-11239514

25、12-10-1112-10-9-1113-10-1113-10-9-11Word格式38-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-

26、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ò)程如下:ans1 =w(5)*(d(3)+d(2)+d(9)-d(12)+w(47)*(d(3)+d(2)+d(9)-d(12)=107800ans2 =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-d(9)+w(15)*(d(50)+d(13)-d(9)-d(10)=1081120ans3

27、=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)=1300390ans4 =w(40)*(d(24)+d(98)-d(23)= 38357ans5 =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)=

28、239514ans6 =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)=381625ans8 =w(17)*(d(58)+d(101)-d(59)= 212670ans10 =w(21)*(d(65)+d(64)-d(69)+w(49)*(d(64)+d(65)-d(69)=77015ans11 =w(19)*(d(60)+d(62)-d(64)+w(34)*(d(60)+d(62)-d(64)+w(35)*(d(60)+d(62)-d(64

29、)+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%而每破壞一條道路都需要成本和代價(jià)，因此需要破壞最少的道路。根 據(jù)上表我們發(fā)現(xiàn)，破壞3-4和4-5, 10-11 , 17-45, 19-20和20-21這六條道路, 得到的總費(fèi)用情況最接近使對(duì)方總費(fèi)用增加25流一策略。破壞后六條道路后的供應(yīng)分布圖如下:圖4:破壞道路后的供應(yīng)分布圖破壞3-4和4-5 , 10-11 , 17-4

30、5, 19-20和20-21這六條道路多消耗的費(fèi)用 為 2403543 元(接近 9304885*25%=2326221.25元)。6.3問(wèn)題三6.3.1 獨(dú)立事件模型建立道路破壞是獨(dú)立事件，相互之間不影響。根據(jù)問(wèn)題一中的供應(yīng)分布圖可以看 到破壞6,8對(duì)費(fèi)用無(wú)影響，固破壞道路序號(hào)為 1、2、3、4、5、7、9,此時(shí)，增 加的最大平均費(fèi)用為：max_crease = E ri* pi其中：ri為破壞道路序號(hào)；i增加的費(fèi)用；pi為破壞道路i的概率；max_crease為破壞道路增加費(fèi)用的最大平均值。6.3.2 模型求解r=107800,1081120,38357,239514,381625,0,2

31、12670,0,77015p=0.6,070.45,0.5,0.55,040.5,0.6,0.6max_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)得到：max_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)可以解決線性，非線性

32、，整數(shù)規(guī)劃無(wú)法有效求解的復(fù)雜問(wèn)題；(2)容易找到全局最優(yōu)解；(3)可以得到一組解。7.1.2 缺點(diǎn)(1)沒(méi)有標(biāo)準(zhǔn)的模型可供應(yīng)用，構(gòu)模依賴于個(gè)人的經(jīng)驗(yàn)和技巧；(2)狀態(tài)變量需滿足無(wú)后效性，有較大的局限性；(3)動(dòng)態(tài)規(guī)劃的維數(shù)災(zāi)難限制了對(duì)規(guī)模較大問(wèn)題的求解效率。Word格式7.2蟻群算法7.2.1 優(yōu)點(diǎn)(1)不依賴于所求問(wèn)題的具體數(shù)學(xué)表達(dá)式描述，具有很強(qiáng)的找到全局最優(yōu) 解的優(yōu)化能力；(2)該算法具有正反饋、較強(qiáng)的魯棒性、全局性、普遍性、優(yōu)良的分布式 并行計(jì)算機(jī)制、易于與其他方法相結(jié)合等諸多優(yōu)點(diǎn)。7.2.2 缺點(diǎn)(1)蟻群算法的成功主要在實(shí)驗(yàn)層次上，很少有理論來(lái)解釋利用蟻群算法 為什么能夠成功地解決

33、這些問(wèn)題，它沒(méi)有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)；(2)蟻群算法的模型普適性不強(qiáng)，其模型不能直接應(yīng)用于實(shí)際優(yōu)化問(wèn)題；(3)蟻群算法的局部搜索能力較弱，易于出現(xiàn)停滯和局部收斂、收斂速度 慢等問(wèn)題，因而往往需要嵌入一些專門的輔助技巧；(4)長(zhǎng)時(shí)間花費(fèi)在解的構(gòu)造上，從而導(dǎo)致搜索時(shí)間過(guò)長(zhǎng)；(5)算法最先基于離散問(wèn)題，不能直接解決連續(xù)優(yōu)化問(wèn)題。Word格式八、參考文獻(xiàn)1 CHRISTOPHEMR通過(guò)降低成本和增加服務(wù)的物流及供應(yīng)鏈管理策略(第二版)M .北京：電子工業(yè)出版社，2003.2趙啟蘭，王稼瓊，劉宏志.物流規(guī)劃中的需求與潛在需求分析 J .中國(guó) 軟科學(xué)，2004(2):92 95.3肖月，倪梅，李伊松.物流需求分

34、析指標(biāo)研究J.鐵道物資科學(xué)管理， 2003(2):33 34.4劉波，孫林巖.從供應(yīng)鏈到需求流動(dòng)網(wǎng)J.工業(yè)工程，2007, 10(2):1-6.5陳劍，蔡連僑.供應(yīng)鏈建模與優(yōu)化J .系統(tǒng)工程理論與實(shí)踐，2001(6):26 33.6任鳴鳴.供應(yīng)鏈系統(tǒng)節(jié)點(diǎn)設(shè)施選址研究D.武漢：華中科技大學(xué)，2008. 口 李嘉.一類特殊車輛路徑問(wèn)題J.東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2001,22 (3)8張濤，張明杰，王夢(mèng)光.不確定車輛數(shù)的車輛路徑問(wèn)題模型和混合算法J. 系統(tǒng)工程理論方法應(yīng)用,2003 (2)9王正彬，杜文.考慮線路安排的物流配送方案模型及其算法研究J.技術(shù)交流,2003 (12)10尹曉峰，杜艷

35、萍.車輛路徑問(wèn)題的蟻群算法研究J.太原科技大學(xué)學(xué)報(bào)，2005,26 (4)Word格式九、附錄%B 49個(gè)城市散點(diǎn)圖的代碼x=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,353 8,3470,3526,3928,4201,4016,4089,4296,4095,4512,3751,3334,3229,3054,3089,

36、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,69 6,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

37、,24,25,26,27,28,30,40,43,44,45for i=1:49if ismember(i,a)=1plot(x(i),y(i),'.red' ,'MarkerSize',10);elseplot(x(i),y(i),'.black' , 'MarkerSize' ,10);endhold ontext(x(i),y(i),num2str(i);end%求鄰接矩陣的代碼s=1 1 1 1 1 1 2 2 3 3 3 4 4 4 4 5 5 5 6 66 7 7 7 8 9 9 9 10 10 10 10 10 10 11 11 11 12 12 12 1213 131313131414141515151616161617171718 181818 1919191919202020202122222222