鋼管的訂購(gòu)及運(yùn)輸優(yōu)化方案

鋼管的訂購(gòu)及運(yùn)輸優(yōu)化方案承諾書我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的,如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）： A 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?吉林省建筑工程學(xué)院建筑裝飾學(xué)院參賽隊(duì)員（打印并簽名）： 1. 姜磊 魏文超 張曉斌 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）： 楊雪 日期：2009年9月出日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2009高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：摘要:從本題中可以看出我們要解決的問(wèn)題是鋼管怎樣訂購(gòu)，怎樣運(yùn)輸，才能使得總費(fèi)用最少。所以，我們從兩個(gè)方面著手考慮這個(gè)問(wèn)題，首先我們考慮怎樣從鋼廠訂購(gòu)貨物，接下來(lái)我們考慮在訂購(gòu)好貨物后我們?cè)鯓影沿浳镞\(yùn)輸?shù)侥康牡亍?duì)于這兩個(gè)問(wèn)題，從題目可知，訂購(gòu)和運(yùn)輸聯(lián)系密切，所以，我們必須同時(shí)考慮考慮鋼管的訂購(gòu)與運(yùn)輸。再由題中給的鋼廠與天然氣管道路線分布圖可以看出，該問(wèn)題等同于把起點(diǎn)的信息通過(guò)最優(yōu)路（即就是花費(fèi)最少的路徑）徑送到目的地，在送往的途中可以有信息的流失，流失的信息即就是用于鋪設(shè)道路的貨物，但不管流失多少信息，到達(dá)目的地時(shí)，總還有剩余的信息。所以，我們就把鋼管的運(yùn)輸看成了最小費(fèi)用最大流問(wèn)題。所以我們通過(guò)對(duì)線路的標(biāo)號(hào)，我們利用floyd算出最大流問(wèn)題算出每一個(gè)鋼廠到每個(gè)點(diǎn)的單位最優(yōu)路徑，然后，再算出在運(yùn)送途中鋼管用于鋪設(shè)管道所花費(fèi)的費(fèi)用，我們把這兩種費(fèi)用相加，就得到了總的費(fèi)用。我們通過(guò)計(jì)算，得出應(yīng)從哪些鋼廠訂購(gòu)多少貨物，以怎樣的路徑進(jìn)行運(yùn)送才能使總費(fèi)用最小。經(jīng)過(guò)計(jì)算我們得出最優(yōu)解：其最小費(fèi)用為1291630萬(wàn)元。在第二問(wèn)中，我們通過(guò)對(duì)問(wèn)題一的精度分析可得：鋼廠S6的鋼管銷價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大；鋼管廠s1的鋼管產(chǎn)量的上限的變化對(duì)總費(fèi)用的影響最大，鋼管廠S3的產(chǎn)量上限的變化對(duì)購(gòu)運(yùn)計(jì)劃的影響最大。對(duì)于第三問(wèn)，我們同樣運(yùn)用問(wèn)題一的解決辦法，先求出每一個(gè)鋼廠到每段道路的最短路徑，然后再求出每一鋼廠運(yùn)送的數(shù)量，還有運(yùn)送途中鋪路石所花費(fèi)的單位費(fèi)用，最后得出最優(yōu)解：其最小費(fèi)用為1396099萬(wàn)元。問(wèn)題重述：（略）問(wèn)題分析：本題看似復(fù)雜，但經(jīng)過(guò)分析我們可以看出該問(wèn)題是求在一個(gè)有權(quán)圖中尋求最優(yōu)路徑的問(wèn)題，然后再求各個(gè)鋼廠的運(yùn)送花費(fèi)問(wèn)題，對(duì)于運(yùn)送費(fèi)用問(wèn)題，由于我們不知道在哪一個(gè)鋼廠訂貨，也不知道定多少，也不知道走哪一條路最合適，所以我們我們利用線性規(guī)劃中的方法，先利用0—1規(guī)劃模型，當(dāng)取0時(shí)，我們就認(rèn)為不在該廠訂貨，或者說(shuō)我們不選擇某一條路徑，這樣我們就輕易的將這個(gè)復(fù)雜的問(wèn)題分解為線性規(guī)劃問(wèn)題。該題中從鋼廠運(yùn)送貨物到目的地的路徑問(wèn)題等同于把起點(diǎn)的信息通過(guò)最優(yōu)路（即就是花費(fèi)最少的路徑）徑送到目的地，在送往的途中可以有信息的流失，流失的信息即就是用于鋪設(shè)道路的貨物，但不管流失多少信息，到達(dá)目的地時(shí)，總還有剩余的信息。所以，我們就把鋼管的運(yùn)輸看成了最小費(fèi)用最大流問(wèn)題。所以，我們通過(guò)對(duì)線路的標(biāo)號(hào)，我們利用最大流問(wèn)題算出每一個(gè)鋼廠到每個(gè)點(diǎn)的單位最優(yōu)路徑，然后，再算出在運(yùn)送途中鋼管用于鋪設(shè)管道所花費(fèi)的費(fèi)用，我們把這兩種費(fèi)用相加，就得到了總的費(fèi)用。對(duì)于問(wèn)題二，可以利用問(wèn)題一在LINGO中對(duì)問(wèn)題已進(jìn)行編程求解，然后根據(jù)該軟件中的精度分析對(duì)每一個(gè)鋼廠進(jìn)行精度分析。我們也可以對(duì)每一個(gè)鋼廠進(jìn)行精度分析，也就是利用主成分分析的方法。在第三問(wèn)中，我們可以利用問(wèn)題一的思路，先找出每一點(diǎn)的最短路徑，再根據(jù)0—1規(guī)劃問(wèn)題進(jìn)行求解?；炯僭O(shè)1．沿管道鋪設(shè)路線上有公路，在計(jì)算運(yùn)費(fèi)時(shí)，與其它普通公路相同；2．公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬(wàn)元（不足整公里的按整公里計(jì)算）；3. 1km主管道鋼管稱為1單位鋼管；4．一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個(gè)單位；1單位鋼管的鐵路運(yùn)價(jià)（如表一所示），1000km以上每增加1至100km運(yùn)價(jià)增加5萬(wàn)元；管道可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到點(diǎn)A1,A2，，A15，而是管道全線）；本問(wèn)題只考慮在鐵路和公路上運(yùn)輸?shù)膯?wèn)題，而不考慮在其它路徑上的情況；模型只考慮鋼管銷價(jià)費(fèi)用和鋼管從鋼管廠運(yùn)送到鋪設(shè)點(diǎn)的鋼管運(yùn)費(fèi)，而不考慮其它費(fèi)用，如轉(zhuǎn)運(yùn)費(fèi)用等；在公路上卸貨,按鋪路的要求卸車；銷售價(jià)和運(yùn)輸價(jià)不受市場(chǎng)價(jià)格變化的影響。鋼廠生產(chǎn)的鋼管都是合格的，不存在返回退貨問(wèn)題；符號(hào)說(shuō)明：S第i鋼管廠Si表示Si的最大生產(chǎn)能力Aj表示需要鋪設(shè)管道路徑上的車站X,j從所有S運(yùn)往Aj的鋼管用于鋪設(shè)Aj點(diǎn)前后側(cè)的鋼管數(shù)F-,j單位產(chǎn)品從S到Aj地的運(yùn)費(fèi)fj表示單位鋼管從Si地運(yùn)往Aj地的最小費(fèi)用Aj,j+1表示Aj和Aj+1兩車站之間需要鋪設(shè)的管道長(zhǎng)度Pi從S訂購(gòu)鋼管的單位價(jià)格z用于訂購(gòu)和運(yùn)輸?shù)目傎M(fèi)用模型的建立與求解:問(wèn)題一1、 模型的建立對(duì)本問(wèn)題而言，實(shí)際上是一個(gè)要求制定訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最小的優(yōu)化問(wèn)題。本模型的總費(fèi)用包括鋼管的銷價(jià)和運(yùn)輸總的費(fèi)用。首先，向某廠訂購(gòu)鋼管，然后將在每個(gè)廠訂購(gòu)的鋼管運(yùn)往需要鋪設(shè)的全路段。由本題的要求可以知道在鋪設(shè)管道時(shí)必須經(jīng)過(guò)A1,A2,…A15點(diǎn)。首先，需要確定將貨物從i地運(yùn)往j地的最優(yōu)路線；然后，確定運(yùn)輸計(jì)劃；最后計(jì)算將運(yùn)往j地的鋼管鋪到各個(gè)管道上的運(yùn)輸費(fèi)用，我們不妨假設(shè)運(yùn)往以j為終點(diǎn)的鋼管只鋪到與j點(diǎn)相鄰的兩段管道上。因此，本問(wèn)題可以按以下步驟求解。1、確定從i地到j(luò)地的最優(yōu)路徑，從而確定出單位鋼管從i地運(yùn)往j地的最小運(yùn)費(fèi)。設(shè)=1,2,…7)表示鋼管廠，Sj(i=1,2,…7)表示Sj的最大生產(chǎn)能力，A/)二1,2,…，⑸表示需要鋪設(shè)鋼管路徑上的車站。假設(shè)從\運(yùn)往Aj的鋼管用

