CUMCM2000年全國大學(xué)生數(shù)模競賽B題優(yōu)秀論文

1、2000年論文選管道訂購與運輸問題編者按：本文采用將待鋪設(shè)管道按單位長度分解成n個需求點，建立運輸模型的方法避免了問題一和三的差別模型切合原賽題要求并針對原問題的規(guī)模，對算法作y-定的改進，得到了較好的結(jié)果本刊予以摘要發(fā)表摘 要：本文在詳細分析的基礎(chǔ)上，通過合理假設(shè)并引人等價轉(zhuǎn)換原則，將管道訂購與運輸問題轉(zhuǎn)化為單一的公路運輸問題運用組合優(yōu)化的思想和方法，給出了數(shù)學(xué)模型·產(chǎn)量未定的運輸模型針對此模型，我們設(shè)計了“改進的最小元素法”和“改進的伏格爾ph"，先求得了個初始解。再通過“試探法”和“迭代法”進行調(diào)調(diào)優(yōu)化最后得出結(jié)果：對第·問最小總費用為1279019萬元；對

2、第三問最小總費用為1407383萬元1 問題的重述(略)2 基本假設(shè) (1)只考慮訂購費用和運輸費用，不考慮裝卸等其它費用 (2)鋼管單價與訂購量、訂購次數(shù)、訂購日期無關(guān) (3)訂購汁劃是指對每個廠商的定貨數(shù)量；運輸方案是指具有如下屬性的(4)訂購汁劃是指對每個廠商的定貨數(shù)量；運輸方案是指具有如下屬性的一批記錄：管道區(qū)間，供應(yīng)廠商，具體運輸路線 (4)將每一單位的管道所在地看成一個需求點，向一單位管道的所在地運輸鋼管即為向一個點運輸鋼管3 符號說明 m：鋼廠總數(shù). n：單位管道總數(shù). 第i個鋼廠 第i個鋼廠的產(chǎn)量上限。 第i個鋼廠單位鋼管的銷售價 管道線上第i個站點。 管道線上第i個單位管道的

3、位置。 f：總費用。 從鋼廠到點的最低單位費用。4 問題分析 運輸費用等價轉(zhuǎn)換法則：按單位運費相等原則將任意兩點間的最短鐵路線轉(zhuǎn)換為公路線對于鐵路線上的任意兩點，用f1oyd算法找出兩點間最短鐵路路線的長度查鐵路運價表求得，對應(yīng)的鐵路單位運費;又設(shè)與該段鐵路等費用的公路長度為，則： 由此，我們就在之間用一條等價的公路線來代替間的最短鐵路線如果之間原來就有公路，就選擇新舊公路中較短的一條這樣，我們就把鐵路運輸網(wǎng)絡(luò)轉(zhuǎn)換成了公路運輸網(wǎng)絡(luò)銷價等價轉(zhuǎn)換法則：按單位費用相等將任意鋼廠的單位銷價轉(zhuǎn)換為公路單位運價對于鋼廠si的銷售單價pi，我們可以虛設(shè)一條公路線，連接鋼廠si及另一虛擬鋼廠，其長度為，并且滿

4、足；從而將鋼廠的銷售單價轉(zhuǎn)換成公路運輸單價，而新鋼廠的銷售價為0.將鐵路和銷價轉(zhuǎn)換為公路的過程可以由計算機編程實現(xiàn)通過上述的分析，我們可以將原問題化為一個相對簡單的產(chǎn)量未定的運輸問題，利用之間的管道距離和鋼廠和站點之間的公路距離建立一個產(chǎn)量未定的運輸問題的模型但是由于并不能代表所有的實際需求點(實際需求點是n個單位管道)，因此，我們可以用f1oyd算法進一步算出7個鋼廠到所有實際的n個需求點(對于問題一，n5171;對于問題三，n5903)的最短路徑，并由此得出一個具有7個供應(yīng)點、n個需求點的產(chǎn)址未定的運輸模型5 模型的建立產(chǎn)量未定的運輸模型根據(jù)假設(shè)4，我們可以將每一單位的管道看成一個需求點，

