個(gè)人模擬第一次01

1、基于最小費(fèi)用的訂購與方案摘要：的采購成本和與調(diào)配是一個(gè)地區(qū)進(jìn)行基礎(chǔ)設(shè)施建設(shè)必須的問題。本文通過成本建立數(shù)學(xué)模型，對的運(yùn)購計(jì)劃進(jìn)行了分析。問題一，通過分步的方式建立模型一，引入矩陣，以總費(fèi)用最小為目標(biāo)，以鋼廠供應(yīng)量、節(jié)點(diǎn)需求量和供需平衡條件為約束，建立運(yùn)購的單目標(biāo)問題。將交通網(wǎng)分成鐵路網(wǎng)和公路網(wǎng)，通過用 Floyd 算法分別求出鐵路和公路網(wǎng)的鄰接矩陣。通過建立價(jià)格函數(shù)，求出綜合交通網(wǎng)絡(luò)的價(jià)格矩陣。將其作為輸入帶入模型，利用 Lingo 軟件編程求解，得到最小總費(fèi)用為 124.6220 億元。同時(shí)建立基于點(diǎn)對點(diǎn)單步 的模型二，利用Lingo 求得精確解，最小總費(fèi)用為124.6108 億元。比較模型

2、一、二，模型一求解精度達(dá)到 99.99%以上，執(zhí)行效率高，在內(nèi)存占用上只有模型二的 ，所以模型一整體上優(yōu)于模型二。201問題二，引入“虛”價(jià)格變量，利用 Lingo 軟件的求解結(jié)果中的 DualPrice 直接找出對總費(fèi)用影響最大的因子；定義運(yùn)購計(jì)劃變化程度函數(shù)，用控制變量法找出對運(yùn)購計(jì)劃影響最大的因子。得出結(jié)論：S1 的銷價(jià)和產(chǎn)量上限對總費(fèi)用的影響最大，分別是-1500每銷價(jià)和 85每；S3 的銷價(jià)對運(yùn)購計(jì)劃影響最大，影響力是 409.738， S1的產(chǎn)量上限對運(yùn)購計(jì)劃的影響最大，影響力是 399.7386。問題三，利用變量法分別對鐵路和公路運(yùn)費(fèi)進(jìn)行單變量分析，得到結(jié)果：r1 改變 1%，總

3、費(fèi)用改變約 0.234%；r2 改變 1%，總費(fèi)用改變約 0.050%。r1 大于 0 時(shí)，對運(yùn)購計(jì)劃變化很小， r1 小于 0 時(shí)，鋼廠運(yùn)購計(jì)劃影響大； r2 與之相反。問題四，利用分解網(wǎng)狀結(jié)構(gòu)提取線性主干的方法，將二維問題簡化成一維問題，利用修正的模型一總費(fèi)用模型求解。計(jì)算得到最小總費(fèi)用為 137.8352 億元。對簡化模型進(jìn)行誤差估計(jì)，求解誤差在 2 億元以內(nèi)。問題一僅考慮總費(fèi)用單一因素，增加總專線數(shù)量最小化這一目標(biāo)。Lingo 求解結(jié)果顯示將總費(fèi)用預(yù)算增加到 126 億時(shí)，可以將總專線數(shù)量從 19 條削減到 14 條。作為總費(fèi)用和總專線最小化的折衷方案。關(guān)鍵字矩陣Floyd 算法變量法

4、網(wǎng)狀結(jié)構(gòu)分解一、問題重述某地需要鋪設(shè)一條A1 ® A2 ® L ® A15 的輸送天然氣主管道。需要的鋼管從鋼廠 S1, S2,S6 采購。鋼廠到施工地點(diǎn)通過鐵路網(wǎng)和公路網(wǎng)（包括施工公路）連在一起。為了方便計(jì)數(shù)，1km 主管道稱為 1。因?yàn)闀r(shí)間緣故，鋼廠提供量有上限 si ，而且在任意一家鋼廠采購管道都不得少于 600。生產(chǎn)上限和出廠銷價(jià) pi 如下表：每的鐵路運(yùn)價(jià)為階梯制，如下表：注：超過 1000km 時(shí)，每增加 100km（不到 100km 按 100km 記）運(yùn)價(jià)增加。5每公里 0.1（小數(shù)部分按 1km 記）。需要注意公路運(yùn)費(fèi)為每一點(diǎn)是，需要運(yùn)送到安裝的

5、位置，不只是運(yùn)到最近的節(jié)點(diǎn)。問題的訂購的立數(shù)學(xué)模型，確定優(yōu)化目標(biāo)（最小費(fèi)用，最短時(shí)間等），給出合理計(jì)劃。問題二：在問題一模型的基礎(chǔ)上，找出哪個(gè)鋼廠的銷價(jià)和產(chǎn)量上限對采購和運(yùn)輸計(jì)劃的影響最大，即求價(jià)格。問題三：當(dāng)公路和鐵路運(yùn)費(fèi)發(fā)生浮動時(shí)（幅度不超過 5%），討論運(yùn)購計(jì)劃和總費(fèi)用的變化情況。問題四：當(dāng)管道鋪設(shè)方案發(fā)生變化時(shí)（線狀變成網(wǎng)狀結(jié)構(gòu)），給出一種解決方案。里程(km)300301350351400401450451500運(yùn)價(jià)()2024273032里程(km)5016006017007018008019009011000運(yùn)價(jià)()3645535860i123456si250028003000p

