供應(yīng)鏈網(wǎng)絡(luò)的建立與破壞問題

1、裝 訂 線目錄摘 要2供應(yīng)鏈網(wǎng)絡(luò)的建立與破壞問題3一、問題重述3二、問題分析32.1問題一：32.2問題二：42.3問題三：4三、模型假設(shè)與符號說明43.1模型假設(shè)：43.2符號說明：4四、模型的建立與求解54.1問題一：54.1.1算法描述：54.1.2模型建立與求解54.2問題二：114.2.1模型的建立與求解114.3問題三：124.3.1模型的建立與求解12五、模型評價17六、參考文獻(xiàn)17七、部分程序代碼1722摘 要在全球化競爭加劇的情況下，越來越多的企業(yè)開始采用供應(yīng)鏈管理策略，以實(shí)現(xiàn)企業(yè)的一體化管理。而供應(yīng)鏈?zhǔn)且粋€復(fù)雜的網(wǎng)狀結(jié)構(gòu)系統(tǒng)，包括供應(yīng)中心和供應(yīng)路線，它的每一部分都面臨著各種

2、潛在的風(fēng)險(xiǎn)，都有可能出現(xiàn)問題從而給整個供應(yīng)鏈帶來嚴(yán)重的影響。因此如何分析、評價和提高供應(yīng)鏈系統(tǒng)的可靠性變得日益迫切。 本論文根據(jù)在城市建設(shè)供應(yīng)中心的費(fèi)用和運(yùn)輸貨物的運(yùn)費(fèi)對全國49個城市和其之間的道路進(jìn)行了研究。在文中應(yīng)用Floyd算法和分治法，通過matlab，C+編程語言編程計(jì)算，成功從這49個城市中計(jì)算最短距離，并最終選擇出了8個最優(yōu)供應(yīng)中心城市，并給出了最優(yōu)供應(yīng)鏈。在此基礎(chǔ)上，本文從破壞者的角度，利用matlab等數(shù)學(xué)工具、C+編程語言和二分法、分治法的思想，分析了在使總費(fèi)用增加一定數(shù)目的情況下，最少需要破壞道路的數(shù)目和具體道路，給企業(yè)提供了防范破壞的依據(jù)。然后本文進(jìn)一步從道路被破壞有一

3、定概率的情況下出發(fā)，利用數(shù)據(jù)之間有無相關(guān)性，分析出了破壞哪些道路能使平均費(fèi)用增加最多這一問題，給企業(yè)提供了更可靠的防范破壞依據(jù)。關(guān)鍵字：供應(yīng)鏈 Floyd算法 分治法 圖論 相關(guān)性供應(yīng)鏈網(wǎng)絡(luò)的建立與破壞問題一、問題重述 現(xiàn)有某物流公司要在全國各城市之間建立供應(yīng)鏈網(wǎng)絡(luò)。需要選定部分城市作為供應(yīng)點(diǎn)，將貨物運(yùn)輸?shù)礁鞒鞘?。通常每個供應(yīng)點(diǎn)的貨物是充足的，可以充分滿足相應(yīng)城市的需求。 設(shè)該公司考慮共考慮49個城市的網(wǎng)絡(luò)，城市的坐標(biāo)見表1。城市之間的道路連接關(guān)系見表2。在每個城市建立配送中心的固定費(fèi)用和需求量表3，并假定作為供應(yīng)點(diǎn)的城市其供應(yīng)量可以滿足有需要的城市的需求?，F(xiàn)將要建立一個供應(yīng)網(wǎng)絡(luò)，為各城市提供

4、貨物供應(yīng)。貨物運(yùn)輸利用汽車進(jìn)行公路運(yùn)輸。設(shè)每噸每公里運(yùn)輸費(fèi)用為0.5元?，F(xiàn)提出如下問題：現(xiàn)在要從49個城市中選取部分城市做為供給點(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)用最小，問建立多少個供應(yīng)點(diǎn)最好。給出選中作為供應(yīng)點(diǎn)的城市，并給出每個供應(yīng)點(diǎn)供應(yīng)的城市。同時根據(jù)坐標(biāo)作出每一個供應(yīng)點(diǎn)到需求點(diǎn)的連接圖。假定有某組織對該供應(yīng)網(wǎng)絡(luò)的道路進(jìn)行破壞。并非所有的道路都可以被破壞，可破壞的道路見表4。當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過該道路的只有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是使對方總費(fèi)用增加25%，而每破壞一條道路都