5、向一單位管道的所在地運輸鋼管即為向一個點運輸鋼管對每個點，我們可以根據(jù)該點的位置和最短等價公路距離，求出各鋼廠與該點之間最小單位運輸費用(銷價已經(jīng)歸人運輸費用之中了)設(shè)總共有m個供應(yīng)點(鋼廠)，n個需求點，我們就可以得到一個產(chǎn)量未定的運輸模型：有m個供應(yīng)點、n個需求點，每個供應(yīng)點的供應(yīng)量；每個需求點需要1單位，運輸單價矩陣為c，求使得總運輸費用最小的運輸方案其數(shù)學(xué)規(guī)劃模型： 其中： 為單位費用矩陣 為決策矩陣，也為0-1矩陣6 模型的求解對于本題，上述0-1規(guī)劃規(guī)模宏大，現(xiàn)有的一些算法不能勝任，我們必須具體問題具體分析，結(jié)合本題實際情況，尋找行之有效的算法(1)初始方案的改進的最小元素法和改進

6、的伏格爾法*改進的最小元素法改進的最小元素法又稱為貪婪法或瞎子爬山法，它的宗旨是每一步都取當(dāng)前的最優(yōu)值算法步驟為，對費用矩陣c作n次下列循環(huán)：c中找一個最小值；令c的第j的所有數(shù)據(jù)改為+；如果，第i個供應(yīng)點的供應(yīng)量已達上限，將c的第i行數(shù)據(jù)全改為+。對于問題一和問題三，我們用貪婪法求得的最小總費用的初始分別為1286692.1萬元和1414515.2萬元。*改進的伏格爾法改進的最小元素法確定的初始方案往往缺乏全局觀念，即為了省節(jié)一處的費用，在其它處要花費更多，改進的伏格爾法的主要思想：一個目的地如果不能采用最小值供應(yīng)（供應(yīng)點供應(yīng)不足），就必須考慮次小值供應(yīng)，這里就存在一個差額，差額越大，在不能

7、采用最小值時，損失越大，因此，改進的伏格爾法的宗旨是每一步對當(dāng)前差值最大的點取當(dāng)前最小值。算法的步驟為，對矩陣c做n次下循環(huán)：指出每一行最小值與最大值之差最大的一行，第i行，找出該行的最小值為令c的第j列的所有數(shù)據(jù)改為；如果，第i個供應(yīng)點的供應(yīng)量已達上限，令c的第i行的所有數(shù)據(jù)為。對于問題一和問題三，我們用改進的伏格爾法求得方案的總費用分別為1279019萬元和1407383萬元。（2）調(diào)整優(yōu)化調(diào)整優(yōu)化是將一個離最優(yōu)解很近的初始解調(diào)整到在調(diào)整算法下無法更優(yōu)的程度調(diào)整優(yōu)化分兩個部分，第一部分是用試探法對供應(yīng)點的供應(yīng)量進行優(yōu)化第二部分是用迭代法對供應(yīng)點進行兩兩對調(diào)優(yōu)化*試探法調(diào)整優(yōu)化實際供應(yīng)量在5

8、00以下的供應(yīng)點對每個實際供應(yīng)量在500以·f的供應(yīng)點，只存在兩種合理的優(yōu)化方法：一種是將其供應(yīng)量增加到500，另一種是將其供應(yīng)量減少到0試探法將分別試探進行下列兩種優(yōu)化：其一是先將供應(yīng)點的供應(yīng)量強行提升至500，使用改進的伏格爾法的優(yōu)先順序，從其它供應(yīng)點負責(zé)供應(yīng)的需求點搶奪一部分，再用對調(diào)法優(yōu)化至無法更優(yōu)，得出一個總費用f1；其二是先將該供應(yīng)點的供應(yīng)量調(diào)整為0，其原供應(yīng)的需求點由其它鋼廠用改進的伏格爾法的優(yōu)先順序補充，再用對調(diào)法優(yōu)化至無法更優(yōu)，得出一個總費用f2那么，就應(yīng)當(dāng)采取總費用較小的方法例如，對于第一問，按改進的伏格爾法獲得的初始方案中，s7的用量僅為245，優(yōu)化時，試探將其

