關(guān)于煉油廠的選址問(wèn)題

1、第五屆太原地區(qū)數(shù)學(xué)建模聯(lián)賽承 諾 書(shū)我們仔細(xì)閱讀了太原地區(qū)數(shù)學(xué)建模聯(lián)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從a/b中選擇一項(xiàng)填寫(xiě)）： 我們的參賽報(bào)名號(hào)為： 參賽隊(duì)員 (打印并簽名) ：1. 2

2、. 3. 日期： 2011 年 5 月 15 日第五屆太原地區(qū)數(shù)學(xué)建模聯(lián)賽評(píng)閱記錄評(píng)閱記錄（可供評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注煉油廠選址問(wèn)題摘要本文對(duì)煉油廠選址問(wèn)題進(jìn)行了深入研究。問(wèn)題一，首先考慮在位置可以隨意選擇的情況下，并且其距離可為直線，計(jì)算出最佳位置，有結(jié)果可知，此位置不在任何一油井處，其次，選擇距離此最優(yōu)點(diǎn)距離最近的油井口作為煉油廠選址地點(diǎn)，可知，其余八個(gè)油井到煉油廠距離=各油井到最佳位置的距離+最佳距離到最近油井（煉油廠選址）的距離，則問(wèn)題一可解決。問(wèn)題二，考慮兩點(diǎn)間距離為直線計(jì)算，首先排除產(chǎn)量的干擾，只計(jì)算出選擇哪個(gè)點(diǎn)的情況下此點(diǎn)到各個(gè)點(diǎn)的距離之和最小，其次，加入產(chǎn)量的影響，進(jìn)行加

3、權(quán)處理，從而得出最優(yōu)點(diǎn)，即為煉油廠選擇地點(diǎn)。問(wèn)題三，應(yīng)用重心法，首先，計(jì)算任意兩個(gè)油井之間的距離，然后根據(jù)相距遠(yuǎn)近分為兩個(gè)區(qū)域，分別計(jì)算兩個(gè)區(qū)域的最優(yōu)解，煉油廠則選擇在這兩個(gè)最優(yōu)解處，問(wèn)題三可解。本文綜合考慮多種方案的因素，所建立的模型結(jié)構(gòu)嚴(yán)謹(jǐn)、邏輯性強(qiáng)。最后并對(duì)模型進(jìn)行了推廣。關(guān)鍵詞最優(yōu)化，選址， 線性最優(yōu)化，重心法，二元函數(shù)，加權(quán)，轉(zhuǎn)化思想，lingo軟件，幾何畫(huà)板一、問(wèn)題的重述（優(yōu)化選址問(wèn)題）1.1基本問(wèn)題某一油田在一平坦地區(qū)擁有九口油井，各油井的年產(chǎn)量均不同，所有的原油都需要運(yùn)輸?shù)綗捰蛷S進(jìn)行提煉。不考慮煉油廠的建設(shè)費(fèi)用，總費(fèi)用僅和煉油廠的位置有關(guān)，在不同的情況下討論煉油廠如何選址得出最

4、優(yōu)解問(wèn)題。1.2需要解決的問(wèn)題第一，折線情況下，如何選擇折線方案才能達(dá)到最優(yōu)解問(wèn)題第二，在煉油廠不被限制的情況下，如何選擇煉油廠位置才能到各個(gè)點(diǎn)距離最短第三，建立兩個(gè)煉油廠的情況下，如何分配兩個(gè)煉油廠的位置以達(dá)到最優(yōu)解二、模型假設(shè)1. 假設(shè)煉油廠和井口都是理性化的質(zhì)點(diǎn)。2. 假設(shè)油井輸油量單位時(shí)間內(nèi)不變。3. 假設(shè)煉油廠的建設(shè)資金是確定的，不會(huì)因規(guī)模的大小而改變。成本僅為運(yùn)輸費(fèi)用。三、符號(hào)表示符號(hào)含義運(yùn)輸費(fèi)用（，）（i=1，2，3，4，5，6，7，8，9）九個(gè)油井的坐標(biāo)（，） 兩個(gè)煉油廠接受九個(gè)油井的輸油量（，） （，）a、b煉油廠的坐標(biāo)各油井口所供應(yīng)的油量各油井距離煉油廠的距離c單位距離運(yùn)費(fèi)

