1、目錄(ml) TOC o 1-3 h z u HYPERLINK l _Toc355108683 一、問題(wnt)重述 PAGEREF _Toc355108683 h 2 HYPERLINK l _Toc355108684 二、問題(wnt)提出 PAGEREF _Toc355108684 h 2 HYPERLINK l _Toc355108685 三、問題分析 PAGEREF _Toc355108685 h 3 HYPERLINK l _Toc355108686 四、模型假設(shè) PAGEREF _Toc355108686 h 3 HYPERLINK l _Toc355108687 五、主要符

2、號說明 PAGEREF _Toc355108687 h 4 HYPERLINK l _Toc355108688 六、模型的建立與求解 PAGEREF _Toc355108688 h 5 HYPERLINK l _Toc355108689 6.1問題一 PAGEREF _Toc355108689 h 5 HYPERLINK l _Toc355108690 6.1.1 蟻群算法的基本理論 PAGEREF _Toc355108690 h 6 HYPERLINK l _Toc355108691 6.1.2模型求解 PAGEREF _Toc355108691 h 9 HYPERLINK l _Toc35

3、5108692 6.2問題二 PAGEREF _Toc355108692 h 11 HYPERLINK l _Toc355108693 6.2.1迪杰斯特拉算法 PAGEREF _Toc355108693 h 11 HYPERLINK l _Toc355108694 6.2.2模型求解 PAGEREF _Toc355108694 h 12 HYPERLINK l _Toc355108695 6.3問題三 PAGEREF _Toc355108695 h 14 HYPERLINK l _Toc355108696 6.3.1獨(dú)立事件模型建立 PAGEREF _Toc355108696 h 14 HY

4、PERLINK l _Toc355108697 6.3.2模型求解 PAGEREF _Toc355108697 h 15 HYPERLINK l _Toc355108698 七、模型的優(yōu)缺點(diǎn) PAGEREF _Toc355108698 h 15 HYPERLINK l _Toc355108699 7.1動(dòng)態(tài)規(guī)劃 PAGEREF _Toc355108699 h 15 HYPERLINK l _Toc355108700 7.1.1優(yōu)點(diǎn) PAGEREF _Toc355108700 h 15 HYPERLINK l _Toc355108701 7.1.2缺點(diǎn) PAGEREF _Toc355108701

5、 h 15 HYPERLINK l _Toc355108702 7.2蟻群算法 PAGEREF _Toc355108702 h 16 HYPERLINK l _Toc355108703 7.2.1優(yōu)點(diǎn) PAGEREF _Toc355108703 h 16 HYPERLINK l _Toc355108704 7.2.2缺點(diǎn) PAGEREF _Toc355108704 h 16 HYPERLINK l _Toc355108705 八、參考文獻(xiàn) PAGEREF _Toc355108705 h 17 HYPERLINK l _Toc355108706 九、附錄 PAGEREF _Toc35510870

6、6 h 18一、問題(wnt)重述全球化競爭的加劇促使越來越多的企業(yè)開始采用供應(yīng)鏈管理(gunl)策略，以實(shí)現(xiàn)企業(yè)的一體化管理。供應(yīng)鏈?zhǔn)且粋€(gè)復(fù)雜的網(wǎng)狀結(jié)構(gòu)系統(tǒng)，每一部分都面臨著各種潛在的風(fēng)險(xiǎn)，任何一部分出現(xiàn)問題都可能給整個(gè)供應(yīng)鏈帶來嚴(yán)重的影響，因此如何分析、評價(jià)和提高供應(yīng)鏈系統(tǒng)的可靠性變得日益迫切。設(shè)施系統(tǒng)是供應(yīng)鏈的核心，在供應(yīng)鏈研究中有著極其重要的地位。在一個(gè)設(shè)施系統(tǒng)中，某些個(gè)設(shè)施由于自然災(zāi)害或者其他因素的影響可能失效，例如(lr)911恐怖襲擊事件、2004年的印度洋海嘯、2008年的汶川地震等都對諸多行業(yè)的設(shè)施系統(tǒng)造成了嚴(yán)重的破壞。 現(xiàn)有某物流公司要在全國各城市之間建立供應(yīng)鏈網(wǎng)絡(luò)。需要選

