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

目錄一、問(wèn)題重述 一、問(wèn)題重述1.1問(wèn)題背景全球化競(jìng)爭(zhēng)的加劇促使越來(lái)越多的企業(yè)開(kāi)始采用供應(yīng)鏈管理策略，以實(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)的可靠性變得日益迫切。1.2問(wèn)題提出現(xiàn)有某物流公司要在全國(guó)各城市之間建立供應(yīng)鏈網(wǎng)絡(luò)。需要選定部分城市作為供應(yīng)點(diǎn)，將貨物運(yùn)輸?shù)礁鞒鞘?。通常每個(gè)供應(yīng)點(diǎn)的貨物是充足的，可以充分滿足相應(yīng)城市的需求。設(shè)該公司考慮共考慮49個(gè)城市的網(wǎng)絡(luò)，已知城市的坐標(biāo)城市之間的道路連接關(guān)系、在每個(gè)城市建立配送中心的固定費(fèi)用和需求量，并假定作為供應(yīng)點(diǎn)的城市其供應(yīng)量可以滿足有需要的城市的需求。現(xiàn)將要建立一個(gè)供應(yīng)網(wǎng)絡(luò)，為各城市提供貨物供應(yīng)。設(shè)每噸每公里運(yùn)輸費(fèi)用為0.5元?，F(xiàn)提出如下問(wèn)題：?jiǎn)栴}一：現(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)的連接圖。問(wèn)題二：現(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)的連接圖。問(wèn)題三：假定各道路能否被破壞具有隨機(jī)性，當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過(guò)該道路的只有改道，但總是沿最短路運(yùn)輸。由于破壞方選取一些邊進(jìn)行破壞時(shí)，這些邊不一定被破壞，而是服從一定的概率分布。設(shè)可破壞的邊及各邊破壞的概率見(jiàn)表。運(yùn)輸時(shí)產(chǎn)生的費(fèi)用可按照各種情況下的平均費(fèi)用來(lái)考慮。如果破壞方選取的策略是使對(duì)方平均總費(fèi)用增加最大。給出具體的破壞道路和平均總費(fèi)。二、問(wèn)題分析2.1問(wèn)題一的分析問(wèn)題一研究的主要是從49個(gè)城市中找到適當(dāng)數(shù)量的供應(yīng)點(diǎn)及其位置來(lái)使運(yùn)輸費(fèi)用和基建費(fèi)用的總費(fèi)用達(dá)到最低?？傎M(fèi)用由運(yùn)輸費(fèi)用和基建費(fèi)用組成,隨著選取供應(yīng)點(diǎn)的數(shù)量的增多,運(yùn)輸費(fèi)用減小,但基建費(fèi)用會(huì)隨之增加,很明顯,這是一個(gè)0-1規(guī)劃問(wèn)題。我們可以先通過(guò)題中所給的數(shù)據(jù)運(yùn)用Floyd算法求出每個(gè)城市到其他城市的最短距離，然后給出相應(yīng)的約束條件,運(yùn)用Lingo軟件進(jìn)行求解,即可得出確定的供應(yīng)點(diǎn),使總費(fèi)用達(dá)到最低。最后根據(jù)選中作為供應(yīng)點(diǎn)的城市的坐標(biāo)作出每一個(gè)供應(yīng)點(diǎn)到需求點(diǎn)的連接圖。2.2問(wèn)題二的分析問(wèn)題二主要研究的是破壞盡可能少的道路來(lái)使總費(fèi)用增加25%,于是可以假設(shè)當(dāng)某條道路被破壞時(shí)，把該條道路的距離改成一個(gè)很大的值（例如把道路的距離改成1000000公里），這樣就可以近似的看成這個(gè)道路是不通的。當(dāng)某條道路被破壞時(shí)，根據(jù)新得到的數(shù)據(jù)用floyd算法重新求出各城市到其他城市的最短距離，然后求出其他沒(méi)有供應(yīng)點(diǎn)的城市距離最近的供應(yīng)點(diǎn)及其之間的距離，最后就可以求出當(dāng)該道路被破壞時(shí)的總費(fèi)用。根據(jù)題中給出的數(shù)據(jù)，提煉出約束條件，建立模型求當(dāng)總費(fèi)用增加25%時(shí)破壞的道路數(shù)量最少的情況，這樣就求出了最小的道路數(shù)和具體的道路。另外，在分析道路關(guān)系圖時(shí)，發(fā)現(xiàn)9條可以被破壞的道路中城市21到城市49之間的路如果被破壞，供應(yīng)點(diǎn)就無(wú)法供應(yīng)城市49，所以這條道路不能被破壞。2.3問(wèn)題三的分析問(wèn)題三主要研究的是給出適當(dāng)?shù)钠茐牡缆返姆桨?，使得?duì)方的平均總費(fèi)用能夠達(dá)到最大，平均總費(fèi)用由建造供應(yīng)點(diǎn)的基建費(fèi)用和各種情況下運(yùn)輸?shù)钠骄M(fèi)用組成，當(dāng)給出道路破壞的方案后，由于8個(gè)供應(yīng)點(diǎn)是固定的，所以建造供應(yīng)點(diǎn)的基建費(fèi)用是不變的，變化的是運(yùn)輸?shù)钠骄M(fèi)用。由于破壞方選取一些道路進(jìn)行破壞時(shí)，這些邊不一定被破壞，而是服從一定的概率分布。所以求運(yùn)輸?shù)钠骄M(fèi)用其實(shí)就是根據(jù)相應(yīng)的概率分布求運(yùn)輸費(fèi)用的期望值。由于有8條道路可以被破壞，所以可以給出255種道路破壞方案。在一個(gè)具體的道路破壞的方案時(shí)，例如有確定的k條道路被破壞的情況下，由于破壞方選取一些道路進(jìn)行破壞時(shí)，這些道路不一定被破壞，而是服從一定的概率分布，所以有2k種的情況，在2可以根據(jù)上面的分析建立模型，運(yùn)用matlab編寫(xiě)相應(yīng)的求平均總費(fèi)用的程序來(lái)求出各種方案的平均總費(fèi)用，最后就可以得到相應(yīng)的方案使平均總費(fèi)用達(dá)到最大。三、模型假設(shè)假設(shè)1：道路破壞但原供給點(diǎn)及其所供應(yīng)的城市不變；假設(shè)2：假定各道路能否被破壞具有隨機(jī)性。假設(shè)3：網(wǎng)絡(luò)內(nèi)的所有道路都是暢通無(wú)阻的；假設(shè)4：兩城市之間除了公路運(yùn)輸沒(méi)有其他的運(yùn)輸方式；假設(shè)5：運(yùn)輸單價(jià)不受燃料等因素影響；假設(shè)6：供應(yīng)點(diǎn)的城市其供應(yīng)量可以滿足有需要的城市的需求；假設(shè)7：各城市的需求量在一段時(shí)間內(nèi)固定不變；假設(shè)8：假設(shè)當(dāng)某條邊被破壞時(shí)，把該條邊的距離改成一個(gè)很大的值（例如改成1000000公里）。四、定義與符號(hào)說(shuō)明0-1變量，判斷第i個(gè)城市是否建立供給點(diǎn)1表示0表示0-1變量，判斷1表示0表示在第i個(gè)城市建立供給點(diǎn)的固定費(fèi)用第j個(gè)城市的貨物需求量第i個(gè)城市到底j個(gè)城市的最短路徑r(i)代表i條可以被破壞的路y(i)0-1變量，判斷是否破壞第i條路y(i)為1時(shí)，代表破壞這條路y(i)為0時(shí)，不破壞這條路道路破壞前的總費(fèi)用費(fèi)用道路破壞后的總費(fèi)用△道路破壞前后的增加的總費(fèi)用MM為平均總費(fèi)用T運(yùn)輸?shù)钠骄M(fèi)用J8個(gè)供應(yīng)點(diǎn)的基建費(fèi)用五、模型建立及求解數(shù)據(jù)預(yù)處理1、根據(jù)表1和表2所給的數(shù)據(jù)，運(yùn)用matlab軟件，編寫(xiě)相應(yīng)的程序（見(jiàn)附錄），畫(huà)出各個(gè)城市及其之間道路關(guān)系圖。如圖所示：圖1各城市道路關(guān)系圖2、構(gòu)造一個(gè)49*49的矩陣C[i][j]，根據(jù)表2中的數(shù)據(jù)對(duì)C[i][j]進(jìn)行初始化:若從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],若u<C[i][j],則令C[i][j]=u，否則直接轉(zhuǎn)到3。（3）若j<49,則令j=j+1，轉(zhuǎn)到2；否則轉(zhuǎn)到4。（4）若i<49，則令i=i=1，轉(zhuǎn)到2；否則轉(zhuǎn)到5。（5）若k<49，則令k=k+1，j=1，i=1，轉(zhuǎn)到2；否則輸出。通過(guò)這種算法最后得到的矩陣C[i][j]就是任意兩個(gè)城市i和j之間的最短路徑，得到一個(gè)的數(shù)據(jù)陣（附錄表）。在此我們截取部分（10×10）的數(shù)據(jù)，詳見(jiàn)下表2：表2任意兩個(gè)城市間的最短路徑12345678910101202704805407991129135912601094212003705806609191249147912001034327037002107401069139916291151985448058021005301279160918391361119555406607405300133916691899180016346799919106912791339033056020591893711291249139916091669330023023892223813591479162918391899560230026192453912601200115113611800205923892619028010109410349851195163418932223245328005.1問(wèn)題一模型的建立與求解5.1.1、模型的建立1、約束條件的確立：1、第j個(gè)城市只能接受一個(gè)供應(yīng)點(diǎn)給它提供貨物，即：其中判斷第i個(gè)城市是否給第j個(gè)城市提供貨物供應(yīng)。2、對(duì)于任意一個(gè)城市i，若不在該城市建配送點(diǎn)，則=0且，因此可得約束條件：；若在該城市建配送點(diǎn)，則=1且或1，因此也可得約束條件：。綜上，我們有約束條件：其中表示是否在第i個(gè)城市建立供應(yīng)點(diǎn)2、目標(biāo)函數(shù)的確立經(jīng)過(guò)對(duì)題目的分析，可總費(fèi)等于建立供給點(diǎn)的花費(fèi)固定費(fèi)用與從供應(yīng)點(diǎn)運(yùn)輸?shù)叫枨簏c(diǎn)會(huì)產(chǎn)生運(yùn)輸費(fèi)用之和，現(xiàn)在我們要求建立供給點(diǎn)的數(shù)量使使總費(fèi)用最小其中表示第i個(gè)城市到底j個(gè)城市的最短路徑，表示在第i個(gè)城市建立供給點(diǎn)的固定費(fèi)用。3、0-1整數(shù)線性規(guī)劃模型綜上我們可得出：5.2、模型的求解1、用Lingo軟件編寫(xiě)程序（附錄問(wèn)題一）求解得出結(jié)果，詳見(jiàn)表3：表3建立供應(yīng)點(diǎn)城市及其相應(yīng)需求點(diǎn)建供應(yīng)點(diǎn)的城市該供應(yīng)點(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,31，4514,17,18,44,45，1、根據(jù)表1及表2所給的數(shù)據(jù)，首先對(duì)49個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)注，再運(yùn)用matlab軟件，編寫(xiě)相應(yīng)的程序（見(jiàn)附錄），找出了49個(gè)城市中可以作為供應(yīng)點(diǎn)以及不可以作為供應(yīng)點(diǎn)城市，如圖：圖2城市及供應(yīng)點(diǎn)分布圖2、運(yùn)用matlab編程序結(jié)合幾何畫(huà)圖板得出每個(gè)供應(yīng)點(diǎn)城市到需要該供應(yīng)點(diǎn)提供貨物的城市的線路圖如下：圖3供應(yīng)點(diǎn)到需求點(diǎn)的連接圖其中實(shí)心點(diǎn)即為可以建供應(yīng)點(diǎn)的城市，箭頭指向的點(diǎn)為接受貨物供應(yīng)的城市。有的城市和供應(yīng)點(diǎn)并不直接相連，可以按照箭頭所指的中轉(zhuǎn)城市進(jìn)行貨物供應(yīng)。3、按照l(shuí)ingo軟件計(jì)算的結(jié)果和相應(yīng)的的路徑，可以知建立8個(gè)供應(yīng)點(diǎn)：4,7,11,20,23,26,28，45可以使總費(fèi)用最小為S1=9197118（元）5.2問(wèn)題二模型的建立與求解5.2.1模型的建立約束條件的建立（1）破壞方選取的策略是使對(duì)方總費(fèi)用增加25%，即：其中為道路破壞前的總費(fèi)用費(fèi)用，道路破壞后的總費(fèi)用。由題意得，必須至少要比增加25%。（2）被破壞的道路上的數(shù)目小于8，即：目標(biāo)函數(shù)的建立有問(wèn)題知當(dāng)某條道路被破壞后，該條道路就不能再被使用，以前運(yùn)輸經(jīng)過(guò)該道路的只有改道，但總是沿最短路運(yùn)輸。因此需要破壞最少的道路。。其中r(i)代表8條可以被破壞的路，y(i)為0-1變量，當(dāng)y(i)為1時(shí)，代表破壞這條路；y(i)為1時(shí)，不破壞這條路。minR為可破壞道路數(shù)的最小數(shù)量。3、模型的建立5.2.2模型的分析求解1、該問(wèn)題的關(guān)鍵點(diǎn)在于對(duì)QUOTEC后的求解，這里我們運(yùn)用matlab軟件進(jìn)行編程（見(jiàn)附錄問(wèn)題二），來(lái)對(duì)求解。當(dāng)?shù)缆繁黄茐暮?，我們可以把相?yīng)的道路距離改為一個(gè)很大的值（例如1000000000），這樣當(dāng)我們?cè)谟胒loyd算法求最短路時(shí)就可以把這條道路繞過(guò)去，就可以近似把道路看成是被破壞的。從建立的道路關(guān)系圖中可以看出到達(dá)城市49的路只有一條，從城市21出發(fā)，因此如果這條路被破壞的話，城市49將得不到供應(yīng)，因此這條道路不能被破壞，這樣可以被破壞的路就只有8條。當(dāng)某幾條道路被破壞后，這條道路的距離就相應(yīng)的被賦以一個(gè)很大的值，然后用floyd算法求出破壞后的各城市到其他城市的最短路徑，然后分別求出沒(méi)有建立供應(yīng)點(diǎn)的城市到41個(gè)城市到8個(gè)供應(yīng)點(diǎn)的最短路，這樣就可以求出總費(fèi)用。當(dāng)被破壞的道路只有一條時(shí)一共有C81種情況，當(dāng)破壞的道路有兩條時(shí)，一共有C82種情況，依次類(lèi)推，一共有2、根據(jù)以上分析可以求出被破壞的道路序列號(hào)以及被破壞的道路見(jiàn)下表：表4被破壞道路的序列號(hào)及相關(guān)道路被破壞的道路序列號(hào)城市1城市2被破壞的道路1454→52344→34101111→105192020→197174545→179202120→21我們根據(jù)算出來(lái)的被破壞的道路以及第一問(wèn)中得出來(lái)的供給方案，得出來(lái)改道后的供給運(yùn)輸?shù)缆穲D，見(jiàn)圖4圖4改道后的運(yùn)輸?shù)缆穲D其中：1、較細(xì)的實(shí)線表示不需要改道的運(yùn)輸路線；2、較粗的虛線表示改道后的運(yùn)輸路線；3、虛線連接的點(diǎn)表示需要作為中轉(zhuǎn)點(diǎn)的城市，虛線的起點(diǎn)表示供應(yīng)點(diǎn)，箭頭指向的點(diǎn)表示被供應(yīng)點(diǎn)。4、下表列出了道路被破壞后，建供應(yīng)點(diǎn)城市給相應(yīng)的被供應(yīng)城市的貨物運(yùn)輸?shù)缆返淖兓闆r以及這種變化帶來(lái)的費(fèi)用的增加量，如表所示：表5新的運(yùn)輸?shù)缆芳案牡篮笤黾拥馁M(fèi)用受影響的供應(yīng)點(diǎn)道路破壞前的貨物運(yùn)輸?shù)缆返缆菲茐暮蟮呢浳镞\(yùn)輸?shù)缆吩黾拥馁M(fèi)用44→3→14→16→3→14065604→3→24→16→15→23116804→54→30→51059254→3→154→16→15102208.54→5→474→30→47648831111→1011→9→105959211→10→1211→9→10→1246508.511→10→3811→9→10→3872675.511→10→4311→9→10→43905342020→19→3320→48→18→19→33364149.520→19→3420→48→18→19→3428572.520→19→3520→48→18→19→35121043.520→1920→48→18→1940832720→2120→48→18→19→2113798220→21→4920→48→18→19→21→4948647.54545→1745→18→1721934245→17→1445→18→14127710增加的總費(fèi)用△2380659據(jù)此，我們?nèi)菀浊蟮玫缆繁黄茐暮螅跐M足題設(shè)條件下的總費(fèi)用：=+△因此由以上我們可以得出第二問(wèn)的解答為：破壞線路的序列號(hào)為：1,2,4,5,7,9破壞線路為：4→5，4→3，11→10，20→19，20→21，45→17；總費(fèi)用：11577777（元）5.3問(wèn)題三模型的建立與求解1、平均總費(fèi)用由8個(gè)供應(yīng)點(diǎn)的基建費(fèi)用和運(yùn)輸?shù)钠骄M(fèi)用組成maxM=J+maxTM為平均總費(fèi)用，J為8個(gè)供應(yīng)點(diǎn)的基建費(fèi)用，T為運(yùn)輸?shù)钠骄M(fèi)用。2、由于J為固定的，所以求平均總費(fèi)用的最大值實(shí)際上只需求運(yùn)輸?shù)钠骄M(fèi)用的最大值。例如當(dāng)只有一條邊可能被破壞時(shí)（假設(shè)該邊被破壞的概率為p），有2種情況，則t前為道路破壞前的運(yùn)輸費(fèi)用，t后為道路破壞后的運(yùn)輸費(fèi)用，當(dāng)可能破壞的道路數(shù)為2時(shí)，有223、由于有8條邊可以被破壞，所以可以給出256種道路破壞方案（包含8條道路都不被破壞的情況），每個(gè)道路破壞方案都可以產(chǎn)生一個(gè)平均總費(fèi)用，只需求出256種平均總費(fèi)用中的最大值即可。4、根據(jù)題目中的條件，運(yùn)用matlab軟件建立模型，來(lái)求解平均總費(fèi)用。在這256種道路破壞方案中，可以分為8種情況來(lái)討論，分別按破壞的道路的數(shù)目來(lái)區(qū)分。例如方案中破壞的邊數(shù)目為k時(shí)，可以產(chǎn)生一個(gè)C8k種道路破壞方案，針對(duì)C8k種道路破壞方案的一種具體破壞方案時(shí)，由于有每種情況都對(duì)應(yīng)相應(yīng)的概率，可以用matlab的dec2bin的函數(shù)產(chǎn)生一個(gè)k列的0-1全排列（這個(gè)排列為2kk的矩陣），0代表不破壞該道路，1代表破壞該道路，每一行都代表2k種情況中的一種情況，再根據(jù)表4中的數(shù)據(jù)可以求出相應(yīng)的概率，利用問(wèn)題二中編寫(xiě)的求破壞的道路的總費(fèi)用的程序可以求出2k種情況下的運(yùn)輸費(fèi)用，再利用相應(yīng)的概率，求出2然后就可以求出在破壞的道路的數(shù)目為k時(shí)，C8k種方案的平均總費(fèi)用。再求出C8k種方案的平均總費(fèi)用中的最大值。變換k的值，k由1變換到8，就可以求出在8表6破壞的邊的數(shù)目及其相應(yīng)的平均費(fèi)用最大值破壞邊的個(gè)數(shù)n有n條邊被破壞時(shí)平均總費(fèi)用中的最大值123456785、然后根據(jù)表中的數(shù)據(jù)畫(huà)出了隨著破壞的道路的數(shù)量的不同，相應(yīng)的平均總費(fèi)用最大值的變化趨勢(shì)圖，如下:圖5最大平均費(fèi)用中的最大值隨破壞邊數(shù)的變化圖由圖中可以看出隨著破壞的道路的數(shù)量的增加，平均總費(fèi)用的最大值大體上呈現(xiàn)出一個(gè)上升的趨勢(shì)，但當(dāng)破壞的道路數(shù)為7或8時(shí)，平均總費(fèi)用的最大值相同，都為最大值。當(dāng)破壞的道路數(shù)為7時(shí)。共有C87種情況，可以找出平均總費(fèi)用最大時(shí)對(duì)應(yīng)的道路破壞方案為因此如果要使對(duì)方平均總費(fèi)用增加最大，可以有兩種方案進(jìn)行選擇。方案一：1,2，3,4,5,7,9；方案二：1,2，3,4,5,6,7,9；但如果考慮到每破壞一條道路都需要成本和代價(jià)，最優(yōu)的方案一即：1,2,3,4,5,7,9（數(shù)字代表破壞的道路序號(hào)）；。6、根據(jù)以上分析可以按方案二求出被破壞七條的道路序列號(hào)以及被破壞的道路見(jiàn)下表：表七被破壞道路的序列號(hào)及相關(guān)道路被破壞的道路序列號(hào)城市1城市2被破壞的道路1454→52344→337407→404101111→105192020→197174545→179202120→21無(wú)論按照方案一還是方案二得到的平均總費(fèi)用均為:（元）。六、模型的評(píng)價(jià)、改進(jìn)及推廣6.1模型的評(píng)價(jià)在本文中，我們的思路、方法及數(shù)學(xué)模型的合理性主要體現(xiàn)在以下幾個(gè)方面：1、假設(shè)的合理性：各城市的需求量在一段時(shí)間內(nèi)固定不變,供應(yīng)點(diǎn)的城市其供應(yīng)量可以滿足有需要的城市的需求,道路破壞但原供給點(diǎn)及其所供應(yīng)的城市不變,各道路能否被破壞具有隨機(jī)性.這些都是十分合理的假設(shè)。2、思維的合理性：本文我們按先后及由淺入深的邏輯關(guān)系展開(kāi)了對(duì)問(wèn)題求解的思路，思路的流程圖如圖所示：合理假設(shè)精確計(jì)算科學(xué)建模合理假設(shè)精確計(jì)算科學(xué)建模模型的進(jìn)一步改進(jìn)和評(píng)價(jià)模型的進(jìn)一步改進(jìn)和評(píng)價(jià)圖6思路流程圖3、模型的科學(xué)性：解決問(wèn)題過(guò)程中我們采用Floyd算法，0-1整數(shù)規(guī)劃算法分析問(wèn)題。這都是科學(xué)的數(shù)學(xué)模型在解決圖中任意兩點(diǎn)間最短距離時(shí)我們采用了Floyd算法，精確性很高，對(duì)現(xiàn)實(shí)問(wèn)題的出來(lái)還是可以滿足要求的。4、模型的可靠性：除了論文中所用方法，我們?cè)诮r(shí)還嘗試使用過(guò)其他方法，諸如Dijkstra算法、蟻群算法，遺傳算法等，都得到了比較相近的結(jié)果，可見(jiàn)我們的模型是可靠的。6.2模型的改進(jìn)與推廣在解決第一問(wèn)時(shí)，我們嘗試了窮舉法，編寫(xiě)了matlab程序，但計(jì)算量太大，等待結(jié)果的時(shí)間很長(zhǎng)。后來(lái)我們結(jié)合約束條件，運(yùn)用lingo軟件，把它轉(zhuǎn)化為0-1規(guī)劃問(wèn)題，使模型大大簡(jiǎn)化，大大縮短了運(yùn)行的時(shí)間。在解決第二問(wèn)和第三問(wèn)時(shí)，由于只有255種情況，我們根據(jù)題中的條件，通過(guò)matlab編寫(xiě)了相應(yīng)的求總費(fèi)用的程序，遍歷了所有可能的結(jié)果。由于涉及到的情況比較少，可以用遍歷法很快的求出結(jié)果，但當(dāng)處理大量的數(shù)據(jù)時(shí)，這樣的方法就會(huì)消耗很多的時(shí)間。七、參考文獻(xiàn)[1]姜啟源《數(shù)學(xué)模型》，高等教育出版社，2003。[2]趙靜、但琦，《數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)》，高等教育出版社、施普林格出版社，2000年第一版。[3]謝金星、薛毅，《優(yōu)化建模與LINDO/LINGO軟件》，清華大學(xué)出版社，2005年7月第一版。[4]蘇金明，《MATLAB工具箱應(yīng)用》，電子工業(yè)出版社，2004年第一版。[5]肖華勇，《實(shí)用數(shù)學(xué)建模與軟件應(yīng)用》西北工業(yè)大學(xué)出版社。[6]西北工業(yè)大學(xué)數(shù)學(xué)建模指導(dǎo)委員會(huì)，《數(shù)學(xué)建模簡(jiǎn)明教程》高等教育出版社。八、附錄問(wèn)題一的程序model:sets:weizhi/1..49/:x,jijian,xuqiu;assign(weizhi,weizhi):D,l;endsetsdata:jijian=@ole('C:\Users\hjk123\Desktop\table3','cost');xuqiu=@ole('C:\Users\hjk123\Desktop\table3','need');D=@ole('C:\Users\hjk123\Desktop\shortestpath');enddatamin=@sum(weizhi(k):x(k)*jijian(k))+@sum(weizhi(j):@sum(weizhi(i):xuqiu(j)*D(i,j)*l(i,j)))*0.5;@for(weizhi(i):@bin(x(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)<=x(i)));End問(wèn)題二程序t=1:8;f=nchoosek(t,1);%′ó1μ?8?D?ò3?k??êyμ?è???áD[m,n]=size(f);a=1;b=1;mn=0;fora=1:mtable5=table2;forb=1:nt=find(table4(f(a,b),1)==table5(:,1));s=find(table4(f(a,b),2)==table5(:,2));j=intersect(t,s);table5(j,3)=1000000000;end%°???μ?μ??·?3?μ1000000000A=table5;B=sparse([A(:,1)',A(:,2)'],[A(:,2)',A(:,1)'],[A(:,3)',A(:,3)']);C=zeros(49);fori=1:49[dist,path,pred]=graphshortestpath(B,i);C(i,:)=dist;end%?ò3??÷μ?μ?????μ?μ?×??ì?àà?l1=[47112023262845];l2=[123568910121314151617181921222425272930313233343536373839404142434446474849];fori=1:41k=min(C(l2(i),l1));g(i)=k*table3(l2(i),2)*0.5;endh=sum(g);mn(a)=h+272080+457824+411616+526680+684608+31008+196384+243808;%?ó3?×ü·?ó?end問(wèn)題三的程序k=8;str=dec2bin(0:2^k-1);table6=str;%D?3ék??01μ?è???áDth=1:8;f=nchoosek(th,k);[m,n]=size(f);[tc,tk]=size(table6);fg=zeros(1,m);forpl=1:mtable5=table2;forc=1:2^ntable5=table2;forab=1:tkiftable6(c,ab)=='1't=find(table4(f(pl,ab),1)==table5(:,1));