1、2013年河南科技大學(xué)數(shù)學(xué)建模選拔賽承 諾 書我們仔細(xì)閱讀了數(shù)學(xué)建模選拔賽的規(guī)則.我們完全明白，在做題期間不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人研究、討論與選拔題有關(guān)的問題。我們知道，抄襲別人的成果是違反選拔規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守選拔規(guī)則，以保證選拔的公正、公平性。如有違反選拔規(guī)則的行為，我們將受到嚴(yán)肅處理。我們選擇的題號是（從A/B/C中選擇一項(xiàng)填寫）： C 隊(duì)員簽名 日期： 2013 年 8月 23日2013年河南科技大學(xué)數(shù)學(xué)建模競賽

2、選拔編 號 專 用 頁評閱編號（評閱前進(jìn)行編號）：評閱記錄（評閱時使用）：評閱人評分備注供應(yīng)鏈網(wǎng)絡(luò)的建立與道路破壞問題摘要全球化競爭的加劇促使越來越多的企業(yè)開始采用供應(yīng)鏈管理策略，以實(shí)現(xiàn)企業(yè)的一體化管理。本文先以最低成本為目標(biāo)，在給定條件下，建立最佳配送中心選址模型；然后以破壞方出發(fā)，以破壞成本最低，物流費(fèi)用增加特定倍數(shù)來建立道路破壞模型，最后解決問題。針對問題一：首先利用floyd算法，確定了每個城市到其他城市的最短路路徑，然后利用0-1規(guī)劃建立了以運(yùn)輸費(fèi)用最低為目標(biāo)的函數(shù)模型 ，最后根據(jù)限制條件利用lingo進(jìn)行最優(yōu)化求解找到了4,7,11,20,23,26,48,45這八個最佳供應(yīng)點(diǎn)并且

3、根據(jù)這八個點(diǎn)的坐標(biāo)在圖上作出每一個供應(yīng)點(diǎn)到需求點(diǎn)的連接圖。針對問題二：利用隱枚舉法，首先分別計(jì)算了破壞一條道路所增加的費(fèi)用，然后利用所得到的圖和數(shù)據(jù)分析可知道破壞24-25這條路對實(shí)際結(jié)果沒有價值，將其排除，如果破壞2149這條道路，則49號城市的需求量將無法滿足，即無論付出多大代價也無法送貨到49號城市，及費(fèi)用可視為無窮大，于是可分為兩類：1.破壞2149這條路，費(fèi)用無窮大，滿足。2.不破壞2149這條路，用lingo對剩余七條路分析得到： 2021和2019這兩條道路相互影響，除此之外其它五條路相互獨(dú)立，也就是說破壞其中任意一條路后不會用到其他幾條路，最后以破壞最少的路，來達(dá)到最大的破壞效

4、果為原則，經(jīng)過計(jì)算得到最優(yōu)破壞方案：破壞43，2019，2021，7404四條線路，是其費(fèi)用增加2544195，增加比率27.71%。針對問題三：要求使對方平均總費(fèi)用至少增加100%,破壞最少的路，來達(dá)到最大的破壞效果,.建立平均費(fèi)用評判法，用公式表示破壞和未破壞的平均費(fèi)用得到平均費(fèi)用, 49號城市只能接受通過2149這條線路的貨物，如果破壞了2149這條線路，所需要的平均費(fèi)用將是無窮大，大于100%，條件成立.如果不考慮2149這條線路，根據(jù)第二問的相關(guān)性，我們知道如果同時破壞2019和2021這兩條線路，結(jié)果會有影響，于是我們單獨(dú)求出了同時破壞這兩條線路所需要的平均費(fèi)用題目要求使對方平均總