7、定部分城市作為供應(yīng)點(diǎn)，將貨物運(yùn)輸?shù)礁鞒鞘小ＭǔＣ總€(gè)供應(yīng)點(diǎn)的貨物是充足的，可以充分滿足相應(yīng)城市的需求。假設(shè)該公司共考慮49個(gè)城市的網(wǎng)絡(luò)并假定作為供應(yīng)點(diǎn)的城市其供應(yīng)量可以滿足有需要的城市的需求。現(xiàn)將要建立一個(gè)供應(yīng)網(wǎng)絡(luò)，為各城市提供貨物供應(yīng)。貨物運(yùn)輸利用汽車進(jìn)行公路運(yùn)輸。二、問題提出（1）現(xiàn)在要從49個(gè)城市中選取部分城市做為供給點(diǎn)供應(yīng)本城市及其它城市。建立供給點(diǎn)會花費(fèi)固定費(fèi)用，從供應(yīng)點(diǎn)運(yùn)輸?shù)叫枨簏c(diǎn)會產(chǎn)生運(yùn)輸費(fèi)用，要使總費(fèi)用最小，問建立多少個(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）假定有某組織對該供應(yīng)網(wǎng)絡(luò)的道路進(jìn)行破壞。并非

8、所有的道路都可以被破壞。當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過該道路的只有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是使對方總費(fèi)用增加25%，而每破壞一條道路都需要成本和代價(jià)，因此需要破壞最少的道路。問破壞方選取哪幾條線路進(jìn)行破壞。給出具體的破壞道路和總費(fèi)用。 （3）假定各道路能否被破壞具有隨機(jī)性，當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過該道路的只有改道，但總是沿最短路(dunl)運(yùn)輸。由于破壞方選取一些邊進(jìn)行破壞時(shí)，這些邊不一定被破壞，而是服從一定的概率分布。運(yùn)輸時(shí)產(chǎn)生的費(fèi)用可按照各種情況下的平均費(fèi)用來考慮。如果破壞方選取的策略是使對方平均總費(fèi)用增加最大

9、。給出具體的破壞道路和平均總費(fèi)用。三、問題(wnt)分析問題(wnt)一：對問題一中的運(yùn)輸調(diào)度問題進(jìn)行分析，根據(jù)動(dòng)態(tài)規(guī)劃算法進(jìn)行處理，利用lingo對其數(shù)學(xué)模型進(jìn)行求解，但該方式給出的算法所搜索的空間容量很大，利用目前的計(jì)算機(jī)求此問題的精確解已很難實(shí)現(xiàn)，并且需要相當(dāng)長的時(shí)間才有可能得到精確解，且其規(guī)模較小實(shí)際應(yīng)用的意義不大。為此，我們結(jié)合蟻群算法在求解運(yùn)輸調(diào)度問題上的優(yōu)勢，在此基礎(chǔ)上，將蟻群算法結(jié)合運(yùn)輸調(diào)度模型進(jìn)行仿真實(shí)現(xiàn)。問題二：我們建立了基于迪杰斯特拉算法的模型。根據(jù)題目所給的的信息，對可破壞的道路進(jìn)行逐一破壞分析，得到最短傳輸路徑和相應(yīng)多消耗的費(fèi)用。再根據(jù)破壞方使對方總費(fèi)用增加25%這一

10、策略得到具體破壞的道路和總費(fèi)用。問題三：該問題是在問題二的基礎(chǔ)上的優(yōu)化，由于破壞方選取一些邊進(jìn)行破壞時(shí)，這些邊不一定被破壞，而是服從一定的概率分布。在考慮此問題時(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)輸貨物的不同對供應(yīng)點(diǎn)設(shè)立的影響；（5）忽略貨物需求量、發(fā)送量、交發(fā)貨(f hu)時(shí)間、車輛容量限制、行駛里程限制及時(shí)間限制的影響；（6）假設(shè)兩城市之間

11、除了公路運(yùn)輸沒有(mi yu)其他運(yùn)輸方式；（7）假設(shè)運(yùn)輸單價(jià)(dnji)不受天氣和油價(jià)等因素影響；（8）假設(shè)各城市的需求量在一段時(shí)間內(nèi)固定不變。五、主要符號說明數(shù)學(xué)符號符號說明元素i在t時(shí)刻存在的螞蟻數(shù)量路徑(i，j)上t時(shí)刻的信息素濃度數(shù)值n城市數(shù)目m蟻群算法的規(guī)模即蟻群中的螞蟻總數(shù)t時(shí)刻所有城市間路徑上的信息素殘留量的集合螞蟻k下一步允許選擇的城市信息素強(qiáng)度影響因子啟發(fā)函數(shù)distn存放從源點(diǎn)到每個(gè)終點(diǎn)當(dāng)前最短路徑的長度pathn存放相應(yīng)路徑S已求得最短路徑的終點(diǎn)的集合cos(i)表示以第i個(gè)城市建立供應(yīng)點(diǎn)所需的固定費(fèi)用w(i)表示第i個(gè)城市所需的貨物重量d(i)路線序號i的距離乘以每公

12、里費(fèi)用0.5元之后的值Totali以i為供應(yīng)中心和周圍城市構(gòu)成網(wǎng)絡(luò)所需的總費(fèi)用ansi表示破壞道路要多序號i后要多花費(fèi)的費(fèi)用六、模型(mxng)的建立與求解供應(yīng)鏈網(wǎng)絡(luò)中一個(gè)重要的網(wǎng)絡(luò)節(jié)點(diǎn)(ji din)是供應(yīng)點(diǎn)設(shè)立。一般來講，如果用戶(yngh)較為固定，按照配送費(fèi)用最小或者到各個(gè)消費(fèi)地的距離之和最小的原則，即供應(yīng)點(diǎn)處于使物流網(wǎng)路運(yùn)營費(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)者配送，形成輻射型。需

13、求地需求地需求地供應(yīng)點(diǎn)圖1：輻射型格局設(shè)立輻射型的格局應(yīng)滿足兩個(gè)方面的條件。一是需求地在供應(yīng)點(diǎn)周圍幾乎是均勻分布，并且供應(yīng)點(diǎn)周圍是用戶相對集中的經(jīng)濟(jì)區(qū)域；二是供應(yīng)點(diǎn)是連接主干輸送線路和配送線路的一個(gè)轉(zhuǎn)運(yùn)站，把貨物送到指定地點(diǎn)。6.1問題(wnt)一根據(jù)題中所給出的各城市(chngsh)坐標(biāo)和各公路段及里程表，得到49個(gè)城市(chngsh)的分布圖如下。圖2：城市的分布圖對問題一中的運(yùn)輸調(diào)度問題進(jìn)行分析，根據(jù)動(dòng)態(tài)規(guī)劃算法進(jìn)行處理，利用lingo對其數(shù)學(xué)模型進(jìn)行編程并求解，但該方式給出的算法所搜索的空間容量很大，利用目前的計(jì)算機(jī)求此問題的精確解已很難實(shí)現(xiàn)，并且需要相當(dāng)長的時(shí)間才有可能得到精確解，且

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

15、選擇。蟻群算法是一種模擬自然界螞蟻覓食(m sh)行為的啟發(fā)式搜索算法，由意大利學(xué)者(xuzh)M. Dorigo模擬此過程提出。其主要特點(diǎn)正反饋、并行式搜索。它尤其適用于處理傳統(tǒng)搜索方法難于解決(jiju)的復(fù)雜和非線性問題，可廣泛用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域，是21世紀(jì)有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)之一。首先我們要對螞蟻的搜索環(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è)路