于鋪設(shè)Aj點(diǎn)前后側(cè)的鋼管數(shù)為xi,j單位，單位產(chǎn)品從S到Aj地的運(yùn)費(fèi)為Fi,j萬(wàn)元，用fj表示單位鋼管從S?地運(yùn)往Aj地的最小費(fèi)用，貝I」：f=minFi,j i,j（1）2、建立從耳廠運(yùn)送Xj單位鋼管到Aj點(diǎn)的運(yùn)費(fèi)的模型：用z1表示訂購(gòu)的所有鋼管全部運(yùn)到Aj點(diǎn)的總運(yùn)費(fèi)，貝U：st.st.遲X<s九i,jiij=1遲X>500九i,j ij=1九=]1當(dāng)S生產(chǎn)時(shí)廠]0當(dāng)S不生產(chǎn)時(shí)iy++y-=Yxjj i,ji=1y++y-=Ajj+i j,j+iXi,j>0 （2）其中：y；和y-分別表示運(yùn)到A7地鋼管用于鋪A7點(diǎn)前邊和后邊的鋼管長(zhǎng)度；A7,7+i表示Aj和Aj+i之間需要鋪設(shè)的管道長(zhǎng)度3將運(yùn)到Aj處的鋼管鋪到相鄰兩段路上的運(yùn)輸費(fèi)用根據(jù)假設(shè)，在鋪設(shè)鋼管時(shí)，dx單位鋼管從第k點(diǎn)運(yùn)到k+1點(diǎn)的運(yùn)費(fèi)為：jk+1kjk+1k0.1dx=0.13）由（3）式可得如下模型（1）當(dāng)y+和歹-+1均為整單位數(shù)時(shí)，設(shè)其運(yùn)費(fèi)用z21表示，則:卡(1+y+)?y++(1+y-)?y-z=乙0.1x j j 凹 曰212j=1