5、需要成本和代價，因此需要破壞最少的道路。問破壞方選取哪幾條線路進(jìn)行破壞。給出具體的破壞道路和總費(fèi)用。 假定各道路能否被破壞具有隨機(jī)性，當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過該道路的只有改道，但總是沿最短路運(yùn)輸。由于破壞方選取一些邊進(jìn)行破壞時，這些邊不一定被破壞，而是服從一定的概率分布。設(shè)可破壞的邊及各邊破壞的概率見表4。運(yùn)輸時產(chǎn)生的費(fèi)用可按照各種情況下的平均費(fèi)用來考慮。如果破壞方選取的策略是使對方平均總費(fèi)用至少增加100%，同樣需要破壞最少的道路。問破壞方將選取哪幾條線路進(jìn)行破壞。給出具體的破壞道路和平均總費(fèi)用。 二、問題分析2.1問題一：根據(jù)題目條件可知，供應(yīng)中心的選擇由建

6、設(shè)費(fèi)用和運(yùn)輸費(fèi)用共同決定，而題中已給出各個城市建設(shè)供應(yīng)中心的費(fèi)用，所以首先要解決的問題是計(jì)算出每兩個城市之間的最小距離（如果兩個城市之間無直達(dá)道路，可繞道而行），此問題可用floyd算法解決。為了使選擇供應(yīng)中心時的權(quán)值統(tǒng)一，即權(quán)值的單位一樣，需將距離權(quán)值轉(zhuǎn)化為成本權(quán)值，因?yàn)槊績蓚€城市之間的最小路程已經(jīng)計(jì)算出來，并且每個城市的需求量和每公里的運(yùn)費(fèi)已知，則可通過簡單的程序?qū)⒕嚯x權(quán)值轉(zhuǎn)化為成本權(quán)值，即計(jì)算出有供應(yīng)關(guān)系的城市之間所花費(fèi)的運(yùn)費(fèi)。這樣一來，就可以著手選擇供應(yīng)中心。首先給每個城市選擇理想供應(yīng)中心城市。所謂理想的供應(yīng)中心城市是指滿足以下條件的其他城市：比如給第i個城市選擇理想供應(yīng)中心城市j，則

7、 1.j城市的供應(yīng)中心建設(shè)費(fèi)用不是1000000000，即可用作供應(yīng)中心。2.j給i供給貨物所花的路費(fèi)應(yīng)該小于在第i個城市建設(shè)供應(yīng)中心的費(fèi)用（若路費(fèi)大于建設(shè)供應(yīng)中心的費(fèi)用，則摒棄從j城市為第i個城市供應(yīng)的做法，直接在第i個城市建立供應(yīng)中心）這樣經(jīng)過初步篩選，可得到第i個城市的全部理想供應(yīng)城市j。在此基礎(chǔ)上，可根據(jù)貪心算法的思想，結(jié)合matlab繪制出來的坐標(biāo)地圖，人為地將區(qū)域劃分成小塊。在每一個小塊內(nèi)可人為地選擇一個供應(yīng)中心，此供應(yīng)中心為其他被供應(yīng)城市供應(yīng)貨物的運(yùn)費(fèi)相對較小。由此確定出大致的供應(yīng)中心城市數(shù)目。編程，在28個城市中輸入所有的可能組合，畫出總費(fèi)用變化圖，得出最終的最優(yōu)解。2.2問題