16、徑上的信息素通常設(shè)定為一個(gè)常數(shù)。螞蟻k(k=1,2,，m)在路徑的搜索過程中，根據(jù)不同路徑上的信息素濃度來決定其下一步的搜索路徑。表示在t時(shí)刻螞蟻k由元素(城市)i轉(zhuǎn)移到元素(城市)j的選擇概率。式中，表示螞蟻k下一步允許選擇的城市，為信息素強(qiáng)度影響因子，表示螞蟻對于信息素濃度的敏感程度也表明此路徑的相對重要性。其值越大，此時(shí)螞蟻在選擇下一搜索路徑時(shí)，容易受到信息素濃度的影響，螞蟻更趨向于信息素濃度較高的路徑，也就是有更多螞蟻?zhàn)哌^的路徑同時(shí)也是增強(qiáng)了螞蟻間的交流信息使彼此間的協(xié)調(diào)機(jī)制更明顯。為能見度因子又稱期望因子，表示螞蟻本身的能見度對在路徑選擇中的重要性。其值越大則螞蟻選擇路徑時(shí)越是依賴于

17、能見度信息。當(dāng)取值很高時(shí)螞蟻則是以一種幾乎貪婪的規(guī)則選擇下一步的搜索路徑，而忽略信息素影響。為啟發(fā)函數(shù)，其表達(dá)式如下:式中，表示兩個(gè)相鄰(xin ln)元素間的距離。的數(shù)值越小，說明兩城市(chngsh)相距越近同時(shí)越大，也就越大，螞蟻下一步(y b)選擇這一個(gè)城市的概率也就越高，這也就說該函數(shù)表征了螞蟻從一個(gè)城市到另一個(gè)城市的期望度數(shù)值。隨著螞蟻的不斷搜索，很多路徑上都會留下信息素，為了防止各個(gè)路徑上的大量殘留信息素不斷積累從而導(dǎo)致螞蟻忽略能見度信息，當(dāng)每只螞蟻每完成一步搜索或者螞蟻完成對n個(gè)城市的搜索(也就是算法完成一次迭代)后，需要對每條路徑上殘留的信息素量進(jìn)行更新。這樣在t+n時(shí)刻路徑