（2）當(dāng)廠和萬(wàn)+1均為非整單位數(shù)時(shí)，設(shè)其運(yùn)費(fèi)用z22表示,貝U：z22‘ 0.1X(1+[y;])?[y;]+2(y;一[y；])?(】+[y；z222(1+ y-)?[ y-] + 2(y+ - [y - ]) ?(1 + [y-])+0.1 x j+1 j+1 j j+1 /+12=0.05 x {(1+ [y+]) ? (2y+ - [y+]) + (1 + y -) ? (2y- -[y-])}/ // /+1 /+1 /+1其中：[y+]表示y+的整數(shù)部分；[y-+1]表示y-+1的整數(shù)部分；綜合上述兩式可得：4）z二遲0.05x{(1+[y+])?(2y+—[y+])+(1+y-)?(2y一—[y一4）2/// /+1 /+1 /+1/=1s.t.遲x<s九i,/ii/=1遲x>500九i,/ i/=1九=ji 當(dāng)s生產(chǎn)時(shí)廠]0當(dāng)S不生產(chǎn)時(shí)iy++y-=丫x//i,/i=1y++y- =A/ /+1 /,/+1[y+]+[y-]=A -1/ /+1 /,/+1x>0i,/其中：z2表示運(yùn)到Aj處的鋼管鋪到相鄰兩段路上的運(yùn)輸費(fèi)用4建立訂購(gòu)費(fèi)用的模型i=1j=1i=1j=15）用z表示訂購(gòu)和運(yùn)輸?shù)目傎M(fèi)用，由（2）、（4）、（5）可得本問(wèn)題的優(yōu)化模型

如下：minz=z+z+z123即：mmz二瓦0.05x{(1+[y+]) ?(2y+—[y+])+(1 +y-)? (2y- -[y-])}j jj j+i j+ij+ij=ij=1j=ij=1i=1i=1j=1s.t.藝x<S九i,j iij=1遲x>500九i,j ij=1、f1當(dāng)S生產(chǎn)時(shí)i[0 當(dāng)S不生產(chǎn)時(shí)iy++y-=YxTOC\o"1-5"\h\zjj i,ji=1y++y- =Aj j+1 j,j+1[y+]+[y-]=A -1j j+1 j,j+1x>0i,j模型的求解:（1）首先求解fi,j此問(wèn)題相當(dāng)于求解最小費(fèi)用流問(wèn)題，即求出從Si點(diǎn)運(yùn)送單位鋼管到A7點(diǎn)的最小費(fèi)用。按常規(guī)，本問(wèn)題可以按求最短路的常規(guī)方法求解。但由于本問(wèn)題中沿鐵路的單位運(yùn)費(fèi)由它前邊經(jīng)過(guò)的鐵路長(zhǎng)度而變化。根據(jù)問(wèn)題的需要，我們不妨假設(shè)如果從Si點(diǎn)到A7點(diǎn)的鋼管經(jīng)過(guò)鐵路后，一旦走公路，那么，該鋼管將不會(huì)再通過(guò)鐵路運(yùn)輸。則假設(shè)沿鐵路行走，直到走到與公路S2 b24相連為止。如果需要從Si點(diǎn)運(yùn)鋼管到A7點(diǎn)，則需要找出從該點(diǎn)到目的點(diǎn)間的最優(yōu)路線。現(xiàn)在從每個(gè)鋼廠出發(fā)，求出每個(gè)鋼廠到需要鋪設(shè)管道的路徑上的每

個(gè)節(jié)點(diǎn)的單位鋼管量的最小費(fèi)用。那么，我們以Si,Aj以及鐵路的端點(diǎn)等為點(diǎn)，以鋼管的可能運(yùn)輸路線為邊,以單位鋼管的運(yùn)輸費(fèi)用為權(quán)建立加權(quán)圖，根據(jù)flyod算法求出每個(gè)鋼管廠Si到各個(gè)節(jié)點(diǎn)Aj的最小單位運(yùn)輸費(fèi)用。如下表所示：最小運(yùn)費(fèi)單價(jià)表S1s2s3s4s5s6s7A23203360.3375.3410.34003400.3425.3A3300.2345.2355.2395.2380.2385.2405.2A4258.6326.6336.6376.6361.6366.6386.6A5198266276316301306326A6180.5250.5260.5300.5285.5290.5310.5A7163.1241251291276278.1301A8181.2226.2241.2276.2266.2266.2291.2A9224.2269.2203.2244.2234.2234.2259.2A10252297237222212211236All256301241211188197224A12266311251221206187216A13281.2326.2266.2236.2226.2166.2198.2A14288333273243228161186A15302347287257242178162sis2s3s4s5s6s7盤山220265199240230230255A172553002402101S7196223A182603052452152001S3210A19265310250220206186215A20275320260230220160192A212853302702402301501S6（2）根據(jù)以上結(jié)果,繼續(xù)求解最小總費(fèi)用的模型原問(wèn)題屬于非線性規(guī)劃問(wèn)題的最優(yōu)解，但針對(duì)我們現(xiàn)在的情況來(lái)說(shuō)，不能找到較好的方法求解，我們可以根據(jù)線性（非線性）規(guī)劃問(wèn)題與網(wǎng)絡(luò)流分析之間的密切聯(lián)系，將原問(wèn)題轉(zhuǎn)化為下面的網(wǎng)絡(luò)流問(wèn)題進(jìn)行求解。本問(wèn)題在求出si點(diǎn)到Aj點(diǎn)的單位最小運(yùn)費(fèi)后，可以轉(zhuǎn)化為有i個(gè)鋼管廠給j個(gè)鋪設(shè)公路點(diǎn)供鋼管，然后第j個(gè)鋪設(shè)點(diǎn)的鋼管運(yùn)往鋪設(shè)處（管道全線）的網(wǎng)絡(luò)流問(wèn)題，假設(shè)用叨=1，…，7）表示第i個(gè)鋼管廠的最大生產(chǎn)量，：表示從i地運(yùn)往j地的單位運(yùn)價(jià)，每單位鋼管的成本為匚?萬(wàn)元，運(yùn)往j點(diǎn)后的每個(gè)點(diǎn)輸出的管道數(shù)為dm運(yùn)費(fèi)為cm?。用X表示第i地流出的鋼管總數(shù)。我們可以構(gòu)造源和匯,可建立如下的網(wǎng)絡(luò)流優(yōu)化問(wèn)題。其網(wǎng)絡(luò)流如下圖所示該網(wǎng)絡(luò)中每段弧上的兩個(gè)數(shù)字，前者是該段弧的容量，后者是與該段弧相應(yīng)的費(fèi)用。符號(hào)-表示該段弧容量無(wú)限制。圖中：s/二h…,J）表示第i個(gè)鋼廠的生產(chǎn)能力“少二】，…，7）表示第i個(gè)鋼廠生產(chǎn)鋼管的銷價(jià)f,7表示從i地運(yùn)往j地的單位鋼管的運(yùn)費(fèi)Cm表示運(yùn)往Aj的鋼管運(yùn)往鋪道上的費(fèi)用dm（m二1，2,…15）表示運(yùn)往d地的鋼管數(shù)目

在上述網(wǎng)絡(luò)中必須知道cm,這樣必須在上述求解網(wǎng)絡(luò)的基礎(chǔ)上加上枚舉法。但是，在這樣短的時(shí)間里不能編出求解此問(wèn)題的全局最優(yōu)解?，F(xiàn)在只有運(yùn)用求近似解的方法求解。否則不能求解。我們可以運(yùn)用現(xiàn)成的軟件，比如說(shuō)Lingo數(shù)學(xué)軟件，但是，在用它求解的過(guò)程中，不能將枚舉法加在程序里只有通過(guò)其他一些方法求出較好的初始值，然后求出前面一部分的最優(yōu)解我們可以在確定Aj處的鋼管數(shù)后，運(yùn)用將鋼管鋪到整段路上的運(yùn)輸費(fèi)最小為目標(biāo)確定出下一個(gè)局部的最優(yōu)解。將上述兩部分的解結(jié)合起來(lái)便可求出本問(wèn)題的近似最優(yōu)解。首先，根據(jù)以下準(zhǔn)則，確定出求下圖的最優(yōu)解的初始解。在未給定初始值的情況下,為了使我們的解盡可能地解接近其最優(yōu)解,我們根據(jù)自身的特點(diǎn)和工廠、鐵路、公路以及鋪設(shè)點(diǎn)分布情況，從而我們作出如下規(guī)則來(lái)確定模型的初始解域：運(yùn)輸位置一旦離開鐵路，而到達(dá)公路上后就不會(huì)再回到鐵路上。鄰近原則：即將離工廠最近的鋪設(shè)點(diǎn)為我們優(yōu)先考慮定購(gòu)點(diǎn)。鋼廠與鋪設(shè)點(diǎn)之間的運(yùn)輸費(fèi)用最少的優(yōu)先考慮為我們的定購(gòu)點(diǎn)。一旦某工廠被定為定購(gòu)點(diǎn)，它將盡最大的需求量去定購(gòu)。大致根據(jù)以上規(guī)則和其分布特點(diǎn)，我們得到如下較優(yōu)的初始值，即：Aj(j二l，2……14,⑸堆積點(diǎn)所定購(gòu)的鋼管量為0,261,482,515,571,153,373，212，574，330，317，170，257，655，141。將上述數(shù)據(jù)作為我們的初始可行解,由后面的程序即可求出其最小費(fèi)用為1291630萬(wàn)元,其具體的訂貨、運(yùn)輸安排如下：訂貨安排運(yùn)輸安排S]800x二2741,4x二1531,6x二3731,7S800x=2612,22x=222,3x=3052,5x=2122.8S1000x=2663,5x=7343,9S40

S51348x=4605.3x=2415.4x=3305.10x=3175.11S61223x=1706,12x=2576.13x=6556.14x=141615S0問(wèn)題二：通過(guò)分析問(wèn)題一中關(guān)于銷價(jià)的約束，Lingo運(yùn)行后得到的結(jié)果得S1S2S3S4S5S6S7影子價(jià)格-800-800-10000-1320-1250.990影子價(jià)格表示在最優(yōu)解下“資源”增加一個(gè)單位時(shí)“效益”的增量即每個(gè)鋼廠銷售價(jià)格每減少一萬(wàn)元，對(duì)總費(fèi)用的影響。從表中數(shù)據(jù)分析S5鋼廠鋼管的銷價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大。通過(guò)分析問(wèn)題一中關(guān)于產(chǎn)量的約束，Lingo運(yùn)行后得到的結(jié)果得S1S2S3S4S5S6S7影子價(jià)：格10335253.330016分析表中數(shù)據(jù)，得S1鋼廠鋼管的產(chǎn)量上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大。問(wèn)題三題圖二為樹形圖，采用Floyd算法，用matlab編程求出單位鋼管從S運(yùn)輸?shù)紸j的最小運(yùn)輸費(fèi)用

最小運(yùn)費(fèi)單價(jià)表S1s2s3s4s5s6s7A23203360.3375.3410.34003400.3425.3A3300.2345.2355.2395.2380.2385.2405.2A4258.6326.6336.6376.6361.6366.6386.6A5198266276316301306326A6180.5250.5260.5300.5285.5290.5310.5A7163.1241251291276278.1301A8181.2226.2241.2276.2266.2266.2291.2A9224.2269.2203.2244.2234.2234.2259.2A10252297237222212211236All256301241211188197224A12266311251221206187216A13281.2326.2266.2236.2226.2166.2198.2A14288333273243228161186A15302347287257242178162sis2s3s4s5s6s7盤山220265199240230230255A172553002402101S7196223A182603052452152001S3210A19265310250220206186215A20275320260230220160192A212853302702402301501S6由于樹形圖的出現(xiàn)，則某些管道處會(huì)出現(xiàn)多支路。則模型一中的一些條件就不再適用，此時(shí)可考慮多增加一些支路變量，并增加約束，在目標(biāo)函數(shù)中增加相應(yīng)的鋪設(shè)費(fèi)。目標(biāo)函數(shù)：mmz二瓦0.05x{(1+[y+]) ?(2y+—[y+])+(1 +y-)? (2y- -[y-])}j jj j+i j+ij+ij=ij=1j=ij=1i=1i=1j=1st.遲x<S九i,jiij=1遲x>500九TOC\o"1-5"\h\zi,j ij=1、f1當(dāng)S生產(chǎn)時(shí)i[0 當(dāng)S不生產(chǎn)時(shí)iy++y-=Yxjj i,ji=1y++y- =Aj j+1 j,j+1[y+]+[y-]=A -1j j+1 j,j+1x>0i,j3．在確定出上述結(jié)果后，運(yùn)用下列準(zhǔn)則，確定下列初始解，再利用相同的方法編制附錄中的程序。從而可得到如下最優(yōu)解：總的最小費(fèi)用為1396099萬(wàn)元，具體的訂貨和運(yùn)輸計(jì)劃詳細(xì)見下表訂貨安排運(yùn)輸安排S]800x=2741.5x=1531.6x=3731.7S2800x=5152.4x=732.5x=2122,8S554x=2243,5x=3303,10S40

S52000x=2615.2x=4825.3x=7285,9x=3225,11x=225.16x=1855.17S1749x=266,9x=1706.12x=2576.13x=6556.14x=1416.15x=606,18x=1616.19x=1796.20x=1006.21S70結(jié)果分析由于總費(fèi)用由訂購(gòu)費(fèi)用和運(yùn)輸費(fèi)兩部分組成，運(yùn)輸費(fèi)又由一般線路上的運(yùn)輸費(fèi)和鋪設(shè)管道上的運(yùn)輸費(fèi)組成。我們將其分段求出最優(yōu)，然后綜合考慮這種解法不容易得到全局最優(yōu)解，但經(jīng)過(guò)我們多次的反復(fù)優(yōu)化，使我們的結(jié)果趨于穩(wěn)定。預(yù)想求出全局最優(yōu)解，可以按我們?cè)谏厦嫣岢龅姆蔷€性優(yōu)化或網(wǎng)絡(luò)最小費(fèi)用最大流求解。另外，我們借助于Lingo軟件求解，同時(shí)進(jìn)行了靈敏度分析。模型的評(píng)價(jià)及改進(jìn)1．優(yōu)點(diǎn)：1）本問(wèn)題中運(yùn)用了現(xiàn)代使用較廣的網(wǎng)絡(luò)流算法，同時(shí)又結(jié)合枚舉法進(jìn)行求

解。這樣模型的推廣性較強(qiáng)，計(jì)算結(jié)果較為準(zhǔn)確2）問(wèn)題將費(fèi)用流轉(zhuǎn)化為網(wǎng)絡(luò)流，具有較強(qiáng)的推廣性和準(zhǔn)確性3）本問(wèn)題構(gòu)造出的模型算法較簡(jiǎn)單，也可以運(yùn)用手算的方法來(lái)得到比較滿意的結(jié)果。2．缺點(diǎn)：1）由于本問(wèn)題有現(xiàn)成的比較先進(jìn)的解法，但由于缺乏基本的數(shù)學(xué)軟件資料，不能將其準(zhǔn)確求解。于在求解最短路時(shí)，我們用人工計(jì)算容易將問(wèn)題復(fù)雜化，同時(shí)，容易出錯(cuò)3）作為圖論問(wèn)題的技術(shù)而言，求解過(guò)程較難，且不易求出最優(yōu)解參考文獻(xiàn)1、數(shù)學(xué)建模（第三版）姜啟源謝金星葉俊高等教育出版社2006.82、數(shù)學(xué)模型（第二版）姜啟源高等教育出版社19933、數(shù)學(xué)建模原理與案例馮杰黃力偉王勤尹成義科學(xué)出版社2007.5附錄用matlab建立Floyd函數(shù)的M文件，編程如下：function[D,path]=floyd（a） fori=1:nD=a;path=zeros(n,n);ifD(i,j)~=inf

D=a;path=zeros(n,n);ifD(i,j)~=infpath(i,j)=j;ifD(i,k)+D(k,j)<D(i,j)endD(i,j)=D(i,k)+D(k,j);endpath(i,j)=path(i,k);endendfork=1:nendfori=1:nendforj=1:nend用Floyd算法求鐵路最短距離，以7個(gè)鋼管廠和17個(gè)中轉(zhuǎn)點(diǎn)建立初始距離矩陣Gj\*24，對(duì)于任意兩點(diǎn)之間的距離，如果兩點(diǎn)之間有鐵路直接連接，其值為兩點(diǎn)間鐵路的距離；如果兩點(diǎn)之間沒(méi)有鐵路直接連接，則其值為inf。用Floyd算法求公路最短距離，以15個(gè)鋪設(shè)節(jié)點(diǎn)、17個(gè)中轉(zhuǎn)點(diǎn)和S1、S6、S7三個(gè)鋼管廠建立初始距離矩陣g{*35，對(duì)于任意兩點(diǎn)之間的距離，如果兩點(diǎn)之間有公路直接連接，其值為兩點(diǎn)間公路的距離；如果兩點(diǎn)之間沒(méi)有公路直接連接，則其值為inf。用Floyd算法求鐵路和公路最少費(fèi)用，編程如下：%距離轉(zhuǎn)換為費(fèi)用的程序D1=D1*0.1; %把公路最短距離m2(k)={300+k};換算成公路最少費(fèi)用m3(k)={350+k};fork=1:300m4(k)={400+k};m1(k)={k};m5(k)={450+k};endend

m6(k)={500+k};m7(k)={600+k};m8(k)={700+k};m6(k)={500+k};m7(k)={600+k};m8(k)={700+k};m9(k)={800+k};m0(k)={900+k};endfori=1:24forj=1:24%把鐵路最短距離換算成鐵路最少費(fèi)用switchD(i,j)case0D(i,j)=0;casem1D(i,j)=20;casem2D(i,j)=23;casem3D(i,j)=26;D(i,j)=29;casem5D(i,j)=32;casem6D(i,j)=37;casem7D(i,j)=44;casem8D(i,j)=50;casem9D(i,j)=55;casem0D(i,j)=60;otherwiseD(i,j)=ceil((D(i,j)-1000)/100)*5+60;endendendcasem4%c矩陣表示七個(gè)鋼管生產(chǎn)廠到十五個(gè)鋪設(shè)節(jié)點(diǎn)之間的距離，先把它們都設(shè)成20000（任意一個(gè)鋼管廠到任意一個(gè)鋪設(shè)節(jié)點(diǎn)之間的距離不會(huì)超過(guò)

c=[200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000];fori=1:7 %7fori=1:7 %7個(gè)鋼管生產(chǎn)廠fork=1:15%15個(gè)鋪設(shè)節(jié)點(diǎn)八、、forj=8:24%7個(gè)鋼管生產(chǎn)廠和17個(gè)中轉(zhuǎn)點(diǎn)，i=1,表示第一個(gè)鋼管生產(chǎn)廠，j=8,表示第一個(gè)中轉(zhuǎn)點(diǎn)ifc(i,k)>D(i,j)+D1(k,j+8)c(i,k)=D(i,j)+D1(k,j+8);%對(duì)于所有中轉(zhuǎn)點(diǎn)，在鐵路網(wǎng)和公路網(wǎng)上的下標(biāo)相差8endendendendendfori=1:7endendendfori=1:7fork=1:15ifc(i,k)>D(i,1)+D1(k,33)c(i,k)=D(i,1)+D1(k,33);%33代表第一個(gè)鋼管生產(chǎn)廠S1點(diǎn)endifc(i,k)>D(i,6)+D1(k,34)c(i,k)=D(i,6)+D1(k,34);%34代表第六個(gè)鋼管生產(chǎn)廠S6點(diǎn)運(yùn)行結(jié)果如下：?jiǎn)栴}一用Lingo軟件求解的編程：model:sets:supply/S1..S7/:p,s,t;need/A1..A15/:L,R,b;links(supply,need):c,x;endsetsdata:ifc(i,k)>D(i,7)+D1(k,35)c(i,k)=D(i,7)+D1(k,35);%35代表第七個(gè)鋼管生產(chǎn)廠S7點(diǎn)endend%因?yàn)镾1,S6,S7這三個(gè)鋼管廠有公路直接連接到鋪設(shè)節(jié)點(diǎn)，所以把這三個(gè)點(diǎn)單獨(dú)處理ends=80080010002000200020003000;b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,;c=170.7160.3140.298.638.020.53.121.264.292.096.0106.0121.2128.0142.0205.3190.2171.6111.095.586.071.2114.2142.0146.0156.0171.2178.0192.0220.3200.2181.6121.0105.596.086.248.282.086.096.0111.2118.0132.0250.3235.2216.6156.0140.5131.0116.284.262.051.061.076.283.097.0245.3225.2206.6146.0130.5121.0111.279.257.033.051.071.273.087.0255.3235.2216.6156.0140.5131.0121.284.262.051.045.026.211.028.0265.3245.2226.6166.0150.5141.0131.299.277.066.056.038.226.02.0;enddatamin=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+0.05*@sum(need(j):L(j)八2+L(j)+R(j)八2+R(j));@for(supply(i):@sum(need(j):x(i,j))>=500*t(i));@for(supply(i):@sum(need(j):x(i,j))<=s(i)*t(i));@for(supply(i):@bin(t(i)));@for(need(j):@sum(supply(i):x(i,j))=L(j)+R(j));@for(need(j)|j#NE#15:b(j)=R(j)+L(j+1));R(15)=0;L(1)=0;@gin(@sum(links(i,j):x(i,j)));p(1)=160;p(2)=155;p(3)=155;p(4)=160;p(5)=155;p(6)=150;p(7)=160;end用Floyd算法求鐵路最短距離，matlab編程與問(wèn)題一相同用Floyd算法求公路最短距離，以21個(gè)鋪設(shè)節(jié)點(diǎn)和14個(gè)中轉(zhuǎn)點(diǎn)建立初始距離矩陣°2j{*35，D2矩陣的意義與前面D矩陣相似再次調(diào)用距離轉(zhuǎn)費(fèi)用程序，求出鐵路和公路最少費(fèi)用%h矩陣表示七個(gè)鋼管生產(chǎn)廠到21個(gè)鋪設(shè)節(jié)點(diǎn)之間的距離，先把它們都設(shè)成20000(任意一個(gè)鋼管廠到任意一個(gè)鋪設(shè)節(jié)點(diǎn)之間的距離不會(huì)超過(guò)20000)，然后用for循環(huán)求出最小值h=[200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000

200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000;200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000200002000020000];fori=1:7ifh(i,m)>D(i,j)+D2(k,j+8)m=1;h(i,m)=D(i,j)+D2(k,j+8);forendk=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34]endm=m+1;forj=8:24m=m+1;endendfori=1:7m=1;fork=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34]ifh(i,m)>D(i,1)+D2(k,33)h(i,m)=D(i,1)+D2(k,33);endifh(i,m)>D(i,6)+D2(k,34)h(i,m)=D(i,6)+D2(k,34);endifh(i,m)>D(i,7)+D2(k,35)h(i,m)=D(i,7)+D2(k,35);endm=m+1;endend問(wèn)題三用軟件Lingo編程model:sets:supply/S1..S7/:p,s,t;need/A1..A21/:L,R,Z,b;links(supply,need):c,x;endsetsdata:p=16015515516