9、降為0和將其提升為500后的最優(yōu)結(jié)果，分別為1279019萬元和1280506萬元，則說明應(yīng)將s，降為0*用迭代法進行對調(diào)優(yōu)化改進的伏格爾法給出的初始值雖然很接近最優(yōu)值，但仍有不足之處，即可能存在兩個需求點，調(diào)換供應(yīng)點能使總費用更小，例如，需求點a和6的供應(yīng)點是x和y，費用分別是c(x,a)和c(y,b)，如果讓y供應(yīng)a，x供應(yīng)b的話，費用將是c(y，a)和r(c，b)，如果： c(y，a)+r(x，b)<c(x，a)+c(y，b)則說明對調(diào)后總費用更低因此，我們可以采用迭代法對任意兩個需求點的供應(yīng)點兩兩對調(diào)至無法更優(yōu)由于一共只有m7個供應(yīng)點，所以兩兩對調(diào)的可行方案一共有種，因此，兩兩對

10、調(diào)供應(yīng)點的方法是可行的，具體步驟如下：stepl 對于任意兩個供應(yīng)點xi和xj i1，2，m j=1，2，m 1)找出所有由xi供應(yīng)的需求點，構(gòu)成點集aa1,a2,c2)找出所有由xj供應(yīng)的需求點，構(gòu)成點集bb1,b2,3)對a中所有點，如果改用xj來供應(yīng)，將付出的代價構(gòu)成向量4)對b中所有點，如果改用xi來供應(yīng)，將付出的代價構(gòu)成向量5)對分別按升序排序6)同時對從前向后遍歷，如果(表示對調(diào)供應(yīng)者將降低總費用)，則對調(diào)其供應(yīng)者，直到出現(xiàn)為止step2 統(tǒng)計這輪對調(diào)后的總費用是否比原來的總費用f有明顯的進步，即。如果有明顯的進步，則再回stepl執(zhí)行，否則結(jié)束優(yōu)化令人振奮的是，采用改進的最小元素

11、法和改進的伏格爾法得到問題一的初始方案分別采用這種優(yōu)化方案后，竟都達到了相同的最小費用：1279019萬元(3)結(jié)果(略)參考文獻1薛秀謙等編著運籌學(xué).中國礦業(yè)大學(xué)出版社1998年2趙新澤著線性規(guī)劃的新方法和應(yīng)用世界圖書出版社，1996年3王樹禾著圖論極其算法中國科學(xué)技術(shù)大學(xué)出版社1990年4lucas w f著離散與系統(tǒng)模型3國防科技大學(xué)出版社，1996年鋼管訂購和運輸策略段曉軍， 俞昌盛， 吳建德指導(dǎo)老師： 張勝貴(西北工業(yè)大學(xué)，西安 710072)編者按：本文節(jié)選的是原淪文中模型的分析與建立以及之前的準(zhǔn)備工作部分該部分通過單位鋼管的最小運購費，建立了問題求解的二次規(guī)劃模型特點是思路、表述

12、簡明、清晰，尤其是第3問的模型具有較強的般性，適用于樹形結(jié)構(gòu)的通常情形值得注意的是模型中有關(guān)鋪設(shè)費的假設(shè)和表達式與常見情形略有不同摘要：在鋪設(shè)管道為一條線的情況下我們建立了解決鋼管訂購和運輸問題的非線性規(guī)劃模型由于變量較少約束條件大都為線性的，口標(biāo)函數(shù)為二次函數(shù)所以利用lingo軟件可以很快求得比較滿意的訂購和運輸方案我們利用matlab軟件，對所得到的數(shù)據(jù)進行擬合，得到相應(yīng)的反映銷價變化對總費用影響的曲線，然后比較各個鋼廠鋼管銷價變化對總費用影響的大小對于鋼廠鋼管產(chǎn)量上限變化對總費用和購運計劃的影響我們也作了類似的處理如果要鋪設(shè)的管道是樹形圖，我們對樹形圖的每條邊定向，建立了與鋪設(shè)管道為&#

13、183;條線時類似的數(shù)學(xué)模型從而大大拓廣了模刑的使用范圍在論文中我們還對所建立的模型的優(yōu)缺點和需要改進的方向進行了討論1 符號說明·：鋼廠在指定期限內(nèi)鋼管的最大產(chǎn)量；·，之間鋪設(shè)管道的里程數(shù)；·：單位鋼管從鋼廠運到，所需最小訂購和運輸費用；·鋼廠是否承擔(dān)制造這種鋼管；·鋼廠運抵aj點的鋼管數(shù)量，不含路過aj的部分；·運到ai的所有鋼管沿鋪設(shè)的數(shù)量；·：運抵ai的所有鋼管沿鋪設(shè)的數(shù)量；·：樹中aj的度數(shù)；·樹中aj的入度；·樹中aj的出度；·單位鋼管1公里的公路運輸費用。2 基本假設(shè)根據(jù)