6、i150160155150155155二、問題分析2.1 問題一的分析對于問題一，本題是一類典型的問題，我們很容易想到建立一個(gè)單目標(biāo)模型。對于求解目標(biāo)的選擇，題目中涉及鐵路公路運(yùn)費(fèi)，首先想到的應(yīng)該是建立以最小費(fèi)用為目標(biāo)的單目標(biāo)模型。在后續(xù)的深入分析中，我們可以考慮將專線數(shù)量、時(shí)間等因素作為目標(biāo)函數(shù)。2.2 問題二的分析問題二需要求解并比較不同鋼廠的銷價(jià)和產(chǎn)量上限的影響最大的。價(jià)格，找出其中2.3 問題三的分析問題三要求在總費(fèi)用最小的基礎(chǔ)上，運(yùn)費(fèi)浮動導(dǎo)致的方案調(diào)整，觀察分析多種方案的變化情況，給出分析結(jié)論。2.4 問題四的分析問題四要求當(dāng)題目要求發(fā)生變化時(shí)，需要問題一的模型是否仍然適用，如果能用

7、，是否需要做出一些調(diào)整來適應(yīng)新的情況？需要根據(jù)實(shí)際情況，找出解決變形問題的方法。三、模型假設(shè)與符號系統(tǒng)3.1 模型的假設(shè)（1）連續(xù)性假設(shè)：鋼廠賣出的量可以不為整數(shù)。（2）穩(wěn)定性假設(shè)：在開始生產(chǎn)到出廠前，價(jià)格不變；在出廠后到到達(dá)目的地前，運(yùn)費(fèi)發(fā)生變化。（3）無限性假設(shè)：每段鐵路、公路的運(yùn)力都能滿足的流量需求。3.2 符號系統(tǒng)問題一符號系統(tǒng)符號意義W總費(fèi)用億元P采購成本億元T成本億元T SA鋼廠(S)施工沿線節(jié)點(diǎn)(A)的成本億元T AP施工沿線節(jié)點(diǎn)(A)施工沿線各點(diǎn)(Point)的成本億元ai, j第 i 個(gè)鋼廠向第 j 個(gè)節(jié)點(diǎn)的量/1kmbj第 j 各節(jié)點(diǎn)(A)的需求量/1kmti第 i 個(gè)鋼廠

8、的供應(yīng)量/1kmsi第 i 個(gè)鋼廠的產(chǎn)量上限/1kmpi第 i 個(gè)鋼廠的銷價(jià)zi ,j 第 i 個(gè)鋼廠到第 j 個(gè)節(jié)點(diǎn)的距離kmxi ,k 鐵路距離kmy k ,j公路距離kmC1i, j第 i 個(gè)鋼廠到第 j 個(gè)節(jié)點(diǎn)每價(jià)格C1i, j鐵路每價(jià)格C 2i, j公路每價(jià)格Lj第 j 個(gè)節(jié)點(diǎn)向左的量/1kmRj第 j 個(gè)節(jié)點(diǎn)向右的量/1kmDj第 j 段施工段長度kmNk第k 個(gè)節(jié)點(diǎn)在全部路段的序號/問題二符號系統(tǒng)注：與問題一重復(fù)部分不再列出。問題三符號系統(tǒng)注：與問題一重復(fù)部分不再列出。四、問題一的建模與求解4.1 問題分析在問題一中，我們確立最小總費(fèi)用（運(yùn)購成本）為目標(biāo)。其中，總費(fèi)用分為采購成本

9、和成本。約束包括鋼廠供應(yīng)量約束，管道沿線需求量約束，供求平衡約束以及求解問題引入變量內(nèi)在的約束。根據(jù)目標(biāo)和約束我們得到原問題完整的數(shù)學(xué)描述。問題一的建模流程圖如下：確定目標(biāo)函數(shù)定義變量問題的數(shù)學(xué)描述找出相關(guān)約束圖 4-1 問題模流程圖符號意義r1鐵路利率浮動率/r2公路利率浮動率/符號意義fake _ pi“虛價(jià)格”P購計(jì)劃變化程度函數(shù)/1km4.2 模型立4.2.1 目標(biāo)函數(shù)下面我們建立總費(fèi)用最小化的單目標(biāo)模型。我們以最小總費(fèi)用為大部分目標(biāo)，總費(fèi)用W 分為采購成本 P 和成本T 兩W = P + Tai, j陣 A ：表示第 i 個(gè)鋼廠向第 j 個(gè)節(jié)點(diǎn)的量（），由此得到矩æ a1,

10、1a1,15 öa1,22,2.ç a÷aaA = ç2,15 ÷2,1ç÷.ç a÷aaè6,15 ø6,16,2l采購成本 Pti (i=1,2,.,6) 表示第 i 個(gè)鋼廠的供應(yīng)量， pi (i=1,2,.,6) 表示第 i 個(gè)鋼廠的銷價(jià)，所以采購成本為：6615P = åti pii=1= å(åai, j )pii=1 j =1l距離 xi,k , yk , j , zi, j問題要求運(yùn)送到施工沿線個(gè)點(diǎn)，所有的一定會經(jīng)過A1, A2 , A3.A