8、二：問題一中已求解出了最優(yōu)解，繪制出了供應(yīng)關(guān)系圖。由題可知，可被破壞的道路只有9條，數(shù)目較少，在此基礎(chǔ)上，利用二分法的思想和問題一中求總費(fèi)用的程序進(jìn)行試驗(yàn)，得到滿足要求的被破壞道路。2.3問題三：問題三相對問題二而言只是給可破壞道路附加了一定的成功概率，因此要解決破壞哪些道路可使平均總費(fèi)用增加最多這一問題，可利用問題二中的程序和部分?jǐn)?shù)據(jù)。由繪制出的供應(yīng)關(guān)系圖可知，許多被破壞的道路之間是沒有影響的，即無相關(guān)性，它們共同被破壞產(chǎn)生的總費(fèi)用期望可以直接由它們單獨(dú)被破壞產(chǎn)生的總費(fèi)用期望相加得到。而小部分有影響、有相關(guān)性的道路可利用程序運(yùn)行得出它們共同作用的產(chǎn)生的總費(fèi)用期望。三、模型假設(shè)與符號說明3.1

9、模型假設(shè)：（1）供應(yīng)中心的選擇是任意的，不受政治、地理、環(huán)境等因素的影響；（2）各地交通條件相同，運(yùn)輸過程中不受交通條件的影響；3.2符號說明：i第i個城市；j對第i個城市來說為理想供應(yīng)中心的城市；mi第i個城市建立配送中心的固定費(fèi)用；Ri第i個城市的需求量；Z表示總費(fèi)用；Sji為第i個城市供應(yīng)貨物的理想供應(yīng)中心j到第i個城市的路程；Sji，max為第i個城市供應(yīng)貨物的運(yùn)費(fèi)不超過在第i個城市建立供應(yīng)中心時的最大供應(yīng)離；Smin每兩個城市之間的最小距離E期望值PAA事件發(fā)生的概率AA事件發(fā)生max平均總費(fèi)用增加值四、模型的建立與求解4.1問題一：4.1.1算法描述：（1）Floyd算法Floyd

10、算法又稱為弗洛伊德算法，插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。Floyd算法的基本思想如下：從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過若干個節(jié)點(diǎn)X到B。所以，我們假設(shè)Dis(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短路徑的距離，對于每一個節(jié)點(diǎn)X，我們檢查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設(shè)置Dis(AB) = Dis(AX) + Dis(XB)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)X，Dis(AB)中記錄的便是A到B的最短路徑的距離。 (2)分治法：分治法字面

11、上的解釋是“分而治之”，就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。分治策略是：對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。如果原問題可分割成k個子問題，1<kn ，且這些子問題都可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為

12、使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。4.1.2模型建立與求解（1）運(yùn)用Floyd算法計(jì)算出每兩個城市之間的最小距離Smin根據(jù)Floyd算法，用matlab工具編程，計(jì)算出每兩個城市之間的最小距離。（代碼見附錄）每兩個城市之間的最小距離：distance.txt（2）求每個城市的最大供應(yīng)距離Sji，max如果其它城市給第i個城市供應(yīng)貨物所花費(fèi)的運(yùn)輸費(fèi)用大于在i城市建設(shè)供應(yīng)中心的固定花費(fèi)，

13、顯然不如直接在第i個城市建設(shè)供應(yīng)中心。因此，每個城市存在一個最大供應(yīng)距離Sji，max。Sji，max=mi/(Ri*0.5)用C語言編程得到最大供應(yīng)距離：(3)運(yùn)用分治法和matlab，求出局部地區(qū)的可能最優(yōu)解a.求理想供應(yīng)中心城市給每個城市選擇理想供應(yīng)中心城市。所謂理想的供應(yīng)中心城市是指滿足以下條件的其他城市：比如給第i個城市選擇理想供應(yīng)中心城市j，則 a） j城市的供應(yīng)中心建設(shè)費(fèi)用不是1000000000，即可用作供應(yīng)中心。b） j給i供給貨物所花的路費(fèi)應(yīng)該小于在第i個城市建設(shè)供應(yīng)中心的費(fèi)用（若路費(fèi)大于建設(shè)供應(yīng)中心的費(fèi)用，則摒棄從j城市為第i個城市供應(yīng)的做法，直接在第i個城市建立供應(yīng)中心

14、）由這些條件可知，只要滿足SminSji，max的城市j均是第i個城市的理想供應(yīng)中心城市。用matlab編程得到每個城市的的理想供應(yīng)中心城市。見下表：理想供應(yīng)中心城市選擇表城市最大供應(yīng)距離Sji，max小于最大距離的點(diǎn)理想供應(yīng)中心城市j118243 4 5 7 10 11 12 14 15 16 17 18 27 28 30 40 43 44 45210000000001 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 315201 4 5 7 10 11 12 14 15 16 17 1

