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

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

2、計為 190 噸。可以選用兩種運(yùn)輸方式：公路運(yùn)輸和鐵路運(yùn)輸。 倉庫 D1 只能通過公路向回收中心 C1 和 C2 進(jìn)行運(yùn)輸，運(yùn)費(fèi)分別為 12 歐元/噸和 14 歐元/噸。倉庫 D2 只能向回收中心 C2 運(yùn)輸，可以選擇通過鐵路或公路，運(yùn)費(fèi)分別為12 歐元/噸和 14 歐元/噸。倉庫 D3 可以通過公路向回收中心 C2 運(yùn)輸（9 歐元/噸）， 或通過鐵路或公路向回收中心 C3 運(yùn)輸，運(yùn)費(fèi)分別為 4 歐元/噸和 5 歐元/噸。倉庫 D4 可以通過鐵路或公路向回收中心 C2 運(yùn)輸，運(yùn)費(fèi)分別為 11 歐元/噸和 14 歐元/噸，或 者通過鐵路或公路向回收中心 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ī)章之外，對公路運(yùn)輸不存在其他特殊的限制。那么 此公司應(yīng)如何運(yùn)輸這 190 噸化學(xué)物品才能夠使總運(yùn)費(fèi)最低？2、 摘要 運(yùn)輸費(fèi)用最低化是我們在現(xiàn)代社會經(jīng)常會遇到的一個問題。在社會的經(jīng)濟(jì)生產(chǎn)活動中，企業(yè)與客戶都會想方設(shè)法合理調(diào)撥資源、降低運(yùn)輸費(fèi)用，實(shí)現(xiàn)雙方利益最大化，完成資源優(yōu)化配置。本文以使物流運(yùn)費(fèi)成本最低為研究對象，在供應(yīng)量，需求量和單位運(yùn)費(fèi)都已確定的情況下，可用線性規(guī)劃方法來解決運(yùn)輸中的組織調(diào)撥問題。在本文中，我們主要解決的是化學(xué)物品配送最優(yōu)的問題，即是使我們花費(fèi)的總運(yùn)

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

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

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

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

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

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

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) 除了這種基于圖的問題數(shù)學(xué)表達(dá)之外，也可以將使用方式 m 從倉庫 d 運(yùn)輸?shù)侥?標(biāo) c 的運(yùn)量表示為決策變量 trasnport dcm ，對每個可能出現(xiàn)的三元組 (d ,c,m)都建立 這樣的決策變量，從而得到另一種問題表達(dá)方式。這樣總運(yùn)量就可以表示為所有有定義的變量 trasnport d

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

12、相連的結(jié)點(diǎn) (i , j )都定義一個流變量。 然而，對于稀疏圖，如我們所使用的這個圖，更常用（效率也更高）的方法是將圖表示為弧的列表的形式。在下面的 Mosel 程序?qū)崿F(xiàn)種就使用了這種表示方法?； = (i , j )將用標(biāo)號 a 進(jìn)行索引，而不是用對應(yīng)的結(jié)點(diǎn)對 (i , j )進(jìn)行索引?；〉牧斜頌槎S數(shù)組 A ，其中 Aa1 = i ， Aa 2 = i 。在讀入數(shù)據(jù)后（即弧集為已知）將定義流變 量。注意在下面的實(shí)現(xiàn)中，未采用數(shù)字對結(jié)點(diǎn)進(jìn)行編號，而是用名稱“Source”，“D2”， “C4”等，這樣能夠能夠方便對結(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! 弧的最小和最大通過量end-declarationsinitializations from e2minflow.datA MINQ MINCAP MAXCAP COSTend-initializations finalize(ARCS)! 計算結(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)! 最小和最大流通過量For all(a in ARCS |

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

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計算結(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.”彈出一個對話框（介紹此對話框），選擇“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