1、運輸問題摘要本文主要研究了配送貨物的行使路線問題。根據題目要求,采用Fleury算法,建立01型整數規劃模型，并利用lingo，求出了最短行使路線和裝配方案，使得運輸公司運貨的總費用最少。針對問題一，本文將運送路線看作是10個客戶點作為頂點的有向的網絡圖，做出賦權鄰接矩陣，采用Dijkstra算法思想，利用lingo編程,求出從客戶2到客戶10最短的行使路線，最短行使路線為：，路程為85公里。針對問題二，要求設計貨車從提貨點到送貨點再返回提貨點的最短路線。本文采用Fleury算法思想，根據不同的權值客戶與客戶之間的距離，形成Euler回路，建立線性規劃模型，利用lingo, 求出有最小權的Ha

2、milton圈，即最短的行駛路線。最短的行使路線為：路程為225公里。針對問題三，本文首先從每輛車的容量與各個客戶的需求量之間的關系考慮，得出每輛車的載貨量在36至50之間，進一步分析得出兩種情況：1、兩輛車分別裝5個和4個客戶的貨物；2、兩輛車分別裝6個和3個客戶的貨物。然后分別對以上兩種情況進行討論，分別以其中一輛車行使的最小路程為目標函數，以 每個客戶必須有車到達、車的裝載容量和附加變量防止構成內圈為約束條件，建立01線性規劃模型，利用lingo，通過比擬優化，得出最正確的配送方案如下表：車號行使路線路徑長度公里總路徑長度公里負責的客戶1號車135 2904,5,8,9,102號車155

3、 2,3,6,7針對問題四，我們以總運費最小為目標函數，約束條件和問題三的類似，建立0-1型整數規劃模型。運用lingo求得當有4輛車運送貨物時總費用最小，為645元。具體運輸方式為：； ；關鍵詞：0-1型整數規劃 Fleury算法 Lingo一、問題重述某運輸公司為10個客戶配送貨物，假定提貨點就在客戶1所在的位置，從第i個客戶到第j個客戶的路線距離單位公里用下面矩陣中的位置上的數表示其中表示兩個客戶之間無直接的路線到達。運送員在給第二個客戶卸貨完成的時候，臨時接到新的調度通知，讓他先給客戶10送貨，送給客戶10的貨已在運送員的車上，請幫運送員設計一個到客戶10的盡可能短的行使路線假定上述矩

4、陣中給出了所有可能的路線選擇。現運輸公司派了一輛大的貨車為這10個客戶配送貨物，假定這輛貨車一次能裝滿10個客戶所需要的全部貨物，請問貨車從提貨點出發給10個客戶配送完貨物后再回到提貨點所行使的盡可能短的行使路線？對所設計的算法進行分析。現因資源緊張，運輸公司沒有大貨車可以使用，改用兩輛小的貨車配送貨物。每輛小貨車的容量為50個單位，每個客戶所需要的貨物量分別為8，13，6，9，7，15，10，5，12，9個單位，請問兩輛小貨車應該分別給那幾個客戶配送貨物以及行使怎樣的路線使它們從提貨點出發最后回到提貨點所行使的距離之和盡可能短？對所設計的算法進行分析。如果改用更小容量的車，每車容量為25個單

5、位，但用車數量不限，每個客戶所需要的貨物量同第3問，并假設每出一輛車的出車費為100元，運貨的價格為1元/公里不考慮空車返回的費用，請問如何安排車輛才能使得運輸公司運貨的總費用最省？二、問題分析問題一的分析題目要求設計一個盡可能短的行路線，使運送員在給第2個客戶卸貨完成的時候讓他先給客戶10送貨。從客戶與客戶之間的距離矩陣可以發現客戶2到客戶10無直接的路線到達，于是本文將運送路線看做是10個客戶點作為頂點的有向的網絡圖，然后編寫程序，利用lingo,求出最短的行使路線。問題二的分析題目要求設計貨車從提貨點1出發給10個客戶配送完貨物后再回到提貨點盡可能短的行使路線。這個問題與旅行商問題類似，