18、(i，j)上的信息素濃度可以按照下面的公式調(diào)整。式中表示信息素?fù)]發(fā)因子，則表示信息素殘留因子。為了更加貼近自然界中的螞蟻群體，并防止信息素的過度累積，通常的取值范圍為:；在完成一次迭代后用表示路徑(i，j)上的信息素增量，初始時(shí)刻，則表示螞蟻k在本次搜索過程中于路徑(i，j)上留下的信息素量。在蟻群算法中，信息素的更新策略直接關(guān)系著算法的效率和成功與否，而信息素更新的策略也會根據(jù)待解決的問題特點(diǎn)來選擇。DorigoM曾經(jīng)提出了三種不同的基本蟻群算法模型。這三種模型分別是:Ant-Cycle模型、Ant-Quantity模型和Ant一Density模型。其中三種模型的差別在于信息素增量的求法的不

19、同。在Ant-Cycle模型(mxng)中式中，Q表示(biosh)信息素強(qiáng)度，它在一定程度上影響算法的收斂速度;表示k只螞蟻(my)在本次循環(huán)中所走路徑的總長度。在Ant-Quanity模型中在Ant-Density模型中其中Ant-Quanity模型和Ant-Density模型采用的是局部信息素更新策略，也就是說螞蟻在每走完一步到達(dá)下一城市就對剛剛走過的路徑信息素進(jìn)行更新；而Ant-Cycle模型中則是采用全局的信息素更新策略，當(dāng)一只螞蟻訪問過所有城市以后才會對所走過的路徑進(jìn)行信息素更新。6.1.2模型求解用蟻群算法對問題一進(jìn)行分析，得到最優(yōu)結(jié)果為：選擇出拉薩、長春、蘭州、太原、宜昌、成都

20、、南寧、杭州這八個(gè)城市為供應(yīng)點(diǎn)，總費(fèi)用為9304885元。每個(gè)供應(yīng)點(diǎn)供應(yīng)的城市及每一個(gè)供應(yīng)點(diǎn)到需求點(diǎn)的連接圖如下：圖3：供應(yīng)(gngyng)點(diǎn)供應(yīng)范圍圖每個(gè)供應(yīng)(gngyng)點(diǎn)供應(yīng)的城市及費(fèi)用(fi yong)情況如下表：表1：供應(yīng)點(diǎn)供應(yīng)城市及費(fèi)用情況表編號供應(yīng)點(diǎn)建立供應(yīng)范圍費(fèi)用（元）1拉薩無310082長春沈陽大連，通遼，白城海拉爾，哈爾濱11401063蘭州烏市，西寧，銀川，西安延安8714524太原呼市包頭，石家莊北京，石家莊天津，石家莊濟(jì)南，鄭州14004005宜昌武漢，長沙，南陽8257806成都重慶12382987南寧貴陽，昆明，柳州，?？谌齺?，廣州深圳澳門，廣州臺北169063

21、78杭州上海，寧波，福州廈門，福州臺北，南昌，南京青島，南京徐州，南京合肥2107604總費(fèi)用共計(jì)：9304885其中費(fèi)用的計(jì)算過程如下：Total2=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)= 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

22、)+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)+w

23、(35)*(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)= 21076046.2問題(wnt)二假定有某組織對該供應(yīng)網(wǎng)絡(luò)的道路進(jìn)行破壞。并非所有的道路都可以被破壞。當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前運(yùn)

