數(shù)學(xué)模型運(yùn)輸方式選擇

1、數(shù)學(xué)模型課程設(shè)計(jì)報(bào)告書(shū)安徽工業(yè)大學(xué)數(shù)理學(xué)院 論文題目：選擇運(yùn)輸方式姓 名 趙星宇專(zhuān) 業(yè) 信息與計(jì)算科學(xué)班 級(jí) 信111學(xué) 號(hào) 119084103指導(dǎo)教師 侯為根2014年 6 月 25 日 目錄1、 課程設(shè)計(jì)題目.1二、摘要.2三、問(wèn)題分析.3四、數(shù)學(xué)模型的表達(dá). 4-65、 模型實(shí)現(xiàn).6-86、 計(jì)算結(jié)果.8-9七、附件LINGO. .9-131、 課程設(shè)計(jì)題目 選擇運(yùn)輸方式題目：在法國(guó)西南部有一家公司，這家公司需要將 180 噸存放于倉(cāng)庫(kù) D1 到 D4 中的化學(xué)產(chǎn)品運(yùn)輸?shù)?3 個(gè)回收中心 C1，C2 和 C3。倉(cāng)庫(kù) D1 到 D4 分別儲(chǔ)存有 50，40，35， 和 65 噸化學(xué)產(chǎn)品，總

2、計(jì)為 190 噸?？梢赃x用兩種運(yùn)輸方式：公路運(yùn)輸和鐵路運(yùn)輸。 倉(cāng)庫(kù) D1 只能通過(guò)公路向回收中心 C1 和 C2 進(jìn)行運(yùn)輸，運(yùn)費(fèi)分別為 12 歐元/噸和 14 歐元/噸。倉(cāng)庫(kù) D2 只能向回收中心 C2 運(yùn)輸，可以選擇通過(guò)鐵路或公路，運(yùn)費(fèi)分別為12 歐元/噸和 14 歐元/噸。倉(cāng)庫(kù) D3 可以通過(guò)公路向回收中心 C2 運(yùn)輸（9 歐元/噸）， 或通過(guò)鐵路或公路向回收中心 C3 運(yùn)輸，運(yùn)費(fèi)分別為 4 歐元/噸和 5 歐元/噸。倉(cāng)庫(kù) D4 可以通過(guò)鐵路或公路向回收中心 C2 運(yùn)輸，運(yùn)費(fèi)分別為 11 歐元/噸和 14 歐元/噸，或 者通過(guò)鐵路或公路向回收中心 C3 運(yùn)輸，運(yùn)費(fèi)分別為 10 歐元/噸和

3、14 歐元/噸。此公司與鐵路公司簽訂的化學(xué)物品運(yùn)輸合同規(guī)定，每次運(yùn)輸量至少應(yīng)為 10 噸， 最多為 50 噸。除了標(biāo)準(zhǔn)的安全規(guī)章之外，對(duì)公路運(yùn)輸不存在其他特殊的限制。那么 此公司應(yīng)如何運(yùn)輸這 190 噸化學(xué)物品才能夠使總運(yùn)費(fèi)最低？2、 摘要 運(yùn)輸費(fèi)用最低化是我們?cè)诂F(xiàn)代社會(huì)經(jīng)常會(huì)遇到的一個(gè)問(wèn)題。在社會(huì)的經(jīng)濟(jì)生產(chǎn)活動(dòng)中，企業(yè)與客戶(hù)都會(huì)想方設(shè)法合理調(diào)撥資源、降低運(yùn)輸費(fèi)用，實(shí)現(xiàn)雙方利益最大化，完成資源優(yōu)化配置。本文以使物流運(yùn)費(fèi)成本最低為研究對(duì)象，在供應(yīng)量，需求量和單位運(yùn)費(fèi)都已確定的情況下，可用線(xiàn)性規(guī)劃方法來(lái)解決運(yùn)輸中的組織調(diào)撥問(wèn)題。在本文中，我們主要解決的是化學(xué)物品配送最優(yōu)的問(wèn)題，即是使我們花費(fèi)的總運(yùn)