15、8 27 28 30 40 43 44 45 415201 3 5 10 11 12 14 15 16 17 18 27 28 30 40 43 44 45 515201 3 4 15 16 17 27 28 30 40 43 44610000000001 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 712161 40810000000001 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 4

16、4 45 910000000001 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 1021281 3 4 5 11 12 13 14 15 16 17 18 19 20 22 24 27 28 30 40 43 44 45 11121610 12 13 14 15 16 17 43 1215201 3 4 10 11 13 14 15 16 17 18 19 27 43 44 4513182410 11 12 14 15 16 17 18 19 20 43 44 451421281 3

17、4 5 10 11 12 13 15 16 17 18 19 20 22 23 24 27 28 30 43 44 45 1524321 3 4 5 7 10 11 12 13 14 16 17 18 19 20 22 23 24 27 28 30 40 43 44 45 1624321 3 4 5 7 10 11 12 13 14 15 17 18 19 20 22 23 24 27 28 30 40 43 44 45 1718241 3 4 5 10 11 12 13 14 15 16 18 19 20 22 23 24 27 28 30 43 44 451818241 3 4 10 11

18、 12 13 14 15 16 17 19 20 22 23 24 25 27 43 44 451924321 3 4 10 11 12 13 14 15 16 17 18 20 22 23 24 25 27 43 44 45 20152017 18 19 22 23 24 25 45 2110000000001 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 22152014 16 17 18 20 23 24 25 27 44 45 23121622 24 27 45 24152017

19、 18 19 20 22 23 25 27 45 25152020 22 23 24 2612162724321 3 4 5 7 10 11 12 13 14 15 16 17 18 19 20 22 23 24 25 28 30 40 43 44 45 28121627 302910000000001 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 453015201 3 4 5 15 16 27 28 44 3110000000001 3 4 5 7 10 11 12 13 14 15 16

20、 17 18 19 20 22 23 24 25 26 27 28 30 40 43 44 453210000000001 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 453310000000001 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 453410000000001 3 4 5 7 10 11 12 13 14 15 16 17 18 19 20 22 23 24 25 26 27

21、 28 30 40 43 44 453510000000001 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 453610000000001 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 453710000000001 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 45381000000000

22、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 453910000000001 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 454018241 3 4 5 7 15 16 43 4110000000001 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 454210000000001 3 4

23、 5 7 10 11 12 13 14 15 16 17 18 19 20 22 23 24 25 26 27 28 30 40 43 44 454315201 3 4 5 10 11 12 13 14 15 16 17 18 27 44 45 4412161 3 4 10 12 14 15 16 17 18 27 43 45 4512163 4 10 12 14 15 16 17 18 22 23 27 44 4610000000001 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 4547

24、10000000001 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 454810000000001 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 454910000000001 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注釋：最大供應(yīng)距離為1000000000表示該城市可由任意一個能

25、夠建設(shè)供應(yīng)中心的城市為其供應(yīng)貨物b.用分治法思想結(jié)合上表得到的局部分區(qū)圖：使用分治法的思想，若想總體費(fèi)用最低，則局部的費(fèi)用應(yīng)該最低。上表已經(jīng)得到每個城市的理想供應(yīng)中心，每個城市真實(shí)的供應(yīng)中心應(yīng)該從理想供應(yīng)中心中選擇。因此可以人為地將所有城市分為8塊區(qū)域，在每一個區(qū)域內(nèi)存在一個供應(yīng)中心為此區(qū)域內(nèi)的其他城市供應(yīng)貨物。（部分處于中間地區(qū)的城市分區(qū)不太明顯，可屬于周圍的任一區(qū)域）由上圖可知供應(yīng)中心城市應(yīng)該有8個。它們的可能為： 11,23,26,28,7,4,19,4511,23,26,28,7,4,20,4511,23,26,28,7,3,19,4511,23,26,28,7,3,20,4511,2