5、費(fèi)用至少增加100%，我們假設(shè)這7條線路全部被破壞，得到平均總費(fèi)用為4786487，使對方的平均總費(fèi)用增加了64.19%，達(dá)不到100%的要求，于是我們按照達(dá)到最大的破壞程度來作為標(biāo)準(zhǔn)，得到的結(jié)果是破壞45，43，740，1110，1745，2019，2021這七條線路關(guān)鍵詞：最短路floyd算法 0-1規(guī)劃最優(yōu)化求解 隱枚舉法 相關(guān)獨(dú)立性17一 問題重述全球化競爭的加劇促使越來越多的企業(yè)開始采用供應(yīng)鏈管理策略，以實(shí)現(xiàn)企業(yè)的一體化管理。供應(yīng)鏈?zhǔn)且粋€復(fù)雜的網(wǎng)狀結(jié)構(gòu)系統(tǒng)，每一部分都面臨著各種潛在的風(fēng)險(xiǎn)，任何一部分出現(xiàn)問題都可能給整個供應(yīng)鏈帶來嚴(yán)重的影響，因此如何分析、評價和提高供應(yīng)鏈系統(tǒng)的可靠性變

6、得日益迫切。設(shè)施系統(tǒng)是供應(yīng)鏈的核心，在供應(yīng)鏈研究中有著極其重要的地位。在一個設(shè)施系統(tǒng)中，某些個設(shè)施由于自然災(zāi)害或者其他因素的影響可能失效，例如911恐怖襲擊事件、2004年的印度洋海嘯、2008年的汶川地震等都對諸多行業(yè)的設(shè)施系統(tǒng)造成了嚴(yán)重的破壞。 現(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)量可以滿足有需要的城市的需求。現(xiàn)將要

7、建立一個供應(yīng)網(wǎng)絡(luò)，為各城市提供貨物供應(yīng)。貨物運(yùn)輸利用汽車進(jìn)行公路運(yùn)輸。設(shè)每噸每公里運(yùn)輸費(fèi)用為0.5元。現(xiàn)提出如下問題：1. 現(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)的連接圖。2. 假定有某組織對該供應(yīng)網(wǎng)絡(luò)的道路進(jìn)行破壞。并非所有的道路都可以被破壞，可破壞的道路見表4。當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過該道路的只有改道，但總是沿最短路運(yùn)輸。如果破壞方選取的策略是

8、使對方總費(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

9、.1問題一的分析對于問題一，這是一個最優(yōu)路徑和最優(yōu)化問題，就是要在成本最低的情況下找到最佳供應(yīng)點(diǎn)選址，建立選址模型。首先根據(jù)題中所各的數(shù)據(jù)利用floyd算法，算出每個城市到其他城市的最短距離，然后建立0-1模型：p（i,j）=1表示i城市向j城市提供貨物，等于0表示不提供貨物，x（i）=1，表示i處建供貨點(diǎn)，等于0表示不建供應(yīng)點(diǎn)，C（i）為第i處建供應(yīng)點(diǎn)費(fèi)用，以運(yùn)輸費(fèi)用最小為目標(biāo)建立函數(shù)模型min=，最后根據(jù)限制條件利用lingo求解得到供應(yīng)點(diǎn)，并根據(jù)所求供應(yīng)點(diǎn)坐標(biāo)作出每一個供應(yīng)點(diǎn)到需求點(diǎn)的連接圖。2.2問題二的分析對于問題二，問題是破壞最短的道路使總費(fèi)用增加25%，首先分別計(jì)算了只破壞一條道

10、路所增加的費(fèi)用，了解每條道路破壞之后增加的費(fèi)用程度，對圖像進(jìn)行分析可得，2425這條道路不作為最優(yōu)的運(yùn)輸路線，即破壞這條道路沒有任何的實(shí)際價值，在此將這條道路排除在破壞的范圍之外，如果破壞2149這條道路，則49號城市的需求量將無法滿足，即無論付出多大代價也無法送貨到49號城市，及費(fèi)用可視為無窮大，那題目要求的條件立馬滿足，成立，此為第一種情況；第二種情況是，2149這條道路不被破壞，然后對其他7條路進(jìn)行分析。除了2021和2019這兩條道路相互有影響之外，其他兩個破壞之后造成的影響相互獨(dú)立，即其他任意幾條道路同時破壞之后增加的費(fèi)用等于這些道路單獨(dú)破壞之后增加的費(fèi)用之和。另外需要申明的是當(dāng)20

11、21和2019這兩條道路同時破壞之后，最優(yōu)的配送中心城市也會發(fā)生變化，即原來由20號配送中心城市送貨的，將變?yōu)?5號城市配送，原因是，45號城市配送路途更短，更優(yōu)化，這些需要改變的被配送城市分別是19號，21號，33號，34號，35號和49號城市，將2021和2019這兩條道路同時破壞之后增加的費(fèi)用計(jì)算出來，作為一個整體，與其他可破壞的、獨(dú)立的五條路同時作為被破壞的考慮對象，需明確的是這六個部分是相互獨(dú)立的。先計(jì)算出需要增加的費(fèi)用為2295039.5元，再按最優(yōu)方案的思想將這六部分適當(dāng)組合，最后得到最優(yōu)的破壞方案2.3問題三的分析對于問題三，要求使對方平均總費(fèi)用至少增加100%,破壞最少的路，

