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

供給網(wǎng)絡(luò)的建立與道路破壞問題摘要本文針對供給鏈網(wǎng)絡(luò)的建立與道路破壞問題，運(yùn)用Floyd算法、0-1整數(shù)規(guī)劃、遍歷法等多種方法，借助Lingo、Matlab等軟件，綜合分析了49個城市的供給鏈網(wǎng)絡(luò)的相關(guān)數(shù)據(jù)，建立了線性規(guī)劃模型、影響度模型以及優(yōu)先選擇模型，得到了城市運(yùn)輸供給鏈中最優(yōu)供給點(diǎn)及破壞道路時破壞程度不同情況下的最優(yōu)破壞方案。針對問題一，由于49個城市中*些城市的建站費(fèi)用過高，不適合建立供給點(diǎn)。將這些城市剔除后共有28個城市可以作為供給點(diǎn)。通過題中所給的數(shù)據(jù)運(yùn)用floyd算法，借助MATLAB軟件求出每個城市到其他城市的最短距離，然后寫出目標(biāo)函數(shù)及相應(yīng)的約束條件,采用0-1整數(shù)規(guī)劃法建立現(xiàn)行規(guī)劃模型,使用Lingo軟件得到建立8個供給點(diǎn)費(fèi)用最少，供給點(diǎn)城市編號分別為4、7、11、20、23、26、28、45。針對問題二，研究破壞道路的方案，使對方平均總費(fèi)用增加25%,將被破壞的道路間的距離改成一個很大的值，近似看作這條路是不通的。運(yùn)用floyd算法，借助MATLAB軟件求出道路破壞后供給點(diǎn)城市與各城市之間的最短距離，再建立目標(biāo)函數(shù)及約束條件，建立影響度模型，運(yùn)用Lingo軟件得出道路破壞后的最短運(yùn)輸路線，進(jìn)一步得到破壞后的運(yùn)輸費(fèi)用，與破壞前費(fèi)用相減可以得到道路破壞后增加的費(fèi)用，當(dāng)使總費(fèi)用增加25%時最少破壞道路的序列號為1、2、4、5、7、9，總費(fèi)用增加11577797元。針對問題三，主要研究的是破壞盡可能少的道路來使對方平均總費(fèi)用至少增加100%，供給點(diǎn)的基建費(fèi)用是固定不變的，決定平均總費(fèi)用的只是運(yùn)輸?shù)钠骄傎M(fèi)。所以求運(yùn)輸?shù)钠骄M(fèi)用其實(shí)就是根據(jù)相應(yīng)的概率分布求運(yùn)輸費(fèi)用的期望值。由于有8條道路可以被破壞，所以可以給出255種道路破壞方案。由于破壞方選取一些道路進(jìn)展破壞時，這些道路不一定被破壞，而是服從一定的概率分布，可以根據(jù)上面的分析建立優(yōu)先選擇模型，運(yùn)用MATLAB編寫相應(yīng)的求平均總費(fèi)用的程序來求出各種方案的平均總費(fèi)用，得出破壞道路的序列號為1、2、4、5、7、9，平均總費(fèi)用為1.059×107元。最后，對本文解決問題的方法和模型進(jìn)展推廣，分析了在其他領(lǐng)域的應(yīng)用，并且綜合評價了模型的優(yōu)缺點(diǎn)。關(guān)鍵詞：供給鏈網(wǎng)絡(luò)；道路破壞；0-1整數(shù)規(guī)劃；Floyd算法；LINGO§1問題的重述1.1背景知識全球化競爭的加劇促使越來越多的企業(yè)開場采用供給鏈管理策略，以實(shí)現(xiàn)企業(yè)的一體化管理。供給鏈?zhǔn)且粋€復(fù)雜的網(wǎng)狀構(gòu)造系統(tǒng)，每一局部都面臨著各種潛在的風(fēng)險，任何一局部出現(xiàn)問題都可能給整個供給鏈帶來嚴(yán)重的影響，因此如何分析、評價和提高供給鏈系統(tǒng)的可靠性變得日益迫切。設(shè)施系統(tǒng)是供給鏈的核心，在供給鏈研究中有著極其重要的地位。在一個設(shè)施系統(tǒng)中，*些個設(shè)施由于自然災(zāi)害或者其他因素的影響可能失效，例如911恐懼襲擊事件、2004年的印度洋海嘯、2008年的汶川地震等都對諸多行業(yè)的設(shè)施系統(tǒng)造成了嚴(yán)重的破壞?，F(xiàn)有*物流公司要在全國各城市之間建立供給鏈網(wǎng)絡(luò)。需要選定局部城市作為供給點(diǎn)，將貨物運(yùn)輸?shù)礁鞒鞘?。通常每個供給點(diǎn)的貨物是充足的，可以充分滿足相應(yīng)城市的需求。設(shè)該公司考慮共考慮49個城市的網(wǎng)絡(luò)，并假定作為供給點(diǎn)的城市其供給量可以滿足有需要的城市的需求?，F(xiàn)將要建立一個供給網(wǎng)絡(luò)，為各城市提供貨物供給。貨物運(yùn)輸利用汽車進(jìn)展公路運(yùn)輸，設(shè)每噸每公里運(yùn)輸費(fèi)用為0.5元。1.2相關(guān)數(shù)據(jù)1.49個城市的網(wǎng)絡(luò)坐標(biāo)〔詳見表1〕；2.城市之間的道路連接關(guān)系〔詳見表2〕；3.每個城市建立配送中心的固定費(fèi)用和需求量〔詳見表3〕；4.可破壞的道路〔詳見表4〕。1.3具體問題1.現(xiàn)在要從49個城市中選取局部城市做為供給點(diǎn)供給本城市及其它城市。建立供給點(diǎn)會花費(fèi)固定費(fèi)用，從供給點(diǎn)運(yùn)輸?shù)叫枨簏c(diǎn)會產(chǎn)生運(yùn)輸費(fèi)用，要使總費(fèi)用最小，問建立多少個供給點(diǎn)最好。給出選中作為供給點(diǎn)的城市，并給出每個供給點(diǎn)供給的城市。同時根據(jù)坐標(biāo)作出每一個供給點(diǎn)到需求點(diǎn)的連接圖。2.假定有*組織對該供給網(wǎng)絡(luò)的道路進(jìn)展破壞。并非所有的道路都可以被破壞，可破壞的道路見表4。當(dāng)*條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過該道路的只有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是使對方總費(fèi)用增加25%，而每破壞一條道路都需要本錢和代價，因此需要破壞最少的道路。問破壞方選取哪幾條線路進(jìn)展破壞。給出具體的破壞道路和總費(fèi)用。3.假定各道路能否被破壞具有隨機(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對問題的總體分析通過對題目所提供的49個城市的運(yùn)輸供給鏈數(shù)據(jù)進(jìn)展分析，運(yùn)用Floyd算法求出每個城市到其他城市的最短距離，再根據(jù)題意列出目標(biāo)函數(shù)及相關(guān)的約束條件，利用Lingo程序求解出最優(yōu)解。對于對供給網(wǎng)絡(luò)的道路進(jìn)展破壞問題中，由于破壞程度不同，即破壞的成功率并不一定是百分之百，當(dāng)破壞是百分之百時，把該條路的距離改成一個很大的值，將得到的新數(shù)據(jù)運(yùn)用Floyd算法求出每個城市到其他城市的最短距離，然后給出相應(yīng)的約束條件建立模型求滿足條件的最優(yōu)解。假設(shè)破壞不是百分之百時，即破壞服從一定的概率時，根據(jù)相應(yīng)的概率分布求運(yùn)輸費(fèi)用即為運(yùn)輸?shù)钠骄M(fèi)用，利用Matlab程序得到滿足條件的最優(yōu)解。2.2具體問題的分析⑴對問題1的分析問題一研究的主要是從49個城市中找到適當(dāng)數(shù)量的供給點(diǎn)來使運(yùn)輸費(fèi)用和基建費(fèi)用的總費(fèi)用到達(dá)最低。我們可以先通過題中所給的數(shù)據(jù)運(yùn)用floyd算法求出每個城市到其他城市的最短距離，然后給出相應(yīng)的約束條件,運(yùn)用Lingo軟件進(jìn)展求解,即可得出確定的供給點(diǎn),使總費(fèi)用到達(dá)最低。最后根據(jù)選中作為供給點(diǎn)的城市的坐標(biāo)作出每一個供給點(diǎn)到需求點(diǎn)的連接圖。⑵對問題2的分析問題二主要研究的是破壞盡可能少的道路來使總費(fèi)用增加25%,于是可以假設(shè)當(dāng)*條道路被破壞時，把該條道路的距離改成一個很大的值，這樣就可以近似的看成這個道路是不通的。當(dāng)*條道路被破壞時，根據(jù)新得到的數(shù)據(jù)用floyd算法重新求出各城市到其他城市的最短距離，然后求出其他沒有供給點(diǎn)的城[2]市距離最近的供給點(diǎn)及其之間的距離，最后就可以求出當(dāng)該道路被破壞時的總費(fèi)用。然后給出相應(yīng)的約束條件，建立模型求當(dāng)總費(fèi)用增加25%時破壞的道路數(shù)量最少的情況，這樣就求出了最少的道路數(shù)和具體的道路及總費(fèi)用。⑶對問題3的分析問題三主要研究的是給出適當(dāng)?shù)钠茐牡缆返姆桨福瑢Ψ狡骄傎M(fèi)用至少增加100%，平均總費(fèi)用由建造供給點(diǎn)的基建費(fèi)用和各種情況下運(yùn)輸?shù)钠骄M(fèi)用組成，當(dāng)給出道路破壞的方案后，由于8個供給點(diǎn)是固定的，所以建造供給點(diǎn)的基建費(fèi)用是不變的，變化的是運(yùn)輸?shù)钠骄M(fèi)用。由于破壞方選取一些道路進(jìn)展破壞時，這些邊不一定被破壞，而是服從一定的概率分布。所以求運(yùn)輸?shù)钠骄M(fèi)用其實(shí)就是根據(jù)相應(yīng)的概率分布求運(yùn)輸費(fèi)用的期望值。由于有6條道路可以被破壞，所以可以給出64種道路破壞方案。由于破壞方選取一些道路進(jìn)展破壞時，這些道路不一定被破壞，而是服從一定的概率分布，所以有種情況，在種的情況下運(yùn)輸費(fèi)用的期望值就是運(yùn)輸?shù)钠骄傎M(fèi)用。根據(jù)上面的分析建立模型，求出各種方案的平均總費(fèi)用，最后就可以得到相應(yīng)的方案使得在破壞道路最少的情況下平均總費(fèi)用到達(dá)最大?！?模型的假設(shè)〔1〕假設(shè)各道路能否被破壞具有隨機(jī)性；〔2〕假定所有城市之間均可以通過公路運(yùn)輸進(jìn)展物資運(yùn)輸；〔3〕假設(shè)問題二中對任意道路破壞的成功率為百分之百；〔4〕假設(shè)各城市的需求量固定不變；〔5〕假設(shè)在運(yùn)輸網(wǎng)絡(luò)簡單設(shè)期間和*組織破壞期間不會遭遇地震，海嘯等自然災(zāi)害的影響；〔6〕所有數(shù)據(jù)來源真實(shí)可靠?！?名詞解釋與符號說明4.1名詞解釋1.供給鏈網(wǎng)絡(luò)：供給鏈網(wǎng)絡(luò)是由與核心企業(yè)相連的成員組織構(gòu)成的，這些組織直接或間接與他們的供給商或客戶相連，從起始端到消費(fèi)端。必須分類并確定哪些成員對公司以及供給鏈的成功起著決定作用，以便對它們給予關(guān)注和合理分配資源。2.配送中心[1]：是一種物流結(jié)點(diǎn)，它不以貯藏倉庫的這種單一的形式出現(xiàn)，而是發(fā)揮配送職能的流通倉庫。也稱做基地、據(jù)點(diǎn)或流通中心。配送中心的目的是降低運(yùn)輸本錢、減少銷售時機(jī)的損失，為此建立設(shè)施、設(shè)備并開展經(jīng)營、管理工作[1]。3.floyd算法：floyd算法又稱為弗洛伊德算法、插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。通過一個圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣，從圖的帶權(quán)鄰接矩陣開場，遞歸地進(jìn)展n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；以此類推，最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點(diǎn)到j(luò)號頂點(diǎn)的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點(diǎn)矩陣path來記錄兩點(diǎn)間的最短路徑。4.2符號說明符號符號說明0-1變量，判斷第i個城市是否建立供給點(diǎn)0-1變量，判斷從第i個城市是否給第j個城市配送貨物在第i個城市建立供給點(diǎn)的固定費(fèi)用第j個城市的貨物需求量第i個城市到第j個城市的最短路徑代表i條可以破壞的路0-1變量，判斷是否破壞第i條路道路破壞前的總費(fèi)用道路破壞后的總費(fèi)用道路破壞前后的增加的總費(fèi)用平均總費(fèi)用運(yùn)輸?shù)钠骄M(fèi)用8個供給點(diǎn)基建費(fèi)用§5模型的建立與求解5.1線性規(guī)劃模型1.模型的分析對于問題一，研究的主要是從49個城市中找到適當(dāng)數(shù)量的供給點(diǎn)及其位置來使運(yùn)輸費(fèi)用和基建費(fèi)用的總費(fèi)用到達(dá)最低。總費(fèi)用由運(yùn)輸費(fèi)用和基建費(fèi)用組成,隨著選取供給點(diǎn)的數(shù)量的增多,運(yùn)輸費(fèi)用減小,但基建費(fèi)用會隨之增加,很明顯,這是一個0-1規(guī)劃問題。我們先通過題中所給的數(shù)據(jù)運(yùn)用floyd算法求出每個城市到其他城市的最短距離，然后給出相應(yīng)的約束條件,運(yùn)用Lingo軟件進(jìn)展求解,即可得出確定的供給點(diǎn),使總費(fèi)用到達(dá)最低。最后根據(jù)選中作為供給點(diǎn)的城市的坐標(biāo)作出每一個供給點(diǎn)到需求點(diǎn)的連接圖。2.模型的準(zhǔn)備從49個城市中選取n個作為供給點(diǎn)，一共是有種方案，但由于*些城市的建站費(fèi)用過高，不適合建立供給點(diǎn)，我們將這些城市剔除后共有28個城市可以作為供給點(diǎn)，再運(yùn)用MATLAB軟件編程〔見程序1〕，畫出各城市之間道路關(guān)系圖如圖1所示〔圖中1-49為各城市編號〕。圖1各城市之間道路關(guān)系圖3.模型的建立通過對問題的分析與數(shù)據(jù)的整理可以根據(jù)Floyd算法[2-3]求出任意兩個城市之間的最短公路長度，得到一個49×49的矩陣C[i][j]，根據(jù)表2中的數(shù)據(jù)對C[i][j]進(jìn)展初始化，假設(shè)從i市到j(luò)市有直達(dá)路徑，則將表格中的數(shù)據(jù)賦給C[i][j],否則將付給C[i][j]，然后用Floyed算法求出從i市到j(luò)市的最短路徑。Floyed算法思想如下：〔1〕i=1;j=1;k=1;〔2〕u=C[i][k]+C[k][j],假設(shè)u<C[i][j],則令C[i][j]=u，否則直接轉(zhuǎn)到3?！?〕假設(shè)j<49,則令j=j+1，轉(zhuǎn)到2；否則轉(zhuǎn)到4。〔4〕假設(shè)i<49，則令i=i=1，轉(zhuǎn)到2；否則轉(zhuǎn)到5?！?〕假設(shè)k<49，則令k=k+1，j=1，i=1，轉(zhuǎn)到2；否則輸出。通過這種算法運(yùn)用MATLAB軟件編程〔見程序2〕，最后得到的矩陣C[i][j]就是任意兩個城市i和j之間的最短路徑，得到一個的數(shù)據(jù)陣，我們截取局部〔10×10〕的數(shù)據(jù)如表1所示。表1各城市之間最短距離城市編號1234567891010120270480540799112913591260109421200370580660919124914791200103432702700210740106913991629115198544805802100530127916091839136111955540660740530013391669189918001634679991910691279133903305602059189371129124913991609166933002302389222381359147916291839189956023002619245391260120011511361180020592389261902801010941034985119516341893222324532800運(yùn)用Floyd算法求出每個城市到其他城市的最短距離后，然后給出相應(yīng)的約束條件如下：1.第j個城市只能承受一個供給點(diǎn)給它提供貨物，即：其中l(wèi)(i,j)判斷第i個城市是否給第j個城市提供貨物供給。2.對于任意一個城市i，假設(shè)不在該城市建配送點(diǎn)，則*(i)=0且l(i,j)0，因此可得約束條件：l(i,j)*(i)；假設(shè)在該城市建配送點(diǎn)，則*(i)=1且l(i,j)0或1，因此也可得約束條件：l(i,j)*(i)。綜上，我們有約束條件：其中*(i)表示是否在第i個城市建立供給點(diǎn)。而總費(fèi)等于建立供給點(diǎn)的花費(fèi)固定費(fèi)用與從供給點(diǎn)運(yùn)輸?shù)叫枨簏c(diǎn)產(chǎn)生運(yùn)輸費(fèi)用之和，現(xiàn)在我們要求建立供給點(diǎn)的數(shù)量使使總費(fèi)用最小。即：其中D(i,j)表示第i個城市到底j個城市的最短路徑，h(i)表示在第i個城市建立供給點(diǎn)的固定費(fèi)用。于是我們可以建立0-1整數(shù)規(guī)劃模型[4]，綜合上述約束條件有：用Lingo軟件編寫程序〔見程序3〕求解得出結(jié)果，如表2所示：表2建立供給點(diǎn)城市及其相應(yīng)需求點(diǎn)建供給點(diǎn)城市為提供貨物城市41,2,3,4,5,15,16,27,46,4776,7,8,39,40,41,42119,10,11,12,13,32,36,37,38,432019,20,21,24,25,33,34,35,48,492322,2326262828,29,30,314514,17,18,44,45由lingo軟件得出的結(jié)果可知，可以作為供給點(diǎn)的城市編號為4、7、11、20、23、26、28、45，運(yùn)用matlab軟件編寫相應(yīng)的程序〔見程序4〕，畫出了49個城市中可以作為供給點(diǎn)以及不可以作為供給點(diǎn)城市〔實(shí)心點(diǎn)代表可以作為供給點(diǎn)的城市，空心點(diǎn)代表不可以作為供給點(diǎn)的城市〕，如圖2所示。圖2供給點(diǎn)城市以及不作為供給點(diǎn)城市再根據(jù)lingo軟件[5]得出的各供給點(diǎn)所對應(yīng)的供給的城市，可以利用matlab軟件結(jié)合幾何畫板畫出每個供給點(diǎn)城市到需要該供給點(diǎn)提供貨物的城市線路圖如圖3所示。圖3供給點(diǎn)到需求點(diǎn)路線圖其中實(shí)心點(diǎn)即為可以建供給點(diǎn)的城市，箭頭指向的點(diǎn)為承受貨物供給的城市。有的城市和供給點(diǎn)并不直接相連，可以按照箭頭所指的中轉(zhuǎn)城市進(jìn)展貨物供給。4.模型的求解運(yùn)用Floyed算法算出任意兩個城市之間的最短公路長度，再用lingo軟件求解得出建立8個供給點(diǎn)費(fèi)用最少，這8個供給點(diǎn)城市編號分別為4、7、11、20、23、26、28、45。5.2影響度模型1.模型的分析問題二主要研究的是破壞盡可能少的道路來使總費(fèi)用增加25%,于是可以假設(shè)當(dāng)*條道路被破壞時，把該條道路的距離改成一個很大的值，這樣就可以近似的看成這個道路是不通的。當(dāng)*條道路被破壞時，根據(jù)新得到的數(shù)據(jù)用floyd算法重新求出各城市到其他城市的最短距離，求出其他沒有供給點(diǎn)的城市距離最近的供給點(diǎn)及其之間的距離，最后就可以求出當(dāng)該道路被破壞時的總費(fèi)用。然后給出相應(yīng)的約束條件，建立模型求當(dāng)總費(fèi)用增加25%時破壞的道路數(shù)量最少的情況，這樣就求出了最少的道路數(shù)和具體的道路及總費(fèi)用，程序流程圖如圖4所示。圖4程序流程圖2.模型的準(zhǔn)備道路被破壞后，我們把相應(yīng)的道路距離改為一個很大的值〔例如1000000000〕，這樣當(dāng)我們在用floyd算法求最短路時就可以把這條道路繞過去，就可以近似把道路看成是被破壞的。從建立的道路關(guān)系圖4中可以直觀的看出到達(dá)城市49的路只有一條，從城市21出發(fā)，因此如果這條路被破壞的話，城市49將得不到供給，因此這條道路不能被破壞，這樣可以被破壞的路就只有8條，如表3所示。表3能夠破壞的道路道路序號城市1城市21452343740410115192071745920213.模型的建立當(dāng)*條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過該道路的只有改道，但總是沿最短路運(yùn)輸，因此需要破壞最少的道路，即：其中r(i)代表8條可以被破壞的路，y(i)為0-1變量，當(dāng)y(i)為1時，代表破壞這條路；y(i)為0時，不破壞這條路。minR為可破壞道路數(shù)的最小數(shù)量。由于破壞方選擇的策略是使對方總費(fèi)用增加25%，即：其中S1為道路破壞前的總費(fèi)用，S2為道路破壞后的總費(fèi)用，被破壞的道路數(shù)小于8，即：，建立線性規(guī)劃模型有：由Lingo軟件求解可以得出被破壞的道路序列號以及被破壞的道路如表4所示，表4被破壞的道路序號被破壞的道路序號城市1城市2被破壞的道路1454→52344→34101111→105192020→197174545→179202120→21當(dāng)被破壞的道路只有一條時一共有8種情況，當(dāng)破壞的道路有兩條時，一共有種情況，依次類推，由于情況比擬少，可以用遍歷法把所有的情況及其總費(fèi)用求出來，再對數(shù)據(jù)進(jìn)展分析比照，找到當(dāng)總費(fèi)用比破壞前費(fèi)用增加25%時破壞的道路數(shù)最少的情況。首先采用Floyd算法，運(yùn)用MATLAB軟件針對被破壞的道路中供給點(diǎn)城市的貨物運(yùn)輸路線進(jìn)展處理，其中破壞的道路影響的供給點(diǎn)城市有4〔〕、11〔〕、20〔〕、45〔〕。分別對各受影響的供給點(diǎn)進(jìn)展分析，當(dāng)受影響的供給點(diǎn)為4〔〕時，道路1、2被破壞后，供給點(diǎn)4〔〕向各城市供給的路線將發(fā)生變化，運(yùn)用Floyd算法算出當(dāng)?shù)缆?、2被破壞后供給點(diǎn)4到其提供貨物的城市的最短距離，得出道路被破壞后的運(yùn)輸路線如表5所示。表5道路1、2破壞前后的運(yùn)輸?shù)缆肥苡绊懙墓┙o點(diǎn)道路破壞前的運(yùn)輸?shù)缆返缆菲茐暮蟮呢浳镞\(yùn)輸?shù)缆?4→3→14→16→3→14→3→24→16→15→24→54→30→54→3→154→16→154→5→474→30→47當(dāng)?shù)缆?被破壞時，供給點(diǎn)城市11〔〕的供貨道路受到影響，采用Floyd算法求出當(dāng)?shù)缆?1→10被破壞時供給點(diǎn)城市11〔〕到各需求城市的最短路徑，得出道路4被破壞后供給點(diǎn)城市11〔〕的運(yùn)輸路線如表6所示。表6道路4破壞后的運(yùn)輸?shù)缆肥苡绊懙墓┙o點(diǎn)道路破壞前的運(yùn)輸?shù)缆返缆菲茐暮蟮呢浳镞\(yùn)輸?shù)缆?111→1011→9→1011→10→1211→9→10→1211→10→3811→9→10→3811→10→4311→9→10→43當(dāng)?shù)缆?、9被破壞時供給點(diǎn)城市20〔〕的供貨道路受到影響，采用Floyd算法求出當(dāng)?shù)缆?、9被破壞時供給點(diǎn)城市20〔〕到各需求城市的最短路徑，得出道路5、9被破壞后供給點(diǎn)城市20〔〕的運(yùn)輸路線如表7所示。表7道路5、9破壞后的運(yùn)輸?shù)缆肥苡绊懙墓┙o點(diǎn)道路破壞前的運(yùn)輸?shù)缆返缆菲茐暮蟮呢浳镞\(yùn)輸?shù)缆?020→19→3320→48→18→19→3320→19→3420→48→18→19→3420→19→3520→48→18→19→3520→1920→48→18→1920→2120→48→18→19→2120→21→4920→48→18→19→21→49當(dāng)?shù)缆?被破壞時供給點(diǎn)城市45〔〕的供貨道路受到影響，采用Floyd算法求出當(dāng)?shù)缆?被破壞時供給點(diǎn)城市45〔〕到各需求城市的最短路徑，得出道路7被破壞后供給點(diǎn)城市45〔〕的運(yùn)輸路線如表8所示。表8道路7破壞后的運(yùn)輸?shù)缆肥苡绊懙墓┙o點(diǎn)道路破壞前的運(yùn)輸?shù)缆返缆菲茐暮蟮呢浳镞\(yùn)輸?shù)缆?545→1745→18→1745→17→1445→18→14運(yùn)用MATLAB軟件結(jié)合幾何畫板將改道后的運(yùn)輸?shù)缆穲D畫出如圖5所示，其中較細(xì)的實(shí)線表示不需要改道的運(yùn)輸路線，較粗的虛線表示改道后的運(yùn)輸路線；虛線連接的點(diǎn)表示需要作為中轉(zhuǎn)點(diǎn)的城市，虛線的起點(diǎn)表示供給點(diǎn)，箭頭指向的點(diǎn)表示被供給點(diǎn)。圖5改道后的運(yùn)輸?shù)缆穲D破壞方選取的策略是使對方總費(fèi)用增加25%且要求破壞的道路最少，將各受影響的供給點(diǎn)道路破壞前的運(yùn)輸費(fèi)用和道路破壞后的運(yùn)輸費(fèi)用整合如表9所示。表9道路破壞本錢增加情況道路序號增加本錢原本錢百分比19130891971181%21081168.5919711812%426931091971183%538162591971184%734705291971184%9186629.591971182%4.模型的求解觀察表10道路破壞的線路，因?yàn)槠茐姆降牟呗允鞘箤Ψ娇傎M(fèi)用增加25%，所以可利用表10中的百分比〔道路破壞后，運(yùn)輸增加的本錢與原本錢的百分比〕進(jìn)展線性規(guī)劃，從而得到最優(yōu)的結(jié)果。利用Lingo程序求解，得到破壞方的最正確破壞方案，即破壞路線的序列號為1、2、4、5、7、9，破壞的道路如圖5中虛線所示：圖5道路破壞路線圖道路被破壞后，造成費(fèi)用增加，參照表9可得最終費(fèi)用為9197118+2716340.5=11577797元。5.3優(yōu)先選擇模型1.模型的分析針對該問題可以先計算出道路破壞之前的運(yùn)輸費(fèi)用，道路受到破壞的平均運(yùn)輸費(fèi)用，道路破壞之前的運(yùn)輸總費(fèi)用，道路破壞后的運(yùn)輸總費(fèi)用。列出破壞前后的運(yùn)輸費(fèi)用應(yīng)該滿足的數(shù)學(xué)關(guān)系式，分別對64種情況進(jìn)展討論，得到在破壞最少的道路前提下，使得對方平均總費(fèi)用最大。程序流程圖為：2.模型的準(zhǔn)備①運(yùn)輸時產(chǎn)生的費(fèi)用可按照各種情況下的平均費(fèi)用來考慮。如果破壞方選取的策略是使對方平均總費(fèi)增加最大，同時需要破壞最少的道路。道路受破壞的平均費(fèi)用為：，其中表示道路破壞之前的運(yùn)輸總費(fèi)用，表示道路破壞后的運(yùn)輸總費(fèi)用。道路破壞之前的運(yùn)輸費(fèi)用：，道路受到破壞的平均運(yùn)輸費(fèi)用應(yīng)滿足：其中是對方平均總費(fèi)用的增加率，在〔〕越小的前提下越大越好②24、25兩城市道路破壞，供給點(diǎn)城市對其供給并未受到影響；21、49兩城市的道路破壞后49將得不到供給，對這兩條道路選擇破壞不會對對方平均總費(fèi)用產(chǎn)生影響，因而這兩條道路在道路破壞方案選擇中不予考慮。對除24、25，21、49兩條道路之外的其余7條道路的破壞前后的平均總費(fèi)用例表如下，見表10。表10道路破壞前后平均總費(fèi)用受破壞的道路破壞前的運(yùn)輸費(fèi)用道路破壞改道破壞后的平均費(fèi)用4→52427064→30→53075894→30→474→3735221.54→16→3→115556704→16→15→24→16→157→401359937→41→40103183.511→1081645011→9→10108324911→9→10→1211→9→10→3811→9→10→4320→19648495.520→48→18→19→33157060820→48→18→19→3420→48→18→19→3520→48→18→1945→1730737445→18→1765442645→18→1420→216650520→48→18→19→21186629.520→48→18→19→21→49從表1可以看出7、40兩城市的道路破壞前的運(yùn)輸費(fèi)用為135993，破壞后的運(yùn)輸費(fèi)用為103183.5，破壞前后的運(yùn)輸費(fèi)用反而減少，不能到達(dá)道路破壞的效果。③根據(jù)對六條道路破壞前后的平均總費(fèi)用進(jìn)展計算列表如下，見表11。表11破壞道路后增加的費(fèi)用受破壞的道路破壞前運(yùn)輸費(fèi)用道路破壞的平均費(fèi)用增加的費(fèi)用4→5242706281635.838929.84→3735221.51309535.45574313.9511→10816450949849.5133399.520→19648495.51155657.38507161.8845→1730737448090017352620→2166505138579.772074.73.模型的建立根據(jù)模型的分析及準(zhǔn)備可以得出，可以破壞的道路有六條，再對六條道路分別進(jìn)展考慮共有64種情況，建立模型[8]，即：如果同時破壞了條道路〔〕，則破壞之前的平均總費(fèi)用等于：破壞條道路之后的平均增加的總費(fèi)用為:等于每條到道路的增加的平均費(fèi)用之和。對64種情況進(jìn)展討論，找出滿足在最小且越大的情況下，選擇破壞哪幾條道路。不同破壞的道路個數(shù)對應(yīng)的六組平均總費(fèi)用中，取每組平均總費(fèi)用中的最大值，如表12所示。表12平均總費(fèi)用最大值破壞邊的個數(shù)平均總費(fèi)用中的最大值10.953935621.0163829231.02878682541.03975458251.05048708261.0590422371.06062564581.060625645根據(jù)表3用MATLAB作出破壞道路的個數(shù)與平均總費(fèi)用最大值的走勢圖〔MATLAB作圖程序見程序5〕如下：圖6平均總費(fèi)用走勢圖4.模型的求解根據(jù)圖1分析，隨著破壞的道路的數(shù)量的增加，平均總費(fèi)用的最大值大體上呈現(xiàn)出一個上升的趨勢，但當(dāng)破壞的道路數(shù)為6時，平均總費(fèi)用到達(dá)最大值為：元。因而選擇破壞的道路序號為：1、2、4、5、7、9?！?誤差分析優(yōu)先選擇模型中[6]，根據(jù)計算的道路受破壞的平均費(fèi)用存有一定的誤差。根據(jù)表11中的數(shù)據(jù)結(jié)合表13，道路破壞后的運(yùn)輸費(fèi)用表表13道路破壞后的運(yùn)輸費(fèi)用表受破壞的道路破壞后的費(fèi)用4→53075894→3155567011→10108324920→19157060845→1765442620→21186629.5利用E*CEL對道路破壞前后及增加的運(yùn)輸費(fèi)用作圖。圖7道路破壞前后及增加的運(yùn)輸費(fèi)用圖利用MATLAB對道路破壞前后及道路破壞的平均費(fèi)用作圖〔MATLAB作圖[7]程序見程序6〕圖8道路破壞前后及道路破壞的平均費(fèi)用圖圖8中的藍(lán)色折線條表示道路破壞的平均運(yùn)輸總費(fèi)用，高于圖7中黃色折線條表示的道路破壞前后的增加費(fèi)用，低于道路破壞前的費(fèi)用，因而不可防止的存有一定誤差?！?模型的評價與推廣6.1模型的評價1.優(yōu)點(diǎn)(1)在解決最優(yōu)問題時，分別運(yùn)用MATLB和Lingo兩個語言來實(shí)現(xiàn)模型的運(yùn)算，兩種語言很好的結(jié)合解決了問題；(2)在解決任意兩城市之間最短距離時采用Floyd算法，準(zhǔn)確度很高；(3)論文中對數(shù)據(jù)進(jìn)展處理做了很多圖表，使結(jié)果簡單直觀；(4)運(yùn)用多種數(shù)學(xué)軟件〔如MATLAB、Lingo〕，取長補(bǔ)短，使計算結(jié)果更加準(zhǔn)確、明晰。(5)從破壞者角度出發(fā)，考慮炸路的價值問題，優(yōu)先炸價值比擬高的路，模型具有完備性和通用性，實(shí)用價值高。2.缺點(diǎn)(1)在解決問題的過程，編程的比重相對于建立模型的比重偏大；(2)對一些數(shù)據(jù)進(jìn)展了必要的近似處理，會帶來一定的誤差。6.2模型的推廣在解決第一問時，我們嘗試了窮舉法，編寫了matlab程序，但計算量太大，等待結(jié)果的時間很長。后來我們結(jié)合約束條件，運(yùn)用lingo軟件，把它轉(zhuǎn)化為0-1規(guī)劃問題，使模型大大簡化，大大縮短了運(yùn)行的時間。解決此問題的模型可以推廣到交巡警效勞平臺設(shè)置與調(diào)度優(yōu)化問題中，交巡警效勞平臺的管轄圍分配及警力調(diào)度問題是一個具有實(shí)際背景的新課題，其本質(zhì)是優(yōu)化問題。涉及的主要知識背景為圖論、整數(shù)規(guī)劃等，可利用最短路徑、最優(yōu)指派等方法來求解。主要思想為根據(jù)實(shí)際背景設(shè)置約束條件，求解最優(yōu)目標(biāo)值，進(jìn)而給出滿足多個目標(biāo)的最正確方案。與該論文所用方法不謀而合。參考文獻(xiàn)[1]百度百科.配送中心，baike.baidu./link[2]華友．運(yùn)籌學(xué)[M].中國科技大學(xué).2008.8.[3]中庚．實(shí)用運(yùn)籌學(xué)[M].清華大學(xué).2007.12.[4]桂元，黃己立．?dāng)?shù)學(xué)建模[M]．中國科技大學(xué).2008.8.[5]金星，薛毅．優(yōu)化模型與LINDO/LINGO軟件[M].清華大學(xué).2005.7.[6]冬梅；大學(xué)生數(shù)學(xué)建模競賽與教學(xué)策略研究；師大學(xué)2008。[7]胡守信,柏年,基于MATLAB的數(shù)學(xué)實(shí)驗(yàn),:科學(xué),2004.6第一版。[8]啟源等.數(shù)學(xué)模型〔第三版〕[M].高等教育.2003.8。附表1:表1各城市坐標(biāo)編號城市坐標(biāo)*(公里)坐標(biāo)Y(公里)編號城市坐標(biāo)*(公里)坐標(biāo)Y(公里)13639268526130416882**371226012730072030334882465282562224443326244429238123245呼市32382771302788250964196295631烏市1332330574312321032臺北4263106984386343033353870294177175634澳門3470696103918182135352673711406116303639289711237801788374201160313402911623840162285143676142239408926131537152322404296292016342920924140953374173507162442海拉爾451227101833941357433751205519343979944333418932029357604532291633213140450463054229022276915084730892749232545164348304491924277811744930532612523701025附表2:表2各公路段及里程表序號城市1城市2距離〔公里〕序號城市1城市2距離〔公里〕1121205215433492132705316175403155405416275504167995516434735115420561644285614084457171838072337058174440682153605917453629342106018197801031531161182410101131644062184550812455306318486641341643064192071014427630651921580154307606619341301653072067193512717540152168193668818547186692021560196733070202465020639387712025820216407277220483052278230732149270237404297422233402474134775222449025842819762225109026910280772227910279111907822457952891584079232599029101127980232621703010121608123279203110146608224256503210156808324485603310385988425262320341043325852629194035111388086263126723611146408727287003711371538827306403812146108927446373912166509027463044012175409128292304112434359228305004213146809328311980431319102094304755444133249095333536451336266963536591461337592973843368471417270984041304481418640994042929491419860100414266950151643010144454665115383611024647541附表3:表3各城市作配送中心的固定費(fèi)用城市費(fèi)用(元)需求量(噸)城市費(fèi)用(元)需求量(噸)11123584123226310085121000000000974279411847743733400965281963843234272080358291000000000194516948022330114760151610000000007153110000000002347457824753321000000000246810000000009893310000000007019100000000013913410000000005510663936624351000000000233114116166773610000000001741237012048737100000000056813580032636381000000000761145266804953910000000005831573324860340289104317168767367214110000000002041776060883442100000000027218585504642437204809481995577678644699200115020526680693452438084012110000000001564610000000002242224753203257471000000000217236846081126481000000000366242766403644910000000005525403560531〔注：1000000000表示該點(diǎn)不用，費(fèi)用太高〕附表4:表4破壞道路及概率道路序號城市1城市2破壞概率1450.62340.737400.45410110.5519200.55624250.4717450.5821490.6920210.6程序1:A=[3639371234883326323841964312438641773918406137804029367637153429350733943439293531402769254527782370130430072562238127881332426335383470352639284201401640894296409545123751333432293054308930443053;2685260124652444277129563210343017561821163017881162142223222092162413577997604501508164311741025168820302244232425093305106970269673797116032285261329203374271020551893163322902749919261];*=A(1,:);y=A(2,:);plot(*,y,'*')te*t(3639,2685,'1');te*t(3712,2601,'2');te*t(3488,2465,'3');te*t(3326,2444,'4');te*t(3238,2771,'5');te*t(4196,2956,'6');te*t(4312,3210,'7');te*t(4386,3430,'8');te*t(4177,1756,'9');te*t(3918,1821,'10');te*t(4061,1630,'11');te*t(3780,1788,'12');te*t(4029,1162,'13');te*t(3676,1422,'14');te*t(3715,2322,'15');te*t(3429,2092,'16');te*t(3507,1624,'17');te*t(3394,1357,'18');te*t(3439,799,'19');te*t(2935,760,'20');te*t(3140,450,'21')te*t(2769,1508,'22');te*t(2545,1643,'23');te*t(2778,1174,'24');te*t(2370,1025,'25');te*t(1304,1688,'26');te*t(3007,2030,'27');te*t(2562,2244,'28');te*t(2381,2324,'29');te*t(2788,2509,'30');te*t(1332,3305,'31');te*t(4263,1069,'32');te*t(3538,702,'33');te*t(3470,696,'34');te*t(3526,737,'35');te*t(3928,971,'36');te*t(4201,1603,'37');te*t(4016,2285,'38');te*t(4089,2613,'39');te*t(4296,2920,'40');te*t(4095,3374,'41');te*t(4512,2710,'42');te*t(3751,2055,'43');te*t(3334,1893,'44');te*t(3229,1633,'45');te*t(3054,2290,'46');te*t(3089,2749,'47');te*t(3044,919,'48');te*t(3053,261,'49');B=[11111122333444455566677789991010101010101111111212121213131313131414141515151616161617171718181818191919191920202020212222222222232323242425262627272727282828303335384040414446;235615403154151651627303040477394084041421011151112141538431314371416174314193236371718191638431727434418444519244548202134353621242548492324252745252627254826293128304446293031473536434142424547];[pq]=size(B);form=1:q;line([A(1,B(1,m))A(1,B(2,m))],[A(2,B(1,m))A(2,B(2,m))],'Marker','.','LineStyle','-')end程序2:n=49;a=zeros(n);a(1,2)=120;a(1,3)=270;a(1,5)=540;a(1,6)=799;a(1,15)=420;a(2,3)=370;a(2,15)=360;a(3,4)=210;a(3,15)=311;a(3,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)=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,38)=361;a(15,43)=349;a(16,17)=540;a(16,27)=550;a(16,43)=473;a(16,44)=285;a(17,18)=380;a(17,44)=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,27)=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;a=a+a';M=ma*(ma*(a))*n^2;%M為充分大的正實(shí)數(shù)a=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendenda,path程序3:sets:weizhi/1..49/:*,jijian,*uqiu;