24、輸經(jīng)過該道路的只有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是使對方總費(fèi)用增加25%，而每破壞一條道路都需要成本(chngbn)和代價(jià)，因此需要破壞最少的道路。對于此問題(wnt)，我們采用迪杰斯特拉算法進(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中

25、，直到全部頂點(diǎn)都加入到S中）。第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示，U=V-S，U中的頂點(diǎn)不斷的加入到S中，直到U為空，S=V）。在U加入S的過程中，始終保持源點(diǎn)到S中各頂點(diǎn)的最短路徑長度小于或等于源點(diǎn)到U中任意頂點(diǎn)的最短路徑長度。迪杰斯特拉算法(sun f)執(zhí)行步驟設(shè) n 為圖 G=(V,E) 中的頂點(diǎn)數(shù)，distn 存放從源點(diǎn)到每個(gè)終點(diǎn)(zhngdin)當(dāng)前最短路徑的長度，pathn存放相應(yīng)路徑，S為已求得最短路徑的終點(diǎn)的集合，U為V-S，初始為不含有(hn yu)源點(diǎn)的所有頂點(diǎn)。（1）初始化已求的最短路徑的集合S為只含有元素源點(diǎn)a，S=a。（2）從U中選取一個(gè)距離源點(diǎn)v最小的頂

26、點(diǎn)k，把k加入S中（該選定的距離就是v到k的最短路徑長度）。（3）以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u（u U）的距離（經(jīng)過頂點(diǎn)k）比原來距離（不經(jīng)過頂點(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模型求解假定有某組織對該供應(yīng)網(wǎng)絡(luò)的道路進(jìn)行破壞。并非所有的道路都可以被破壞，可破壞的道路見下表。表2：破壞道路表道路序號城市1城市21452343740410115192062425717458214992021根據(jù)(gnj)第一題得到(d do)的供應(yīng)范圍的分布圖并結(jié)合上

27、表，我們運(yùn)用迪杰斯特拉算法(sun f)對破壞后道路進(jìn)行分析，求得了改道后的最短路運(yùn)輸路徑和破壞道路后所多消耗的費(fèi)用。表3：破壞道路后路線更改及多消耗費(fèi)用表序號破壞的道路原路線更改后路線多消耗的費(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-738

28、357510-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無影響無影響不產(chǎn)生817-4517-4517-44-45212670921-49無影響無影響不產(chǎn)生1020-2120-2121-19-207701549-21-2049-21-19-201119-20和20-2119-2019-18-45650969

29、34-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其中(qzhng)，破壞道路后多消耗的費(fèi)用計(jì)算過程如下：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(7)-d(9)+w(15)*(d(50)+d(1

30、3)-d(9)-d(10)= 1081120ans3=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

31、(38)*(d(27)+d(26)-d(29)=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

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

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

34、9514,381625,0,212670,0,77015p=0.6,0.7,0.45,0.5,0.55,0.4,0.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)得到(d do)：max_crease=1431200 根據(jù)以上分析可以(ky)得到：破壞(phui)道路的序號為1、2、3、4、5、7、9，平均總費(fèi)用為1431200元七

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

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

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

38、法研究J.技術(shù)交流，2003（12）10 尹曉峰，杜艷萍.車輛路徑問題的蟻群算法研究J.太原科技大學(xué)學(xué)報(bào)，2005,26（4）九、附錄(fl)%畫49個(gè)城市(chngsh)散點(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,3538,3470,3526,3928,4201,4016,4089,4296,4095,4

39、512,3751,3334,3229,3054,3089,3044,3053y=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,261a=1,3,4,5,7,10,11,12,13,1

40、4,15,16,17,18,19,20,22,23,24,25,26,27,28,30,40,43,44,45for i=1:49 if ismember(i,a)=1 plot(x(i),y(i),.red,MarkerSize,10); else plot(x(i),y(i),.black,MarkerSize,10); end hold on text(x(i),y(i),num2str(i);end %求鄰接矩陣的代碼(di m)s=1 1 1 1 1 1 2 2 3 3 3 4 4 4 4 5 5 5 6 6 6 7 7 7 8 9 9 9 10 10 10 10 10 10 11 11 11 12 12 12 12 13 13 13 13 13 14 14 14 15 15 15 16 16 16 16 17 17 17 18 18 18 18 19 19 19 19 19 20 20 20 20 21 22 22 22 22 22 23 23 23 24 24 25 26 26 27 27 27 27 28 28 28 30 33 35 38 40 40 41 44 46d=2 3 5 6 15 40 3 15 4 15 16 5 16 27 30 30 40 47