6、于是，本文將路線轉化為Hamilton圈，根據不同的權值客戶與客戶之間的距離，利用lingo, 求出有最小權的Hamilton圈，即最短的行駛路線。 對于問題三，我們將貨物分成兩種情況進行分析。第一種情況：兩輛車中一輛車裝載4個客戶的貨物，另外一輛車裝載5個客戶的貨物。第二種情況：兩輛車中一輛車裝載3個客戶的貨物，另外一輛車裝載6個客戶的貨物。但是每輛車貨物的容量小于50大于36，我們將每輛車的容量作為約束條件。每個客戶點總會有一輛車進入，然后再離開，我們對這個問題采用01規劃模型進行運算。 將添加一種在原模型上附加充分的約束條件以防止產生子巡回的方法，把額外變量附加到問題中。可以把這些變量看

7、作是連續的雖然這些變量在最優解中取普通的整數值。現在附加下面形式的約束條件：將其中一輛車行使的最小路程為目標函數，建立線性規劃模型。2.4問題四的分析 對于問題四，要使總費用最低，必須使出車費與運費的和最少。由于車輛的個數不限，我們首先假設用k輛車來運送貨物，又根據每輛車最多可運25個單位的貨物，所以至少4輛車運送貨物。又因為不考慮空車輛返回時的費用，故只需考慮運輸貨物時的路程最短。我們建立01型整數規劃模型，將最小費用作為目標函數，運用lingo求得最優解，得出最正確的配送方案。三、問題假設1、假設提貨點就在客戶1所在的位置，客戶1所需的貨物不用裝車配送；2、假設每個客戶需要的是同一種貨物。

8、四、符號說明其中一輛車負責的客戶數第i個客戶到第j個客戶的路程，i,j=1,2,10為1時，表示走過城市i到城市j之間的路i,j=1,2,10Z一輛運貨車走過的路程W總費用五、模型的建立與求解模型一的建立與求解 由客戶與客戶之間的距離矩陣可以看出，這是一個有向網絡圖且圖中有10個頂點，現需要求從頂點2到頂點10的最短路。設為賦權鄰接矩陣，其分量為決策變量為，當=1時，說明弧位于頂點2至頂點n的路上；否那么=0.其數學規劃表達式為：S.t. 由上面的數學規劃表達式和客戶與客戶之間的距離矩陣，編寫程序，利用lingo見附錄1,求得從客戶2到客戶10的最短行使路線為：；最短路程為：30+25+10+

9、20=85公里.公司要求用送貨員從客戶1出發，給其它9個客戶送貨，最后再返回出發地，這和旅行商問題類似。于是，設城市的個數為 n, 是兩個城市i與j之間的距離，=0或11表示走過城市i到城市j之間的路，0表示沒有走過城市i到城市j之間的路，表示集合s中元素個數。有s.t. 由上面的數學規劃表達式和客戶與客戶之間的距離矩陣，編寫程序，利用lingo(見附錄2),求得從客戶1 出發，經過其它各個客戶點再回到客戶1的最短行使路線為：最短路程為：25+10+25+30+15+20+10+20+20+50=225公里.每輛車的容量要小于50，可以轉換為一輛車所裝載的貨物大于36小于50，可建立約束條件為

10、： 因為是兩輛車給顧客送貨，所以說每輛車不需要經過所有的顧客點，每個顧客點只需要有車經過，然后在離開即可。因此我們采用01規劃模型將進去顧客點用1表示否那么用0表示，離開顧客點用1表示否那么用0表示。所以我們建立的約束條件為： 故可建立如下模型：運用lingo見附錄3可以求得以下結果表1 其中一輛車經過的路徑及長度K的值滿足條件的較短路徑1-1路徑長度單位：公里3955135由以上數據我們求出一輛車的最短路徑，第二輛車的行使路徑必須經過第一輛車所沒經過的客戶點。于是我們建立新的模型，如下所示：運用lingo求得結果如下：表2 另一輛車經過的路徑及長度K的值滿足條件的較短路徑2-1路徑長度單位：

11、公里62054155通過表1、表2，我們得出：第一種情況兩輛車中一輛車裝載5個客戶的貨物，另外一輛車裝載4個客戶的貨物，總的路徑長度為：135+155=290公里；第二種情況兩輛車中一輛車裝載3個客戶的貨物，另外一輛車裝載6個客戶的貨物，總的路徑長度為：95+205=300公里。根據題目要求行使的距離之和盡可能短，因此，第一種情況的方案較好。在執行此方案時，一號車的載貨量為：9+7+5+12+9=42；二號車的載貨量為：13+6+15+10=44，滿足車容量條件。表3 最優的配送方案車號行使路線路徑長度公里總路徑長度公里負責的客戶1號車135 2904,5,8,9,102號車155 2,3,6