4、費(fèi)最少。我們運(yùn)用系統(tǒng)的觀(guān)點(diǎn)和方法，進(jìn)行綜合分析，發(fā)現(xiàn)問(wèn)題，解決問(wèn)題，使物流運(yùn)輸活動(dòng)更加優(yōu)化、物流運(yùn)輸成本更加合理化。根據(jù)題目中所給出的各約束條件，四個(gè)倉(cāng)庫(kù)、三個(gè)回收中心，每個(gè)倉(cāng)庫(kù)所能到達(dá)的回收中心及運(yùn)費(fèi)也不同。針對(duì)題目中所給信息，要使者190噸化學(xué)物品全部運(yùn)輸?shù)交厥罩行?，同時(shí)，每個(gè)倉(cāng)庫(kù)只能到達(dá)部分回收中心?；谶@兩個(gè)條件，我們建立了在運(yùn)輸目的地有限制情況下使用總運(yùn)費(fèi)最少的模型。我們依據(jù)此模型得出的最優(yōu)運(yùn)輸方案最終要能符合雙方要求，實(shí)現(xiàn)運(yùn)輸資源的合理優(yōu)化使用。 關(guān)鍵詞：化學(xué)物品運(yùn)輸 線(xiàn)性規(guī)劃運(yùn)輸優(yōu)化問(wèn)題運(yùn)費(fèi)最少3、 問(wèn)題分析在本文中，我們主要解決的是化學(xué)物品最優(yōu)的問(wèn)題。在這里的最優(yōu)即是使我們的總

5、運(yùn)費(fèi)花費(fèi)的最少。根據(jù)題目中所給出的條件是有四個(gè)在不同位置的倉(cāng)庫(kù)，每個(gè)倉(cāng)庫(kù)可到達(dá)的回收中心有限制。一共有三個(gè)回收中心，到達(dá)每個(gè)回收中心的方式有兩種，鐵路和公路且費(fèi)用不同。在這次的建模中我們所需要解決的問(wèn)題正是求解一個(gè)最優(yōu)的運(yùn)輸方案，使得總運(yùn)費(fèi)最少。圖形表達(dá)： 圖一運(yùn)輸網(wǎng)絡(luò)圖4、 數(shù)學(xué)模型的表達(dá) 我們將把此問(wèn)題建模為一個(gè)具有固定總通過(guò)量的最小費(fèi)用流問(wèn)題（minimum cost flow problem）。我們先來(lái)構(gòu)造一幅圖 G = (NODES , ARCS )。首先向結(jié)點(diǎn)集合NODES 中加入一組結(jié)點(diǎn)，代表各個(gè)倉(cāng)庫(kù)，然后再加入一組結(jié)點(diǎn)，代表回收中心（參 照?qǐng)D 10.1）?；〖?ARCS 中包

6、含了在所有倉(cāng)庫(kù)和回收中心之間可能存在的連接。運(yùn)輸方案即對(duì)應(yīng)于圖 G 中的一個(gè)流，即在每一條弧 (i , j )上的流 flowij 。弧 (i , j )具有一個(gè)最小通過(guò)量 MINCAPij（除鐵路運(yùn)輸其他均為 0），一個(gè)最大通過(guò)量 MAXCAPij（即 運(yùn)力上限，除鐵路運(yùn)輸外均為無(wú)窮大），以及每噸的運(yùn)輸成本 COSTij 。從一個(gè)倉(cāng)庫(kù)到一個(gè)處理中心之間的兩種運(yùn)輸方式需對(duì)應(yīng)兩條不同的弧。在這樣的圖中，兩個(gè)結(jié)點(diǎn)之間至多有 p 條弧，稱(chēng)為 p -圖。這樣的圖無(wú)法編碼為（二維）矩陣： 例如費(fèi)用矩陣中的元素 COSTij 只能表示一個(gè)費(fèi)用。為將此圖轉(zhuǎn)化為兩個(gè)結(jié)點(diǎn)之間至多有一條弧的圖，可以為倉(cāng)庫(kù) i 和