5、a第一個(gè)煉油廠b第二個(gè)煉油廠四、問(wèn)題分析問(wèn)題一采用遞進(jìn)方法，先計(jì)算直線最優(yōu)解，然后計(jì)算折線最優(yōu)解，問(wèn)題二先計(jì)算距離最優(yōu)解，再加權(quán)計(jì)算最優(yōu)解，問(wèn)題三先劃分為兩個(gè)區(qū)域，再分別計(jì)算兩個(gè)區(qū)域的最優(yōu)解，得出兩個(gè)煉油廠的選址地點(diǎn)五、模型的建立與求解問(wèn)題一：模型的建立假設(shè)煉油廠不一定要選擇在某個(gè)井口位置，且各井口到最優(yōu)點(diǎn)之間為直線連接，得出最優(yōu)點(diǎn)后，再找出距離此點(diǎn)最近的油井口，則煉油廠選擇在距離最優(yōu)點(diǎn)最近的油井口處，其他任意八個(gè)油井口到達(dá)此油井口折線方案為，先到達(dá)最優(yōu)點(diǎn)處，再由最優(yōu)點(diǎn)到達(dá)煉油廠（距離最優(yōu)點(diǎn)最近的油井口），即為答案。模型的解答首先找出九個(gè)點(diǎn)的最優(yōu)點(diǎn)，使九個(gè)點(diǎn)到達(dá)最優(yōu)點(diǎn)的直線距離之和最短使用li

6、ngo軟件：計(jì)算公式為編程程序?yàn)椋簃odel:sets:r/1.9/:q;c/1.2/:;link(r,c):d;endsetsdata:d=22 38 8 13 4 81 51 32 38 11 17 12 81 63 19 45 62 12;q=17 40 60 20 25 15 50 8 30;enddatamin=sum(r(i):q(i)*(x-d(i,1)2+(y-d(i,2)2)0.5);end其結(jié)果為local optimal solution found at iteration: 88 objective value: 10212.67 variable value red

7、uced cost x 32.42261 0.000000 y 35.05965 0.000000 q( 1) 17.00000 0.000000 q( 2) 40.00000 0.000000 q( 3) 60.00000 0.000000 q( 4) 20.00000 0.000000 q( 5) 25.00000 0.000000 q( 6) 15.00000 0.000000 q( 7) 50.00000 0.000000 q( 8) 8.000000 0.000000 q( 9) 30.00000 0.000000 d( 1, 1) 22.00000 0.000000 d( 1, 2

8、) 38.00000 0.000000 d( 2, 1) 8.000000 0.000000 d( 2, 2) 13.00000 0.000000 d( 3, 1) 4.000000 0.000000 d( 3, 2) 81.00000 0.000000 d( 4, 1) 51.00000 0.000000 d( 4, 2) 32.00000 0.000000 d( 5, 1) 38.00000 0.000000 d( 5, 2) 11.00000 0.000000 d( 6, 1) 17.00000 0.000000 d( 6, 2) 12.00000 0.000000 d( 7, 1) 8

9、1.00000 0.000000 d( 7, 2) 63.00000 0.000000 d( 8, 1) 19.00000 0.000000 d( 8, 2) 45.00000 0.000000 d( 9, 1) 62.00000 0.000000 d( 9, 2) 12.00000 0.000000 row slack or surplus dual price 1 10212.67 -1.000000可得出，最優(yōu)點(diǎn)坐標(biāo)為x（32.42261，35.05965），最優(yōu)點(diǎn)所需費(fèi)用為10212.7p然后計(jì)算哪一個(gè)油井口與此最優(yōu)點(diǎn)距離最近，本文使用的幾何畫(huà)板軟件使用：結(jié)果如下（比例尺：1:1000

10、00）可得出一號(hào)井距離最優(yōu)點(diǎn)x距離為1.95km，則煉油廠選擇在一號(hào)井位置為最佳解，即煉油廠應(yīng)選擇在一號(hào)井處一號(hào)井到最佳點(diǎn)所需運(yùn)費(fèi)為：1.95p則其他八個(gè)油井從最佳點(diǎn)到一號(hào)油井所需運(yùn)費(fèi)為：8*1.95p=15.60p由此可得出，其余二號(hào)到九號(hào)油井至煉油廠所需總運(yùn)費(fèi)為：z=10212.70p+15.60p-1.95p=10226.35p所以，問(wèn)題一的解答為：煉油廠選擇在一號(hào)油井處所需總運(yùn)費(fèi)為10226.35p問(wèn)題二模型的建立煉油廠可選擇區(qū)域?yàn)椋核鶉傻膮^(qū)域內(nèi)，選擇最優(yōu)點(diǎn)，使各油井到煉油廠的運(yùn)費(fèi)最少模型的解答首先算出最短距離的最優(yōu)解使用lingo軟件：計(jì)算公式為編程程序?yàn)椋簃odel:sets:r