11、15 中的至少一個(gè)節(jié)點(diǎn)，我們先讓所有從 6 個(gè)鋼廠定向到這15 個(gè)節(jié)點(diǎn)。zi ,j 表示第 i 個(gè)鋼廠到第 j 個(gè)節(jié)點(diǎn)的距離， zi ,j 又可分為鐵路距離 xi,k 和公路距離 yk , j ：k Î1, 2,.,17)zi, j = xi,k + yk , j(i = 1, 2,., 6 j = 1, 2,.,15,事實(shí)上，一個(gè)鋼廠到一個(gè)節(jié)點(diǎn)有多種路徑可以選擇，存在這樣一個(gè)交通樞紐 k，同時(shí)連結(jié)鐵路網(wǎng)和公路網(wǎng)，這樣的點(diǎn)在圖中共有 17 個(gè)，所以每對(i, j ) 共有 17 種組合方式，然后通過每種組合方式的價(jià)格最低的一種組合方式：xi,k價(jià)格比較，保留總¾C¾

12、;i , j (¾Xi ,k ¾,Yk , j¾) = ¾min C¾i , j ® Xi,kyk , jYk , j注：分別對鐵路網(wǎng)和公路網(wǎng)建立距離矩陣，利用 Floyd 算法計(jì)算各自的鄰接矩陣。C1l價(jià)格i, j借助復(fù)雜的鐵路網(wǎng)和公路網(wǎng)到指定地點(diǎn)。故將第 i 個(gè)鋼廠到第j價(jià)格C1和公路價(jià)格C細(xì)分為鐵路個(gè)節(jié)點(diǎn)i, ji, j執(zhí)行階梯價(jià)格C1 = f (x ) ：價(jià)格C 2。根據(jù)題意鐵路i, ji, j1i, jx £ 300300<x £ 500350<x £ 400ì20

13、9;24ïï27ïf ( x) = í.C =1ï60900<x £ 1000ïï60 + 5æ é x -1000 ù +ö1÷ x>1000ïç êëúû100èøî注： x公路表示函數(shù)；價(jià)格C 2 ：f2 ( y ) = 0.1× y價(jià)格Ci, j ：C 2 =綜上，第 i 個(gè)鋼廠到第 j 個(gè)節(jié)點(diǎn)C(x , y= C+ C 2 = f (x ) +

14、f ( y)1i, ji,kk , ji, ji j1i,k2k , j注：k 根據(jù)(i, j ) 唯一確定，即(i, j ) ¾m¾inC¾® k 。成本T根據(jù)前面的簡化，l成本 T 有可分為鋼廠(S)施工沿線節(jié)點(diǎn)(A)的成本T SA 和施工沿線節(jié)點(diǎn)(A)施工沿線各點(diǎn)(Point)的成本T AP ：T = T SA + T AP鋼廠(S)施工沿線節(jié)點(diǎn)(A)的成本T SA ：l6 15åå i, j i, jT=SAa Ci=1 j =1施工沿線節(jié)點(diǎn)(A)施工沿線各點(diǎn)(Point)的成本T APl每個(gè)節(jié)點(diǎn)都向 的兩側(cè) ， 定義向左的量

15、為 Lj (j = 1, 2,.,15) ，向右量為 Rj (j= 1, 2,.,15)。題目中給出管道施的f2 ( y ) = 0.1× y ，可價(jià)格C 2 =工沿線為公路，也就是滿足公路中的AP以得到Tj的計(jì)算式：LjRj= å(1+ 2 + . + L ) × 0.1+ å(1+ 2 + . + R ) × 0.1T APjjji=1i=1可以近似表示成：()T AP= 0.05 L + R22jjj綜合得到T AP 表如下：1515()åå=T= 0.05×L + RT APAP22jjjj=1j=1綜上，

16、最小總費(fèi)用目標(biāo)函數(shù)W 表如下：6156 1515()minW = å(åa)p + ååaåjjC+ 0.05×L + R22i, jii, j i, ji=1 j=1i=1 j=1j=14.2.2 約束條件l供應(yīng)量約束根據(jù)題意，各鋼廠生產(chǎn)量的下限為 600；上限為 si ：15= åai, j j=1(i = 1, 2,., 6)600 £ ti£ sil節(jié)點(diǎn)需求量約束每個(gè)節(jié)點(diǎn)(A)的需求量為左右側(cè)的需量之和：6= å ai, j i=1= Lj + Rjbjl管道施工段需求量約束每段施工段所

17、需由兩端點(diǎn)供應(yīng)：(1 £ j £ 14)Rj + Lj +1 = DjL1 = 0, R15 = 0注： A1 ® A15 總共 15 個(gè)點(diǎn)組成 14 條線段。供需平衡約束l總供應(yīng)量要與總需求量相等：6 1561514ååai, j i=1 j =1= åti = åbj i=1j =1= å Di, j j =14.2.3 綜合模型根據(jù) 4.2.1 和 4.2.2，求解最小總費(fèi)用的單目標(biāo)模型如下：6156 1515()minW = å(åa)p + åå aåjj

18、C+ 0.05×L + R22i, jii, j i, ji=1 j =1i=1 j =1j =1ì600 £ t15= å(i = 1, 2,., 6)£ saïïii, jij =1ï6ïbj = åai, j= Lj + Rj ( j = 1, 2,.,15)i=1ï(1 £ j £ 14)s.t.íRj + Lj +1 = DjïL= 0, R = 0ï115ï6 1561514ïååai

19、, j= åti = åbj i=1j =1= å Di, j j =1ï i=1 j =1ïî4. 3 模型的求解4.3.1 求解步驟Step1：對圖上各點(diǎn)進(jìn)行標(biāo)號，通過陣。利用 Floyd 算法計(jì)算距離矩Step2：從距離矩陣到價(jià)格矩陣。將價(jià)格矩陣導(dǎo)出到 Cdata.txt 文件中保存。Step3：將上述算。模型通過 Lingo 實(shí)現(xiàn)，并且Cdata.txt 中的數(shù)據(jù)用于計(jì)Step4：并分析結(jié)果。問題一的總費(fèi)用最小化的計(jì)算流程圖如下：計(jì)算鄰接矩陣計(jì)算運(yùn)輸價(jià)格矩陣將數(shù)據(jù)導(dǎo)入 txt通過 Lingo 求解目標(biāo)圖 4-2 問題一的最小費(fèi)

20、用模型的計(jì)算流程圖4.3.2 數(shù)據(jù)預(yù)處理圖中一共有 39 個(gè)點(diǎn)，鐵路網(wǎng)有 24 節(jié)點(diǎn)，公路網(wǎng)有 32 個(gè)節(jié)點(diǎn)，共用(24+32-39=17)個(gè)節(jié)點(diǎn)。因?yàn)殍F路和公路的計(jì)價(jià)規(guī)則不一樣，所以我們分別建立鐵路網(wǎng)和公路網(wǎng)的鄰接矩陣 R24´24 , H32´32 （利用 Floyd 算法）。1615280S618S4160S313330401602022680S2705069070A155001250180110720520886242011A1410462910202S5A137572301150201042A125061254803A1119532031A103060A9680A

21、8A115010210452462010A711942054502A6A80A516067502A43A3311120圖 4-3鐵路網(wǎng)節(jié)點(diǎn)標(biāo)號A2A1128141923213017下面給出代碼鐵路網(wǎng)領(lǐng)接矩陣 R（具體數(shù)據(jù)參見附錄）：function R = RailroadR = zeros(24,24);R(1,24)=450; R(2,24)=80; R(3,24)=1150; R(3,8)=1150; R(4,5)=3060; R(5,6)=195;R(6,7)=50; R(7,8)=202; R(8,9)=720; R(8,23)=1250; R(9,10)=520; R(9,22)=

22、690;R(10,19)=180; R(11,19)=88; R(11,20)=462; R(12,18)=70; R(13,15)=160;R(13,18)=330; R(14,15)=70; R(15,16)=280; R(16,17)=30; R(18,19)=160; R(19,21)=680;R = R + R' R(R=0)=inf;n = size(R); for i=1:nR(i,i) = 0; %對角線元素清 0End%*以下是 Floyd 算法*% for k = 1:nfor i = 1:nfor j = 1:nif R(i,j) > R(i,k) + R(

23、k,j)R(i,j) = R(i,k) + R(k,j);endendendendend161730280S6S4160S3153304016020680S27050136907014A15125018081105007203252088126211462420A1491010202S531A1375S12301150104222030A125073612480529A1119532031A103060A928680A8A2711501021042656202510A71194205450A6A80224A52360617502A4223A321311120A220A1圖 4-4公路網(wǎng)節(jié)點(diǎn)標(biāo)號