26、3,26,28,40,4,19,4511,23,26,28,40,4,20,4511,23,26,28,40,3,19,4511,23,26,28,40,3,20,45（4）編程驗(yàn)證最優(yōu)解用C+語言編程，此程序功能為：任意輸入i個城市作為供應(yīng)中心，輸出以這些城市為供應(yīng)中心所產(chǎn)生的總費(fèi)用Z。經(jīng)過比較以上8組可能的最優(yōu)解所產(chǎn)生的總費(fèi)用，得出4,7,11,20,23,26,28,45這一組的總費(fèi)用最低這一結(jié)論。綜上，4,7,11,20,23,26,28,45即為最優(yōu)解。用matlab繪制出供應(yīng)關(guān)系圖如下：注釋：其中紅色的點(diǎn)代表供應(yīng)中心，箭頭代表運(yùn)輸方向?？傎M(fèi)用：Z=9197114（元）4.2問題二：

27、4.2.1模型的建立與求解本題的目標(biāo)是破壞最少的道路產(chǎn)生至少25%的總費(fèi)用增加，即Z9197114*25%=2299278.5。由供應(yīng)關(guān)系圖可知，在可破壞的9條道路中，破壞第6條和第8條對總費(fèi)用沒有影響。因此只從1,2,3,4,5,7,9號道路中選擇被破壞道路。應(yīng)用問題二中的程序，只需更改被破壞道路的數(shù)據(jù)，即可得到破壞后的總費(fèi)用。先從破壞一條道路開始嘗試，結(jié)果見下表：只破壞一條道路時的所有結(jié)果：被破壞道路序號破壞后的總費(fèi)用Z1總費(fèi)用增長Z1928842291278210278283108113939232301351574939565219850859578739381595794117642

28、146209927412976985由表可知，當(dāng)破壞一條道路時所產(chǎn)生的的總費(fèi)用增長遠(yuǎn)遠(yuǎn)小于2299278.5元，因此從破壞7條道路開始嘗試。全部破壞時的結(jié)果：被破壞道路序號破壞后的總費(fèi)用Z1（元）總費(fèi)用增長Z（元）1,2,3,4,5,7,9116129622415848滿足要求，繼續(xù)嘗試破壞6條道路的情況。破壞六條道路后的所有結(jié)果：被破壞道路序號破壞后的總費(fèi)用Z1（元）總費(fèi)用增長Z2,3,4,5,7,91144840022512861,3,4,5,7,91038776611906521,2,4,5,7,91157777523806611,2,3,5,7,91134365121465371,2,

29、3,4,7,91103900818418941,2,3,4,5,91139831222011981,2,3,4,5,7113436182146504其中，破壞1,2,4,5,7,9號道路滿足要求。繼續(xù)運(yùn)行程序，當(dāng)破壞5條道路時沒有滿足條件的道路，因此，破壞方案為：1,2,4,5,7,9總費(fèi)用：Z=115777754.3問題三：4.3.1模型的建立與求解a.根據(jù)供應(yīng)關(guān)系圖分析道路之間的相關(guān)性由供應(yīng)關(guān)系圖可知，大部分道路都不在一個小的子區(qū)域內(nèi)。若不在一個小區(qū)域內(nèi)，則其產(chǎn)生的影響是不相關(guān)的，即具有直接加和性。在此現(xiàn)象的基礎(chǔ)上，進(jìn)行驗(yàn)證。被破壞的道路序號破壞后的總費(fèi)用Z1（元）總費(fèi)用增長Z單條道路相加

30、有無相關(guān)性19288422913082102782831081169392323013518749395652198538595787393816256919711407941176421465089197114099274129770151,21044281512457011172477有2,31031344011163261116326無2,41054756413504501279707有2,71049290312957891295789無2,51065987814627641462764無2,91035526811581541158154無1,79503042305928305928無1

31、,59670017472903472903無1,39323579126465126465無1,49486930289816289816無1,99365407168293168293無3,9930928611217235217有3,49430809233695233695無3,79446921249807249807無3,59613896416782416782無4,79610272413158413158無4,59777247580133580133無4,99472637275523275523無7,99488749291635291635無5,99848053650939458640有5,7

