全國數學建模競賽B題優(yōu)秀論文

1、1 問題重述2 基本假設 (1)只考慮訂購費用和運輸費用，不考慮裝卸等其它費用 (2)鋼管單價與訂購量、訂購次數、訂購日期無關(3)訂購汁劃是指對每個廠商的定貨數量；運輸方案是指具有如下屬性的一批記錄：管道區(qū)間，供應廠商，具體運輸路線 (4)將每一單位的管道所在地看成一個需求點，向一單位管道的所在地運輸鋼管即為向一個點運輸鋼管3 符號說明 M：鋼廠總數. n：單位管道總數.第i個鋼廠 第i個鋼廠的產量上限。第i個鋼廠單位鋼管的銷售價 管道線上第i個站點。管道線上第i個單位管道的位置。 F：總費用。從鋼廠到點的最低單位費用。4 問題的簡化求 S AP 矩陣的基本思路是圖的最短路算法 . 由于鐵路

2、的運輸費用與線路的長度不是線性關系 ,必須對鐵路網做一些預處理才能套用圖的標準最短路算法 . 下面敘述求 S AP 矩陣的過程:1. 利用圖的標準最短路算法 ,從鐵路網絡得出圖中任兩個點之間的最短路徑表 T (如 果兩個點之間不連通 ,認為它們之間的最短路長度為+ ) .2. 利用題中的鐵路運價表將 T 中的每個元素 (即最短距離 )轉化為運輸費用 ,將運輸費 用表記為 C.3. 將公路的長度換算為運輸費用 ,由公路路程圖 (包括要沿線鋪設管道的公路 )得出公路費用圖 G,若 i, j 不連通 ,則令 Gij = + .4.對于任一組 ( i , j) 1, n × 1, m 如果

3、Cij <+ ,且小于 Gij ,那么就在公路費 用圖中加一條邊. 即令 Gij = minCij , Gij .5.利用圖的標準最短路算法 ,求公路費用圖中任一個 S 點到任一個 A 點的最小費用 路徑 ,得出 S AP 矩陣. 如表 1所示:SAP 矩陣A123456789101112131415S1170716031402986380205312126429209601060121212801420221572053190217161110955860712114214201460156017121780192032307220320021816121010559608624828

4、20860960111211801320426072503235221661560140513101162842620510610762830970525572453225220661460130512101112792570330510712730870626572553235221661560140513101212842620510450262110280727572653245222661660150514101312992760660560382260205問題分析 運輸費用等價轉換法則：按單位運費相等原則將任意兩點間的最短鐵路線轉換為公路線對于鐵路線上的任意兩點，用F1oyd算法找

5、出兩點間最短鐵路路線的長度查鐵路運價表求得，對應的鐵路單位運費;又設與該段鐵路等費用的公路長度為，則：由此，我們就在之間用一條等價的公路線來代替間的最短鐵路線如果之間原來就有公路，就選擇新舊公路中較短的一條這樣，我們就把鐵路運輸網絡轉換成了公路運輸網絡銷價等價轉換法則：按單位費用相等將任意鋼廠的單位銷價轉換為公路單位運價對于鋼廠Si的銷售單價Pi，我們可以虛設一條公路線，連接鋼廠Si及另一虛擬鋼廠，其長度為，并且滿足；從而將鋼廠的銷售單價轉換成公路運輸單價，而新鋼廠的銷售價為0.將鐵路和銷價轉換為公路的過程可以由計算機編程實現(xiàn)通過上述的分析，我們可以將原問題化為一個相對簡單的產量未定的運輸問題

6、，利用之間的管道距離和鋼廠和站點之間的公路距離建立一個產量未定的運輸問題的模型但是由于并不能代表所有的實際需求點(實際需求點是n個單位管道)，因此，我們可以用F1oyd算法進一步算出7個鋼廠到所有實際的n個需求點(對于問題一，n5171;對于問題三，n5903)的最短路徑，并由此得出一個具有7個供應點、n個需求點的產址未定的運輸模型6 模型的建立產量未定的運輸模型根據假設4，我們可以將每一單位的管道看成一個需求點，向一單位管道的所在地運輸鋼管即為向一個點運輸鋼管對每個點，我們可以根據該點的位置和最短等價公路距離，求出各鋼廠與該點之間最小單位運輸費用(銷價已經歸人運輸費用之中了)設總共有m個供應