11、/1.9/:;c/1.2/:;link(r,c):d;endsetsdata:d=22 38 8 13 4 81 51 32 38 11 17 12 81 63 19 45 62 12;enddatabnd(0,x,81);bnd(0,y,81);min=sum(r(i):(x-d(i,1)2+(y-d(i,2)2)0.5);end其結(jié)果為： local optimal solution found at iteration: 60 objective value: 276.1968 variable value reduced cost x 29.41813 -0.3864516e-08 y

12、 31.25604 0.000000 d( 1, 1) 22.00000 0.000000 d( 1, 2) 38.00000 0.000000 d( 2, 1) 8.000000 0.000000 d( 2, 2) 13.00000 0.000000 d( 3, 1) 4.000000 0.000000 d( 3, 2) 81.00000 0.000000 d( 4, 1) 51.00000 0.000000 d( 4, 2) 32.00000 0.000000 d( 5, 1) 38.00000 0.000000 d( 5, 2) 11.00000 0.000000 d( 6, 1) 17

13、.00000 0.000000 d( 6, 2) 12.00000 0.000000 d( 7, 1) 81.00000 0.000000 d( 7, 2) 63.00000 0.000000 d( 8, 1) 19.00000 0.000000 d( 8, 2) 45.00000 0.000000 d( 9, 1) 62.00000 0.000000 d( 9, 2) 12.00000 0.000000 row slack or surplus dual price 1 276.1968 -1.000000可得出，最優(yōu)點(diǎn)坐標(biāo)為x（29.41813，31.25604），最優(yōu)點(diǎn)到各油井距離之和為

14、276.197km其次，進(jìn)行加權(quán)處理：使用lingo軟件：編程程序?yàn)椋簃odel:sets:r/1.9/:q;c/1.2/:;link(r,c):d;endsetsdata:d=22 38 8 13 4 81 51 32 38 11 17 12 81 63 19 45 62 12;q=17 40 60 20 25 15 50 8 30;enddatabnd(0,x,81);bnd(0,y,81);min=sum(r(i):q(i)*(x-d(i,1)2+(y-d(i,2)2)0.5);end其結(jié)果為： local optimal solution found at iteration: 65

15、objective value: 10212.67 variable value reduced cost x 32.42261 0.000000 y 35.05965 0.000000 q( 1) 17.00000 0.000000 q( 2) 40.00000 0.000000 q( 3) 60.00000 0.000000 q( 4) 20.00000 0.000000 q( 5) 25.00000 0.000000 q( 6) 15.00000 0.000000 q( 7) 50.00000 0.000000 q( 8) 8.000000 0.000000 q( 9) 30.00000

16、 0.000000 d( 1, 1) 22.00000 0.000000 d( 1, 2) 38.00000 0.000000 d( 2, 1) 8.000000 0.000000 d( 2, 2) 13.00000 0.000000 d( 3, 1) 4.000000 0.000000 d( 3, 2) 81.00000 0.000000 d( 4, 1) 51.00000 0.000000 d( 4, 2) 32.00000 0.000000 d( 5, 1) 38.00000 0.000000 d( 5, 2) 11.00000 0.000000 d( 6, 1) 17.00000 0.

17、000000 d( 6, 2) 12.00000 0.000000 d( 7, 1) 81.00000 0.000000 d( 7, 2) 63.00000 0.000000 d( 8, 1) 19.00000 0.000000 d( 8, 2) 45.00000 0.000000 d( 9, 1) 62.00000 0.000000 d( 9, 2) 12.00000 0.000000 row slack or surplus dual price 1 10212.67 -1.000000可得出，最優(yōu)點(diǎn)坐標(biāo)為x（32.42261，35.05965），最優(yōu)點(diǎn)所需費(fèi)用為10212.7p所以，煉油

18、廠應(yīng)選擇在（32.42261，35.05965）處，所需總運(yùn)費(fèi)為10212.7p問(wèn)題二解決問(wèn)題三模型的建立（重心法）這是一個(gè)典型的選址問(wèn)題，由于要選擇兩個(gè)煉油廠，根據(jù)聚類算法的思想，即同一類對(duì)象的相似度較高，而不同類的對(duì)象相似度較小的原理，需要將需求點(diǎn)劃分成兩個(gè)區(qū)域。1.劃分區(qū)域：首先，在坐標(biāo)紙上描繪出所有的油井口，并把所有油井口用直線連接起來(lái)，以距離為邊做出一個(gè)完全圖，如圖所示：圖一井口110224.390337.1510.440444.547.2110.410554.813.2211.933.790664.061.3910.776.053.220779.8313.5712.126.6110

19、.3512.550881.175.195.985.35.975.079.90997.328.2813.823.053.686.98.358.310表一然后，根據(jù)它們彼此的距離（如表一所示），先刪除距離最大的邊，然后再刪除余下邊中距離最大的，依次進(jìn)行下去，直到圖被分為兩個(gè)彼此分離的圖像，如下圖所示：分為兩個(gè)區(qū)域，然后分別對(duì)a、b兩煉油廠進(jìn)行求解。2.公式（重心法選址）的推導(dǎo)：假設(shè)有n個(gè)油井口，油井口的坐標(biāo)為（，），煉油廠的位置為（,）,則運(yùn)輸成本為：其中，c為單位距離的運(yùn)輸成本，為兩點(diǎn)間的距離，為產(chǎn)油量。按重心法，將各油井口視為有重量的質(zhì)點(diǎn)，為各質(zhì)點(diǎn)的等效重量，重心是到各質(zhì)點(diǎn)距離最短距離的點(diǎn)，這

20、樣，尋求煉油廠的地址問(wèn)題，就轉(zhuǎn)化為求重心坐標(biāo)的問(wèn)題，所以接下來(lái)就是解決求解重心的問(wèn)題。假設(shè)各個(gè)質(zhì)點(diǎn)的等效質(zhì)量為g，根據(jù)重心的特征，可知，等效重量在重心對(duì)遠(yuǎn)點(diǎn)的力矩等于各質(zhì)點(diǎn)在面上的力矩之和，即：由于x軸與y軸互相垂直，為不相關(guān)變量，所以可以把力矩延著x軸、y軸分解，即重心對(duì)x軸、y軸的力矩，等于各質(zhì)點(diǎn)對(duì)x軸、y軸的力矩之和。那么可以得到： 又因?yàn)間為等效質(zhì)量，所以?？偵峡傻茫?（1）（，）就為所要求解的重心，也就是煉油廠的最優(yōu)位置。模型的求解（excle表格）對(duì)比重心法，中心坐標(biāo)的求解，本論文選擇excle 表格對(duì)其求解，a、b兩煉油廠的求解數(shù)據(jù)與過(guò)程分別見(jiàn)表二和表三。對(duì)于第一塊區(qū)域（數(shù)據(jù)如表