32、9793359596245596245無注釋：紅色代表有相關(guān)性的道路，其余為無相關(guān)性道路。由上表可知，（1,2）（2,4）（3,9）（5,9）之間具有相關(guān)性，而其他道路之間則沒有相關(guān)性。進(jìn)一步分析三條道路的相關(guān)性，得出（1,2,4）（3,5,9）之間有相關(guān)性，其它則沒有相關(guān)性。與供應(yīng)關(guān)系圖對應(yīng)可知，沒有相關(guān)性的道路之間距離較遠(yuǎn)，當(dāng)其中任何一條被破壞時，其它道路不受影響。有相關(guān)性的道路之間距離則較近，其中一條被破壞時會影響其它道路，包括其他道路被破壞時所繞行的道路。由此得出結(jié)論：沒有相關(guān)性的道路之間運(yùn)費(fèi)可以進(jìn)行疊加，進(jìn)而期望值也可以進(jìn)行疊加。而有相關(guān)性的道路之間運(yùn)費(fèi)不能進(jìn)行疊加，期望值也不能進(jìn)行

33、疊加，只能用公式進(jìn)行計(jì)算。計(jì)算公式為：E=PA*A根據(jù)計(jì)算公式和期望的疊加性，得出：當(dāng)破壞的道路為一條時：被破壞的道路序號平均總費(fèi)用增加值154784.82756818.3315834.154992695209893.7560710732580946209當(dāng)破壞的道路為兩條時：被破壞的道路序號平均總費(fèi)用增加值1,2421165.51,335293.71,477010.51,51323221,781038.51,9504792,33863092,44404042,5483337.52,7432053.52,94014943,457537.53,51128493,761565.53,941277.

34、34,5154565.54,71032824,972722.55,7158593.55,9159768.57,976750.5當(dāng)破壞的道路為三條時：被破壞的道路序號平均總費(fèi)用增加值1,2,3286050.53331,2,4321328.94331,2,53507361,2,73165471,2,92961742,3,42906242,3,5327498.33332,3,7293309.33332,3,9272936.33332,4,5363561.66672,4,7329372.66672,4,9308999.66672,5,73579952,5,93376222,7,9303432.6667

35、3,4,5108317.33333,4,768854.666673,4,953755.333333,5,7111002.53333,5,9111788.79333,7,956440.666674,5,7138813.66674,5,9103043.66674,7,999648.666675,7,9175688由上表繪制出下面的折線圖。并且分析每種情況下的平均總費(fèi)用增加值的最大值：當(dāng)破壞一條道路時：max 1=756818.3當(dāng)破壞兩條道路時：max 2=483337.5當(dāng)破壞三條道路時：max 3=363561.6667因此得出結(jié)論，被破壞道路越多，平均費(fèi)用增加值越少。由上圖可知，若當(dāng)?shù)缆菲茐?/p>

36、代價較大時，應(yīng)該持“少破壞、多增加”的原則進(jìn)行破壞。當(dāng)?shù)缆菲茐拇鷥r較小時，持“多破壞，多增加”的原則。故結(jié)合上圖給出以下結(jié)論：當(dāng)破壞道路的代價較大時，選擇2號道路進(jìn)行破壞。平均總費(fèi)用增加為756797元?？傎M(fèi)用當(dāng)破壞道路代價較小時，選擇1，2，3，4，5，7，9道路進(jìn)行破壞。平均總費(fèi)用增加為1406663.21五、模型評價此模型利用了Floyd算法和分治法進(jìn)行計(jì)算，利用了matlab和C+等語言進(jìn)行編程，成功解決了三個問題，是一個可行的數(shù)學(xué)模型。但是，此模型在應(yīng)運(yùn)分治法人為地得到局部最優(yōu)解的過程中容易產(chǎn)生錯誤，且計(jì)算量較大，需要強(qiáng)大的編程能力。六、參考文獻(xiàn)1管志忠.典型數(shù)模與matlab編程.