7、處理中心 j 之間的每種運(yùn)輸方式都創(chuàng)建一個(gè)假想的結(jié)點(diǎn)。例如，在倉(cāng)庫(kù) D2（結(jié)點(diǎn) 3）和處理中心 C1（結(jié)點(diǎn) 12）之間存在一條公路連 接和一條鐵路連接。為避免生成具有兩條弧 (3,12)的 2-圖，我們可以創(chuàng)建一個(gè)結(jié)點(diǎn) 6對(duì)應(yīng)于鐵路運(yùn)輸，以及一個(gè)結(jié)點(diǎn) 7 對(duì)應(yīng)于公路運(yùn)輸。則鐵路運(yùn)輸即變?yōu)槁窂?(3,6,12) ， 公路運(yùn)輸即變?yōu)?(3,7,12)。只為弧 (3,6)和 (3,7) 設(shè)置通過(guò)量和費(fèi)用。在此圖中未將倉(cāng)庫(kù)的存儲(chǔ)量納入考慮。為此，我們創(chuàng)建一個(gè)源結(jié)點(diǎn)（假想的結(jié)點(diǎn)1），此結(jié)點(diǎn)將用弧 (1,d ) 連接到每個(gè)倉(cāng)庫(kù)結(jié)點(diǎn) d 上，且此弧的通過(guò)量為 MAXCAP1d ， 對(duì)應(yīng)于倉(cāng)庫(kù) d 處的存儲(chǔ)量

8、。因此離開(kāi)倉(cāng)庫(kù) d 的流不會(huì)超過(guò)此值。為方便數(shù)學(xué)模型的表達(dá)，我們也創(chuàng)建一個(gè)宿結(jié)點(diǎn)（假想的結(jié)點(diǎn) 15），并且連接到每個(gè)處理中心結(jié)點(diǎn)上。 這樣最終得 到的圖即可 以表示為圖 10.1，其 中 每條弧 (i , j ) 都對(duì)應(yīng)于一個(gè)三 元 組( MINCAP ,MAXCAP ,COST )?！?”表示通過(guò)量為無(wú)窮大。第 11 頁(yè) 共 14 頁(yè) 在此數(shù)學(xué)模型中包含了流守恒約束條件（10.2.2），也稱(chēng)為 Kirchhoff 定理：每個(gè)結(jié)點(diǎn)處的入流都等于此結(jié)點(diǎn)處的出流（除了源和宿結(jié)點(diǎn)之外）。每條弧上的流都至少取值為 MINCAPij （約束條件（10.2.3），且不超過(guò)最大通過(guò)量 MAXCAPij （約

9、束條 件（10.2.4）。式（10.2.5）對(duì)總流量加以約束，即 MINQ = 180 噸。這樣就迫使離開(kāi)源（結(jié)點(diǎn) 1）的流總量等于 MINQ 。由于在此網(wǎng)絡(luò)中流保持守恒，因此也可以使 用宿結(jié)點(diǎn)的入流總量等于 MINQ 作為約束條件。在這個(gè)約束條件中，我們可以將等號(hào)替換為 號(hào)，由于在最小化總成本時(shí)也將最小化總流量，因此此時(shí)總運(yùn)輸量將取此 下界值。最后要解釋一下目標(biāo)函數(shù)（10.2.1）。 COSTij 是每噸的運(yùn)費(fèi)成本，因此通過(guò)弧 (i , j )運(yùn)輸?shù)牧?flowij 的費(fèi)用為 COSTij flowij 。因此最小化總運(yùn)費(fèi)即最小化所有弧 上的總費(fèi)用。最終，通過(guò)定義這樣的圖，我們可以得到相當(dāng)簡(jiǎn)