21、二所示）：井口37求和x坐標(biāo)481y坐標(biāo)8163產(chǎn)量6050110x*產(chǎn)量24040504290y*產(chǎn)量486031508010數(shù)據(jù)帶入公式（1），可以求出=39.0000， =72.8181。對(duì)于第二個(gè)區(qū)域（數(shù)據(jù)如表三所示）：井口1245689求和x坐標(biāo)2285138171962y坐標(biāo)38133211124512產(chǎn)量1740202515830155x*產(chǎn)量374320102095025515218604931y*產(chǎn)量6465206402751803603602981數(shù)據(jù)帶入公式（1），可以求出=31.8129， =19.2322。則兩個(gè)煉油廠選址為：a煉油廠選址坐標(biāo)為（39.0000，72.

22、8181） b煉油廠選址坐標(biāo)為（31.8129，19.2322）第一個(gè)區(qū)域所需費(fèi)用為：使用lingo軟件：編程程序?yàn)椋簃odel:sets:r/1.2/:q;c/1.2/:;link(r,c):d;endsetsdata:d=4 81 81 63;q=60 50;enddatamin=sum(r(i):q(i)*(x-d(i,1)2+(y-d(i,2)2)0.5);end結(jié)果為： local optimal solution found at iteration: 233 objective value: 3953.796 variable value reduced cost x 4.000

23、039 0.1364229e-05 y 80.99997 -0.1908817e-05 q( 1) 60.00000 0.000000 q( 2) 50.00000 0.000000 d( 1, 1) 4.000000 0.000000 d( 1, 2) 81.00000 0.000000 d( 2, 1) 81.00000 0.000000 d( 2, 2) 63.00000 0.000000 row slack or surplus dual price 1 3953.796 -1.000000則第一部分費(fèi)用為：3953.8p第二個(gè)區(qū)域所需費(fèi)用為：使用lingo軟件：編程程序?yàn)椋簃odel

24、:sets:r/1.7/:q;c/1.2/:;link(r,c):d;endsetsdata:d=22 38 8 13 51 32 38 11 17 12 19 45 62 12;q=17 40 20 25 15 8 30;enddatamin=sum(r(i):q(i)*(x-d(i,1)2+(y-d(i,2)2)0.5);end結(jié)果為： local optimal solution found at iteration: 90 objective value: 3460.883 variable value reduced cost x 31.37184 0.000000 y 17.302

25、47 0.000000 q( 1) 17.00000 0.000000 q( 2) 40.00000 0.000000 q( 3) 20.00000 0.000000 q( 4) 25.00000 0.000000 q( 5) 15.00000 0.000000 q( 6) 8.000000 0.000000 q( 7) 30.00000 0.000000 d( 1, 1) 22.00000 0.000000 d( 1, 2) 38.00000 0.000000 d( 2, 1) 8.000000 0.000000 d( 2, 2) 13.00000 0.000000 d( 3, 1) 51.0