37、中國科學(xué)技術(shù)大學(xué)出版社.2010.62周永正.數(shù)學(xué)建模.同濟(jì)大學(xué)出版社.2010.8七、部分程序代碼1.用Floyd算法計(jì)算最短距離，以文件的形式輸出，實(shí)現(xiàn)代碼（matlab）n=49; %總共49個點(diǎn)A=zeros(n,n);for i=1:n for j=1:n if(i=j) A(i,j)=0; else A(i,j)=100000; end endend A(1,2)=120;A(1,3)=270;A(1,5)=540;A(1,6)=799;A(1,15)=420;A(1,40)=844;A(2,3)=370;A(2,15)=360;A(3,4)=210;A(3,15)=311;A(3

38、,16)=440;A(4,5)=530;A(4,16)=430;A(4,27)=630;A(4,30)=760;A(5,30)=720;A(5,40)=1521;A(5,47)=186;A(6,7)=330;A(6,39)=387;A(6,40)=727;A(7,8)=230;A(7,40)=429;A(7,41)=347;A(8,42)=819;A(9,10)=280;A(9,11)=190; A(9,15)=840;A(10,11)=279;A(10,12)=160;A(10,14)=660;A(10,15)=680; A(10,38)=598;A(10,43)=325;A(11,13)=

39、880;A(11,14)=640;A(11,37)=153; A(12,14)=610;A(12,16)=650;A(12,17)=540;A(12,43)=435;A(13,14)=680;A(13,19)=1020;A(13,32)=490;A(13,36)=266;A(13,37)=592;A(14,17)=270;A(14,18)=640;A(14,19)=860;A(15,16)=430;A(15,43)=349;A(15,38)=361;A(16,17)=540;A(16,27)=550;A(16,43)=473;A(16,44)=285;A(17,18)=380;A(17,44)

40、=406;A(17,45)=362;A(18,19)=780;A(18,24)=1010;A(18,45)=508;A(18,48)=664;A(19,20)=710;A(19,21)=580;A(19,34)=130;A(19,35)=127;A(19,36)=688;A(20,21)=560;A(20,24)=650;A(20,25)=820;A(20,48)=305;A(21,49)=270;A(22,23)=340;A(22,24)=490;A(22,25)=1090;A(22,27)=910;A(22,45)=795;A(23,25)=990;A(23,26)=2170;A(23,2

41、7)=920;A(24,25)=650;A(24,48)=560;A(25,26)=2320;A(26,29)=1940;A(26,31)=2672;A(27,28)=700;A(27,30)=640;A(27,44)=637;A(27,46)=304;A(28,29)=230;A(28,30)=500;A(28,31)=1980;A(30,47)=554;A(33,35)=36;A(35,36)=591;A(38,43)=368;A(40,41)=304;A(40,42)=929;A(41,42)=669;A(44,45)=466;A(46,47)=541;for j=1:n for i=1

42、:j-1 A(j,i)=A(i,j); %使對稱 endend m,n=size(A);B=zeros(m,n);B=A;for k=1:n for i=1 :n for j=1:n t=B(i,k)+B(k,j); if t<B(i,j) B(i,j)=t; end end endend%輸出距離矩陣fid=fopen('distance.txt','w'); for i=1:n for j=1:n fprintf(fid,'%4d ',B(i,j);s end fprintf(fid,'n'); end fclose(f

43、id);2.將距離權(quán)值轉(zhuǎn)換為成本權(quán)值的程序代碼：#include<fstream>#include<iostream>#include<mem.h>using namespace std;ifstream fin_dem("xuqiu.txt");ifstream fin_dis("distance.txt");ofstream fout("APSP.out");int main() int a,b,c; int xuqiu49; int juli4949; int money4949; for(i

44、nt i=0;i<49;i+) xuqiui=0; for(int j=0;j<49;j+) juliij=0; for(int i=0;i<49;i+) fin_dem>>a; xuqiui=a; cout<<xuqiui; for(int i=0;i<49;i+) for(int j=0;j<49;j+) fin_dis>>b; juliij=b; cout<<b; for(int i=0;i<49;i+) for(int j=0;j<49;j+) moneyij=juliij*xuqiuj*0.5;

45、 fout<<moneyij<<" " fout<<endl; return 0;3.輸入任意的8個城市，輸出總的費(fèi)用和每個供應(yīng)中心到相應(yīng)被供應(yīng)點(diǎn)的費(fèi)用：#include<fstream>#include<iostream>#include<string>#define N 8#define M 49using namespace std;ifstream fin_dem("benjin.txt");ifstream fin_dis("APSP.out");ifstream fin_