10、潔的數(shù)學(xué)模型。注意，在約束條 件（10.2.3）中也隱含給出了變量非負(fù)的約束條件。 minimize （10.2.1） i NODES ,i SOURCE ,SINK := (10.2.2) (i,j) ARCS, (10.2.3) (i,j) ARCS, (10.2.4) = MINQ (10.2.5) 除了這種基于圖的問(wèn)題數(shù)學(xué)表達(dá)之外，也可以將使用方式 m 從倉(cāng)庫(kù) d 運(yùn)輸?shù)侥?標(biāo) c 的運(yùn)量表示為決策變量 trasnport dcm ，對(duì)每個(gè)可能出現(xiàn)的三元組 (d ,c,m)都建立 這樣的決策變量，從而得到另一種問(wèn)題表達(dá)方式。這樣總運(yùn)量就可以表示為所有有定義的變量 trasnport d

11、cm 的和，目標(biāo)函 數(shù)即所有可 行的三元組 (d ,c,m) 對(duì)應(yīng)的 COSTdcm trasnport dcm 的和。每種運(yùn)輸方式的最小和最大運(yùn)力限制將表示為對(duì)應(yīng)變 量 trasnport dcm 的上界和下界約束條件，這一點(diǎn)與上述的（10.2.3）和（10.2.4）很相似。對(duì)于我們這個(gè)問(wèn)題，這種表達(dá)方式可能比基于圖的模型表達(dá)要容易一些。但在后面的模型實(shí)現(xiàn)和進(jìn)一步的討論中，我們?nèi)匀皇褂眠@種更一般的最小費(fèi)用流模型，即（10.2.1）到（10.2.5）給出的模型。5、 模型實(shí)現(xiàn) 從這個(gè)問(wèn)題可以引出一個(gè)經(jīng)典的問(wèn)題，即圖的編碼?？梢詫D定義為 N N 的 矩陣形式，其中 N 為結(jié)點(diǎn)總數(shù)，并為每對(duì)由弧

12、相連的結(jié)點(diǎn) (i , j )都定義一個(gè)流變量。 然而，對(duì)于稀疏圖，如我們所使用的這個(gè)圖，更常用（效率也更高）的方法是將圖表示為弧的列表的形式。在下面的 Mosel 程序?qū)崿F(xiàn)種就使用了這種表示方法?； = (i , j )將用標(biāo)號(hào) a 進(jìn)行索引，而不是用對(duì)應(yīng)的結(jié)點(diǎn)對(duì) (i , j )進(jìn)行索引。弧的列表為二維數(shù)組 A ，其中 Aa1 = i ， Aa 2 = i 。在讀入數(shù)據(jù)后（即弧集為已知）將定義流變 量。注意在下面的實(shí)現(xiàn)中，未采用數(shù)字對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，而是用名稱(chēng)“Source”，“D2”， “C4”等，這樣能夠能夠方便對(duì)結(jié)果進(jìn)行解釋。model E-2 Minimum cost flow us

13、es declarationsNODES: set of string! 結(jié)點(diǎn)集合MINQ : integer ! 運(yùn)輸總量A: array(ARCS:range,1.2) of string! 弧COST: array(ARCS) of integer! 每條弧的運(yùn)輸成本MINCAP,MAXCAP: array(ARCS) of integer! 弧的最小和最大通過(guò)量end-declarationsinitializations from e2minflow.datA MINQ MINCAP MAXCAP COSTend-initializations finalize(ARCS)! 計(jì)算結(jié)