7、點(鋼廠)，n個需求點，我們就可以得到一個產量未定的運輸模型：有m個供應點、n個需求點，每個供應點的供應量；每個需求點需要1單位，運輸單價矩陣為C，求使得總運輸費用最小的運輸方案其數學規(guī)劃模型：其中： 為單位費用矩陣為決策矩陣，也為0-1矩陣代碼如下7 模型的求解對于本題，上述0-1規(guī)劃規(guī)模宏大，現(xiàn)有的一些算法不能勝任，我們必須具體問題具體分析，結合本題實際情況，尋找行之有效的算法(1)初始方案的改進的最小元素法和改進的伏格爾法*改進的最小元素法改進的最小元素法又稱為貪婪法或瞎子爬山法，它的宗旨是每一步都取當前的最優(yōu)值算法步驟為，對費用矩陣C作n次下列循環(huán)：C中找一個最小值；令C的第j的所有數

8、據改為+；如果，第i個供應點的供應量已達上限，將C的第i行數據全改為+。對于問題一和問題三，我們用貪婪法求得的最小總費用的初始分別為1286692.1萬元和1414515.2萬元。（2）調整優(yōu)化調整優(yōu)化是將一個離最優(yōu)解很近的初始解調整到在調整算法下無法更優(yōu)的程度調整優(yōu)化分兩個部分，第一部分是用試探法對供應點的供應量進行優(yōu)化第二部分是用迭代法對供應點進行兩兩對調優(yōu)化*試探法調整優(yōu)化實際供應量在500以下的供應點對每個實際供應量在500以·F的供應點，只存在兩種合理的優(yōu)化方法：一種是將其供應量增加到500，另一種是將其供應量減少到0試探法將分別試探進行下列兩種優(yōu)化：其一是先將供應點的供應

9、量強行提升至500，使用改進的伏格爾法的優(yōu)先順序，從其它供應點負責供應的需求點搶奪一部分，再用對調法優(yōu)化至無法更優(yōu)，得出一個總費用F1；其二是先將該供應點的供應量調整為0，其原供應的需求點由其它鋼廠用改進的伏格爾法的優(yōu)先順序補充，再用對調法優(yōu)化至無法更優(yōu)，得出一個總費用F2那么，就應當采取總費用較小的方法例如，對于第一問，按改進的伏格爾法獲得的初始方案中，S7的用量僅為245，優(yōu)化時，試探將其降為0和將其提升為500后的最優(yōu)結果，分別為1279019萬元和1280506萬元，則說明應將S，降為0*用迭代法進行對調優(yōu)化改進的伏格爾法給出的初始值雖然很接近最優(yōu)值，但仍有不足之處，即可能存在兩個需求

10、點，調換供應點能使總費用更小，例如，需求點a和6的供應點是x和y，費用分別是C(x,a)和C(y,b)，如果讓y供應a，x供應b的話，費用將是C(y，a)和r(c，b)，如果： C(y，a)+r(x，b)<C(x，a)+C(y，b)則說明對調后總費用更低因此，我們可以采用迭代法對任意兩個需求點的供應點兩兩對調至無法更優(yōu)由于一共只有m7個供應點，所以兩兩對調的可行方案一共有種，因此，兩兩對調供應點的方法是可行的，具體步驟如下：Stepl 對于任意兩個供應點xi和xj i1，2，m j=1，2，m 1)找出所有由xi供應的需求點，構成點集Aa1,a2,c2)找出所有由xj供應的需求點，構成點