12、來達(dá)到最大的破壞效果,.建立平均費(fèi)用評判法，用公式，表示破壞和未破壞的平均費(fèi)用得到平均費(fèi)用,然后和第二問一樣來分析問題三 模型假設(shè)1. 假設(shè)每條道路都是暢通無阻的，不考慮非人為因素的交通阻礙。2. 供應(yīng)點(diǎn)的貨物完全滿足應(yīng)點(diǎn)城市的要求。3. 道路的破壞具有隨機(jī)性。4. 各城市的發(fā)展水平保持平衡，不發(fā)生突變。5. 兩個城市之間的貨物運(yùn)輸方式只考慮汽車運(yùn)輸。6. 不考慮自然因素所造成的油價上漲，運(yùn)費(fèi)增加等問題。7. 假設(shè)每條道路的破壞成本相同。四 符號說明1.C（i）：第i處建供應(yīng)點(diǎn)費(fèi)用.2.S（i，j）：i,j之間最短路距離.3.m（j）:第j處需要供貨量.4.x（i）:x（i）=1表示i城市建立

13、供應(yīng)點(diǎn)，x（i）=0表示i城市不建立供應(yīng)點(diǎn)5.p（i,j）：p（i,j）=1表示i城市向j城市提供貨物，p（i,j）=0表示不提供貨物6.：平均總費(fèi)用7.mi：對應(yīng)城市的需求量，8.pi：道路破壞的成功率，9.s1：破壞之前的最優(yōu)運(yùn)輸距離，10.s2：破壞之后的最優(yōu)運(yùn)輸距離五 模型的建立與求解5.1第一問：5.1.1最短路徑的求解：由于建立供給點(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ùn)輸費(fèi)用，而運(yùn)輸費(fèi)用與路徑有關(guān)，于是首先要找到每個城市到其他城市的最短路徑，我們先根據(jù)題中所給的坐標(biāo)畫出了路徑圖如下圖1（圖1）然后運(yùn)用floyd算法的基本思想：NNYY開

14、始輸入YYN結(jié)束得到最短路徑（由于數(shù)據(jù)量較大，具體見附錄）。5.1.2最優(yōu)模型的建立：找到最短路徑后利用最優(yōu)化理論中的0-1規(guī)劃，將所有城市劃分為兩類，即建立供應(yīng)點(diǎn)的城市和不建立供應(yīng)點(diǎn)的城市，然后根據(jù)題目已知的條件建立如下模型：設(shè)cost為總花銷C（i）為第i處建供應(yīng)點(diǎn)費(fèi)用 （已知）S（i，j）為i,j之間最短路距離 （為矩陣，求出）m（j）為第j處需要供貨量 （已知）x（i）=1，表示i城市建立供應(yīng)點(diǎn)，等于0表示i城市不建立供應(yīng)點(diǎn)，p（i,j）=1表示i城市向j城市提供貨物，等于0表示不提供貨物，j只接受49個供應(yīng)點(diǎn)中一個的貨物提供，所以，只有x(i)=1的時候p（i,j）才可能等于1，于是