14、點(diǎn)集合NODES:= union(a in ARCS) A(a,1),A(a,2)declarationsflow: array(ARCS) of mpvar! 弧上的流end-declarations! 目標(biāo)函數(shù)：總運(yùn)輸成本Cost:= sum(a in ARCS) COST(a)*flow(a)! 流平衡：入流等于出流For all(n in NODES | nSOURCE and nSINK)sum(a in ARCS | A(a,2)=n) flow(a) = sum(a in ARCS | A(a,1)=n) flow(a)! 最小和最大流通過(guò)量For all(a in ARCS |

15、 MAXCAP(a) 0) do flow(a) = MINCAP(a)flow(a) = MINQ! 求解此問(wèn)題minimize(Cost)end-model6、 計(jì)算結(jié)果 最低運(yùn)輸成本為 1,715 歐元。圖 10.2 示意了此時(shí)的解決方案：在實(shí)際用于運(yùn)輸 的弧上標(biāo)出了運(yùn)輸量，未使用的弧用虛線(xiàn)表示。例如，倉(cāng)庫(kù) D1 的所有 50 噸庫(kù)存都 將通過(guò)公路運(yùn)輸?shù)交厥罩行?2。 上圖最優(yōu)運(yùn)輸方案 應(yīng)注意到，這種對(duì)弧上的流有最小約束的問(wèn)題可能會(huì)無(wú)法找到可行解。在本例中，如果 MINQ = 9 ，則由于所有鐵路運(yùn)輸?shù)幕〉淖畹屯ㄟ^(guò)量都是 10 噸，因此無(wú)法使用 鐵路運(yùn)輸。七、附件 Lingo編寫(xiě)模型程序

16、：model:! 3 Warehouse,4 Customer Transportation Problem;sets: Warehouse/1.3/:a; Customer/1.4/:b; Routes(warehouse,customer):c,x;End sets!here are the parameters;data:a=30,25,21;b=15,17,22,12;c=6,2,6,7, 4,9,5,3, 8,8,1,5;End data! The objective;obj min=sum(routes:c*x);!The supply constraints;for(wareho

17、use(i):supsum(customer(j):x(i,j)=a(i);!The demand constraints;for(customer(j):dem sum(warehouse(i):x(i,j)=b(j);end計(jì)算結(jié)果：Global optimal solution found. Objective value: 161.0000 Total solver iterations: 6 Variable Value Reduced Cost A( 1) 30.00000 0.000000 A( 2) 25.00000 0.000000 A( 3) 21.00000 0.0000

18、00 B( 1) 15.00000 0.000000 B( 2) 17.00000 0.000000 B( 3) 22.00000 0.000000 B( 4) 12.00000 0.000000 C( 1, 1) 6.000000 0.000000 C( 1, 2) 2.000000 0.000000 C( 1, 3) 6.000000 0.000000 C( 1, 4) 7.000000 0.000000 C( 2, 1) 4.000000 0.000000 C( 2, 2) 9.000000 0.000000 C( 2, 3) 5.000000 0.000000 C( 2, 4) 3.0

19、00000 0.000000 C( 3, 1) 8.000000 0.000000 C( 3, 2) 8.000000 0.000000 C( 3, 3) 1.000000 0.000000 C( 3, 4) 5.000000 0.000000 X( 1, 1) 2.000000 0.000000 X( 1, 2) 17.00000 0.000000 X( 1, 3) 1.000000 0.000000 X( 1, 4) 0.000000 2.000000 X( 2, 1) 13.00000 0.000000 X( 2, 2) 0.000000 9.000000 X( 2, 3) 0.0000

20、00 1.000000 X( 2, 4) 12.00000 0.000000 X( 3, 1) 0.000000 7.000000 X( 3, 2) 0.000000 11.00000 X( 3, 3) 21.00000 0.000000 X( 3, 4) 0.000000 5.000000 Row Slack or Surplus Dual Price OBJ 161.0000 -1.000000 SUP( 1) 10.00000 0.000000 SUP( 2) 0.000000 2.000000 SUP( 3) 0.000000 5.000000 DEM( 1) 0.000000 -6.

21、000000 DEM( 2) 0.000000 -2.000000 DEM( 3) 0.000000 -6.000000事實(shí)上，我們關(guān)心更多的是那些非零變量，因此，可選擇“Lingo|solution.”彈出一個(gè)對(duì)話(huà)框（介紹此對(duì)話(huà)框），選擇“nonzeros only”，即可只列出非零變量： Global optimal solution found. Objective value: 161.0000 Total solver iterations: 6 Variable Value Reduced Cost A( 1) 30.00000 0.000000 A( 2) 25.00000 0.000000 A( 3) 21.00000 0.000000 B( 1) 15.00000 0.000000 B( 2) 17.00000 0.000000 B( 3) 22.00000