11、集Bb1,b2,3)對A中所有點，如果改用xj來供應，將付出的代價構成向量4)對B中所有點，如果改用xi來供應，將付出的代價構成向量5)對分別按升序排序6)同時對從前向后遍歷，如果(表示對調供應者將降低總費用)，則對調其供應者，直到出現(xiàn)為止Step2 統(tǒng)計這輪對調后的總費用是否比原來的總費用F有明顯的進步，即。如果有明顯的進步，則再回Stepl執(zhí)行，否則結束優(yōu)化采用改進的最小元素法和改進的伏格爾法得到問題一的初始方案分別采用這種優(yōu)化方案后，竟都達到了相同的最小費用：1279019萬元 8 結果：通過合理假設并引人等價轉換原則，將管道訂購與運輸問題轉化為單一的公路運輸問題運用組合優(yōu)化的思想和方法

12、，給出了數學模型·產量未定的運輸模型針對此模型，我們設計了“改進的最小元素法”和“改進的伏格爾Ph"，先求得了個初始解。再通過“試探法”和“迭代法”進行調調優(yōu)化最后得出結果：對第·問最小總費用為1279019萬元；對第三問最小總費用為1407383萬元參考文獻1薛秀謙等編著運籌學.中國礦業(yè)大學出版社1998年2趙新澤著線性規(guī)劃的新方法和應用世界圖書出版社，1996年3王樹禾著圖論極其算法中國科學技術大學出版社1990年4LUCAS W F著離散與系統(tǒng)模型3國防科技大學出版社，1996年鋼管訂購和運輸策略1 符號說明·：鋼廠在指定期限內鋼管的最大產量；&#

13、183;，之間鋪設管道的里程數；·：單位鋼管從鋼廠運到，所需最小訂購和運輸費用；·鋼廠是否承擔制造這種鋼管；·鋼廠運抵Aj點的鋼管數量，不含路過Aj的部分；·運到Ai的所有鋼管沿鋪設的數量；·：運抵Ai的所有鋼管沿鋪設的數量；·：樹中Aj的度數；·樹中Aj的入度；·樹中Aj的出度；·單位鋼管1公里的公路運輸費用。2 基本假設根據題目的要求，并為達到簡化問題的目的，我們有以下假設：1假設運到Aj的鋼管，只能在之間包含Aj的某個區(qū)段內鋪設,并且到達Aj的鋼管在之間包含Aj的鋪設區(qū)段和到達Aj+1，的鋼管在Aj

14、到Aj+2之間包含Aj+l的鋪設區(qū)段不相交否則的話，總可以調節(jié)鋪設方案，使得總費用減少2在考慮問題2時，假設鋼管價格不可能有太大幅度變化所以，我們只考慮鋼管價格在其原售價10的范圍內波動同時，我們假定，鋼廠的產量不可能成倍的增加或減少我們在減少300個單位，增加600個單位的范圍內討論，這意味著我們不考慮鋼廠破產或者超大規(guī)模擴大生產的情況3在具體鋪設每一公里時，我們只把鋼管運到每一公里開始的地方，沿運送方向向前鋪，然后往前鋪設的運送費用我們不予考慮3 模型建立1問題l的模型(1)決策變量我們首先引入一組0一1變量,其中表示鋼廠Si是否承擔制造這種鋼管如果鋼廠Si承擔制造這種鋼管，則，否則.所有

15、的鋼管，都是先運用后，或者轉運到其它地方，或者在包含Aj的一個區(qū)段內鋪設，我們設從鋼廠Si運抵Aj的一個區(qū)段內鋪設的鋼管數量為,這里我們用變量Zj來表示從所有的鋼廠運到Aj的鋼管總量中沿鋪設的部分，這里j=1,2, ,14.這樣，我們一共引入了三組決策變量：。（2）目標函數問題的目的是求好的訂購和運輸方案，使得總費用最小，事實上，總費用可以分成兩部分。第一部分包括鋼管的訂購費用和鋼管從鋼廠運抵所需的運費；我們用來表示單位鋼管從鋼廠所需的最小訂購和運輸費用，則第一部分費用為第二部分費用是指鋼管運抵后，再運到具體鋪設地點的費用，由假設3，從到區(qū)段部分所需的費用為其中表示鋪設管道的長度，這樣，我們不

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