15、p(i,j)<x(i)可知建供貨點(diǎn)的總費(fèi)用為運(yùn)輸總費(fèi)用為 限制條件為限制條件5.1.3模型求解：根據(jù)所得到的模型和限制條件，利用ligo求解得到如下表1表1建供應(yīng)點(diǎn)所供應(yīng)的城市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,314517,18,44,45可知道，當(dāng)在編號為4，7，11，20，23，26，28，45的城市建立八個貨物供應(yīng)點(diǎn)時會使得花費(fèi)最少。5.1.4再找到了八個最佳供應(yīng)點(diǎn)后

16、利用幾何畫板，根據(jù)題目所給的數(shù)據(jù)做出了每一個供應(yīng)點(diǎn)到需求點(diǎn)的連接圖。（圖2）5.2第二問對于問題二，我們首選考慮該路線是不是我們的運(yùn)輸路線，經(jīng)過對比發(fā)現(xiàn)，2425這條線路不再我們的運(yùn)輸路線上，破壞他沒有意義，所以排除這條線路。我們假設(shè)如果破壞一條線路之后，如果一定要再從這條線路運(yùn)送貨物，把這種情況所需要的費(fèi)用當(dāng)做無窮大。我們發(fā)現(xiàn)49號城市只能接受通過2149這條線路的貨物，如果破壞了2149這條線路，增加的運(yùn)輸費(fèi)用將是無窮大，大于25%，條件成立如果不考慮破壞2149這條線路的話，那么剩下還有7條線路能進(jìn)行分析我們根據(jù)圖示發(fā)現(xiàn)了分別破壞這7條路所影響到的其他線路表2被破壞的線路影響到的線路45

17、45454743434314324315740740740421110111011101211103811104320192019201934201935201935331745451745171420212021202149利用lingo，用與第一問同樣的程序，分別求出了分別破壞這7條線路所改遷的線路，結(jié)果如下表3表3被破壞的線路影響到的線路改遷之后的線路454543054547430474343416343141631432416324315416157407407411074042784211101110119101110121191012111038119103811104311910

18、43201920192021192019342021193420193520211935201935332021193533174545174518174517144518142021202120192120214920192149很容易我們可以利用題目中所給的數(shù)據(jù)算出來改遷之后的線路要增加多少花費(fèi)表4所破壞的道路改遷之后增加的花費(fèi)4517080843114863974047455211101283102019382676.51745347052202177015上表是只破壞一條道路的話所增加的費(fèi)用，如果我們破壞2條道路的話，我們利用lingo發(fā)現(xiàn)，同時破壞2019和2021這2條路線的話對線

19、路的改遷有影響，而其他線路如果任意破壞兩條，改遷的線路還是不變，我們稱為是相互獨(dú)立的。可以得到同時破壞2019和2021這2條路線之后所改遷的線路表5破壞的線路影響的線路改遷之后的路線2021和2019201945181920193445181934201935451819352019353345181935332021451819212021494518192149可以很容易算出破壞這兩條線路所增加的費(fèi)用為921004元根據(jù)我們所得到的數(shù)據(jù)可以列出來如下表格來幫助我們分析問題表6被破壞的線路影響到的線路改遷后的線路改遷前的距離改遷后的距離所需貨物增加的費(fèi)用454543055301480223

20、1059251708084547430477161314217648834343416321087096531845011486394314163148011401232406560432416325801240974321420431541615521860603102208.57407407411042977762410857647455274042784213584049272365976111011101191027937062428392128310111012119101243953048722158.5111038119103887796876134625.51110431191

21、0436046959143134201920192021197101140430168990382676.520193420211934840127043011825201935202119358371267430500952019353320211935338731306433151766.51745451745181736288852621934234705245171445181463211485161277102021202120192156012907305694077015202149201921498301560730200752021和201920194518192791288

22、100939653792100420193445181934439141897926922.5201935451819358771415538626772019353345181935336041451847296873.52021451819215601868130810202420214945181921498302138130835970求出了破壞一條道路的話所增加的費(fèi)用，如果我們破壞2條道路的話，我們利用lingo發(fā)現(xiàn)，同時破壞2019和2021這2條路線的話對線路的改遷有影響，而其他線路如果任意破壞兩條，改遷的線路還是不變，我們稱為是相互獨(dú)立的。可以得到同時破壞2019和2021這2