24、18公路網(wǎng)領(lǐng)接矩陣 H（具體數(shù)據(jù)參見附錄）： function H = HighwayH = zeros(32,32);H(1,19)=3; H(2,20)=2; H(3,21)=620; H(4,22)=10; H(5,23)=5; H(6,24)=10;H(7,24)=31; H(8,25)=12; H(9,26)=42; H(10,27)=75; H(11,28)=10; H(12,29)=10;H(13,30)=62; H(14,31)=110; H(15,31)=50; H(16,32)=20; H(17,32)=40; D=120, 311, 750, 606, 194, 205,

25、 210, 680, 480, 320, 220, 230, 420, 500;for i=18:31H(i,i+1) = D(i-17);endH = H + H' H(H=0)=inf;n = size(H); for i=1:nH(i,i) = 0; %對角線元素清 0end19%*以下是 Floyd 算法*% for k = 1:nfor i = 1:nfor j = 1:nif H(i,j) > H(i,k) + H(k,j)H(i,j) = H(i,k) + H(k,j);endendendendend® C1y® C 2根據(jù)函數(shù) x和將 R, H

26、 矩陣到價(jià)格矩陣i, ji, ji, ji, jC1,C2 。以點(diǎn)到點(diǎn)最小體數(shù)據(jù)參見附錄）。成本為目標(biāo)，獲得綜合價(jià)格矩陣C（具代碼如下clc;R = Railroad;H = Highway;n1 = size(R,1); n2 = size(H,1);C1=zeros(n1, n1); C2=zeros(n2, n2); %C1,C2 分別對應(yīng)鐵路和公路的格價(jià)Tiered_prices = 0, 20, 24, 27, 30, 32, 36, 45, 53, 58, 60; %階梯價(jià)格dist = 0, 300, 350, 400, 450, 500, 600, 700, 800, 900,