assign(weizhi,weizhi):D,l;

endsets

data:

jijian=ole('C:\Users\Administrator\Desktop\數(shù)據(jù)源','cost');

*uqiu=ole('C:\Users\Administrator\Desktop\數(shù)據(jù)源','need');

D=ole('C:\Users\Administrator\Desktop\數(shù)據(jù)源','shortestpath');

enddata

min=sum(weizhi(k):*(k)*jijian(k))+sum(weizhi(j):sum(weizhi(i):*uqiu(j)*D(i,j)*l(i,j)))*0.5;

for(weizhi(i):bin(*(i)));

for(assign(i,j):bin(l(i,j)));

for(weizhi(j):sum(weizhi(i):l(i,j))=1);

for(weizhi(i):for(weizhi(j):l(i,j)<=*(i)));

End

程序4:A=[3639371234883326323841964312438641773918406137804029367637153429350733943439293531402769254527782370130430072562238127881332426335383470352639284201401640894296409545123751333432293054308930443053;2685260124652444277129563210343017561821163017881162142223222092162413577997604501508164311741025168820302244232425093305106970269673797116032285261329203374271020551893163322902749919261];a=[26,28,23,20,4,45,7,11];*1=A(1,a);y1=A(2,a);b=[1,2,3,5,6,8,9,10,12,13,14,15,16,17,18,19,21,22,24,25,27,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,46,47,48,49];*2=A(1,b);y2=A(2,b);plot