23、條路線之后所改遷的線路表7破壞的線路影響的線路改遷之后的路線2021和2019201945181920193445181934201935451819352019353345181935332021451819212021494518192149可以很容易算出破壞這兩條線路所增加的費(fèi)用為921004元由此可列下表分析表8所破壞的道路改遷之后增加的花費(fèi)45170808431148639740474552111012831017453470522019和2021921004我們的原則是破壞最少的路，來達(dá)到最大的破壞效果由表中數(shù)據(jù)很容易得出最優(yōu)破壞方案：破壞43，2019，2021，7404四條線路

24、，使其費(fèi)用增加2544195，增加比率27.71%。5.3第三問對于第三問：同第二問，2425這條線路不再我們的運(yùn)輸路線上，破壞他沒有意義，所以排除這條線路。49號城市只能接受通過2149這條線路的貨物，如果破壞了2149這條線路，所需要的平均費(fèi)用將是無窮大，大于100%，條件成立每條可破壞的道路具有一定的概率，則需要求平均費(fèi)用，由題意知，平均費(fèi)用指的是破壞道路之后增加的費(fèi)用乘以破壞成功的概率加上沒有破壞道路時的運(yùn)輸費(fèi)用乘以破壞失敗的概率，用公式表示為：，其中是對應(yīng)城市的需求量，是道路破壞的成功率，是破壞之前的最優(yōu)運(yùn)輸距離，是破壞之后的最優(yōu)運(yùn)輸距離。0.5為每公里每噸的運(yùn)輸費(fèi)。下表9給出分別只

25、破壞一條道路所得的平均費(fèi)用表9破壞的線路破壞前用錢平均費(fèi)用45136781239265.843836546.51640593740318536532084.4111081393987809417453073744809002021665051127142019705627916099.1根據(jù)第二問的相關(guān)性，我們知道如果同時破壞2019和2021這兩條線路，結(jié)果會有影響，于是我們單獨(dú)求出了同時破壞這兩條線路所需要的平均費(fèi)用表10破壞的線路破壞前費(fèi)用平均費(fèi)用45136781239265.843836546.51640593740318536532084.4111081393987809417453

26、073744809002019和20215020971015549總和29152744786487題目要求使對方平均總費(fèi)用至少增加100%，我們假設(shè)這7條線路全部被破壞得到平均總費(fèi)用為4786487，使對方的平均總費(fèi)用增加了64.19%，達(dá)不到100%的要求于是我們按照達(dá)到最大的破壞程度來作為標(biāo)準(zhǔn)，得到的結(jié)果是破壞45，43，740，1110，1745，2019，2021這七條線路六 模型的評價與推廣模型的優(yōu)點(diǎn)：1.最短路徑的確定運(yùn)用floyd算法，并根據(jù)題目所給的數(shù)據(jù)，得到的結(jié)果精確可信，然后利用最優(yōu)化理論的0-1規(guī)劃和lingo精確地求的結(jié)果沒有主觀因素，結(jié)果精確可靠。2.根據(jù)描繪的坐標(biāo)圖和數(shù)據(jù)直觀的利用隱枚舉法，篩選出合理的路徑進(jìn)行分析求解，得到精確的結(jié)果，與實(shí)際相連，使人信服。3.對破壞模型進(jìn)行分類計(jì)算，利用極限法，逆向推斷，使復(fù)雜問題簡單化。模型的缺點(diǎn)：1. 當(dāng)路線過多時，利用隱枚舉法將會有海量的數(shù)據(jù)的計(jì)算，不合適于極復(fù)雜路線計(jì)算。2. 當(dāng)路各個路線之間具有復(fù)雜的相關(guān)性時，此種方法不合適。模型的推廣：1 Floyd ，0-1規(guī)劃法廣泛應(yīng)用于最短路徑和選址問題上，具有很好的精確性和實(shí)際性，可以推廣到物流公司的派件，中心銀行和醫(yī)院的建立問題上。2 枚舉法和獨(dú)立法，具有優(yōu)良的實(shí)用性，可以推廣到各類復(fù)雜相關(guān)性問題的解決上。七 參考文獻(xiàn)1 袁紹生，邵大宏，郁時練.LI