27、 1000; %階梯價(jià)格對應(yīng)距離for i=1:n1for j=i+1:n1if(R(i,j) <= dist(end) %鐵路里程在 1000km 之內(nèi)；k=1;while R(i,j) > dist(k) k = k+1;C1(i,j) = Tiered_prices(k);endelse%鐵路里程超過 1000km；C1(i,j) = Tiered_prices(end) + ceil( (R(i,j)-dist(end)/100 )*5;endendendC1 = C1 + C1' % C1(i,j)=C1(j,i) C2 = H.*0.1;%*以下計(jì)算 S1-S6

28、 到 A1-A15 的最小價(jià)格*%S = 7, 23, 22, 21, 20, 17; %R 中鋼廠 S1-S6 對應(yīng)的序號；A = 18:32; %H 中節(jié)點(diǎn) A1-A15 對應(yīng)的序號；C = ones(6,15) * 10000; %S1-S6 到 A1-A15 的最小價(jià)格for i = 1:6for j = 1:15for k = 1:17if C(i,j) > C1(S(i),k) + C2(k,A(j)C(i,j) = C1(S(i),k) + C2(k,A(j);endendendendfile1 = fopen('Cdata.txt','w'

29、);fprintf(file1, '%gt', C' );將 C 的結(jié)果導(dǎo)入到 txt 文件中，供后續(xù)的 Lingo 程序調(diào)用。Lingo 程序如下：LowCost_m1_1.lg4m:Title Lowest Cost; sets:factory/1.6/: s, p, t; node/1.15/: b, d, L, R; link(factory, node): a, c;endsetsdata:s = 1500,800,1500,2500,2800,3000; !產(chǎn)量上限; p = 150,160,155,150,155,155; !S1-S6的價(jià)格;d = 12

30、0,311,750,606,194,205,210,680,480,320,220,230,420,500,0; !A1-A15的分段距離;c = file('Cdata.txt'); !S1-S6到A1-A15的最低enddata價(jià)格;obj min = Q1+Q2+Q3;Q1 = sum(factory(i): t(i) * p(i) ); Q2 = sum(link: a*c );Q3 = sum(node(j): 0.5*(L(j)2+R(j)2)*0.1 );for(node(j): b(j) = sum(factory(i): a(i,j) ); !各節(jié)點(diǎn)的需求量;

31、的生產(chǎn)量;for(factory(i):for(factory(i): for(factory(i):t(i)t(i)t(i)=><sum(node(j): a(i,j) ); !各鋼廠600 ); !各鋼廠生產(chǎn)的產(chǎn)量下限;s(i) ); !各鋼廠生產(chǎn)的產(chǎn)量上限;sum(link: a )=sum(node(j): d(j) ); !需求量等于生產(chǎn)量;for(node(j): b(j) = L(j)+R(j) ); !各節(jié)點(diǎn)向的需求量等節(jié)點(diǎn)左右兩側(cè)的需求量;for(node(j)|j#ne#15: R(j)+L(j+1) = d(j) ); !單側(cè)需求量滿足的關(guān)系式; L(1) =

32、 0; !最左側(cè)節(jié)點(diǎn)的左邊需求量為0;R(15) = 0; !最右側(cè)側(cè)節(jié)點(diǎn)的右邊需求量為0;end4.3.3 求解結(jié)果將 4.2.3 的綜合模型的數(shù)學(xué)描述轉(zhuǎn)化成 Lingo 語言，求解得到：最小總費(fèi)用W = 1246220() = 124.6220(億元) ；采購成本 P = 805951.3() = 80.5951(億元) ；T SA = 356983.9() = 35.6984(億元) = 8.3285(億元)成本；T AP= 83284.5(表 4-1鐵路施工沿線各節(jié)點(diǎn)需求量表 4-2鋼廠供應(yīng)量鋼廠序號123456供應(yīng)量1500664.257907.743600600974序號(A)12

33、345678需要量0200507473606209285294序號(A)9101112131415需要量646366502181218381275矩陣 A = a6´15表 4-312314154.3.4 結(jié)論根據(jù)交通圖和 4.3.3 的結(jié)果，得出如下結(jié)論：只有鋼廠S1 達(dá)到供應(yīng)上限（生產(chǎn)極限）。ü管道節(jié)點(diǎn) A1 不需要供貨， A1 ® A2 施工段全部由 A2 提供。üü離施工地點(diǎn)近的鋼廠 S1, S3 , S6 供應(yīng)量較大。施工長度較長的施工段 Ai ® Ai+1 的兩端點(diǎn) Ai , Ai+1 （至少其中一個(gè)）的需ü求量

34、較大，例如： A3 , A4 , A5 , A9 , A11 。4.3.5 分析u 鋼廠在交通圖中分布不均，東部沒有，中部有5 家鋼廠Si (i = 1, 2,.,5) ，西部一家S6 。 S1 離東部及部分中部施工段最近，主要供應(yīng)中東部施工段，而且東部施工段需求量大，導(dǎo)致S1 達(dá)到供應(yīng)上限。u 中部其他幾家鋼廠分別對應(yīng)中部幾處施工段，供需情況較為均衡。其中S2協(xié)助S1 供應(yīng)中東部地區(qū)， S2 的生產(chǎn)能力最?。ㄗ疃喙?yīng) 800），但是沒有達(dá)到供應(yīng)上限的應(yīng)該是 S2 廠的銷價(jià)最高，在條件沒有優(yōu)勢的10000020200246.25700300261.24300400000500000600038

35、1375施工段應(yīng)該應(yīng)該盡量減少對 S2 的需求。u 西部雖然只有一家鋼廠 S6 ，但是生產(chǎn)能力最大（3000），而西部需求量卻在 1000左右，所以供應(yīng)情況比較樂觀。u 對鋪設(shè)管道長度較長的施工段傾向于兩端點(diǎn)同時(shí)供應(yīng)的解釋：Rj + Lj +1 = Dj (j=1,2,.,14)L1 = 0andR15 = 015åT AP= 0.05(L + R )22jjj =1在不考慮其他因素的情況下，我們知道T AP 取得最小值的條件是：Lj+1 = Rj( j = 1, 2,.,14)上式意味著施工段兩端點(diǎn)的對該段的供應(yīng)量應(yīng)該相等，但是實(shí)際上由于到達(dá)兩端點(diǎn)的鋼材因?yàn)殇N價(jià)和成本不相等的關(guān)系，

36、往往得不到 Lj +1 = Rj 這種形式的結(jié)果，但是會存在這種平均分配的趨勢。4.4 模型二的建立4.4.1 模型一存在的一個(gè)缺陷的分為兩大步，第一步是從鋼廠 S模型一是將到各個(gè)管道施到管道沿線各處位置 Point。工節(jié)點(diǎn) A ，第二步是從各個(gè)管道施工節(jié)點(diǎn) A 這樣做在第一步到第二步的過程中可能會出現(xiàn)示：（成本）浪費(fèi)，如圖所圖 4-5題目圖一的局部示意圖來自鋼廠 S5 ，然后這批鋼材回向 A12 的兩側(cè)A12 的部分，過程中會出現(xiàn)鋼材向左側(cè)管道施工段，這里就出現(xiàn)的了的冗余，造成了多余的成本。下面建立模型二來解決這個(gè)弊端。4.4.2 目標(biāo)函數(shù)因此，在改進(jìn)模型一的基礎(chǔ)上，我們建立點(diǎn)到點(diǎn)的。即將總

37、長為14D = å Dj = 5246km 的管道拆分成 5246 小段 1km 的施工段。這樣改進(jìn)的目的j =1就是為了避免的往復(fù)。æ a1,1a1,5246 öa1,22,2.ç a÷a.aA' = ç2,5246 ÷2,1ç÷.ç a÷a.aè6,5246 ø6,16,2ai, j 表示第 i 個(gè)鋼廠向第 j 小段的鋼材量。各鋼廠的供應(yīng)量ti 如下：5246= å ai, j j =1til 采購成本 P采購成本的計(jì)算方式同模型一類似：652

38、46P = å(å ai, j )pii=1j =1價(jià)格Ci, j鋼廠往第 j 小段l的過程中，相鄰的Ci, j 之間可能會相差 0.1，這里的Ci, j 的計(jì)算比前面稍微復(fù)雜。首先，我們計(jì)算出各節(jié)點(diǎn)在全部路段的序號 Nk ：k -1Nk = å Dk +1i=1(k = 2, 3,.,15)注： Nk 為節(jié)點(diǎn) Ak 對應(yīng)的序號，記 N1 =1，然后對節(jié)點(diǎn)間距 Dk 用累加的方式即可得到節(jié)點(diǎn)在所有小段中的序號。往管道總線上的任意一點(diǎn)一個(gè)。所以我們也得到了Ci, j 的計(jì)算表，必須結(jié)果離該點(diǎn)最近的兩個(gè)端點(diǎn)中的：= min(0.1×( j - NkCi, j

39、j Î( Nk , Nk +1 總價(jià)格T(k = 1, 2l6 5246T = åå ai, jCi, j i=1 j =1總費(fèi)用Wl65246minW = å(aii=1j=14.4.3 約束條件l供應(yīng)量約束根據(jù)題意，各鋼廠生產(chǎn)量的下限為 600；上限為 si ：5246= å ai, j j =1(i = 1, 2,., 6600 £ ti£ sil需求量約束各段需求量bjº 1( j = 1, 2,.,5246) ，約束如下：6å ai, j i=1= bj = 1( j = 1, 2, 5246l

40、供求平衡約束總供應(yīng)量要與總需求量相等：6 524665246åå ai, j i=1 j =1= åti = åbj = 5246i=1j =1l整形約束將總管道分成 5246 份，結(jié)果這樣細(xì)分之后，我們可以可以認(rèn)為每一段上面的來自同一鋼廠，結(jié)合需求約束得出如下結(jié)論：(i = 1, 2,., 6ai, j = 0 or 14.4.4 綜合模型通過對原始問題的仔細(xì)研究，可以人為模型二是對原始問題的精確描述， 理論上是可以求出原始問題的全局最優(yōu)解。模型如下：ï6íå= bj = 1(s.t.ai, ji=ï6 5246

41、6ïåå ai, j= åti =ï i=1 j =1i=1or 1(ii, j = 0ïî4.5 模型二的求解4.5.1 求解步驟求解步驟同 4.3.1，這里不再贅述。4.5.2 數(shù)據(jù)預(yù)處理導(dǎo)出的相同數(shù)據(jù)，處理方法同 4.3.2。利用模型一中Lingo 程序如下：LowCost_m2_1.lg4m:Title Lowest Cost; sets:factory/1.6/: s, p, t; node/1.15/: sum; link(factory, node): c; col/1.5246/; point(factory

42、,col):a, z;endsetsdata:s =p = sum1500,800,1500,2500,2800,3000; !產(chǎn)量上限;150,160,155,150,155,155; !S1-S6的價(jià)格;=0,120,431,1181,1787,1981,2186,2396,3076,3556,3876,4096,4326,4746,5246; !D1-D14的累計(jì)距離;c = file('Cdata.txt'); !S1-S6到A1-A15的最低價(jià)格;enddataobj min = Q1 + Q2;Q1 = sum(factory(i): sum(col(j): z(i

43、,j) * p(i) ); !采購成本;Q2 = sum(point:a*z );!成本;for(factory(i): for(factory(i): for(factory(i):for(factory(i):t(i) =t(i) >con2sum(col(j): z(i,j) ); 600 ); !各鋼廠生產(chǎn)的產(chǎn)量下限;t(i) < s(i) ); !各鋼廠生產(chǎn)的產(chǎn)量上限;for(node(j)|j#ne#15:for(col(k)|k#gt#sum(j)#and#k#le#sum(j+1):a(i,k) = smin( (k-sum(j)*0.1+c(i,j),(sum(j

44、+1)-k)*0.1+c(i,j+1) ) ) ) ); !各微段取最近距離;for(col(j): sum(factory(i): z(i,j) = 1 ); !各微段長度筆來自某一個(gè)鋼廠;end注：運(yùn)行程序的 Lingo 軟件必須為運(yùn)行會因?yàn)閮?nèi)存不夠報(bào)錯。版，對內(nèi)存占用的限制較小，否則4.5.3 求解結(jié)果最小總費(fèi)用W = 1246108(采購成本 P = 805630.0(成本T = 440477.9() = 124.6108(億元)；) = 80.5630(億元)；) = 44.0478(億元)；表 4-4鋼廠供應(yīng)量注：矩陣數(shù)據(jù)量龐大，故不在文中列出，以 Lingo 報(bào)告格式的形式保存在

45、程序文件夾中。4.5.4 結(jié)論我們得到了與模型一結(jié)果類似的結(jié)論：鋼廠序號123456供應(yīng)量1500600971600600975ü只有鋼廠S1 達(dá)到供應(yīng)上限（生產(chǎn)極限）。ü離施工地點(diǎn)近的鋼廠 S1, S3 , S6 供應(yīng)量較大。ü鋼廠S2 , S4 , S5 供應(yīng)量均處于一種供應(yīng)下限的形式，如果沒有 600生產(chǎn)下限的約束，這三家供應(yīng)到生產(chǎn)上限）。量可能被另外兩家部分替代（有一家已經(jīng)達(dá)ü最小總費(fèi)用結(jié)果較模型一有所。4.5.5 分析u 模型二的結(jié)果理論上應(yīng)該是本問題原始情況下的最優(yōu)解，而模型一是對初始模型簡化后的結(jié)果。所以模型二的結(jié)果優(yōu)于模型是必然現(xiàn)象。4.

46、6 兩個(gè)模型的比較經(jīng)過前面建模過程的分析，我們可以做出如下結(jié)論：模型二是對原問題初始情況下的解決，而模型一是對初始模型的簡化，也可以視為對模型二的近似。4.6.1 費(fèi)用比較表 4-5 模型一、二總費(fèi)用及具體費(fèi)用比較在總費(fèi)用和采購成本上模型二優(yōu)于模型一，但是在成本上模型二的結(jié)果竟然比模型一要多。而事實(shí)上，我們在建模過程中，模型二對于模型一的主要優(yōu)勢在于對成本上的優(yōu)化。而求解的結(jié)果卻與預(yù)想的結(jié)果相反。u 對此做出的解釋是：模型的求解目標(biāo)是總費(fèi)用的最小化，而不是費(fèi)用的最小化，模型對成本的優(yōu)化影響到了整體的調(diào)配方案，是起到了優(yōu)化結(jié)果的目的，但是在求解結(jié)果的過程中，局部必須服從與整體。以局部的小犧牲換取

47、整體更大的利益。模型二的優(yōu)化不是沒有產(chǎn)生作用，只不過模型一模型二總費(fèi)用（億元）124.6220124.6108采購成本（ 億元）80.662980.5630成本（ 億元）43.959044.0478被全局方案的變動覆蓋掉了。對模型進(jìn)行進(jìn)行量化比較，可以量化模型一的求解準(zhǔn)確度（模型二已經(jīng)是精確解）。模型一的求解誤差e 如下e = W1 -W2 ´100% = 9´10-3%1%W2由此可見，模型一的簡化的有效的，準(zhǔn)確的。4.6.2 鋼廠供應(yīng)方案的比較表 4-6 模型一、二鋼廠供應(yīng)量比較鋼廠S1, S4 , S5 的供應(yīng)量不變，鋼廠 S6 增加了一，可忽略不計(jì)。主要變化的是鋼廠

48、S2, S3 ，變化量幾乎相等。u 結(jié)合網(wǎng)狀圖和相關(guān)數(shù)據(jù)可知， S3 比 S2 有價(jià)格上的優(yōu)勢，而且 S3 往中部地區(qū)比S2 有距離上的優(yōu)勢，兩座鋼廠相距較近，在方式化整為零后，綜合兩項(xiàng)優(yōu)勢，S2 的部分供應(yīng)量會被S3 替代是理所應(yīng)當(dāng)?shù)摹５?S2的供應(yīng)量存在供應(yīng)下限（600），所以S2 的供應(yīng)量保持在 600 不再減少。4.6.3 程序復(fù)雜度比較u 空間復(fù)雜度比較：模型一的 Lingo 代碼離矩陣是6´5246 的矩陣，模型二占用內(nèi)存為 47KB，由于距占用內(nèi)存 9227KB，遠(yuǎn)高于模型一的內(nèi)存占用。很容易超出 Lingo 內(nèi)部對程序內(nèi)存占用的極限，導(dǎo)致程序無法正常運(yùn)行求解或者求解

49、到一半報(bào)告內(nèi)存占用過大而終止程序。這是模型二的一大劣勢。u 時(shí)間復(fù)雜度比較：模型一程序在 1s 內(nèi)（781）更找出全局最優(yōu)解并終止程序。模型二在 2s 內(nèi)（6785）找出全局最優(yōu)解。模型一鋼廠序號123456供應(yīng)量1500664.257907.743600600974模型二鋼廠序號123456供應(yīng)量15006009716006009754.6.4 比較結(jié)果我們對模型一、二更加本質(zhì)的理解就是劃分精度的不同，模型一可視為對總長為 5246 的管道劃分成不等長的 14 段，而模型二就是將總管道分成 5246 段。劃分得越仔細(xì)，求解的精度越高。總結(jié)前面的比較，模型二在求解精度上不存在大的優(yōu)勢，但是在程

50、序復(fù)雜度方面劣于模型一，所以可以認(rèn)為模型一要比模型二好。問題二、三、四的求解是都基于模型一的。五、問題二的建模與求解5.1 問題分析找出對購和總費(fèi)用影響最大的鋼廠銷價(jià)和產(chǎn)量上限，即找出不同鋼廠的銷價(jià)和產(chǎn)量對購和總費(fèi)用影響的價(jià)格?？傎M(fèi)用的變化，Lingo 在求解過程中求解某些變量的價(jià)格，所以可以直接在問題一的模型上稍作修改，即可找出對總費(fèi)用影響最大鋼廠價(jià)格和產(chǎn)量上限。對于運(yùn)購計(jì)劃的變化，首先定義運(yùn)購計(jì)劃變化程度的函數(shù)，用變量法一次改變一個(gè)變量，建立運(yùn)購計(jì)劃變化程度函數(shù)量化評估，找出對總費(fèi)用影響最大的鋼廠價(jià)格和產(chǎn)量上限。定義運(yùn)購計(jì)劃變化程度函數(shù)對模型一的 Lingo程序稍作修改直接利用 Lingo

51、求解結(jié)果變量法量化比較，得出結(jié)果圖 5-1問題模流程圖運(yùn)購計(jì)劃影響總費(fèi)用影響5.2 問題二的建模5.2.1 鋼廠銷價(jià)對總費(fèi)用影響程序初始輸入價(jià)格參數(shù)是固定值，不可變的，就無法進(jìn)行價(jià)格的計(jì)算。所以這里引入一個(gè)“虛價(jià)格為變量 fake _ pi（“虛”價(jià)格的概念，即解除鋼廠價(jià)格的為定值的約束，令”價(jià)格），然后令原始價(jià)格 pi (i = 1, 2,., 6)為變量fake _ pi 的下限：(i = 1, 2,., 6)fake _ pi ³ pi價(jià)格定值轉(zhuǎn)變成變量后，Lingo 就可以直接計(jì)算出其價(jià)格。同時(shí)也可以保證 fake _ pi 一定會收斂與 pi 而導(dǎo)致問題一、二前后結(jié)果不一致。5.2.2 鋼廠產(chǎn)量上限對總費(fèi)用的影響鋼廠產(chǎn)量ti 在模型一中已經(jīng)是變量了，故不需要其他操作。5.2.3 鋼廠銷價(jià)對運(yùn)購計(jì)劃的影響定義運(yùn)購計(jì)劃變化程度的函數(shù)為：6P = å ti - ti 0i=1注： ti (i = 1, 2,., 6) 為