12、,7模型四的建立與求解每個客戶有一輛車到達為其送貨，所為我們建立的約束條件為：因為不考慮返回時的費用，所以我們建立的約束條件為：每輛車的最大容量為25，所以我們建立的約束條件為：以總費用最小為目標函數建立如下模型： 運用lingo計算出k等于4時，總費用W最小為645。具體路線如下表：表4 最優的配送方案車號行使路線路徑長度公里負責的客戶1號車402,52號車803,4,83號車556,74號車709,10六、模型的評價與推廣模型的優點模型運用01線性規劃模型和整數線性規劃建立的模型比擬簡單明了思路清晰，該模型主要運用lingo進行計算，其中還引入Hamilton圈的進行求解，使得結果更加精確

13、。我們還用統一的模型同時計算出兩輛車的最優路線，得出最優解。模型的缺點及改良該模型計算量較大，數據較多，計算過程比擬繁瑣。我們可以改良模型使得計算量減少，防止在計算中產生的錯誤。模型的推廣該模型可應用于物流行業，運費減少公司獲得的利潤增大。還可應用于郵遞員投遞問題，使郵遞員走的路程最短，提高工作效率。七、參考文獻1?運籌學?教材編寫組，運籌學修訂版，北京：清華大學出版社，1990.2謝金星，薛毅編著，優化建模與LINDO/LINGO 軟件，北京：清華大學出版社， 2005。3白其崢主編，數學建模案例分析，北京：海洋出版社，2000。4萬保成 王田蛾，?lingo9.0 for windows軟

14、件及應用?，吉林農業大學數學教研室，2004。5Frank R. Giordano 著，葉其孝 姜起源譯，?數學建模?，機械工程出版社，2006。八、附錄附錄1model:data: n=10;enddatasets: points/1.n/: F; !10個客戶點; roads(points,points)/ 1,2 2,3 2,5 2,6 2,8 3,4 3,6 3,7 3,8 3,10 4,5 4,6 4,7 4,8 4,9 4,10 5,6 5,7 5,8 5,10 6,7 6,8 6,9 7,8 7,9 7,10 8,9 9,10/: D, P;endsetsdata:D= 50 3

15、0 35 50 60 15 30 50 25 60 45 30 55 20 40 65 60 10 30 55 25 55 35 30 45 60 10 20;enddata F(n)=0; for(points(i) | i #lt# n: F(i)=min(roads(i,j): D(i,j)+F(j);); !顯然，如果P(i,j)=1,那么點i到點n的最短路徑的第一步是i - j，否那么就不是。 由此，我們就可方便確實定出最短路徑; for(roads(i,j): P(i,j)=if(F(i) #eq# D(i,j)+F(j),1,0) );End附錄2MODEL:SETS: CUST

16、OMERS / 1. 10/: U; LINK( CUSTOMERS, CUSTOMERS): DIST,X; ENDSETS DATA: DIST = 0 50 100000 40 25 100000 30 100000 50 100000 50 0 30 100000 35 50 100000 60 10000 100000 100000 30 0 15 100000 30 50 25 100000 60 40 10000 15 0 45 30 55 20 40 65 25 15 100000 45 0 60 10 30 100000 55 100000 50 30 30 60 0 25

17、55 35 1000000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0;ENDDATA N = SIZE( CUSTOMERS); MIN = SUM( LINK: DIST * X); FOR( CUSTOMERS( K): SUM( CUSTOMERS( I)| I #NE# K: X( I, K) = 1; SUM( CUSTOME

18、RS( J)| J #NE# K: X( K, J) = 1; FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K) ); ); FOR( LINK: BIN( X); FOR( CUSTOMERS( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1) );END附錄3model:sets: CUSTOMERS/ 1.10/: u,D; link( CUSTOMERS,

19、 CUSTOMERS):C, x; endsets min = sum( link: C*x); sum(CUSTOMERS( I)| I #ne# 1: x(I, 1)=1; sum(CUSTOMERS( I)| I #ne# 1: x(1,I)=1; FOR( CUSTOMERS(K): sum( CUSTOMERS( I)| I #ne# K: x( I, K)1; sum( CUSTOMERS( J)| J #ne# K: x(K,J)K;sum(link(I,J)|I #ne# J:x(I,J)*D(J)36;sum(link(I,J)|I #ne# J:x(I,J)*D(J)86;for(CUSTOMERS