14、題目的要求，并為達到簡化問題的目的，我們有以下假設(shè)：1假設(shè)運到aj的鋼管，只能在之間包含aj的某個區(qū)段內(nèi)鋪設(shè),并且到達aj的鋼管在之間包含aj的鋪設(shè)區(qū)段和到達aj+1，的鋼管在aj到aj+2之間包含aj+l的鋪設(shè)區(qū)段不相交否則的話，總可以調(diào)節(jié)鋪設(shè)方案，使得總費用減少2在考慮問題2時，假設(shè)鋼管價格不可能有太大幅度變化所以，我們只考慮鋼管價格在其原售價10的范圍內(nèi)波動同時，我們假定，鋼廠的產(chǎn)量不可能成倍的增加或減少我們在減少300個單位，增加600個單位的范圍內(nèi)討論，這意味著我們不考慮鋼廠破產(chǎn)或者超大規(guī)模擴大生產(chǎn)的情況3在具體鋪設(shè)每一公里時，我們只把鋼管運到每一公里開始的地方，沿運送方向向前鋪，然

15、后往前鋪設(shè)的運送費用我們不予考慮3 模型建立1問題l的模型(1)決策變量我們首先引入一組0一1變量,其中表示鋼廠si是否承擔(dān)制造這種鋼管如果鋼廠si承擔(dān)制造這種鋼管，則，否則.所有的鋼管，都是先運用后，或者轉(zhuǎn)運到其它地方，或者在包含aj的一個區(qū)段內(nèi)鋪設(shè)，我們設(shè)從鋼廠si運抵aj的一個區(qū)段內(nèi)鋪設(shè)的鋼管數(shù)量為,這里我們用變量zj來表示從所有的鋼廠運到aj的鋼管總量中沿鋪設(shè)的部分，這里j=1,2, ,14.這樣，我們一共引入了三組決策變量：。（2）目標(biāo)函數(shù)問題的目的是求好的訂購和運輸方案，使得總費用最小，事實上，總費用可以分成兩部分。第一部分包括鋼管的訂購費用和鋼管從鋼廠運抵所需的運費；我們用來表示

16、單位鋼管從鋼廠所需的最小訂購和運輸費用，則第一部分費用為 第二部分費用是指鋼管運抵后，再運到具體鋪設(shè)地點的費用，由假設(shè)3，從到區(qū)段部分所需的費用為 其中表示鋪設(shè)管道的長度，這樣，我們不難得知第二部分費用為 （3）約束條件首先，由于一個鋼廠如果承擔(dān)制造這種鋼管，則至少需要生產(chǎn)500個單位，而鋼廠在指定期限內(nèi)能生產(chǎn)鋼管的最大數(shù)量為個單位，所以，我們得到以下一組約束條件 由于訂購的所有鋼管總量等于的里程數(shù)，那么 很顯然，我們可以設(shè)，因為如果，則相當(dāng)于有數(shù)量的鋼管是從aj直接運送到后再送到具體鋪設(shè)地點。運抵aj的鋼管總數(shù)量，等于向包含aj的區(qū)段鋪設(shè)的里程數(shù)，那么 并且，我們還有（4）數(shù)學(xué)模型通過上面的分析，我們得到問題1的如下模型 可以看出，這是一個非線性規(guī)劃問題。 2問題2的模型 為了分析鋼廠鋼管銷價的變化對購運計劃和總費用的影響，對于每個鋼廠，利用模型(a)，我們分別算出它的鋼管銷價發(fā)生一系列的變化后，所得到的總費用和購運計劃；并根據(jù)所得到的數(shù)據(jù)，利用matlab軟件擬合出銷價變化和總費用變化量關(guān)系的曲線，對所得到的曲線進行分析和對比，找到鋼管銷價變化對購運計劃和總費用影響最大的鋼廠類似地，我們用同樣的方法，對鋼廠產(chǎn)量上限發(fā)生變化對購運計劃和總費用的影響進行了分析 3問題3的模型如